今天做做BNU几年前的网络赛题目,,,
A题:
其实,我们将一团大蒜掰成若干蒜瓣,将蒜瓣分别埋到土里。一年之后,每一个蒜瓣都能长成一团大蒜。
我们假设每团大蒜都由8瓣蒜瓣构成,那么将一团大蒜掰开种下去,第一年就能收获8团大蒜;再将所有的大蒜都种下去,第二年就能收获64团大蒜。
现在我们手里只有一团大蒜,但是我们想知道第n年(1<=n<=10)我们最多能收获多少团大蒜。
Input
接下来有casen行,每一行为一组测试数据。每行包含一个整数n,表示我们想知道第n年的收成。
Output
Sample Input
3 1 5 10
Sample Output
8 32768 1073741824
思路:这题没什么好说的,只要求出pow(8,n)就是答案了,关系也很明确。
代码:
# include<cstdio> # include<iostream> # include<cmath> using namespace std; int main(void) { int icase = 0; int t;cin>>t; while ( t-- ) { int n;cin>>n; long long ans = pow(8,n); printf("%ld\n",ans); //cout<<pow(8,n)<<endl; } }
B题:
LiuLibo’s Party
64-bit integer IO format: %lld
Java class name: Main
现在他想知道,在最理想的情况下,最多他能邀请到多少对相互认识的人。
举例说明一下,如果LiuLibo的两个朋友丁丁和迪迪是相互认识的,另外丁丁和瓜瓜相互认识,但是瓜瓜和迪迪不认识,那么邀请这三个人参加party是符合条件的。其中包含两对相互认识的人:丁丁——迪迪、丁丁——瓜瓜。
Input
如果n=0则表示输入结束。
Output
Sample Input
1 2 3 0
Sample Output
0 1 2
思路:其实就是一个二分图的匹配的问题了,任意画一个二分图,然后把两个独立集合中的顶点进行连线,如果能相互连接,且有边的个数,就是相互认识的人数了。
代码:
# include<cstdio> # include<iostream> # include<cstring> # include<algorithm> # include<string> # include<queue> using namespace std; # define inf 0x3f3f3f3f # define MAX 56 int a[MAX]; int main(void) { int n; while ( cin>>n ) { if ( n==0 ) break; int a = n/2; int b = n-a; cout<<a*b<<endl; } return 0; }
C题:
解题思路:
这道题就是判断一个集合的交集,然后把这些交集中的元素按照从小到大的顺序输出来就可以了,其实也没什难度的,就是把这种求交集的模板要记住了,而且这道题也可以用vector来写,,以前一直不会用STL这几个容器,现在随着见到的题目的增多,越来越会做了。。。
代码:
# include<cstdio> # include<iostream> # include<vector> # include<algorithm> using namespace std; # define MAX 10000+4 int a[MAX]; int b[MAX]; int main(void) { int t;cin>>t; while ( t-- ) { int m;cin>>m; int val; for ( int i = 0;i < m;i++ ) { cin>>a[i]; } int m2; cin>>m2; for ( int i = 0;i < m2;i++ ) { cin>>b[i]; } sort(a,a+m); sort(b,b+m2); int flag = 0; for ( int p = 0,q = 0;p < m&&q < m2; ) { if ( a[p] > b[q] ) { q++; } else if ( a[p] < b[q] ) { p++; } else { if ( flag ) { cout<<" "; } cout<<a[p]; flag = 1; p++; q++; } } if ( !flag ) { cout<<"empty"<<endl; } cout<<endl; } return 0; }
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(int argc, char *argv[]) { int n; cin >> n; for (int i = 0; i < n; ++i) { int m,val; cin >> m; vector<int> v1,v2; for (int j = 0; j < m; ++j) { cin >> val; v1.push_back(val); } cin >> m; for (int j = 0; j < m; ++j) { cin >> val; v2.push_back(val); } sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); int first = true; for (int p= 0, q = 0;p <v1.size() && q < v2.size();) { if (v1[p] < v2[q]) ++p; else if (v1[p] > v2[q]) ++q; else { if (!first) cout << " "; cout << v1[p]; first = false; ++p; ++q; } } if (first) cout << "empty"; cout << endl; } }
D题:
解题思路:说是一道求期望的问题,其实是一道求总分的题目,因为不管怎么样的旋转,一个方块相对于另外一个方块的旋转情况只有4钟,然后得到了这四种旋转的坐标关系,我们就可以了得到总的分数了,然后结果除以4就是最终的答案了。
代码:
# include<cstdio> # include<iostream> # include<cstring> using namespace std; # define MAX 9 char grid1[MAX][MAX]; char grid2[MAX][MAX]; int S ( char x,char y ) { int result = 0; if ( x==y ) { switch( x ) { case '.': result = 1; break; case '*': result = 2; break; case '#': result = 3; break; default: result = 0; break; } } return result; } int main(void) { for ( int i = 0;i < 8;i++ ) { scanf("%s",grid1[i]); } for ( int i = 0;i < 8;i++ ) { scanf("%s",grid2[i]); } int score = 0; for ( int i = 0;i < 8;i++ ) { for ( int j = 0;j < 8;j++ ) { score += S( grid1[i][j],grid2[j][7-i] ); score += S( grid1[i][j],grid2[7-i][7-j] ); score += S( grid1[i][j],grid2[7-j][i] ); score += S( grid1[i][j],grid2[i][j] ); } } printf("%.2lf\n",1.0*score/4); }
E题:
信息战(一)——加密程序
64-bit integer IO format: %lld
Java class name: Main
PRO
BLE
MAB
这样,Oo就得到了一个矩阵,将他按列输出就得到了Oo所要的的密文“PBMRLAOEB”。由于A国编程人员奇缺。所以Oo向你求助,希望你能够帮助他写一个加密程序,从而使得对于任意给定的X、Y以及明文,程序都能输出正确的密文。
Input
第二行至末尾每行均为一个明文(保证明文中字母的个数N <= X*Y)。
Output
Sample Input
3 3 Problem t e s t l I 156-*/- S t u 45/-90 N I v \908() 8768 *er #!@$& S a L
Sample Output
PBMRLAOEB TTCEADSBE LTCIADSBE UVSNEAIRL
思路:有关字符串和数组的简单的处理问题,但是这道题中,让我学到了很多知识,也为以后打div2垫下了基础,就是用一个cnt变量,来控制放入的字符,当我们把一个一维的字符串放入一个二维的字符数组中时,我们所需要做的其实就是记录每一步的变化,用 cnt/y 来控制横向坐标,用cnt%y来控制纵向坐标,再加一个while(cnt<x*y),来处理后续的一些工作了。。
当然在关于小写字母转换成为大写字母的过程中,我也明确了用 s[i]-' a' + 'A' 来表示。。。还有就是在末尾添加字符的过程中,要用到 alpa+'A' ,alpa = ( alpa+1)%26.
代码:
# include<cstdio> # include<iostream> # include<cstring> # include<algorithm> # include<cmath> # include<string> # include<vector> # include<queue> # include<set> # include<map> using namespace std; # define inf 0x3f3f3f3f # define eps 1e-7 # define MAX 233 char s[MAX*MAX]; char grid[MAX][MAX]; int main(void) { int x,y;cin>>x>>y; gets(s); while ( gets(s) ) { int len = strlen(s); int cnt = 0; for ( int i = 0;i < len;i++ ) { if ( s[i] <= 'z'&& s[i] >= 'a' ) { grid[cnt/y][cnt%y] = s[i]-'a'+'A'; cnt++; } else if ( s[i] <= 'Z'&&s[i] >= 'A' ) { grid[cnt/y][cnt%y] = s[i]; cnt++; } } int alp = 0; while ( cnt < x*y ) { grid[cnt/y][cnt%y] = alp+'A'; cnt++; alp = (1+alp)%26; } for ( int i = 0;i < y;i++ ) { for ( int j = 0;j < x;j++ ) { cout<<grid[j][i]; } } cout<<endl; } return 0; }
F题:
G题:
H题:
I题:
J题: