记录一下和队友VP的这场湖北省赛，有空会加上赛后自己的复盘分析和补题情况。
C.Darkness I
#include<bits/stdc++.h> using namespace std; #define rg register #define maxn 105050 #define int long long inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-48; c=getchar(); } return x*f; } int n,m; signed main() { n=read(); m=read(); cout<<min(n,m)+ceil((max(n,m)-min(n,m))/2.0); }
F. Inverse Manacher
#include<bits/stdc++.h> using namespace std; #define rg register #define maxn 2850500 #define mod 998244353 #define int long long inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-48; c=getchar(); } return x*f; } int n; int a[maxn]; char ans[maxn]; int max_r; signed main() { n=read(); for(rg int i=0;i<2*n+2;++i) a[i]=read(); ans[2]='a'; max_r=2; for(rg int i=3;i<2*n+2;++i) { if(i%2==0) { for(rg int j=max_r+2;j<=i-1+a[i];j+=2) { ans[j]=ans[2*i-j]; max_r=j; } // cout<<"i="<<i<<" maxr="<<max_r<<" rr="<<i-1+a[i]<<endl; if(2*i-max_r-2>0&&max_r+2<=i+1+a[i]) { max_r+=2; ans[max_r]=((ans[2*i-max_r]=='a')?'b':'a'); } } else { for(rg int j=max_r+2;j<=i-1+a[i];j+=2) { ans[j]=ans[2*i-j]; max_r=j; } // cout<<"i="<<i<<" maxr="<<max_r<<" rr="<<i-1+a[i]<<endl; if(2*i-max_r-2>0&&max_r+2<=i+1+a[i]) { max_r+=2; ans[max_r]=((ans[2*i-max_r]=='a')?'b':'a'); } } } for(rg int i=2;i<2*n+2;i+=2) { cout<<ans[i]; } }
H. Binary Craziness
#include<bits/stdc++.h> using namespace std; #define rg register #define maxn 1850500 #define mod 998244353 #define int long long inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-48; c=getchar(); } return x*f; } int n,m; int dg[maxn]; int num[maxn],temp[maxn]; bool flag[maxn]; struct node { int val,tot; }; stack<node> q; inline int f(int a,int b) { return (a&b)*(a|b)*(a^b)%mod; } int ans; signed main() { n=read(); m=read(); for(rg int i=1;i<=m;++i) { int a,b; a=read(); b=read(); dg[a]++; dg[b]++; } for(rg int i=1;i<=n;++i) num[dg[i]]++; for(rg int i=1;i<=n;++i) { if(flag[dg[i]]==0) { flag[dg[i]]=1; node a; a.val=dg[i]; a.tot=num[dg[i]]; q.push(a); temp[q.size()]=a.val; } } int cnt=q.size(); for(rg int i=1;i<=cnt;++i) { int val=temp[i]; int tot=(num[val]+1)*num[val]/2; ans+=f(val,val)*tot; ans%=mod; for(rg int j=i+1;j<=cnt;++j) { ans+=((num[temp[i]]*num[temp[j]])*f(val,temp[j])); ans%=mod; } } cout<<ans; }
J. Expansion
#include<bits/stdc++.h> using namespace std; #define rg register #define maxn 550500 #define mod 998244353 #define int long long inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-48; c=getchar(); } return x*f; } int n; int a[maxn]; int t; int s[maxn],max_top; inline int find(int now) { for(rg int i=now+1;i<=n;++i) { if(s[i]>=max_top&&s[i+1]<s[i]) return i; } return n; } inline int get(int l,int r) { int minn=99999999999; int sum=0; for(rg int i=l+1;i<=r;++i) { sum+=s[i]; minn=min(minn,sum); max_top=max(max_top,s[i]); } return minn; } int sum,st; signed main() { n=read(); for(rg int i=1;i<=n;++i) a[i]=read(),s[i]=s[i-1]+a[i]; for(rg int i=1;i<=n;++i) { sum+=s[i]; if(s[i+1]<=s[i]&&s[i]>0) { st=i; max_top=s[i]; break; } if(s[i]<0) { cout<<-1; return 0; } } if(s[n]<0) { cout<<-1; return 0; } for(rg int i=st;i<n;++i) { int nxt=find(i); int nd=get(i,nxt); // cout<<"i="<<i<<" sum="<<sum<<" nxt="<<nxt<<" nd="<<nd<<endl; if(sum>=abs(nd)) { for(rg int j=i+1;j<=nxt;++j) sum+=s[j]; i=nxt-1; continue; } else { // cout<<"i="<<i<<" sum="<<sum<<" nd="<<nd<<" nxt="<<nxt<<" s[i]="<<s[i]<<" t+="<<ceil((double)(1.0*(abs(sum+nd)))/(double)(1.0*s[i]))<<" t="<<t<<endl; t+=ceil((double)(1.0*(abs(sum+nd)))/(double)(1.0*s[i])); sum=ceil((double)(1.0*(abs(sum+nd)))/(double)(1.0*s[i]))*s[i]+sum; for(rg int j=i+1;j<=nxt;++j) sum+=s[j]; i=nxt-1; } } // cout<<"t="<<t<<endl; cout<<t+n; }
K. Dice Game
#include<bits/stdc++.h> using namespace std; #define rg register #define maxn 105050 #define int long long #define mod 998244353 inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-48; c=getchar(); } return x*f; } inline long long qp(long long a,long long b) { long long ans=1; while(b>0) { if(b&1) ans=(ans*a)%mod; a=(long long)(a*a)%mod; b>>=1; } return ans%mod; } int n,m; //p/q p*q^(998244351) mod 998244353 signed main() { n=read(); m=read(); // cout<<qp(64,998244351)*27%mod; for(rg int i=1;i<=m;++i)//[1,m]---x [1,x-1] [x+1,m] (x-1)/m的概率赢 (m-x)/m的概率输 { cout<<qp((int)qp(m-1,n),998244351)*(int)qp(m-i,n)%mod<<" "; } }
M. Different Billing
#include<bits/stdc++.h> using namespace std; #define rg register #define maxn 105050 #define int long long inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-48; c=getchar(); } return x*f; } int x,y; //1000 2500 signed main() { x=read(); y=read(); for(rg int i=0;i<=x;++i) { long long sumb=i*1000; if((y-sumb)==0) { cout<<x-i<<" "<<i<<" "<<0; return 0; } else if((y-sumb)>0&&(y-sumb)%2500==0) { cout<<max((int)0,x-i-(y-sumb)/2500)<<" "<<i<<" "<<(y-sumb)/2500; return 0; } } cout<<-1; return 0; }
- Programming Collegiate Provincial Contest Hubeiprogramming collegiate provincial contest programming collegiate provincial shandong programming provincial collegiate sichuan programming collegiate provincial guangdong programming provincial collegiate shandong programming provincial collegiate sponsored programming collegiate provincial counting 2023 programming collegiate provincial 题解programming collegiate provincial programming collegiate jiangsu contest