Coding

Subsequence

There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.

输入描述:

There are multiple test cases.
       
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
       
Proceed to the end of file.

输出描述:

For each test case, print the length of the subsequence on a single line.

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int MAXN=100010;
int q1[MAXN],q2[MAXN];
int rear1,head1;
int rear2,head2;
int a[MAXN];
int main()
{
    int n,m,k;

    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        rear1=head1=0;
        rear2=head2=0;
        int ans=0;
        int now=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            while(head1<rear1&&a[q1[rear1-1]]<a[i])rear1--;
            while(head2<rear2&&a[q2[rear2-1]]>a[i])rear2--;
            q1[rear1++]=i;
            q2[rear2++]=i;
            while(head1<rear1&&head2<rear2&&a[q1[head1]]-a[q2[head2]]>k)
            {
                if(q1[head1]<q2[head2])now=q1[head1++]+1;
                else now=q2[head2++]+1;
            }
            if(head1<rear1&&head2<rear2&&a[q1[head1]]-a[q2[head2]]>=m)
            {
                if(ans<i-now+1)ans=i-now+1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

最长回文

给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等.

输入描述:

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 
两组case之间由空行隔开(该空行不用处理)
       
字符串长度len <= 110000

输出描述:

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

char s[211000],c[111000];
int p[211000];

void init()
{
    int i,j;
    s[0]='@';
    for(i=0;c[i]!=0;i++)
    {
        s[2*i+1]='#';
        s[2*i+2]=c[i];
    }
    s[2*i+1]='#';
    s[2*i+2]=0;
}

int manacher()
{
    int id=0,mx=0,i;
    for(i=1;s[i]!=0;i++)
    {
        p[i]=mx>i?min(p[2*id-i],mx-i):1;
        while(s[i+p[i]] == s[i-p[i]])p[i]++;
        if(i+p[i]>mx)
        {
            mx=i+p[i];
            id=i;
        }
    }
    mx=0;
    for(i=1;s[i]!=0;i++)
    {
        if(p[i]>mx)mx=p[i];
    }
    return mx-1;
}

int main()
{
    while(~scanf("%s",c))
    {
        init();
        printf("%d\n",manacher());
    }
    return 0;
}

畅通工程

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路.

输入描述:

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 
       
注意:两个城市之间可以有多条道路相通,也就是说
       
3 3 
1 2 
1 2 
2 1 
这种输入也是合法的
       
当N为0时，输入结束，该用例不被处理。 

输出描述:

对每个测试用例，在1行里输出最少还需要建设的道路数目。

#include <stdio.h>
int p[1222];
int i;
int find(int x)
{
    if(x!=p[x])
        p[x]=find(p[x]);
    return p[x];
}
int hebing(int x,int y)
{
    return p[x]=y;
}
int main()
{
    int n,m,x,y,x1,y1;
    while(~scanf("%d%d",&n,&m)&&n)
    {
        for(i=1;i<=1222;i++)
            p[i]=i;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            x1=find(x);
            y1=find(y);
            if(x1!=y1)
                hebing(x1,y1);
        }
        int ans=0;
        for(i=1;i<=n;i++)
        {
            if(p[i]==i)
                ans++;
        }
        printf("%d\n",ans-1);
    }
    return 0;
}

胜利大逃亡

Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.

魔王住在一个城堡里,城堡是一个ABC的立方体,可以被表示成A个B*C的矩阵,
刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.

输入描述:

输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表城堡的大小和魔王回来的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块......),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙.(如果对输入描述不清楚,可以参考Sample Input中的迷宫描述,它表示的就是上图中的迷宫)
       

特别注意:本题的测试数据非常大,请使用scanf输入,我不能保证使用cin能不超时.在本OJ上请使用Visual C++提交.

输出描述:

对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int A, B, C, T;
struct point {
    int x, y, z;
    int t;
    point(int x=0, int y=0, int z=0, int t=0): x(x), y(y), z(z), t(t) {}
};
int direct[][3] = {{1,0,0}, {-1,0,0}, {0,0,1}, {0,0,-1}, {0,1,0}, {0,-1,0}};
int Map[55][55][55];
int BFS() {
    queue<point> que;
    que.push(point(0,0,0,0));
    while(que.size()) {
        point p = que.front();
        que.pop();
        if(p.t > T)
            continue;
        if(p.x == A-1 && p.y == B-1 && p.z == C-1)
            return p.t;
        for(int k=0; k<6; ++k) {
            int nx = p.x + direct[k][0];
            int ny = p.y + direct[k][1];
            int nz = p.z + direct[k][2];
            if(nx >=0 && nx<A && ny>=0 && ny<B && nz>=0 && nz<C && Map[nx][ny][nz] == 0) {
                que.push(point(nx, ny, nz, p.t+1));
                Map[nx][ny][nz] = 1;
            }
        }
    }
    return - 1;

}

int main()
{
    int K;
    scanf("%d", &K);
    while(K--) {
        scanf("%d%d%d%d", &A, &B, &C, &T);
        for(int a=0; a<A; ++a)
            for(int b=0; b<B; ++b)
                for(int c=0; c<C; ++c)
                    scanf("%d", &Map[a][b][c]);
        printf("%d\n", BFS());
    }

    return 0;
}

逃生

糟糕的事情发生啦，现在大家都忙着逃命。但是逃命的通道很窄，大家只能排成一行。

现在有n个人，从1标号到n。同时有一些奇怪的约束条件，每个都形如：a必须在b之前。
同时，社会是不平等的，这些人有的穷有的富。1号最富，2号第二富，以此类推。有钱人就贿赂负责人，所以他们有一些好处。

负责人现在可以安排大家排队的顺序，由于收了好处，所以他要让1号尽量靠前，如果此时还有多种情况，就再让2号尽量靠前，如果还有多种情况，就让3号尽量靠前，以此类推。

那么你就要安排大家的顺序。我们保证一定有解。

输入描述:

第一行一个整数T(1 <= T <= 5),表示测试数据的个数。
       
然后对于每个测试数据，第一行有两个整数n(1 <= n <= 30000)和m(1 <= m <= 100000)，分别表示人数和约束的个数。
       

然后m行，每行两个整数a和b，表示有一个约束a号必须在b号之前。a和b必然不同。

输出描述:

对每个测试数据，输出一行排队的顺序，用空格隔开。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
struct list
{
    int u,v,w;
    int next;
}edge[110000];
int head[33000];
int nums;
void add(int u,int v,int w)
{
    edge[nums].u=u;
    edge[nums].v=v;
    edge[nums].w=w;
    edge[nums].next=head[u];
    head[u]=nums++;
}
int du[33000];
void init()
{
    memset(head,-1,sizeof(head));
    nums=1;
    memset(du,0,sizeof(du));
}
priority_queue<int>que;
vector<int>vec;
int n;
void dos()
{
    vec.clear();
    while(!que.empty())que.pop();
    for(int i=1;i<=n;i++)
    {
        if(du[i]==0)que.push(i);
    }
    while(!que.empty())
    {
        int x=que.top();
        que.pop();
        for(int i=head[x];i!=-1;i=edge[i].next)
        {
            int y=edge[i].v;
            du[y]--;
            if(du[y]==0)
            {
                que.push(y);
            }
        }
        vec.push_back(x);
    }
    for(int i=n-1;i>=0;i--)
    {
        if(i!=n-1)printf(" ");
        printf("%d",vec[i]);
    }
    cout<<endl;
}
int main()
{
    int T,m,a,b;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            add(b,a,1);
            du[a]++;
        }
        dos();
    }
    return 0;
}

亲和串

人随着岁数的增长是越大越聪明还是越大越笨，这是一个值得全世界科学家思考的问题,同样的问题Eddy也一直在思考，因为他在很小的时候就知道亲和串如何判断了，但是发现，现在长大了却不知道怎么去判断亲和串了，于是他只好又再一次来请教聪明且乐于助人的你来解决这个问题。
亲和串的定义是这样的：给定两个字符串s1和s2,如果能通过s1循环移位，使s2包含在s1中，那么我们就说s2 是s1的亲和串。

输入描述:

本题有多组测试数据，每组数据的第一行包含输入字符串s1,第二行包含输入字符串s2，s1与s2的长度均小于100000。

输出描述:

如果s2是s1的亲和串，则输出"yes"，反之，输出"no"。每组测试的输出占一行。

#include<stdio.h>
#include<string.h>
int main()
{
    char s1[200001],s2[110000];
    while(~scanf("%s %s",s1,s2))
    {
        sprintf(s1,"%s%s",s1,s1);
        if(strstr(s1,s2))puts("yes");
        else puts("no");
    }
}

最短路

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

输入描述:

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。

输入保证至少存在1条商店到赛场的路线。

输出描述:

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 1000000
using namespace std;
int city,road;
int mapp[205][205];
int spand[205];
int select[205];
void dij(int city)
{
    int minn,k,i,j;
    memset(select,0,sizeof(select));
    for(i=1;i<=city;i++)
    spand[i]=mapp[1][i];
    spand[1]=0;select[1]=1;
    for(i=2;i<=city;i++)
    {
        minn=INF;k=-1;
        for(j=1;j<=city;j++)
        {
            if(!select[j]&&spand[j]<minn)
            {
                k=j;minn=spand[j];
            }
        }
        if(k==-1)break;
        select[k]=1;
        for(j=1;j<=city;j++)
        {
            if(spand[j]>spand[k]+mapp[k][j]&&!select[j])
            spand[j]=spand[k]+mapp[k][j];
        }
    }
    printf("%d\n",spand[city]);
}
int main()
{
    int i;int x,y,z;
    while(scanf("%d%d",&city,&road)!=EOF)
    {
        if(city==0||road==0)
        break;
        memset(mapp,INF,sizeof(mapp));
        memset(spand,INF,sizeof(spand));
        for(i=1;i<=road;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(mapp[x][y]>z||mapp[y][x]>z)
            {
                mapp[x][y]=z;mapp[y][x]=z;
            }
        }
        dij(city);
    }
    return 0;
}