A题:
Fox Ciel has n boxes in her room. They have the same size and weight, but they might have different strength. The i-th box can hold at most xi boxes on its top (we‘ll call xi the strength of the box).
Since all the boxes have the same size, Ciel cannot put more than one box directly on the top of some box. For example, imagine Ciel has three boxes: the first has strength 2, the second has strength 1 and the third has strength 1. She cannot put the second and the third box simultaneously directly on the top of the first one. But she can put the second box directly on the top of the first one, and then the third box directly on the top of the second one. We will call such a construction of boxes a pile.
Fox Ciel wants to construct piles from all the boxes. Each pile will contain some boxes from top to bottom, and there cannot be more thanxi boxes on the top of i-th box. What is the minimal number of piles she needs to construct?
The first line contains an integer n (1?≤?n?≤?100). The next line contains n integers x1,?x2,?...,?xn (0?≤?xi?≤?100).
Output a single integer — the minimal possible number of piles.
3 0 0 10
2
5 0 1 2 3 4
1
4 0 0 0 0
4
9 0 1 0 2 0 1 1 2 10
3
In example 1, one optimal way is to build 2 piles: the first pile contains boxes 1 and 3 (from top to bottom), the second pile contains only box 2.
In example 2, we can build only 1 pile that contains boxes 1, 2, 3, 4, 5 (from top to bottom).
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> using namespace std; int a[102]; int main() { int n,i,x; while(cin>>n) { memset(a,0,sizeof(a)); for(i=0;i<n;i++) { cin>>x; a[x]++; } int res=0; while(1) { int flag=0; for(i=0;i<=100;i++) { if(a[i]) { flag=1; break; } } if(flag==0) break; int step=0; for(i=0;i<=100;i++) { if((a[i]>=1&&i==step)||(a[i]==1&&step<i)) { a[i]--; step++; } else if(step<i&&a[i]>=2) { a[i]--; step++; //cout<<i<<" "<<step<<" dsad"<<endl; //continue; i--; } } //for(i=0;i<=5;i++) //cout<<a[i]<<" "; //cout<<endl; res++; } cout<<res<<endl; } return 0; } /* 3 0 0 10 5 0 1 2 3 4 4 0 0 0 0 9 0 1 0 2 0 1 1 2 10 7 0 2 2 2 3 4 5 */
这个题目当时写的时候很拙计,虽然样例过了,但是自己随便写了组测试数据就过不了,然后就debug了好久。。
Fox Ciel wants to write a task for a programming contest. The task is: "You are given a simple undirected graph with n vertexes. Each its edge has unit length. You should calculate the number of shortest paths between vertex 1 and vertex 2."
Same with some writers, she wants to make an example with some certain output: for example, her birthday or the number of her boyfriend. Can you help her to make a test case with answer equal exactly to k?
The first line contains a single integer k (1?≤?k?≤?109).
You should output a graph G with n vertexes (2?≤?n?≤?1000). There must be exactly k shortest paths between vertex 1 and vertex 2 of the graph.
The first line must contain an integer n. Then adjacency matrix G with n rows and n columns must follow. Each element of the matrix must be ‘N‘ or ‘Y‘. If Gij is ‘Y‘, then graph G has a edge connecting vertex i and vertex j. Consider the graph vertexes are numbered from 1 ton.
The graph must be undirected and simple: Gii = ‘N‘ and Gij?=?Gji must hold. And there must be at least one path between vertex 1 and vertex 2. It‘s guaranteed that the answer exists. If there multiple correct answers, you can output any of them.
2
4 NNYY NNYY YYNN YYNN
9
8 NNYYYNNN NNNNNYYY YNNNNYYY YNNNNYYY YNNNNYYY NYYYYNNN NYYYYNNN NYYYYNNN
1
2 NY YN
In first example, there are 2 shortest paths: 1-3-2 and 1-4-2.
In second example, there are 9 shortest paths: 1-3-6-2, 1-3-7-2, 1-3-8-2, 1-4-6-2, 1-4-7-2, 1-4-8-2, 1-5-6-2, 1-5-7-2, 1-5-8-2.
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> using namespace std; int mp[100][105]; int main() { int k; int i,j; while(cin>>k) { memset(mp,0,sizeof(mp)); mp[1][5]=1; if(k&(1<<30)) { mp[1][3]=1; mp[1][4]=1; } j=3; for(i=29;i>=1;i--) { mp[j][j+3]=1,mp[j][j+4]=1; mp[j+1][j+3]=1,mp[j+1][j+4]=1; mp[j+2][j+5]=1; if(k&(1<<i)) { mp[j+2][j+3]=1; mp[j+2][j+4]=1; } j+=3; } mp[90][2]=1,mp[91][2]=1; if(k&1) mp[92][2]=1; cout<<92<<endl; for(i=1;i<=92;i++) { for(j=1;j<=92;j++) { if(mp[i][j]||mp[j][i]) cout<<"Y"; else cout<<"N"; } cout<<endl; } } return 0; }
Fox Ciel is playing a card game with her friend Fox Jiro. There are n piles of cards on the table. And there is a positive integer on each card.
The players take turns and Ciel takes the first turn. In Ciel‘s turn she takes a card from the top of any non-empty pile, and in Jiro‘s turn he takes a card from the bottom of any non-empty pile. Each player wants to maximize the total sum of the cards he took. The game ends when all piles become empty.
Suppose Ciel and Jiro play optimally, what is the score of the game?
The first line contain an integer n (1?≤?n?≤?100). Each of the next n lines contains a description of the pile: the first integer in the line issi (1?≤?si?≤?100) — the number of cards in the i-th pile; then follow si positive integers c1, c2, ..., ck, ..., csi (1?≤?ck?≤?1000) — the sequence of the numbers on the cards listed from top of the current pile to bottom of the pile.
Print two integers: the sum of Ciel‘s cards and the sum of Jiro‘s cards if they play optimally.
2 1 100 2 1 10
101 10
1 9 2 8 6 5 9 4 7 1 3
30 15
3 3 1 3 2 3 5 4 6 2 8 7
18 18
3 3 1000 1000 1000 6 1000 1000 1000 1000 1000 1000 5 1000 1000 1000 1000 1000
7000 7000
In the first example, Ciel will take the cards with number 100 and 1, Jiro will take the card with number 10.
In the second example, Ciel will take cards with numbers 2, 8, 6, 5, 9 and Jiro will take cards with numbers 4, 7, 1, 3.
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<vector> using namespace std; vector <int> mq[105]; int xf[105]; int main() { int n,s,x; int i,j; int a,b; while(cin>>n) { for(i=1;i<=100;i++) mq[i].clear(); a=0,b=0; for(i=1;i<=n;i++) { cin>>s; while(s--) { cin>>x; mq[i].push_back(x); } } int t=0; for(i=1;i<=n;i++) { if(!(mq[i].size()&1)) { for(j=0;j<mq[i].size()/2;j++) a+=mq[i][j]; for(;j<mq[i].size();j++) b+=mq[i][j]; } else { for(j=0;j<mq[i].size()/2;j++) a+=mq[i][j]; xf[t++]=mq[i][j++]; for(;j<mq[i].size();j++) b+=mq[i][j]; } } sort(xf,xf+t); int flag=0; for(i=t-1;i>=0;i--) { if(!flag) { a+=xf[i]; flag=1; } else { b+=xf[i]; flag=0; } } cout<<a<<" "<<b<<endl; } return 0; } /* 2 1 100 2 1 10 1 9 2 8 6 5 9 4 7 1 3 3 3 1 3 2 3 5 4 6 2 8 7 3 3 1000 1000 1000 6 1000 1000 1000 1000 1000 1000 5 1000 1000 1000 1000 1000 */