A
n 然后n个数字
要求组合成的段数最大
低高 低高 ...
(a *b -a) *(s/(ab))
#include<stdio.h> #include<string.h> #include<algorithm> #include<deque> #include<set> #include<map> using namespace std; #define ll __int64 #define MAXN 1000010 ll inf=1e9+7; ll z[MAXN]; ll qian[MAXN],hou[MAXN]; ll x[MAXN]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%I64d",&x[i]); sort(x+1,x+n+1); int l,r; l=1; r=n; qian[1]=1; for(int i=2;i<=n+1;i++) { if(i%2==0) z[i]=x[l++]; else z[i]=x[r--]; } hou[n+2]=1; for(int i=n+1;i>=2;i--) hou[i]=(hou[i+1]*z[i])%inf; for(int i=2;i<=n+1;i++) qian[i]=(qian[i-1]*z[i])%inf; ll ji=1; for(int i=2;i<=n+1;i++) ji=(ji*z[i])%inf; ll ans=ji; //printf("%d ",z[3]); for(int i=3;i<=n;i++) { ans=(((ans+ji)%inf-((min(z[i-1],z[i])*qian[i-2])%inf*hou[i+1])%inf)%inf+inf)%inf; } if(n>=2) ans=(((ans+ji)%inf-(min(z[n+1],z[n])*qian[n-1])%inf)%inf+inf)%inf; printf("%I64d ",ans); } return 0; }
H
把U变成I 反过来思考
#include <stdio.h> #include <math.h> #include <algorithm> #include<iterator> #include<map> #include<string.h> typedef long long ll; using namespace std; #define MAXN 1000010 char s[MAXN]; int to[28]; bool vis[MAXN]; int main() { int t; scanf("%d",&t); to[0]=1; memset(vis,0,sizeof(vis)); vis[1]=1; for(int i=1;i<=27;i++) { to[i]=to[i-1]*2; if(to[i]>MAXN) break; vis[to[i]]=1; for(int j=to[i]-6;j>=0;j-=6) { if(vis[j]==1) break; vis[j]=1; } } // printf("%d ",vis[10]); while(t--) { scanf("%s",s); int len=strlen(s); int ok=0; if(s[0]!='M') ok=1; int cnt=0; for(int i=1;i<len;i++) { if(s[i]=='U') cnt=cnt+3; else if(s[i]=='I') cnt++; else ok=1; } if(vis[cnt]==0) ok=1; if(ok==1) printf("No "); else printf("Yes "); } return 0; }
K
深搜
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; #define MAXN 2010 int z[MAXN],s[MAXN],s1[MAXN],s2[MAXN]; int ans[MAXN]; int s3[MAXN]; int ok,n; void dfs(int a,int b,int ind) { if(ind>n||a>n/2||b>n/2) return ; if(a==b&&a==n/2) { int ind1,ind2; for(int i=1;i<=n;i++) { if(ans[i]==0) { ind1=i; break; } } for(int i=1;i<=n;i++) { if(ans[i]==1) { ind2=i; break; } } int ok1=0,i,j; i=ind1; j=ind2; while(i<=n&&j<=n) { if(z[i]!=z[j]) { ok1=1; break; } i++; j++; while(ans[i]!=0) i++; while(ans[j]!=1) j++; } if(ok1==0) { ok=1; } return ; } if(ok==1) return ; if(s1[z[ind+1]]+1<=s[z[ind+1]]/2) { ans[ind+1]=0; s1[z[ind+1]]++; s3[a]=z[ind+1]; dfs(a+1,b,ind+1); s1[z[ind+1]]--; } if(ok==1) return ; if(s2[z[ind+1]]+1<=s[z[ind+1]]/2) { if(s3[b]==z[ind+1]) { ans[ind+1]=1; s2[z[ind+1]]++; dfs(a,b+1,ind+1); s2[z[ind+1]]--; } } if(ok==1) return; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(s,0,sizeof(s)); memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); for(int i=1;i<=n;i++) { scanf("%d",&z[i]); s[z[i]]++; } ok=0; dfs(0,0,0); // printf("%d ",ok); for(int i=1;i<=n;i++) printf("%d",ans[i]); printf(" "); } return 0; }
J
t组样例
n
然后n个平面 n个平面上的点
A B 可以在2个点上连线 每个点只能用一次 而且线不能交叉
sg
0 1 2 3 4
0 0 1 1
四个点可以到达的状态 (2) 或者 (1) ^ (1) 然后打表找规律
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; #define MAXN 2010 int sg[301]={0,0,1,1}; bool vis[310]; int main() { for(int i=4;i<=300;i++) { memset(vis,0,sizeof(vis)); for(int j=0;j<i-1;j++) { vis[sg[j]^sg[i-2-j]]=1; } for(int j=0;j<=300;j++) { if(vis[j]==0) { sg[i]=j; break; } } } int t; scanf("%d",&t); while(t--) { int n; int ans=0; scanf("%d",&n); for(int i=1;i<=n;i++) { int a; scanf("%d",&a); if(a<=52) ans=ans^sg[a]; else { a=(a-53)%34+53; ans=ans^sg[a]; } } if(ans==0) printf("Dave "); else printf("Carol "); } return 0; }