题解:
https://files.cnblogs.com/files/clrs97/ZJCPC24_Tutorial.pdf
Code:
A. Bingo
#include <bits/stdc++.h> using namespace std; string n; int m; typedef long long ll; ll sum[1000005]; int pw[1000005]; bool all[1000005]; int sol[1000020]; void solv() { cin >> n >> m; int am = 0 ; for(int i = 0;i < n.size();i++) am = (10LL * am + n[i] - '0') % m; int ans = m - am; sum[n.size()] = 0; for(int i = 0;i < n.size();i++) { sum[i] = 1LL * ('9' - n[i]) * pw[n.size() - i - 1] ; } all[n.size()] = 1; for(int i = n.size() - 1;i >= 0;i--) { all[i] = all[i + 1] && (n[i] == '9') ; } for(int i = n.size() - 1;i >= 0;i--) sum[i] += sum[i + 1]; string b; int d = m; while(d) { b += ((d % 10) + '0') ; d /= 10; } reverse(b.begin() , b.end()) ; vector<int> rm(b.size() + 1) ; for(int i = b.size() - 1;i >= 0;i--) { rm[i] = (b[i] - '0') * pw[b.size() - i - 1] + rm[i + 1] ; } for(int i = 0;i < n.size() && i + b.size() - 1 < n.size();i++) { //match for(int j = 0 ; j <= b.size();j++) { /// here mat , diff on n[i + j] if(i + j >= n.size()) break ; if(j == b.size()) { if(!all[i + j]) ans = min(ans , 1) ; break; } if(b[j] > n[i + j]) { /// // printf("in %d %d : %d %d %d\n",i,j,(ll)(b[j] - n[i + j] - 1) * pw[n.size() - (i + j) - 1] , sum[i + j + 1] , 1LL * rm[j + 1] * pw[n.size() - (i+b.size())]) ; ans = min((ll)ans , 1 + (ll)(b[j] - n[i + j] - 1) * pw[n.size() - (i + j) - 1] + sum[i + j + 1] + 1LL * rm[j + 1] * pw[n.size() - (i+b.size())]); } if(j == b.size() || i + j >= n.size() || b[j] != n[i + j]) break; } } int L = (int)n.size() - 1; // printf("L %d\n",L) ; for(int i = 0;i < n.size() + 15;i++) sol[i] = 0; for(int i = 0;i < n.size();i++) sol[n.size() - i - 1] = n[i] - '0' ; sol[0] += ans ; for(int i = 0;i <= L;i++) { sol[i + 1] += sol[i] / 10; sol[i] %= 10; if(sol[i + 1]) L = max(L , i + 1) ; } for(int i = L;i >= 0;i--) cout << sol[i] ; cout << '\n'; return ; } int main() { // freopen("in.txt","r",stdin); // freopen("out2.txt","w",stdout) ; ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ; int t;cin >> t; pw[0] = 1; for(int i = 1;i <= 100000;i++) { pw[i] = min(1000000000LL , pw[i - 1] * 10LL) ; } while(t--) solv() ; }
B. Simulated Universe
#include<bits/stdc++.h> using namespace std; const int N=8e3+1e2+7; int T,n; int f[2][N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>T; while(T--) { cin>>n; for(int i=0;i<=n;i++) f[0][i]=-1e9; f[0][0]=0; int now=0,last=1; int ans=0; for(int i=1;i<=n;i++) { swap(now,last); for(int j=0;j<=i+1;j++) f[now][j]=-1e9; string ty; cin>>ty; if(ty=="B") { ans+=2; for(int j=0;j<=i;j++) { if(f[last][j]<0) continue; f[now][j+1]=max(f[now][j],f[last][j]); if(f[last][j]) f[now][j]=max(f[now][j],f[last][j]-1); } } else { int a,b; cin>>a>>b; for(int j=0;j<=i;j++) { if(f[last][j]<0) continue; f[now][max(j-a,0)]=max(f[now][max(j-a,0)],f[last][j]); f[now][j]=max(f[now][j],f[last][j]+b); } } } for(int i=0;i<=n;i++) if(f[now][i]>=0) { ans-=i; break; } cout<<ans<<"\n"; } } /* 1 3 6 1 2 3 4 5 6 6 9 9 8 12 13 10 15 17 12 18 21 */
C. Challenge NPC
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii ; vector<pii> Ed; int main() { ios::sync_with_stdio(false) ; cin.tie(0) ; int k ; cin >> k; int n = k + 2; for(int i = 1;i <= n;i++) { for(int j = 1;j < i;j++) { Ed.push_back({j*2 , i*2 - 1}); Ed.push_back({j*2 - 1 , i *2}); } } cout << n*2 << ' ' << Ed.size() <<' ' << 2 << '\n' ; for(int i = 1;i <= n*2;i++) { cout << (i&1) + 1 <<' ' ; } cout << '\n'; for(auto [x,y] : Ed) cout << x <<' ' << y << '\n'; return 0; }
D. Puzzle: Easy as Scrabble
#include<bits/stdc++.h> using namespace std; using ll=long long; const int N=300005,P=998244353; #define NO {puts("NO"); exit(0);} int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; auto solve(){ int n,m; cin>>n>>m; vector<string> a(n+2); for(auto &s:a) cin>>s; vector f(n+2,vector<array<char,4>>(m+1)); vector inq(n+2,vector<bool>(m+2)); for(int i=1;i<=n;i++){ if(a[i][0]!='.') f[i][1][0]=a[i][0]; if(a[i][m+1]!='.') f[i][m][1]=a[i][m+1]; } for(int j=1;j<=m;j++){ if(a[0][j]!='.') f[1][j][2]=a[0][j]; if(a[n+1][j]!='.') f[n][j][3]=a[n+1][j]; } auto check=[&](int x,int y){ static int vis[256]; static int time; int num=0; ++time; for(auto c:f[x][y]){ if(!isalpha(c)) continue; if(a[x][y]!='x') a[x][y]=c; if(vis[c]!=time){ vis[c]=time; num++; } } if(num>1) return true; return num==1&&a[x][y]=='x'; }; queue<pair<int,int>> qu; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(check(i,j)){ qu.push({i,j}); inq[i][j]=true; } } } while(qu.size()){ auto [x,y]=qu.front(); qu.pop(); inq[x][y]=false; a[x][y]='x'; for(int i=0;i<4;i++){ if(!isalpha(f[x][y][i])) continue; int nx=x+dx[i],ny=y+dy[i]; if(nx<=0||ny<=0||nx>n||ny>m) NO; f[nx][ny][i]=f[x][y][i]; if(a[nx][ny]!='x') a[nx][ny]=f[x][y][i]; if(!inq[nx][ny]&&check(nx,ny)){ inq[nx][ny]=true; qu.push({nx,ny}); } } f[x][y]={0,0,0,0}; } puts("YES"); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='x') a[i][j]='.'; putchar(a[i][j]); } puts(""); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int t=1; // cin>>t; while(t--){ solve(); // cout<<solve()<<'\n'; // cout<<(solve()?"Yes":"No")<<'\n'; } return 0; } /* Generated by powerful Codeforces Tool(cf tool) * Author: sleep__ * Time: 2024-04-04 14:25:05 **/
E. Team Arrangement
#include<cstdio> #include<algorithm> using namespace std; typedef unsigned long long ull; const int N=65,inf=~0U>>1; int n,i,w[N],num[N],ans;ull in[N],out[N]; struct E{int l,r;}e[N]; inline bool cmp(const E&a,const E&b){return a.r<b.r;} inline void solve(int m){ int sum=0; ull S=0; for(int i=1;i<=m;i++){ S^=in[i]; int now=num[i]; sum+=now*w[i]; now*=i; while(now--){ if(!S)return; S-=S&-S; } S^=S&out[i]; } if(sum>ans)ans=sum; } void dfs(int x,int m){ if(x>m)return; num[x]=0; dfs(x+1,m); for(int i=1;;i++){ m-=x; num[x]=i; if(!m)solve(x); if(m<=0)break; dfs(x+1,m); } } int main(){ scanf("%d",&n); for(i=0;i<n;i++)scanf("%d%d",&e[i].l,&e[i].r); sort(e,e+n,cmp); for(i=0;i<n;i++){ in[e[i].l]^=1ULL<<i; out[e[i].r]^=1ULL<<i; } for(i=1;i<=n;i++)scanf("%d",&w[i]); ans=-inf; dfs(1,n); if(ans==-inf)puts("impossible");else printf("%d",ans); }
F. Stage: Agausscrab
#include<bits/stdc++.h> using namespace std; const int N=1e3+1e2+7; int n; string s[N]; int a[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>s[i]>>a[i]; string ans; for(int i=1;i<=n;i++) { int r=0; for(int j=1;j<=n;j++) if(a[j]>a[i]) r++; r+=1; for(int j=1;j<=r;j++) if(s[i].size()) s[i].pop_back(); ans+=s[i]; } ans[0]=ans[0]-'a'+'A'; cout<<"Stage: "<<ans<<"\n"; }
G. Crawling on a Tree
#include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; typedef long long ll; const int N=10005,M=10005; int n,m,i,lim[N],g[N],v[N<<1],w[N<<1],wt[N<<1],nxt[N<<1],ed; int wf[N],wk[N],need[N],sz[N],heavy[N]; ll ans[M]; struct E{ ll s,d[M]; int l,r; void clr(){ s=l=0;r=m; for(int i=0;i<=m;i++)d[i]=0; } }f[15]; inline void add(int x,int y,int z,int k){ v[++ed]=y; w[ed]=z; wt[ed]=k; nxt[ed]=g[x]; g[x]=ed; } inline void merge(const E&A,const E&B,E&C){ int l=A.l+B.l,r=min(A.r+B.r,m); static ll d[M]; int i=A.l+1,j=B.l+1,k=l+1; while(k<=r&&i<=A.r&&j<=B.r)d[k++]=A.d[i]<B.d[j]?A.d[i++]:B.d[j++]; while(k<=r&&i<=A.r)d[k++]=A.d[i++]; while(k<=r&&j<=B.r)d[k++]=B.d[j++]; C.s=A.s+B.s; C.l=l; C.r=r; for(int i=l+1;i<=r;i++)C.d[i]=d[i]; } void dfs(int x,int y){ need[x]=lim[x]; sz[x]=1; for(int i=g[x];i;i=nxt[i]){ int u=v[i]; if(u==y)continue; wf[u]=w[i]; wk[u]=wt[i]; dfs(u,x); sz[x]+=sz[u]; if(sz[u]>sz[heavy[x]])heavy[x]=u; need[x]=max(need[x],need[u]); } } void go(int x,int y,int o){ int u=heavy[x]; if(u){ go(u,x,o); f[o+1].clr(); merge(f[o],f[o+1],f[o]); }else f[o].clr(); for(int i=g[x];i;i=nxt[i]){ int u=v[i]; if(u==y||u==heavy[x])continue; go(u,x,o+1); merge(f[o],f[o+1],f[o]); } int L=need[x],R=wk[x],W=wf[x]; int A=max(f[o].l,L*2-R),B=min(f[o].r,R); if(A>B){ for(int i=1;i<=m;i++)puts("-1"); exit(0); } for(int i=f[o].l+1;i<=A;i++)f[o].s+=f[o].d[i]; f[o].l=A; f[o].r=B; f[o].s+=1LL*(max(L,A)*2-A)*W; for(int i=A+1;i<=B&&i<=L;i++)f[o].d[i]-=W; for(int i=max(A,L)+1;i<=B;i++)f[o].d[i]+=W; } int main(){ scanf("%d%d",&n,&m); for(i=1;i<n;i++){ int x,y,z,k; scanf("%d%d%d%d",&x,&y,&z,&k); add(x,y,z,k); add(y,x,z,k); } for(i=2;i<=n;i++)scanf("%d",&lim[i]); wk[1]=m*2; dfs(1,0); go(1,0,0); for(i=1;i<=m;i++)ans[i]=-1; ll sum=f[0].s; for(i=f[0].l;i<=m;i++){ if(i>=need[1])ans[i]=sum; if(i<m)sum+=f[0].d[i+1]; } for(i=1;i<=m;i++)printf("%lld\n",ans[i]); }
H. Permutation
#include <bits/stdc++.h> using namespace std; int n; const double C = (sqrt(5) - 1) / 2; int f[1000005]; int d[1000005]; int qry(int l,int r) { cout << "? " << l <<' ' << r << '\n' ; fflush(stdout) ; int x ; cin >> x; return x; } void solv() { cin >> n; int l = 1 , r = n; int lst_pos = -1; while(l < r) { int c = d[r - l + 1]; // printf("C %d %d %d\n",l,r,c) ; if(lst_pos == -1) lst_pos = qry(l , r); if(r - l == 1) { if(lst_pos == l) l = r; else r = l; break ; } if(l + c - 1 >= lst_pos) { int x = qry(l , l + c - 1); if(x == lst_pos) r = l + c - 1; else { l = l + c; lst_pos = -1; } } else { int x = qry(r - c + 1 , r); if(x == lst_pos) l = r - c + 1; else { r = r - c; lst_pos = -1; } } } cout << "! " << l << '\n' ; fflush(stdout) ; return ; } int main() { // ios::sync_with_stdio(false) ; cin.tie(0) ; int t;cin >> t; f[1] = f[2] = 0; for(int i = 3;i <= 1000000;i++) { int mxc = (int)(C * i); f[i] = 1e9; for(int j = max(mxc - 10 , (i + 1)/2) ; j <= min(i - 1 , mxc + 10) ; j++) { if(max(f[j] + 1 , f[i - j] + 2) < f[i]) { f[i] = max(f[j] + 1 , f[i - j] + 2) ; d[i] = j; } } // if(f[i] > ceil(1.5 * log2(i)) - 1) { // printf("%d %d %lf\n",i,f[i],ceil(1.5 * log2(i)) - 1); // } } // printf("%d\n",f[1000000]) ;? while(t--) solv() ; }
I. Piggy Sort
#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e3+1e2+7; int T,n,m; int x[N][N],sx[N]; map<int,int> vis[N]; int use[N]; int av[N],bv[N],fd,ans[N]; void dfs(int t) { if(t==n+1) { vector<int> id(n); iota(id.begin(),id.end(),1); sort(id.begin(),id.end(),[&](const int &a,const int &b){ if(av[a]*bv[b]!=av[b]*bv[a]) return av[a]*bv[b]<av[b]*bv[a]; return a<b; }); fd=1; for(int i=0;i<n;i++) ans[id[i]]=i+1; for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n]; return; } for(int i=1;i<=n;i++) { if(use[i]) continue; int va=x[2][i]-x[1][t]; int vb=sx[2]-sx[1]; int ok=1; for(int j=3;j<=m;j++) { if(va*(sx[j]-sx[1])%vb) { ok=0; break; } int w=va*(sx[j]-sx[1])/vb+x[1][t]; if(!vis[j].count(w)||!vis[j][w]) { ok=0; break; } } if(ok) { for(int j=1;j<=m;j++) { int w=va*(sx[j]-sx[1])/vb+x[1][t]; vis[j][w]--; } use[i]=1; av[t]=va,bv[t]=vb; dfs(t+1); use[i]=0; for(int j=1;j<=m;j++) { int w=va*(sx[j]-sx[1])/vb; vis[j][w]++; } } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin>>T; while(T--) { cin>>n>>m; for(int i=1;i<=m;i++) { vis[i].clear(); sx[i]=0; for(int j=1;j<=n;j++) cin>>x[i][j],vis[i][x[i][j]]++,sx[i]+=x[i][j]; } if(sx[1]==sx[2]) { for(int i=1;i<=n;i++) cout<<i<<" \n"[i==n]; continue; } fd=0; dfs(1); assert(fd); } } /* 1 3 6 1 2 3 4 5 6 6 9 9 8 12 13 10 15 17 12 18 21 */
J. Even or Odd Spanning Tree
#include<cstdio> #include<algorithm> using namespace std; const int N=200005,K=18,M=500005,inf=~0U>>1; int Case,n,m,cnt,i,j,x,y,z,tmp,f[N],g[N],v[N<<1],w[N<<1],nxt[N<<1],ed; int d[N],fa[N][K],fe[N][K],fo[N][K]; long long mst,ans;int delta;bool on[M]; struct E{int x,y,z;}e[M]; inline bool cmp(const E&a,const E&b){return a.z<b.z;} inline void umax(int&a,int b){a<b?(a=b):0;} int F(int x){return f[x]==x?x:f[x]=F(f[x]);} inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;} void dfs(int x,int y){ for(int i=1;i<K;i++){ fa[x][i]=fa[fa[x][i-1]][i-1]; fe[x][i]=max(fe[x][i-1],fe[fa[x][i-1]][i-1]); fo[x][i]=max(fo[x][i-1],fo[fa[x][i-1]][i-1]); } for(int i=g[x];i;i=nxt[i]){ int u=v[i],z=w[i]; if(u==y)continue; d[u]=d[x]+1; fa[u][0]=x; if(z&1){ fe[u][0]=0; fo[u][0]=z; }else{ fe[u][0]=z; fo[u][0]=0; } dfs(u,x); } } inline int ask(int x,int y,int w[][K]){ if(x==y)return 0; if(d[x]<d[y])swap(x,y); int ret=0; for(int i=K-1;~i;i--)if(d[fa[x][i]]>=d[y]){ umax(ret,w[x][i]); x=fa[x][i]; } if(x==y)return ret; for(int i=K-1;~i;i--)if(fa[x][i]!=fa[y][i]){ umax(ret,w[x][i]); umax(ret,w[y][i]); x=fa[x][i]; y=fa[y][i]; } umax(ret,w[x][0]); umax(ret,w[y][0]); return ret; } int main(){ scanf("%d",&Case); while(Case--){ scanf("%d%d",&n,&m); for(i=0;i<=n;i++){ g[i]=d[i]=0; for(j=0;j<K;j++)fa[i][j]=fe[i][j]=fo[i][j]=0; } mst=cnt=ed=0; for(i=1;i<=m;i++){ scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); on[i]=0; } sort(e+1,e+m+1,cmp); for(i=1;i<=n;i++)f[i]=i; for(i=1;i<=m;i++){ x=e[i].x,y=e[i].y,z=e[i].z; if(F(x)==F(y))continue; on[i]=1; f[f[x]]=f[y]; mst+=z; cnt++; add(x,y,z),add(y,x,z); } if(cnt<n-1){ puts("-1 -1"); continue; } dfs(1,0); delta=inf; for(i=1;i<=m;i++){ if(on[i])continue; z=e[i].z; tmp=ask(e[i].x,e[i].y,z&1?fe:fo); if(!tmp)continue; z-=tmp; if(delta>z)delta=z; } if(delta<inf)ans=mst+delta;else ans=-1; if(mst&1)swap(ans,mst); printf("%lld %lld\n",mst,ans); } } /* 3 2 1 1 2 5 3 1 1 3 1 4 4 1 2 1 1 3 1 1 4 1 2 4 2 */
K. Sugar Sweet 3
#include <bits/stdc++.h> using namespace std; int A , B , C , x; int n ; const int N = 605; const int mod = 1e9 + 7; int fpow(int a,int b) { int ans = 1; while(b) { if(b & 1) ans = 1LL * ans * a %mod; a = 1LL * a * a %mod; b>>= 1; } return ans; } int F[N][N]; // int Ga[N][N] , Gb[N][N], Gc[N][N]; // int dota[N][N] , dotb[N][N] , dotc[N][N]; int dot[N][N]; int Cata[N] ; int d[N] ; int t[N * 2] , rt[N * 2] ; int lm ; ///多项式的项数 int mat[N][N] , rmat[N][N]; int C_(int a,int b) { return 1LL * t[a] * rt[b] % mod * rt[a - b] % mod; } int A_(int a,int b) { return 1LL * t[a] * rt[a - b] % mod; } vector<int> get_coe(int n , vector<int> w) { ///已知n个点值[1 to n],求sum{ai * wi} 对应的 di的系数,i from 0 to n - 1 for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { mat[i][j] = fpow(i , j - 1) ; // MAT * A = D rmat[i][j] = (i == j) ; } } for(int i = 1;i <= n;i++) { int cur = -1; for(int j = i ;j <= n;j++) { if(mat[j][i]) {cur = j ; break ;} } for(int j = 1;j <= n;j++) {swap(mat[cur][j] , mat[i][j]) ; swap(rmat[cur][j] , rmat[i][j]) ;} int r = fpow(mat[i][i] , mod - 2); for(int j = 1;j <= n;j++) { if(i == j) continue ; int f = (mod - 1LL * mat[j][i] * r %mod) % mod; for(int k = 1;k <= n;k++) {mat[j][k] = (mat[j][k] + 1LL * mat[i][k] * f) % mod ; rmat[j][k] = (rmat[j][k] + 1LL * rmat[i][k] * f) % mod;} } for(int j = 1;j <= n;j++) { mat[i][j] = 1LL * mat[i][j] * r % mod; rmat[i][j] = 1LL * rmat[i][j] * r % mod; } } // for(int i = 1;i <= n;i++ , printf("\n")) for(int j = 1;j <= n;j++) printf("%d ",rmat[i][j]) ; ///A = Rmat * D vector<int> coe(n) ; for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { coe[j] = (coe[j] + 1LL * w[i] * rmat[i + 1][j + 1]) % mod; } } return coe; } int main() { cin >> A >> B >> C >> x; n = A + B + C; if(n & 1) { cout << 0 ; return 0; } if(A > n/2 || B > n/2 || C > n/2) { cout << 0 ; return 0; } t[0] = rt[0] = 1; for(int i = 1;i <= n + 1;i++) t[i] = 1LL * t[i - 1] * i % mod , rt[i] = fpow(t[i] , mod - 2) ; Cata[0] = 1; for(int i = 1;i <= n/2;i++) Cata[i] = 1LL * C_(i*2 , i) * fpow(i + 1 , mod - 2) % mod; //// F[i][j]表示i个主元分j段的方案数,Fi(x)作为其egf F[0][0] = 1; lm = n / 2 + 1; for(int i = 1;i <= n/2;i++) { for(int j = 1;j <= i;j++) { for(int k = 1;k <= i;k++) { ///最后一段包含的主元个数 F[i][j] = (F[i][j] + 1LL * F[i - k][j - 1] * Cata[k - 1]) % mod; } // printf("%d %d : %d\n",i,j,F[i][j]) ; } } for(int i = 0;i <= n/2;i++) { for(int j = 0;j <= i;j++) F[i][j] = 1LL * F[i][j] * rt[j] % mod ; ///变成egf for(int j = 1;j <= lm;j++) { dot[i][j] = 0; for(int k = i;k >= 0;k--) dot[i][j] = (1LL * dot[i][j] * j + F[i][k]) % mod; ///dot 代表点值 } } vector<int> w(n/2 + 1) ; for(int i = 0;i <= n/2;i++) w[i] = 1LL * fpow(i , x) * t[i] % mod; vector<int> coe = get_coe(n/2 + 1 , w) ; /// coe.len = n/2 + 1 int ans = 0; for(int a = 0;a <= n/2 && a <= A;a++) { for(int b = 0;b + a <= n / 2 && b <= B;b++) { int c = n / 2 - a - b; if(c > C) continue ; /// F[a] * F[b] * F[c] for(int i = 1;i <= lm;i++) d[i] = 1LL * dot[a][i] * dot[b][i] % mod * dot[c][i] % mod; // for(int i = 1;i <= lm;i++) printf("%d ",3LL * d[i] % mod) ; printf("\n") ; int sol = 0; for(int i = 1;i <= lm;i++) sol = (sol + 1LL * d[i] * coe[i - 1]) % mod; int sol2 = 0; for(int ab = 0;ab <= A - a && ab <= b; ab++){ int ac = (A - a - ab) ; int bc = (c - ac) ; int ba = (B - b - bc) ; int ca = (a - ba) ; int cb = (C - c - ca) ; if(ac < 0 || bc < 0 || ba < 0 || ca < 0 || cb < 0) continue ; sol2 = (sol2 + 1LL * C_(a , ba) * C_(b , ab) % mod * C_(c , ac)) % mod; } // printf("%d %d %d : %d %d\n",a,b,c,sol,sol2); ans = (ans + 1LL * sol * sol2) % mod; } } cout << ans << '\n'; }
L. Challenge Matrix Multiplication
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; typedef pair<int,int> pii; int to[N] , fir[N] , nxt[N] ; bool ok[N]; int cc = 0; int nc , nodes[N]; void adde(int u,int v) { ++cc; to[cc] = v; nxt[cc] = fir[u]; fir[u] = cc; } int in[N] , out[N] ; int n ,m ; int ans[N]; bool vis[N]; pii fr[N] ; int cnt = 0; int qu[N] , l , r; void bfs(int u) { l = 1 , r = 0; qu[++r] = u; vis[u] = 1; while(l <= r) { int u = qu[l++]; cnt++; for(int i = fir[u] ; i ; i = nxt[i]) { if(!vis[to[i]]) { qu[++r] = to[i] ; vis[to[i]] = 1; } } } return ; } int main() { ios::sync_with_stdio(false) ; cin.tie(0); cout.tie(0); clock_t cl = clock() ; cin >>n>>m; //printf("??? %d %d\n",n,m); for(int i = 1;i <= m;i++) { int u , v;cin >> u >> v; in[v]++ ; out[u]++; adde(u , v); } for(int i = 1;i <= n;i++) ans[i] = 1; int all = m; clock_t sum0 = 0 , sum1 = 0; while(all) { // clock_t a = clock(); for(int i = 1;i <= n;i++) { if(in[i] < out[i]) { memset(vis,0,sizeof(vis)) ; vis[i] = 1; int lst; for(int j = i ; j <= n;j++) { if(!vis[j]) continue ; if(in[j] > out[j]) {lst = j ; break ;} for(int x = fir[j] ; x ; x = nxt[x]) { if(!vis[to[x]] && !ok[x]) { vis[to[x]] = 1; fr[to[x]] = {j , x}; } } } int u = lst ; nc = 0; while(u) { nodes[nc++] = u; if(u != i) in[u]--; if(u != lst) out[u]--; if(u == i) break ; ok[fr[u].second] = 1; u = fr[u].first ; all--; } break ; } } // sum0 += (clock() - a); // a = clock() ; cnt = 0; memset(vis,0,sizeof(vis)); for(int i = 0;i < nc;i++) { bfs(nodes[i]) ; ans[nodes[i]] = cnt; } // static int gg = 0; // sum1 += (clock() - a) ; // printf("i-th round %d %d\n",++gg , nc) ; } // cerr << (double)(clock() - cl) / CLOCKS_PER_SEC <<' ' << (double)sum0 / CLOCKS_PER_SEC <<' ' << (double)sum1 / CLOCKS_PER_SEC << '\n'; // return 0; for(int i = 1;i <= n;i++) cout << ans[i] <<' ' ; cout << '\n'; }
M. Triangles
#include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); long long n,a,b; cin>>n>>a>>b; long long ans=0; for(long long r=1;r<=n;r++) { ans+=r*(r+1); if(r*2>n)ans-=(r*2-n)*(r*2-n+1)/2; } for(long long i=1;i<=b;i++) { ans-=(a-b+1); ans-=max(min(a+1-i,n-a)-(b-i),0ll); } cout<<ans<<endl; return 0; }
标签:include,int,Universal,Cangqian,++,long,ans,Stage,size From: https://www.cnblogs.com/clrs97/p/18405338