5.13五一清北基础班试题1、洛谷P1149 火柴棒等式（时空限制1s / 128MB）题目描述给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示： 注意：1.加号与等号各自需要两根火柴棍2.如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）   3.n根火柴棍必须全部用上输入输出格式输入格式：输入文件matches.in共一行，又一个整数n（n<=24）。输出格式：输出文件matches.out共一行，表示能拼成的不同等式的数目。输入输出样例输入样例#1：样例输入1：14样例输入2：18输出样例#1：样例输出1：2样例输出2：9说明【输入输出样例1解释】2个等式为0+1=1和1+0=1。【输入输出样例2解释】9个等式为：0+4=4     0+11=11    1+10=112+2=4     2+7=9      4+0=47+2=9     10+1=11    11+0=11 2、洛谷P1113 杂务题目描述John的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起来，将他们赶进牛棚，为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的，因为这样才有更多时间挤出更多的牛奶。当然，有些杂务必须在另一些杂务完成的情况下才能进行。比如：只有将奶牛赶进牛棚才能开始为它清洗乳房，还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务1。John有需要完成的n个杂务的清单，并且这份清单是有一定顺序的，杂务k(k>1)的准备工作只可能在杂务1..k-1中。写一个程序从1到n读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作，并且，你可以假定John的农场有足够多的工人来同时完成任意多项任务。输入输出格式输入格式：第1行：一个整数n，必须完成的杂务的数目(3<=n<=10,000)；第2 ~ n+1行： 共有n行，每行有一些用1个空格隔开的整数，分别表示：工作序号(1..n,在输入文件中是有序的)；完成工作所需要的时间len（1<=len<=100）；   一些必须完成的准备工作，总数不超过100个，由一个数字0结束。有些杂务没有需要准备的工作只描述一个单独的0，整个输入文件中不会出现多余的空格。输出格式：一个整数，表示完成所有杂务所需的最短时间。输入输出样例输入样例#1：71 5 02 2 1 03 3 2 04 6 1 05 1 2 4 06 8 2 4 07 4 3 5 6 0输出样例#1：23  3、洛谷P2782 友好城市题目描述有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。没对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航道不相交的情况下，被批准的申请尽量多。输入输出格式输入格式：第1行，一个整数N（1<=N<=5000），表示城市数。第2行到第n+1行，每行两个整数，中间用一个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。（0<=xi<=10000）输出格式：仅一行，输出一个整数，表示政府所能批准的最多申请数。输入输出样例输入样例#1：722 42 610 315 129 817 174 2输出样例#1：4说明1<=N<=5000,0<=xi<=10000

#include<iostream>#include<cstdio>using namespace std;int n,ans;int cost[15]={6,2,5,5,4,5,6,3,7,6};bool check(int a,int b){    int ca=0,cb=0,cc=0;    int c=a+b;    if(a==0)ca+=cost[0];    if(b==0)cb+=cost[0];    if(c==0)cc+=cost[0];    while(a>0)    {        ca+=cost[a%10];        a/=10;    }    while(b>0)    {        cb+=cost[b%10];        b/=10;    }    while(c>0)    {        cc+=cost[c%10];        c/=10;    }    if((ca+cb+cc)==n)        return true;    else return false;}void DFS(int sum){    if(sum>1000)return;    for(int i=0;i<=1000;++i)        if(check(sum,i))        {            ans++;        }    DFS(sum+1);        return;    }int main(){    scanf("%d",&n);    n-=4;    ans=0;    DFS(0);        printf("%d",ans);    return 0;}

#include<iostream>#include<cstdio>#include<cstdlib>#include<queue>#include<cstring>using namespace std;class Edge {    public:    int b,w,next;};queue<int>que;Edge edge[1000005];long long maxtime;int head[1000005],sum=1;int m,n,start,end;int pen[10005];int num=1;bool visit[10005];long long ttt[10005];int tt[10005];void add(int a,int b){    pen[b]++;    edge[sum].b=b;    edge[sum].next=head[a];    head[a]=sum++;}bool topsort(){    for(int i=1;i<=m;++i)        if(!pen[i])        {            visit[i]=true;            que.push(i);        }    while(que.size())    {        int topsize=que.front();        que.pop();        for(int i=head[topsize];i!=-1;i=edge[i].next)        {            int bbb=edge[i].b;            pen[bbb]--;            if(tt[bbb]==ttt[bbb])                ttt[bbb]+=ttt[topsize];            else             ttt[bbb]=max(ttt[bbb],ttt[topsize]+tt[bbb]);            if(!pen[bbb])            {                visit[bbb]=true;                que.push(bbb);            }        }    }}int main(){    memset(head,-1,sizeof(head));    cin>>m;    for(int i=1;i<=m;++i)    {        int no,t,qian;        scanf("%d%d%d",&no,&t,&qian);        ttt[no]=tt[no]=t;        while(qian!=0)        {            add(qian,no);            scanf("%d",&qian);        }    }    topsort();    long long  maxl=0;    for(int i=1;i<=m;++i)        maxl=max(maxl,ttt[i]);    printf("%d",maxl);    return 0;}

#include<iostream>#include<algorithm>#include<cstdio>using namespace std;int n,cnt=0;int f[100000];int main(){    cin>>n;    for(int i=1;i<=n;++i)    {        int a,b;        scanf("%d%d",&a,&b);        int c=b-a;        if(c>=f[cnt])            f[++cnt]=c;        else         {            int p;            p=(lower_bound(f+1,f+cnt+1,c)-f);            f[p]=c;        }    }    cout<<cnt;    return 0;}