Harry And Physical Teacher

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

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 Biological Teacher

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;
}

BestCoder Round #14