今天真是极度的不爽，很不爽！！

今天下午加了一场训练赛。没想到加题加难了。。。

加完题晚上一直在写JSP的作业，怎么也写不完，怎么也写不出来。。。

晚上回到宿舍也一直再调，结果最后调好了，提交作业的时候发现提交时间截止了，怎么能这么悲伤。

------------------------------------------------------------------------------------------------------------------------------------------------------------

言归正传：

下午做了一场周赛。我做了俩题。

1，zoj-3761-Easy billiards

枚举任意两个点，如果两个点可以互相打击，就把这两个点连起来。

最后暴力DFS寻找图中有几个联通块。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<vector>
using namespace std;
#define maxn 2200
struct list
{
    int x;
    int y;
    friend bool operator <(const list &a,const list &b)
    {
        if(a.x!=b.x)return a.x<b.x;
        else return a.y<b.y;
    }
} node[maxn];
vector<list>vec[maxn];
struct listt
{
    int x;
    int y;
    int f;
};
vector<listt>ans;
int maps[maxn][maxn];
int l;
int vis[maxn];
int n;
void dfs(int x,int pre)
{
    if(vis[x])return;
    vis[x]=1;
    for(int i=1;i<=n;i++)
    {
        if(maps[x][i]!=-1&&!vis[i])
        {
            dfs(i,x);
        }
    }
    if(pre==-1)return;
    struct listt p;
    p.x=node[x].x;
    p.y=node[x].y;
    if(p.x==node[pre].x)
    {
        if(p.y>node[pre].y)p.f=1;
        else p.f=2;
    }
    if(p.y==node[pre].y)
    {
        if(p.x>node[pre].x)
        {
            p.f=4;
        }
        else p.f=3;
    }
    ans.push_back(p);
}
int main()
{
    int i,j,k;
    while(~scanf("%d",&n))
    {
        if(n==0)
        {
            cout<<"0"<<endl;
            continue;
        }
        memset(maps,-1,sizeof(maps));
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; i++)
        {
            scanf("%d%d",&node[i].x,&node[i].y);
            vec[i].clear();
        }
        sort(node+1,node+n+1);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(node[i].x==node[j].x||node[i].y==node[j].y)maps[i][j]=1;
            }
        }
        ans.clear();
        int nums;
        nums=0;
        for(i=1;i<=n;i++)
        {
            if(vis[i])continue;
            dfs(i,-1);
            nums++;
        }
        cout<<nums<<endl;
        for(i=0;i<ans.size();i++)
        {
            struct listt p;
            p=ans[i];
            if(p.f==1)printf("(%d, %d) DOWN\n",p.x,p.y);
            else if(p.f==2)printf("(%d, %d) UP\n",p.x,p.y);
            else if(p.f==3)printf("(%d, %d) RIGHT\n",p.x,p.y);
            else printf("(%d, %d) LEFT\n",p.x,p.y);
        }
    }
    return 0;
}

伸展树的模板题，没想到因为写搓了一个i，就TLE了10次。。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define maxn 350000
#define mem(a,b) memset(a,b,sizeof(a))
#define root10 ch[ch[root][1]][0]
#define root1 ch[root][1]
int pre[maxn],ch[maxn][2],root,tot;
int size[maxn];
int key[maxn];
int st[maxn];
int gcd1[maxn];
int gcd0[maxn];
int n;
int pos;
struct list
{
    int val;
    int st;
} node[maxn];
int gcd(int x,int y)
{
   // return 1;
    if(x<y)swap(x,y);
    if(y==0)return x;
    return gcd(y,x%y);
}
void init()
{
    root=tot=0;
    ch[root][0] = ch[root][1] = size[root] = pre[root] = 0;
    gcd0[root] = gcd1[root] = 0;
}
void newnode(int &x,int k,int father)
{
    x=++tot;
    pre[x]=father;
    size[x]=1;
    ch[x][0]=ch[x][1]=0;
    key[x]=node[k].val;
    st[x]=node[k].st;
    gcd0[x]=gcd1[x]=0;
    if(st[x]==0)gcd0[x]=node[k].val;
    else gcd1[x]=node[k].val;
    //cout<<gcd0[x]<<" "<<gcd1[x]<<endl;
}
void push_down(int x)
{

}
void push_up(int x)
{
    int ll=ch[x][0];
    int rr=ch[x][1];
    size[x]=size[ll]+size[rr]+1;
    gcd0[x]=gcd(gcd0[ll],gcd0[rr]);
    gcd1[x]=gcd(gcd1[ll],gcd1[rr]);
    if(st[x])gcd1[x]=gcd(gcd1[x],key[x]);
    else gcd0[x]=gcd(gcd0[x],key[x]);
}
void rot(int x,int kind)
{
    int y=pre[x];
    push_down(y);
    push_down(x);
    ch[y][!kind]=ch[x][kind];
    pre[ch[x][kind]]=y;
    if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    ch[x][kind]=y;
    pre[y]=x;
    push_up(y);
    push_up(x);
}
void splay(int x,int goal)
{
    push_down(x);
    while(pre[x]!=goal)
    {
        if(pre[pre[x]]==goal)
        {
            push_down(pre[x]);
            push_down(x);
            rot(x,ch[pre[x]][0]==x);
        }
        else
        {
            int y=pre[x];
            push_down(pre[y]);
            push_down(y);
            push_down(x);
            int kind=ch[pre[y]][0]==y;
            if(ch[y][kind]==x)
            {
                rot(x,!kind);
                rot(x,kind);
            }
            else
            {
                rot(y,kind);
                rot(x,kind);
            }
        }
    }
    push_up(x);
    if(goal==0)root=x;
}
void buildtree(int &x,int l,int r,int father)
{
    if(l>r)return ;
    int mid=(l+r)/2;
    newnode(x,mid,father);
    buildtree(ch[x][0],l,mid-1,x);
    buildtree(ch[x][1],mid+1,r,x);
    push_up(x);
}
int get_kth(int x,int k)
{
    push_down(x);
    int p=size[ch[x][0]];
    if(p+1==k)return x;
    else if(k<=p)return get_kth(ch[x][0],k);
    else get_kth(ch[x][1],k-p-1);
}
int que(int l,int r,int st)
{
    int x=get_kth(root,l);
    splay(x,0);
    int y=get_kth(root,r+2);
    splay(y,root);
    int ans;
    if(st==0)ans=gcd0[root10];
    else ans=gcd1[root10];
    if(ans==0)return -1;
    else return ans;
}
void add(int x,int val,int st)
{
    int l=get_kth(root,x+1);
    splay(l,0);
    int r=get_kth(root,x+2);
    splay(r,root);
    n++;
    node[n].st=st;
    node[n].val=val;
    newnode(root10,n,root1);
    push_up(root1);
    push_up(root);
}
void del(int x)
{
    int xx=get_kth(root,x);
    splay(xx,0);
    int y=get_kth(root,x+2);
    splay(y,root);
    pre[root10]=0;
    root10=0;
    push_up(root1);
    push_up(root);
}
void resst(int x)
{
    int xx=get_kth(root,x);
    splay(xx,0);
    int y=get_kth(root,x+2);
    splay(y,root);
    st[root10]^=1;
    push_up(root10);
    push_up(root1);
    push_up(root);
}
void resval(int x,int vv)
{
    int xx=get_kth(root,x);
    splay(xx,0);
    int y=get_kth(root,x+2);
    splay(y,root);
    key[root10]=vv;
    push_up(root10);
    push_up(root1);
    push_up(root);
}
char str[101];
int main()
{
    int m,i,j,l,r,val,x;
    int stt;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        node[0].st=0;node[0].val=0;
        for(i=1; i<=n; i++)
        {
            scanf("%d%d",&node[i].val,&node[i].st);
        }
        newnode(root,0,0);
        newnode(root1,0,root);
        buildtree(root10,1,n,root1);
        push_up(root1);
        push_up(root);
        int ii;
        for(ii=1; ii<=m; ii++)
        {
            // debug();
            scanf("%s",str);
            if(str[0]==‘Q‘)
            {
                scanf("%d%d%d",&l,&r,&stt);
                printf("%d\n",que(l,r,stt));
            }
            if(str[0]==‘I‘)
            {
                scanf("%d%d%d",&i,&val,&stt);
                add(i,val,stt);
            }
            if(str[0]==‘D‘)
            {
                scanf("%d",&i);
                del(i);
            }
            if(str[0]==‘R‘)
            {
                scanf("%d",&i);
                resst(i);
            }
            if(str[0]==‘M‘)
            {
                scanf("%d%d",&i,&x);
                resval(i,x);
            }
        }
    }
    return 0;
}

今天继续A了一个AC自动机的题目：

hdu-2296-Ring

需要记录路径，比较麻烦。

用string记录比较方便。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<string>
using namespace std;
const int maxnode=110*11;
const int childnum=26;
const int mod=20090717;
string path[55][maxnode];
struct ac_tree
{
    int chd[maxnode][childnum];
    int val[maxnode];
    int fail[maxnode];
    int Q[maxnode];
    int ID[128];
    int sz;
    int dp[55][maxnode];
    void init()
    {
        fail[0]=0;
        for(int i=0; i<childnum; i++)
        {
            ID[i+‘a‘]=i;
        }
    }
    void reset()
    {
        memset(chd,0,sizeof(chd));
        sz=1;
    }
    void insert(char str[],int k)
    {
        int p=0;
        int len=strlen(str);
        for(int i=0; i<len; i++)
        {
            int c=ID[str[i]];
            if(!chd[p][c])
            {
                memset(chd[sz],0,sizeof(chd[sz]));
                val[sz]=0;
                chd[p][c]=sz++;
            }
            p=chd[p][c];
        }
        val[p]=k;
      //  cout<<str<<" "<<p<<endl;
    }
    void ac_build()
    {
        int *s=Q,*e=Q;
        for(int i=0; i<childnum; i++)
        {
            if(chd[0][i])
            {
                fail[chd[0][i]]=0;
                *e++=chd[0][i];
            }
        }
        while(s!=e)
        {
            int u=*s++;
            for(int i=0; i<childnum; i++)
            {
                int &v=chd[u][i];
                if(v)
                {
                    *e++=v;
                    fail[v]=chd[fail[u]][i];
                   // val[v]=(val[v]+val[fail[v]]);
                }
                else v=chd[fail[u]][i];
            }
        }
    }
    void work(int n)
    {
        int ans=0;
        memset(dp,-1,sizeof(dp));
        dp[0][0]=0;
        for(int i=0; i<=n; i++)
            for(int j=0; j<sz; j++)
                path[i][j].clear();
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<sz; j++)
            {
                if(dp[i][j]==-1) continue;
                for(int k=0; k<26; k++)
                {
                    int cur=chd[j][k];
                    if(dp[i][j]+val[cur]>dp[i+1][cur])
                    {
                        dp[i+1][cur]=dp[i][j]+val[cur];
                        path[i+1][cur]=path[i][j]+(char)(k+‘a‘);
                    }
                    else if(dp[i][j]+val[cur]==dp[i+1][cur]&&path[i][j]+(char)(k+‘a‘)<path[i+1][cur])
                    {
                        path[i+1][cur]=path[i][j]+(char)(k+‘a‘);
                    }
                }
            }
        }
        for(int i=1; i<=n; i++)
            for(int j=0; j<sz; j++)
                ans=max(ans,dp[i][j]);
        if(ans==0)
        {
            puts("");
            return;
        }
       // cout<<ans<<endl;
        string str=" ";
        for(int i=1; i<=n; i++)
        for(int j=0; j<sz; j++)
        if(dp[i][j]==ans&&(str==" "||(path[i][j].size()<str.size()||(path[i][j].size()==str.size()&&path[i][j]<str)))) str=path[i][j];
        cout<<str<<endl;
    }
} AC;
char temp[110][15];
int main()
{
    AC.init();
    int n,m,k;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        AC.reset();
        for(int i=1; i<=m; i++)
        {
            scanf("%s",temp[i]);
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d",&k);
            AC.insert(temp[i],k);
        }
        //cout<<")"<<endl;
        AC.ac_build();
        AC.work(n);
    }
    return 0;
}