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#include 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#include #include #include #include using namespace std;class Edge { public: int b,w,next;};queue 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#include #include 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<