省选时间定了,慌是不可能的,这辈子是不可能的
\(T1\)
//直接看这一位选什么就好了 #define Eternal_Battle ZXK #include<bits/stdc++.h> #define int long long #define MAXN 1000005 using namespace std; int cnt[35][2]; int n,a[MAXN]; void sol() { int res=0; for(int i=30;i>=0;i--) { if(cnt[i][1]&&cnt[i][0]) { puts("-1"); return ; } if(cnt[i][1]) { res|=(1ll<<i); } } printf("%lld\n",res); } int q,x,y; signed main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(int i=1;i<n;i++) { for(int j=30;j>=0;j--) { if(((a[i]^a[i+1])>>j)&1) { cnt[j][a[i]>a[i+1]]++; break; } } } sol(); scanf("%lld",&q); while(q--) { scanf("%lld%lld",&x,&y); if(x<n) { for(int j=30;j>=0;j--) { if(((a[x]^a[x+1])>>j)&1ll) { cnt[j][a[x]>a[x+1]]--; break; } } } if(x>1) { for(int j=30;j>=0;j--) { if(((a[x]^a[x-1])>>j)&1ll) { cnt[j][a[x-1]>a[x]]--; break; } } } a[x]=y; if(x<n) { for(int j=30;j>=0;j--) { if(((a[x]^a[x+1])>>j)&1ll) { cnt[j][a[x]>a[x+1]]++; break; } } } if(x>1) { for(int j=30;j>=0;j--) { if(((a[x]^a[x-1])>>j)&1ll) { cnt[j][a[x-1]>a[x]]++; break; } } } sol(); } }
\(T2\)
//比较贪心的想 //肯定是每个时刻都是使用状态 //那么要求的条件就是后缀的女生>男生 //假如目前女生i在poz<2*i-1,那么贪心的放过去就好了 //对于每一小段都单独统计最小后缀和,求个最大就好了 #include<bits/stdc++.h> #define MAXN 10000000 #define int long long using namespace std; int d[MAXN],b[MAXN],maxd[MAXN]; int pd,tans,ans; string a; signed main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { cin>>a>>b[i]; a=' '+a; for(int j=a.length()-1;j>=1;j--) { if(a[j]=='F') d[i]--; else d[i]++; maxd[i]=max(maxd[i],d[i]); } pd+=d[i]*b[i]; } tans=1; if(pd>0) { cout<<-1; return 0; } else { for(int i=m;i>=1;i--) { if(d[i]>0) tans=max(tans,ans+(b[i]-1)*d[i]+maxd[i]); else tans=max(tans,ans+maxd[i]); ans+=d[i]*b[i]; } } cout<<tans-1; return 0; }
\(T3\)棋盘游戏
\(JOI\)的\(DP\)有亿点点难啊
考虑第一行和第三行必然没有放格子的左右已经放好了,否则无解,那么每个点能不能放只与左右放没放完有关,或者上下放没放,那么直接记录两个\(dp1[i][j]\)表示\(i\)位置在\(j\)时刻放置的方案数,直接大力分讨,上下左右的所有状态枚举一遍转移,使用前缀和优化
#include<bits/stdc++.h> #define mod 1000000007 #define int long long #define MAXN 6060 using namespace std; int n,num,tot; int f[MAXN][MAXN][2],C[MAXN][MAXN],P[MAXN][MAXN],ans; char s[3][MAXN]; void Init() { for(int i=0;i<=n*3;i++) { C[i][0]=1; P[i][0]=1; for(int j=1;j<=i;j++) { C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; P[i][j]=(P[i-1][j]+P[i-1][j-1]*j)%mod; } } return; } void Pre(int x) { for(int i=1;i<=n*2;i++) { f[x][i][0]=(f[x][i][0]+f[x][i-1][0])%mod; f[x][i][1]=(f[x][i][1]+f[x][i-1][1])%mod; } return; } void check() { for(int i=1;i<=n;i++) { if(s[0][i]=='x'&&(s[0][i-1]!='o'||s[0][i+1]!='o')){puts("0");exit(0);} if(s[2][i]=='x'&&(s[2][i-1]!='o'||s[2][i+1]!='o')){puts("0");exit(0);} } return; } void solve() { for(int i=2;i<=n;i++) { int t=0; if(s[0][i]=='x')t++; if(s[2][i]=='x')t++; if(s[1][i]=='x') { if(s[1][i-1]=='o') { f[i][t+1][0]=P[t][t]; if(t==2)f[i][1][1]=P[t][t],f[i][2][1]=2; if(t==1)f[i][1][1]=P[t][t]; Pre(i); num=t+1; continue; } num+=(t+1); for(int j=1;j<=num;j++) { f[i][j][0]=((f[i][j][0]+f[i-1][num][0]*P[j-1][t])%mod+mod)%mod; f[i][j][0]=((f[i][j][0]+(f[i-1][num][1]-f[i-1][max(0ll,j-t-1)][1])*P[j-1][t])%mod+mod)%mod; for(int k=1;k<=t;k++)f[i][j+k][1]=((f[i][j+k][1]+P[t][t]*C[j+k-1][k-1]%mod*C[max(0ll,num-j-k)][t+1-k]%mod*f[i-1][j][0]%mod)%mod+mod)%mod; } Pre(i); } else { if(s[1][i-1]=='x') { ans=ans*(f[i-1][num][1]+f[i-1][num][0])%mod; tot+=num; ans=ans*C[tot][tot-num]%mod; } tot+=t; ans=ans*P[t][t]%mod*C[tot][t]%mod; } } } signed main() { scanf("%lld",&n); for(int i=0;i<=2;i++)scanf("%s",s[i]+1); Init(); check(); ans=1; if(s[1][1]=='x') { f[1][1][0]=1; num=1; Pre(1); } solve(); if(s[1][n]=='x') { ans=ans*f[n][num][0]%mod; tot+=num; ans=ans*C[tot][num]%mod; } printf("%lld\n",ans); }