CF 191 总结
分类:
IT文章
•
2025-01-28 08:25:25
A. Flipping Game
链接：http://codeforces.com/contest/327/problem/A
题意：从 i 到 j 翻转一次使得 1 的 个数最多~
直接暴力搞~
![]()
1 #include <cstdio>
2 #include <cmath>
3 #include <iostream>
4 using namespace std;
5 int N;
6 int a[105], b[105];
7 int main( )
8 {
9 while(scanf("%d", &N)!= EOF){
10 for(int i=0; i<N; ++ i){
11 scanf("%d", &a[i]);
12 b[i]=a[i];
13 }
14 int ans=-1;
15 for( int i=0; i<N; ++ i ){
16 for( int j=i; j<N; ++ j ){
17 for( int k=i; k<=j ; ++ k){
18 b[k]=1-a[k];
19 }
20 int t=0;
21 for( int k=0; k<N; ++ k ){
22 if(b[k]) t++;
23 ans=ans>t?ans:t;
24 b[k]=a[k];
25 }
26 }
27 }
28 printf("%d
", ans);
29 }
30 return 0;
31 }
View Code
B. Hungry Sequence
链接：http://codeforces.com/contest/327/problem/B
题意：生成一个排列， 如果 i < j 那么 p[i]<p[j] 且 p[j]%p[i] != 0 ~
数据范围：n < =10^5 ~ 直接生成10^5个素数即可~
![]()
1 #include <cstdio>
2 #include <cmath>
3 #include <iostream>
4 using namespace std;
5 int a[2000000], p[200000];
6 void getp( )
7 {
8 for( int i=3; i<=10000; i+=2 ){
9 if( !a[i] ){
10 for( int j=i*i; j<2000000; j+=i ){
11 a[j]=1;
12 }
13 }
14 }
15 p[0]=2;
16 int k=1;
17 for(int i=3; i<2000000; i+=2){
18 if( !a[i] )p[k++]=i;
19 }
20 }
21 int main( )
22 {
23 getp( );
24 int N;
25 while( scanf("%d", &N)!= EOF ){
26 for ( int i=0; i<N; ++ i ){
27 printf(i!=N-1?"%d ":"%d
", p[i]);
28 }
29 }
30 return 0;
31 }
View Code
C. Magic Five
链接：http://codeforces.com/contest/327/problem/C
题意：给定字符串 s 和 整数 k 表示有 k 个 s 重复组成的字符串 S‘ 要从中截取一些，使得剩下的字符串能表示的整数能整除5~
思路： 等比数列求和；
例如求sum=2^1+2^2+2^3+2^4+2^5+2^6+2^7 .. + 2^n~
公式就为 若n%2==0 T(n)=T(n/2)+T(n/2)*2^(n/2);
若n%2==1 T(n)=T(n/2)+T(n/2)*2^(n/2)+ 2^n;
![]()
1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 #include <cmath>
5 using namespace std;
6 typedef __int64 LL;
7 const LL Mod=1e9+7;
8 char s[100000];
9 LL m, k, ans, x;
10 LL P_M(int x, int n )
11 {
12 LL rec=1, t=x;
13 while( n ){
14 if(n&1){
15 rec*=t;
16 rec%=Mod;
17 }
18 t*=t;
19 t%=Mod;
20 n>>=1;
21 }
22 return rec;
23 }
24 LL Sum( int x, int n )
25 {
26 if( n==1 )
27 return x;
28 LL t=Sum( x, n/2 );
29 t=( t+t*P_M(m, n/2))%Mod;// m为公比；
30 if( n&1 ) t=(t+P_M( m, n-1)*x)%Mod;// 加上an
31 return t;
32 }
33
34 int main( )
35 {
36 while( scanf("%s%I64d", s, &k)!= EOF ){
37 int l=strlen ( s );
38 m=P_M(2, l), x=1;
39 for( int i=0; i<l; ++ i ){
40 if( s[i]=='5' || s[i]=='0' ){
41 ans=(ans+x)%Mod;
42 }
43 x=(x*2)%Mod;
44 }
45 ans=Sum( ans, k );
46 printf("%I64d
", ans);
47 }
48 return 0;
49 }
View Code
![]()
1 #include <cstdio>
2 #include <cmath>
3 #include <iostream>
4 #include <cstring>
5 #include <stack>
6 using namespace std;
7 #define lega(x, a) ((x)<=(a) && 0 <(x))
8 char s[505][505];
9 bool vi[505][505];
10 int N, M, ans;
11 struct Node
12 {
13 int x, y;
14 bool f;
15 Node( ){}
16 Node(int _x, int _y, bool _f){
17 x=_x, y=_y, f=_f;
18 }
19 }p;
20 stack<Node>sn;
21 const int xx[4]={0,0,1,-1};
22 const int yy[4]={1,-1,0,0};
23 void DFS( int x, int y )
24 {
25 int _x,_y;
26 for( int i=0; i<4; ++ i ){
27 _x=x+xx[i], _y=y+yy[i];
28 if( lega(_x,N) && lega(_y, M) && !vi[_x][_y] ){
29 vi[_x][_y]=1;
30 sn.push(Node( _x,_y, false ));
31 DFS( _x, _y );
32 }
33 }
34 }
35
36 int main( )
37 {
38 while( scanf("%d%d", &N, &M)!= EOF ){
39 for( int i=1;i<=N; ++ i ){
40 scanf("%s", s[i]+1);
41 }
42 while(!sn.empty()){
43 sn.pop( );
44 }
45 memset(vi, 0, sizeof vi);
46 ans=0;
47 for( int i=1; i<=N; ++ i ){
48 for( int j=1; j<=M; ++ j ){
49 if( !vi[i][j]&&s[i][j]=='.' ){
50 vi[i][j]=1;
51 sn.push(Node(i, j, true));
52 ans-=2; // 最后一个不能被拆， 减少两次操作
53 DFS(i, j); }
54 }
55 }
56 ans+=3*sn.size( );
57 printf("%d
", ans);
58 for( int i=1; i<=N; ++ i ){
59 for(int j=1; j<=M; ++ j){
60 if( vi[i][j] ){
61 printf("B %d %d
", i, j);
62 }
63 }
64 }
65 while( !sn.empty( ) ){
66 p=sn.top( );
67 sn.pop( );
68 if( !p.f ){// 只要求建红色的时候边上有蓝色的， 并不是要求最后的状态是红色边上有蓝色
69 printf("D %d %d
", p.x, p.y);
70 printf("R %d %d
", p.x, p.y);
71 }
72 }
73 }
74 return 0;
75 }
