做的不是太好,而且现在对DFS越来越没信心了,不敢用,错过了一题。。
现在先给出前四题。
A:Flipping Game
简单的暴搞,开数组记录0和1的数量就行了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> using namespace std; int a[105]; int main() { int n,i,j,sum=0,s,k,mmax=0; scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%d",&a[i]); sum+=a[i]; } for(i=1; i<=n; i++) { for(j=i; j<=n; j++) { s = sum; for(k=i; k<=j; k++) { s -= a[k]; s += (1-a[k]); if(s>mmax) mmax = s; } } } printf("%d\n",mmax); return 0; }
单纯的筛选素数,Special Judge的题都能偷偷水^_^
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> using namespace std; bool s[1500005]; void get() { memset(s,0,sizeof(s)); s[0] = s[1] = 1; for(int i = 2;i<1500000;i++) { if(s[i] == 0) { for(int j=i*2;j<1500000;j+=i) s[j] = 1; } } } int main() { get(); int n; scanf("%d",&n); int j = 3; printf("2"); for(int i=1;i<n;i++) { while(s[j] == 1) j++; printf(" %d",j); j++; } printf("\n"); return 0; }
去除数字使这个数变成五的倍数,题意不难,难在数据量上,所以需要用快速幂去摸来解决
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #define M 1000000007 using namespace std; char s[100004]; int k; long long f(long long a,long long b,long long &x,long long &y) { long long ans,t; if(b==0) { x=1,y=0; return a; } ans=f(b,a%b,x,y); t=x,x=y,y=t-(a/b)*y; return ans; } long long p(long long base,long long n) { long long r=1; while(n) { if(n&1) r=(r*base)%M; base = (base*base)%M; n>>=1; } return r; } int main() { while(scanf("%s %d",s,&k)!=EOF) { long long a1=0; int len=strlen(s); for(int i=0; i<len; i++) { if(s[i]=='0'||s[i]=='5') { a1=(a1+p(2,i))%M; } } long long q = p(2,len); long long q1 = (q+M-1)%M; long long X,Y; f(q1,M,X,Y); X = (X+M)%M; long long qn_x = (p(q,k)-1)*X%M; long long ans = (a1*qn_x)%M; cout<<ans<<endl; } return 0; }
又是一道Special Judge,一如既往的偷偷水一下^_^
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> using namespace std; int n,m,l,shu; int x[1000000]; int y[1000000]; char z[1000000]; char c; char s[505][505]; bool used[505][505]; int dx[5] = {1,0,-1,0}; int dy[5] = {0,-1,0,1}; void dfs(int xx,int yy) { l++; used[xx][yy] = 1; for(int i=0;i<4;i++) { if(s[xx+dx[i]][yy+dy[i]] == '.'&&used[xx+dx[i]][yy+dy[i]] == 0) { dfs(xx+dx[i],yy+dy[i]); } } if(l != 1) { x[shu] = xx; y[shu] = yy; z[shu] = 'D'; shu++; x[shu] = xx; y[shu] = yy; z[shu] = 'R'; shu++; s[xx][yy] = 'R'; } l--; } int main() { scanf("%d%d",&n,&m); memset(s,0,sizeof(s)); memset(used,0,sizeof(used)); for(int i=1;i<=n;i++) { c = getchar(); for(int j=1;j<=m;j++) { s[i][j] = getchar(); } } shu = 0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i][j] == '.') { x[shu] = i; y[shu] = j; z[shu] = 'B'; shu++; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(s[i][j] == '.') { l = 0; dfs(i,j); } } } printf("%d\n",shu); for(int i=0;i<shu;i++) { printf("%c %d %d\n",z[i],x[i],y[i]); } return 0; }