2015年6月

其实要不是unusual time到十点否则是不会现在参加的。。。
话说居然延迟了十分钟才开始。。。
话说我妈居然全程陪我打CF。。。
<s>原谅我比赛时丑的一比的代码</s>


A
MD又是变量名打错

#include <iostream>
using namespace std;
const int maxn = 2e6 + 100;
int c[maxn] = {0}, *b = c + 10;
inline bool check(int a, int b)
{
    return a^b;
}
int main()
{
    int n;
    cin>>n;
    string a;
    cin>>a;
    int curr = 0;
    for(int i = 0; i < a.length(); i++)
    {
        b[curr] = a[i] - '0';
        if(curr != 0 && check(b[curr], b[curr-1]))
            curr -= 2;
        curr++;
    }
    cout<<curr<<endl;
    return 0;
}

B

#include <iostream>
using namespace std;
const int maxn = 1000 + 100;
int a[maxn] = {0};
int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    int delta = n - a[0];
    a[0] = 0;
    bool ok = true;
    for(int i = 1; i < n; i++)
    {
        int d = i & 1 ? -delta : delta;
        a[i] += (n + d);
        a[i] %= n;
        if(a[i] - a[i - 1] != 1)
        {
            ok = false;
            break;
        }
    }
    if(ok)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

C

#include <iostream>
using namespace std;
int main()
{
    int n, k;
    cin>>n>>k;
    long long ans = 0;
    while(k--)
    {
        int m;
        cin>>m;
        bool one = false;
        int cnt = 0;
        for(int i = 0; i < m; i++)
        {
            int j; cin>>j;
            if(!one && j == 1)
            {
                one = true;
                cnt++;
            }
            else if(one && i + 1 == j)
            {
                cnt++;
            }
        }
        if(one)
            ans += 2 * (m - cnt);
        else
            ans += 2 * m - 1;
    }
    cout<<ans<<endl;
    return 0;
}

310 2015.6.27

A(FST)、B(A)、C(A)
rating: 0(<span style = "color: grey;">unrated</span>) -> 1581(<span style = "color:blue;">expert</span>)
获得成就:<span style="color:red">#人生第一次codeforces #第一次A了题 #第一次FST了题</span>


313 2015.7.23

A(A)、B(FST)、C(A)
rating: 1581(<span style = "color:blue;">expert</span>) -> 1527(<span style = "color:blue;">expert</span>)
获得成就:<span style="color:red">#FST犯脑残错误 #比赛中连续WA3题 #比赛中T了题</span>

本来想顺便写个trie的教程,无奈手头没有专业的画图工具,还是等暑假再补上吧。

hiho

要求相同前缀个数的话,只需要在每一个节点维护一个变量用来记录子串数量。维护很简单,只需要每增加一个字符串时从根走下对每一个经过的节点的该变量加一即可。【啊啊啊我废话好多
多说一句现在数据结构在下真是写得越来越专业了……对比一下以前模仿lrj写的简直就是【】

#include <iostream>
using namespace std;
template<int maxn, int sigma = 26>
class Trie
{
private:
    struct Node
    {
        Node *ch[sigma];
        int cnt;
    }*root, pool[maxn * 2];
    int cnt;
    inline int idx(char c){return c - 'a';}
public:
    Trie()
    {
        root = &pool[0];
        cnt = 1;
    }
    void add(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                p -> ch[idx(s[i])] = &pool[cnt++];
            p -> ch[idx(s[i])] -> cnt++;
            p = p -> ch[idx(s[i])];
        }
    }
    int go(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                return 0;
            p = p -> ch[idx(s[i])];
        }
        return p -> cnt;
    }
};
Trie<1000000> trie;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        trie.add(s);
    }
    int m;
    cin>>m;
    while(m--)
    {
        string s;
        cin>>s;
        cout<<trie.go(s)<<endl;
    }
    return 0;
}

再附一个节点池的炫酷指针版

#include <iostream>
using namespace std;
template<int maxn, int sigma = 26>
class Trie
{
private:
    struct Node
    {
        Node *ch[sigma];
        int cnt;
    }*root, *nodecur, pool[maxn * 2];
    inline int idx(char c){return c - 'a';}
public:
    Trie()
    {
        root = &pool[0];
        nodecur = &pool[1];
    }
    void add(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                p -> ch[idx(s[i])] = nodecur++;
            p -> ch[idx(s[i])] -> cnt++;
            p = p -> ch[idx(s[i])];
        }
    }
    int go(string s)
    {
        Node *p = root;
        for(int i = 0; i < s.length(); i++)
        {
            if(!p -> ch[idx(s[i])])
                return 0;
            p = p -> ch[idx(s[i])];
        }
        return p -> cnt;
    }
};
Trie<1000000> trie;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        trie.add(s);
    }
    int m;
    cin>>m;
    while(m--)
    {
        string s;
        cin>>s;
        cout<<trie.go(s)<<endl;
    }
    return 0;
}

话说指针这东西千万不要乱用啊【捂脸熊】,用得不好会出人命的啊……

好像是#1的样子……只是提前用手机交而已……


A·NBUT1001·纸牌游戏:水题。
B·NBUT1014·N!:数学水题。稍微要提一下的就是二进制零的个数等于十进制因子2的次数。
C·NBUT1022·数星星:水题。
D·NBUT1023·逆反的01串:水题。
E·NBUT1026·汽车加油问题:水题。贪心可证。数组开小加上输入处理错误连续RE+OLE+WA了N发。
F·NBUT1028·该减肥了:水DP。刚开始以为数学可做最后看了数据范围果断用DP算了。

代码等作业结束再贴。

好吧我错了,不需要增广矩阵即可。


数学讲到了二次函数,作业中就多了很多得待定系数法才能解出解析式的题。
系数小解起来还行,大了的话就麻烦了,更何况验算。
嘛,咱一般是用这功能来验算的,学霸们不必焦虑。


首先,二次函数解析式是$ y=ax^2+bx+c $,也就是需要三个方程才能解出来,比一次函数$ y=kx+b $能目测出来的话厉害多了。
那我们就用矩阵解呗。当然这里只说mathematica的方法。
首先我们是要一个$ Ax=B $的形式,$ A $是系数矩阵,而且是增广矩阵,$ x $是未知数向量,$ B $是已知值向量。
所以假设$ x $是k维的,则$ A $为k行k+1列的!要把常数项也扔进去!


比方说我看到了这样一道题:函数$ f(x)=ax^2+bx+c $已知其经过$ (-1,0),(3,0),(2,3) $,求解析式。
那么就有如下的线性方程组:

$$ \left\\{ \begin{array}{c} a-b+c=0 \\\\ 9a+3b+c=0 \\\\ 4a+2b+c=3 \end{array} \right. $$

其系数增广矩阵为

$$ A= \left[ \begin{array}{ccc|c} 1 & -1 & 1 & 0 \\\\ 9 & 3 & 1 & 0 \\\\ 4 & 2 & 1 & 0 \end{array} \right] $$

未知向量为

$$ x= \begin{bmatrix} a \\\\ b \\\\ c \\\\ 1(constant) \end{bmatrix} $$

值向量为

$$ B= \begin{bmatrix} 0 \\\\ 0 \\\\ 3 \end{bmatrix} $$

$$ \left[ \begin{array}{ccc|c} 1 & -1 & 1 & 0 \\\\ 9 & 3 & 1 & 0 \\\\ 4 & 2 & 1 & 0 \end{array} \right] \begin{bmatrix} a \\\\ b \\\\ c \\\\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\\\ 0 \\\\ 3 \end{bmatrix} $$

代码是
In=

A = {{1, -1, 1, 0}, {9, 3, 1, 0 }, {4, 2, 1, 0}};
B = {0, 0, 3};
LinearSolve[A, B]

然后
Out=

{-1, 2, 3, 0}

当然也可以自己写个程序,好像是用高斯消元搞搞。