2015年6月

发现一个新方法

mathematica的函数Manipulate支持带有参数的函数绘图然后可以调节参数。
下面的就是用来调<s>戏</s>试一个二次函数的图像。

Manipulate[
Plot[a*x^2 + b*x + c, {x, -10, 10}], {a, -.1, -3}, {b, 0, 3}, {c, 0, 3}]

<s>这高亮脚本还是自己写的</s>
效果大致是这样QQ截图20150614212514.png

Code Highlight

终于找到一个可以用的代码高亮插件了!
终于找到一个可以用的代码高亮插件了!
高兴的事要说两遍!
是我的错我居然天真地以为百度就能找到全部插件……
考完试后顺便改一改看起来更顺眼的配色方案吧……

hiho week49 欧拉回路

在不要求输出路径的情况下只是简单的一笔画问题。小学奥数啊。
虽说咱市奥校没好好听但这还是会的。

判定条件:存在欧拉回路当且仅当奇数度的点数为2或0。

不过咱不会严格证明啊。。。要死。。。
再次膜拜欧拉神!

#include <iostream>
using namespace std;
const int maxn = 1e4 + 10;
int island[maxn] = {0};
int main()
{
    int n, m;
    cin>>n>>m;
    while(m--)
    {
        int u, v;
        cin>>u>>v;
        island[u]++;
        island[v]++;
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        if(island[i] & 1)
            cnt++;
    if(cnt == 2 || cnt == 0)
        cout<<"Full"<<endl;
    else
        cout<<"Part"<<endl;
    return 0;
}

GDOI'2015D1T1 大冒险

第一题 大冒险 提交文件: adventure.pas/c/cpp 输入文件: adventure.in 输出文件: adventure.out
最近,小明又玩起了一个古老的游戏:大冒险。每个玩家在 N 个格子的环形地图上进行游戏,格子编号为 0 到 N −1。 每一个玩家控制游戏角色,从编号为 0 的格子出发,轮流掷骰子,骰子上的点数为 1 ∼ 6,代表接下来玩家将 向前移动的格子数。
注意的是,地图是环形的,所以假设现在玩家所在的格子为 x,骰子上的点数为 y,那么他将要移动到的格子 为 (x + y) mod N, a mod b 表示 a 除以 b 的余数。 另外 N 个格子中有 M 个格子 (M ≤ N −2) 上有传送门,当玩家到达目标格子且这个格子有传送门时,传送 门将立刻带玩家到另一个格子。如果传送到的格子也有传送门,玩家并不会再次被传送门传送。 玩家到达编号为 N −1 的格子就获胜。 现在小明并不关心他是否能获胜,他只想知道是否可能游戏一段时间后,进入了某个格子,这个格子无论如何 都不能到达终点。
输入格式 第一行有 1 个整数 T,表示数据组数。 接下有 T 个测试样例。 每个测试样例的第一行有 2 个整数,N、M。 接下来 M 行,每行两个整数 x,y,(x ̸= y) 表示编号为 x 的格子,有传送门直接到达编号为 y 的格子。 保证每个格子至多有一个传送门,并且编号为 0 和 N −1 的格子都没有传送门。 输出格式 对于每一个测试样例,如果可能的话,输出“YES”,否则输出“NO”。 adventure.in adventure.out 2 10 7 1 9 3 2 4 2 5 2 6 2 7 2 8 2 10 5 2 1 3 1 4 1 5 1 6 1 YES NO
数据范围 对于 40% 数据,10 ≤ N ≤ 4000
对于 100% 数据,10 ≤ N ≤ 100000,1 ≤ T ≤ 10,0 ≤ M ≤ N −2【待格式化】

双向广搜即可。
比赛时毕竟还是naive!
而且调了半个月最终还是错在变!量!名!打!反!
简直了。这是要退役了的节奏。

#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream cin("adventure.in");
ofstream cout("adventure.out");
const int maxm = 1e5 + 10;
int n, m;
struct Node
{
    int go;
    bool can[2][2];
    vector<int> back;
    void init()
    {
        go = -1;
        memset(can, false, sizeof can);
        back.clear();
    }
} nodes[maxm];
typedef pair<int, bool> pib;
void bfs1()
{
    queue<pib> Q;
    Q.push(make_pair(0, false));
    while(!Q.empty())
    {
        pib t = Q.front(); Q.pop();
        int num = t.first; bool refer = t.second;
        if(num > n - 1)
            continue;
        if((refer && nodes[num].can[0][0]) || (!refer && nodes[num].can[0][1]))
            continue;
        if(refer)
            nodes[num].can[0][0] = true;
        else
            nodes[num].can[0][1] = true;
        if(refer || nodes[num].go == -1)
        {
            for(int i = 1; i <= 6; i++)
                Q.push(make_pair(num + i, false));
        }
        else
        {
            Q.push(make_pair(nodes[num].go, true));
        }
    }
}
void bfs2()
{
    queue<pib> Q;
    Q.push(make_pair(n - 1, false));
    while(!Q.empty())
    {
        pib t = Q.front(); Q.pop();
        int num = t.first; bool refer = t.second;
        if(num < 1)
            continue;
        if((refer && nodes[num].can[1][0]) || (!refer && nodes[num].can[1][1]))
            continue;
        if(refer)
            nodes[num].can[1][0] = true;
        else
            nodes[num].can[1][1] = true;
        if(!(refer || nodes[num].back.empty()))
        {
            for(int i = 0; i < nodes[num].back.size(); i++)
                Q.push(make_pair(nodes[num].back[i], true));
        }
        for(int i = 1; i <= 6; i++)
            Q.push(make_pair(t.first - i, false));
    }
}
bool go()
{
    bfs1();
    bfs2();
    for(int i = 1; i <= n - 1; i++)
        if(!((nodes[i].can[0][0] && nodes[i].can[1][1])
        || (nodes[i].can[0][1] && nodes[i].can[1][0])
        || (nodes[i].can[0][1] && nodes[i].can[1][1])))
            return false;
    return true;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(m == 0)
        {
            cout<<"NO"<<endl;
            continue;
        }
        for(int i = 0; i < n + 10; i++)
            nodes[i].init();
        for(int i = 0; i < m; i++)
        {
            int x, y;
            cin>>x>>y;
            nodes[x].go = y;
            nodes[y].back.push_back(x);
        }
        if(go())
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
    return 0;
}

vijos1437 简单的口令

vijos1437

打算去清远前清理桌面,于是发现了这个GDOI遗留下的未完成品。
最小表示法什么的,虽说有专门的算法,不过SAM用起来似乎更顺手。直接两倍原串后按字典序跑一遍就行了。
但那个神奇的算法还是找个时间研究一下吧。
RE了六次,WA了两次。
原因:变量名打错;字符串被分割称多行却无告知。
呃,几乎每次都是变量名打错而出错的呢。

#include <iostream>
#include <cstring>
using namespace std;
namespace DEL
{
    template<int maxn, int sigma = 26>
    class Suffix_Automaton
    {
    private:
        struct Node
        {
            Node *fail;
            Node *ch[sigma];
            int len;
            Node(){memset(ch, 0, sizeof ch);}
        } *head, *tail, pool[maxn * 2];
        int cnt, len;
        inline int idx(char c)
        {
            return c - 'a';
        }
    public:
        void init(int l)
        {
            //memset(&pool, 0, sizeof pool);
            head = tail = &pool[0];
            cnt = 1;
            len = l;
        }
        void add(char c)
        {
            int id = idx(c);
            Node *p = tail, *newnode = &pool[cnt++];
            newnode -> len = p -> len + 1;
            tail = newnode;
            for(; p && !p -> ch[id]; p = p -> fail)
                p -> ch[id] = newnode;
            if(!p)
                newnode -> fail = head;
            else if(p -> len + 1 == p -> ch[id] -> len)
                newnode -> fail = p -> ch[id];
            else
            {
                Node *q = p -> ch[id], *r = &pool[cnt++];
                *r = *q;
                r -> len = p -> len + 1;
                q -> fail = newnode -> fail = r;
                for(; p && p -> ch[id] == q; p = p -> fail)
                    p -> ch[id] = r;
            }
        }
        int go()
        {
            Node *p = head;
            for(int i = 0; i < len; i++)
                for(int j = 0; j < sigma; j++)
                {
                    if(p -> ch[j])
                    {
                        p = p -> ch[j];
                        break;
                    }
                }
            return p -> len - len;
        }
    };
}
DEL::Suffix_Automaton<1000000> SAM;
int main()
{
    int l;
    cin>>l;
    string s;
    cin>>s;
    string s1;
    while(cin>>s1)
        s += s1;
    SAM.init(l);
    s += s;
    for(unsigned int i = 0; i < s.length(); i++)
        SAM.add(s[i]);
    cout<<SAM.go()<<endl;
    return 0;
}