又AK了之前的一場... 接下來的工作是... 準備模板... 離長春還有不到一周了...
A 簡單模擬，略
A
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 void fix(int &c){
5 if(c > 3) c = 7 - c;
6 }
7 bool chk(int a,int b,int c) {
8 if(a > b) swap(a,b);
9 if(b > c) swap(b,c);
10 if(a > b) swap(a,b);
11 return a==1&&b==2&&c==3;
12 }
13 int main(){
14 int n;
15 cin >> n;
16 int c ;
17 cin >> c;
18 fix(c);
19 bool flag = 1;
20 for(int i =1 ; i <= n; i++) {
21 int a,b;
22 cin >> a >> b;
23 fix(a); fix(b);
24 if(!chk(a,b,c)){flag = 0;break;}
25 }
26 puts(flag?"YES":"NO");
27 }
28 B 貪心
B
1 #include<iostream>
2 using namespace std;
3 long long fib[1000];
4 int main(){
5 int s,k,p;
6 cin >> s >> k;
7 fib[0] = 0, fib[1] = 1;
8 for(int i = 2;; i++) {
9 long long &v = fib[i];
10 for(int j = i-1; j >= 0 && j >= i -k; j-- )
11 v += fib[j];
12 if(v > (int)1e9){
13 p = i;
14 break;
15 }
16 }
17 int __ans[100],len = 0;
18 for(int i = p; i>=0; i--) {
19 if(fib[i] <= s){
20 __ans[len++] = (int)fib[i];
21 s -= fib[i];
22 }
23 }
24 cout<< len << endl;
25 for(int i = 0; i < len; i++)
26 cout<< __ans[i] <<" "; cout<<endl;
27 }
28 C DP
C
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 const int N = 1005;
5 char ch[N][N];
6 int flag[N][2],sum[N][2];
7 int dp[N][2];
8 inline void chkmin(int &a,int b){if(a>b)a=b;}
9 int main(){
10 int n,m,x,y;
11 cin >> n >> m >> x >> y;
12 for(int i = 0; i < n; i++)
13 scanf("%s",ch[i]);
14 for(int j = 0; j < m; j++)
15 for(int i = 0; i < n; i++) {
16 int p = ch[i][j]=='.';
17 flag[j+1][p] ++;
18 }
19 for(int i = 1; i <= m; i++){
20 sum[i][0] = sum[i-1][0] + flag[i][1];
21 sum[i][1] = sum[i-1][1] + flag[i][0];
22 }
23 const int inf = ~0u>>2;
24 for(int i = 1; i <= m; i++) {
25 int &p = dp[i][0], &q = dp[i][1];
26 p = q = inf;
27 for(int j = max(i-y,0);j <=i-x;j++) {
28 chkmin(p,dp[j][1]+sum[i][0]-sum[j][0]);
29 chkmin(q,dp[j][0]+sum[i][1]-sum[j][1]);
30 }
31 }
32 printf("%d\n",min(dp[m][1],dp[m][0]));
33 }
34 D 廣搜
D
1 #include<iostream>
2 #include<cstring>
3 #include<queue>
4 using namespace std;
5 char ch[16][16];
6 char tmp[16][16];
7 int dp[15][15][1<<16];
8 int n,m,len;
9 struct node{int x,y,mask;node(int _x,int _y,int _m):x(_x),y(_y),mask(_m){}};
10 const int inf = 10000000;
11 queue<node> Q;
12 void OP(char ch[][16]){
13 for(int i = 0;i < n; i++)
14 cout << ch[i]<<endl;
15 }
16 inline bool fit(char c) {
17 return c =='@' || c == '.' || c == '0'+len;
18 }
19 void OP(int mask){
20 for(int i = 1; i < len; i++,mask>>=2) cout<< (mask & 3);cout<<endl;
21 }
22 inline bool chkmin(int &a,int b){if(a>b){a=b;return 1;}return 0;}
23 inline bool chkmax(int &a,int b){if(a<b){a=b;return 1;}return 0;}
24 inline void rehash(const node& u){
25 int x = u.x, y = u.y,mask = u.mask;
26 memcpy(tmp,ch,sizeof(ch));
27 //OP(mask);
28 tmp[x][y]='1';
29 for(int i = 2; i <= len; i++, mask >>= 2) {
30 int p = mask & 3;
31 int nx = x + (p==0) - (p==1);
32 int ny = y + (p==2) - (p==3);
33 tmp[nx][ny]='0'+i;
34 x = nx, y = ny;
35 }
36 }
37 int bfs(int sx,int sy,int mask){
38 // cout<<"len: "<<(len-1)*2<<endl;
39 for(int i = 0; i < 15; i++)
40 for(int j = 0; j < 15; j++)
41 for(int k = 0;k<(1<<(len-1)*2);k++)
42 dp[i][j][k] =inf;
43 dp[sx][sy][mask] = 0;
44 Q.push(node(sx,sy,mask));
45 while(!Q.empty()) {
46 node &u = Q.front();
47 rehash(u);
48 int v= dp[u.x][u.y][u.mask];
49 //cout<<"u: "<<u.x<<" "<<u.y<<" "<<v<<endl;
50 //OP(tmp);
51 for(int i = 0; i < 4; i++){
52 int x = u.x + (i==0) - (i==1);
53 int y = u.y + (i==2) - (i==3);
54 int mask = u.mask << 2 | (i^1);
55 mask &= (1<<(len-1)*2)-1;
56 // cout<<"v: "<<x<<" "<<y<<" ";OP(mask);
57 //cout<<dp[x][y][mask]<<endl;
58 if(x >=0 && x < n && y >= 0 && y < m &&fit(tmp[x][y]) && chkmin(dp[x][y][mask],v+1)) {
59 // cout<<"v: "<<x<<" "<<y<<endl;
60 if(tmp[x][y]=='@') return v+1;
61 Q.push(node(x,y,mask));
62 }
63 }
64 Q.pop();
65 }
66 return -1;
67 }
68 int main(){
69 cin >> n >> m;
70 for(int i =0; i < n; i++)
71 cin >> ch[i];
72 int sx,sy;len=0;
73 for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
74 if(ch[i][j]>='0'&&ch[i][j]<='9' && chkmax(len,ch[i][j]-'0')){
75 sx = i,sy = j;
76 }
77 }
78 // cout <<sx<<" "<<sy <<" "<<len<<endl;
79 int mask = 0;
80 for(int i = 2; i <= len;i++) {
81 for(int j = 0;j<4;j++){
82 int x = sx +(j==0)-(j==1);
83 int y = sy +(j==2)-(j==3);
84 if(x >=0 && x < n && y >=0 && y < m && ch[x][y] == ch[sx][sy]-1) {
85 mask <<=2;
86 mask |= j^1;
87 sx = x, sy = y; break;
88 }
89 }
90 }
91 //cout<<sx<<" "<<sy<<endl;
92 for(int i =0 ; i < n; i++)
93 for(int j= 0; j < m; j++) if(ch[i][j]>='1' && ch[i][j]<='9') ch[i][j]='.';
94 // cout<<".."<<endl;
95 cout << bfs(sx,sy,mask) << endl;
96 }
97 E 梅森素數
E
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 const int mod = (int)1e9+7;
5 int pow(int n){
6 long long a = 1, t = 2;
7 while(n){
8 if(n&1) a = (a*t) % mod;
9 t = (t*t) % mod; n >>= 1;
10 }
11 return a;
12 }
13 int main(){
14 int prime[100]={ 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583};
15
16 //for(int i = 1; i <= 40; i++) cout<<prime[i]<<endl;
17 int n; cin >> n; cout<< (pow(prime[n-1]-1) + mod-1) % mod<< endl;
18 }
19 posted on 2012-10-08 15:00
西月弦 閱讀(247)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告