Harry And Physical Teacher

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 38    Accepted Submission(s): 34

As we all know, Harry Porter learns magic at Hogwarts School. However, learning magical knowledge alone is insufficient to become a great magician. Sometimes, Harry also has to gain knowledge from other certain subjects, such as language,
mathematics, English, and even algorithm.
Today, Harry's physical teacher set him a difficult problem: if a small ball moving with a speedV0
made a completely elastic collision with a car moving towards the same direction with a speedV(V<V0),
and the car far outweighs the ball, what was the speed of the small ball after the collision?
This problem was so difficult that Harry hasn't figure out how to solve it. Therefore, he asks you for help. Could you do him this favor?

They are several test cases, you should process to the end of file.
There are two integers V
and V0
for each test case. All the integers are 32-bit signed non-negative integers.

0 10

-10

题意：

a,b两个球a的速度我va。b的速度为vb。va>vb.va,vb同向且a在b的后面。b的质量远大于a。

思路：

a肯定会撞b的。正规的思路应该是动量守恒。机械能守恒。然后blabla。我的思路是既然b的质量远大于a。那么b可以看做是一堵墙。而a撞墙的速度就是va-vb咯。由于弹性碰撞。撞墙后速度肯定是反向啦。所以速度就变为-(va-vb)

但是这个速度是相对墙的。所以转化为绝对速度就为-(va-vb)+vb。

详细见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;

int main()
{
    int v1,v2;

    while(~scanf("%d%d",&v1,&v2))
    {
        printf("%d\n",2*v1-v2);
    }
    return 0;
}

Harry And Dig Machine

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 170    Accepted Submission(s): 50

They are sever test cases, you should process to the end of file.
For each test case, there are two integers n and m.(1≤n,m≤50).
The next n line, each line contains m integer. The j-th number of
ith
line a[i][j] means there are a[i][j] stones on the
jth
cell of the ith
line.( 0≤a[i][j]≤100
, and no more than 10 of a[i][j] will be positive integer).

3 3
0 0 0
0 100 0
0 0 0
2 2
1 1
1 1

4
4

题意：

哈利珀特学挖掘机了。那么问题来了。。。。--||。一个n*m(50*50)的格子。一些格子数字大于0个数不超过10(看到这就懂了).你开始在左上角。然后你要经过所有这些数字大于0的格子然后回到左上角。然后问你最少需要多少步完成这个目标。每步可以往四个方向走一步。

思路：

由于数字大于0的格子不超过10所以可以壮压。这就是经典的TSP问题啦。先对特殊格子编号然后bfs计算两两特殊格子的距离(步数).然后就TSP了。dp[i][s]表示目前在i走到的格子状态为s。

详细见代码:

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int maze[55][55],hs[55][55],vis[55][55];
int dp[13][1<<12],dis[15][15],base[15];
int sx[55],sy[55],cnt,n,m;
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
struct node
{
    int x,y,d;
};
queue<node> q;
void bfs(int id)
{
    while(!q.empty())
        q.pop();
    node tt,nt;
    memset(vis,0,sizeof vis);
    tt.x=sx[id],tt.y=sy[id];
    dis[id][id]=tt.d=0;
    vis[tt.x][tt.y]=1;
    q.push(tt);
    int nx,ny,i;
    while(!q.empty())
    {
        tt=q.front();
        q.pop();
        for(i=0;i<4;i++)
        {
            nx=tt.x+dx[i];
            ny=tt.y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny])
            {
                vis[nx][ny]=1;
                nt.x=nx,nt.y=ny,nt.d=tt.d+1;
                if(hs[nx][ny]!=-1)
                    dis[id][hs[nx][ny]]=nt.d;
                q.push(nt);
            }
        }
    }
}
int main()
{
    int i,j,k,lim;

    base[0]=1;
    for(i=1;i<15;i++)
        base[i]=base[i-1]<<1;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;
        memset(hs,-1,sizeof hs);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&maze[i][j]);
                if(maze[i][j]||(i==1&&j==1))
                {
                    sx[cnt]=i,sy[cnt]=j;
                    hs[i][j]=cnt++;
                }
            }
        }
        for(i=0;i<cnt;i++)
            bfs(i);
        memset(dp,0x3f,sizeof dp);
        dp[0][0]=0;
        lim=1<<cnt;
        for(i=0;i<lim;i++)
        {
            for(j=0;j<cnt;j++)
            {
                if(dp[j][i]==INF)
                    continue;
                for(k=0;k<cnt;k++)
                {
                    if(i&base[k])
                        continue;
                    dp[k][i|base[k]]=min(dp[k][i|base[k]],dp[j][i]+dis[j][k]);
                }
            }
        }
        printf("%d\n",dp[0][lim-1]);
    }
    return 0;
}

Harry And Math Teacher

Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 170    Accepted Submission(s): 48

They are sever test cases, you should process to the end of file.
For each test case, there are two integers n and m(2≤n≤50000,1≤m≤50000)
in the first line, indicate the number of the castle’s layers and the number of queries. And the following m lines, each line contains three or four integers. If the first integer op equals 0, there are two integers a and b (1≤a<b≤n)
follow, indicate the position of Harry and math teacher. Otherwise, there are three integers
x,y,z(1≤x<n,1≤y,z≤2)follow,
it means that the stair between the xth
floor’s yth
door and the (x+1)th
floor’s z-th door changes its state(if it is intact, then it breaks else it joints).

For each query, if op equals 0, you should output one line that contains an integer indicates the number of ways from
ath
floor to the bth
floor.

3 1
0 1 3
3 2
1 2 1 1
0 1 3

8
6

题意：

有一栋楼。每层楼有两扇门。每扇门后面都有两条通向上一层楼的楼梯。楼的层数为n(5e4)。然后m个操作。

0 a b   询问a楼到b楼有多少种走法。a<b。

1 x y z  改变x层楼y们到x+1层楼z门的楼梯状态(可以走。不可以走)。

思路：

c题赛后。读了下题。发现是大水题。我们可以用一个2*2的矩阵来表示x层楼到x+1层楼的楼梯状态。1表示可以走。0表示不能走。然后线段树维护区间乘积就行了。只是现在的线段树的结点为一个2*2的矩阵罢了。单点更新区间查询。

详细见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=50050;
const int mod=1e9+7;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
struct Matrix
{
    int val[3][3];
    Matrix(){ memset(val,0,sizeof val);}
    inline Matrix operator *(const Matrix &op)
    {
        Matrix tt;
        int i,j,k;
        for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
                for(k=1;k<=2;k++)
                    tt.val[i][j]=(tt.val[i][j]+(ll)val[i][k]*op.val[k][j]%mod)%mod;
        return tt;
    }
} yb[maxn<<2];
void build(int L,int R,int rt)
{
    if(L==R)
    {
        yb[rt].val[1][1]=1;
        yb[rt].val[1][2]=1;
        yb[rt].val[2][1]=1;
        yb[rt].val[2][2]=1;
        return;
    }
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    build(lson);
    build(rson);
    yb[rt]=yb[ls]*yb[rs];
}
void update(int L,int R,int rt,int p,int u,int v)
{
    if(L==R)
    {
        yb[rt].val[u][v]^=1;
        return;
    }
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    if(p<=mid)
        update(lson,p,u,v);
    else
        update(rson,p,u,v);
    yb[rt]=yb[ls]*yb[rs];
}
Matrix qu(int L,int R,int rt,int l,int r)
{
    if(l<=L&&R<=r)
        return yb[rt];
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    Matrix tt;
    tt.val[1][1]=tt.val[2][2]=1;
    if(l<=mid)
        tt=tt*qu(lson,l,r);
    if(r>mid)
        tt=tt*qu(rson,l,r);
    return tt;
}
int main()
{
    int n,m,x,y,z,i,op,ans;

    while(~scanf("%d%d",&n,&m))
    {
        n--;
        build(1,n,1);
        for(i=1;i<=m;i++)
        {
            scanf("%d",&op);
            if(!op)
            {
                scanf("%d%d",&x,&y);
                Matrix tt=qu(1,n,1,x,y-1);
                ans=0;
                for(int j=1;j<=2;j++)
                    for(int k=1;k<=2;k++)
                        ans=(ans+tt.val[j][k])%mod;
                printf("%d\n",ans);
            }
            else
            {
                scanf("%d%d%d",&x,&y,&z);
                update(1,n,1,x,y,z);
            }
        }
    }
    return 0;
}

Harry And Biological Teacher

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 26    Accepted Submission(s): 2

They are sever test cases, you should process to the end of file.
For each test case, there are two integers n and m (1≤n≤100000,1≤m≤100000)on
the first line, indicate the number of genes and the number of queries.
The next following n line, each line contains a non-empty string composed by characters 'A' , 'T' , 'C' , 'G'. The sum of all the characters is less than 100000.
Then the next following m line, each line contains two integers a and b(1≤a,b≤n),
indicate the query.

2 1
ACCGT
TTT
1 2
4 4
AAATTT
TTTCCC
CCCGGG
GGGAAA
1 2
2 3
3 4
4 1

1
3
3
3
3

题意:

给你n个由A,G,C,T构成的字符串。n个字符串的总长度不超过1e5.然后m个询问。n，m<=1e5.每次询问a,b两个字符串。找到一个最长的串使得它是a的后缀。然后也是b的前缀。输出它的长度就行了。

思路：

第一想法就是后缀自动机。然后就开搞了。离线处理所有询问。把所有第一个串是a的b建个邻接表。然后依次处理每个a。先对a建后缀自动机。然后对于串b在自动机上匹配就是了。匹配的最大长度的可接受态就是答案。然后一A。甚欢。比赛结束后才发现忘了记忆化。就是对每个a链里的每一个b只需要跑一遍就行了。哎，可惜发现的太晚了。还是无情的T了。就上后再就200ms过了。。。真是冤死了。时间复杂度。由于顶多对n各字符串都建一次后缀自动机。然后每次询问最多也只能匹配a串那么长。所以复杂度为2*总串长。就O(n)咯。

详细见代码:

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
char txt[maxn<<1];
int st[maxn],ans[maxn];
map<int,int> mp;
struct node
{
    node *f,*ch[30];
    int len,ac;
    void init()
    {
        ac=0;
        memset(ch,0,sizeof ch);
    }
}*root,*tail,sam[maxn<<1];
int tot,len,cnt;
struct qnode
{
    qnode *next;
    int v,id;
} ed[maxn<<1],*head[maxn];
void adde(int u,int v,int id)
{
    ed[cnt].v=v;
    ed[cnt].id=id;
    ed[cnt].next=head[u];
    head[u]=&ed[cnt++];
}
void init()
{
    tot=0;
    root=tail=&sam[tot++];
    root->init();
    root->len=0;
}
void Insert(int c)
{
    node *p=tail,*np=&sam[tot++];
    np->init(),np->len=p->len+1;
    while(p&&!p->ch[c])
        p->ch[c]=np,p=p->f;
    tail=np;
    if(!p)
        np->f=root;
    else
    {
        if(p->ch[c]->len==p->len+1)
            np->f=p->ch[c];
        else
        {
            node *q=p->ch[c],*nq=&sam[tot++];
            *nq=*q;
            nq->len=p->len+1;
            q->f=np->f=nq;
            while(p&&p->ch[c]==q)
                p->ch[c]=nq,p=p->f;
        }
    }
}
int main()
{
    int i,j,n,m,len,tl,u,v;

    while(~scanf("%d%d",&n,&m))
    {
        len=cnt=0;
        for(i=1;i<=n;i++)
        {
            st[i]=len;
            scanf("%s",txt+len);
            tl=strlen(txt+len);
            len=len+tl+1;
        }
        memset(head,0,sizeof head);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            adde(u,v,i);
        }
        for(i=1;i<=n;i++)
        {
            init();
            for(j=st[i];txt[j];j++)
                Insert(txt[j]-'A');
            for(node *p=tail;p!=NULL;p=p->f)
                p->ac=1;
            mp.clear();
            for(qnode *q=head[i];q!=NULL;q=q->next)
            {
                if(mp.count(q->v))
                {
                    ans[q->id]=mp[q->v];
                    continue;
                }
                node *p=root;
                int ct=0,aa=0;
                for(j=st[q->v];txt[j];j++)
                    if(p->ch[txt[j]-'A']!=NULL)
                    {
                        ct++,p=p->ch[txt[j]-'A'];
                        if(p->ac)
                            aa=max(aa,ct);
                    }
                    else
                        break;
                ans[q->id]=aa;
                mp[q->v]=aa;
            }
        }
        for(i=1;i<=m;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}