#include<bits/stdc++.h> #define ll long long using namespace std; ll n,m,sum,n1,n2; ll Gcd(ll a,ll b) { if(!b) return a; return Gcd(b,a%b); } ll Ex_gcd(ll a,ll b,ll &x,ll &y) { if(!b){ x=1; y=0; return a;} ll d=Ex_gcd(b,a%b,x,y); ll t=x; x=y; y=t-(a/b)*y; return d; } int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) { ll t; scanf("%lld",&t); sum+=t; } sum%=m; n1=n; n2=n*(n+1)/2; ll gcd=Gcd( Gcd(n1,n2),m ); ll ans=-(sum/gcd)*gcd+sum; cout<<ans<<"\n"; ll a=Gcd(n1,n2),b=m,x,y; Ex_gcd(a,b,x,y); x=x*(ans-sum)/gcd; ll dx=b/gcd; x=x+ceil((-x+1)/dx)*dx; ll s,d; a=n1,b=n2; Ex_gcd(a,b,s,d); s=s*x; d=d*x; s=(s%m+m)%m; d=(d%m+m)%m; cout<<s<<" "<<d; return 0; }
#include<bits/stdc++.h> using namespace std; int n,k,p[3005],Ans=0; int w[3005][11],S=0; int f[3005][3005][2]; int Work(int P) { memset(f,128,sizeof(f)); f[0][0][0]=f[0][0][1]=0; for(int i=1;i<=n;i++) for(int j=0;j<=k-P;j++) { f[i][j][0]=max(f[i][j][0],f[i-1][j][0]); if(j-p[i]>=0) f[i][j][0]=max(f[i][j][0],f[i-1][j-p[i]][0]+w[i][p[i]]); f[i][j][1]=max(f[i][j][1],f[i-1][j][1]); if(P<=p[i]) f[i][j][1]=max(f[i][j][1],f[i-1][j][0]+w[i][P]); if(j-p[i]>=0) f[i][j][1]=max(f[i][j][1],f[i-1][j-p[i]][1]+w[i][p[i]]); } int ans=max(f[n][k-P][0],f[n][k-P][1]); return ans; } int main() { scanf("%d%d",&n,&k); int sum=0; for(int i=1;i<=n;i++) { scanf("%d",p+i); sum+=p[i]; for(int j=1;j<=p[i];j++) scanf("%d",&w[i][j]); S+=w[i][p[i]]; } if(sum<=k) { cout<<S; return 0; } for(int i=0;i<=10;i++) { int t=Work(i); Ans=max(Ans,t); } cout<<Ans; return 0; }
#include<bits/stdc++.h> using namespace std; int n; double a,S,ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lf",&a); S+=a; } ans=S/double(n+1); printf("%.7lf ",2*ans); for(int i=2;i<=n;i++) printf("%.7lf ",ans); return 0; }
#include<bits/stdc++.h> using namespace std; const int MAXN=1005; int T; int n,a[MAXN]; int sum,xx[MAXN*2],yy[MAXN*2]; void Swap(int x,int y,int *b) { sum++; xx[sum]=x; yy[sum]=y; int tmp[MAXN]={0},num=0; for(int i=n-y+1;i<=n;i++) tmp[++num]=b[i]; for(int i=x+1;i<=n-y;i++) tmp[++num]=b[i]; for(int i=1;i<=x;i++) tmp[++num]=b[i]; for(int i=1;i<=n;i++) b[i]=tmp[i]; } void Work() { sum=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); if(n==3) { if(a[1]>a[3]) printf("1\n1 1\n"); else printf("0\n"); return ; } int p; for(int i=1;i<=n;i++) if(a[i]==1){ p=i; break; } if(p==2) { Swap(2,1,a); Swap(1,1,a); } else if(p>2) Swap(1,n-p+1,a); while(1) { int k=1; for(int i=2;i<=n;i++) { if(a[i]>a[i-1]) k++; else break; } if(k==n) break; int j=1; for(int i=1;i<=k;i++) if(a[n]>a[i]) j=i; if(j<n-2) { Swap(j,2,a); Swap(1,j,a); } if(j==n-2) { Swap(1,1,a); Swap(n-2,1,a); Swap(2,n-3,a); Swap(n-3,1,a); Swap(1,n-2,a); } } cout<<sum<<"\n"; for(int i=1;i<=sum;i++) cout<<xx[i]<<" "<<yy[i]<<"\n"; } int main() { scanf("%d",&T); while(T--) Work(); return 0; }
#include<bits/stdc++.h> using namespace std; int n,m; char s[10005]; map<string,int> ma; int main() { cin>>n; while(n--) { int flag=0; cin>>m; while(m--) { scanf("%s",s+1); int len=strlen(s+1); if(ma[s+1]) continue; for(int i=3;i<=len;i++) { if(s[i-2]=='b'&&s[i-1]=='i'&&s[i]=='e') { ma[s+1]=1; printf("%s\n",s+1); flag=1; break; } } } if(!flag) puts("Time to play Genshin Impact, Teacher Rice!"); } return 0; }
#include<bits/stdc++.h> #define ll long long using namespace std; const int MAXN=1e5+5,MAXM=1e5+5; const ll mod=998244353; int T; struct Edge { int nxt,to; }e[MAXM*2]; int cnt,h[MAXN]; void Add_edge(int x,int y) { e[++cnt]=(Edge){h[x],y}; h[x]=cnt; } int n,m; int vis[MAXN]; int node; ll f[MAXN],dep[MAXN],deg[MAXN]; ll trans1[MAXN],trans2[MAXN]; void Get_hash(int u,int fa) { f[u]=19260817; dep[u]=deg[u]=1; vector<int> a; for(int i=h[u];i;i=e[i].nxt) { int v=e[i].to; if( v==fa || vis[v] ) continue; Get_hash(v,u); f[u]=(f[u]+f[v])%mod; dep[u]=max(dep[u],dep[v]+1); deg[u]++; a.push_back(v); } f[u]=f[u]*trans1[dep[u]]%mod*trans2[deg[u]]%mod; } int dfn[MAXN],id; int fa[MAXN]; int c[MAXN],num=0; void Get_loop(int u) { dfn[u]=++id; for(int i=h[u];i;i=e[i].nxt) { int v=e[i].to; if(v==fa[u]) continue; if(dfn[v]) { if(dfn[v]<dfn[u]) continue; c[++num]=v; for(;v!=u;v=fa[v]) c[++num]=fa[v]; return ; } else fa[v]=u,Get_loop(v); } } void Clean() { cnt=0; for(int i=1;i<=n;i++) h[i]=0; for(int i=1;i<=n;i++) vis[i]=0; for(int i=1;i<=n;i++) dfn[i]=0; id=0; for(int i=1;i<=num;i++) c[i]=0; num=0; } ll random(ll x) { return (ll)(1.0*rand()/RAND_MAX*x)+1; } void Work() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) trans1[i]=random(1e7),trans2[i]=random(1e7); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); Add_edge(x,y); Add_edge(y,x); } if(m==n-1||m>n) { cnt=0; for(int i=1;i<=n;i++) h[i]=0;//clean if(m==n-1){ puts("YES"); return; } if(m>n){ puts("NO"); return; } } Get_loop(1); for(int i=1;i<=num;i++) vis[c[i]]=1; for(int i=1;i<=num;i++) Get_hash(c[i],0); int flag1=1,flag2=1; for(int i=2;i<=num;i++) if( f[c[i]]!=f[c[1]]){ flag1=0; break; } for(int i=3;i<=num;i+=2) if( f[c[i]]!=f[c[1]]){ flag2=0; break; } for(int i=4;i<=num;i+=2) if( f[c[i]]!=f[c[2]]){ flag2=0; break; } if( flag1 || ( flag2 && num%2==0 ) ) puts("YES"); else puts("NO"); Clean(); } int main() { scanf("%d",&T); while(T--) Work(); return 0; }
#include<bits/stdc++.h> using namespace std; const int K=3333; int random() { return (int)(1.0*rand()/RAND_MAX*1e9); } map<int,int> ma; int main() { srand(time(0)); int m=0,x; for(int i=1;i<=K;i++) { printf("walk %d\n",random()); fflush(stdout); scanf("%d",&x); if(x>m) m=x; } for(int i=1;i<=K;i++) { printf("walk %d\n",1); fflush(stdout); scanf("%d",&x); if(ma[x]) { printf("guess %d",i-1); return 0; } else ma[x]=i; } printf("walk %d\n",m); fflush(stdout); scanf("%d",&x); if(ma[x]) { printf("guess %d",K+m-ma[x]); return 0; } for(int i=1;i<=K;i++) { printf("walk %d\n",K); fflush(stdout); scanf("%d",&x); if(ma[x]) { printf("guess %d",(i+1)*K+m-ma[x]); return 0; } } return 0; }
#include<bits/stdc++.h> #define ll long long using namespace std; int n,q; char s[1000005]; int ch[1000005][27],tot=1; ll cnt[1000005],w[27][27],pfx=0; int big[27]; void Trie_insert() { scanf("%s",s+1); int len=strlen(s+1),p=1; for(int i=1;i<=len;i++) { int x=s[i]-'a'+1; if(!ch[p][x]) ch[p][x]=++tot; int t=p; p=ch[p][x]; cnt[p]++; for(int j=1;j<=26;j++) if(x!=j) w[j][x]+=cnt[ch[t][j]]; } for(int i=1;i<=26;i++) if(ch[p][i]) pfx+=cnt[ch[p][i]]; } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) Trie_insert(); while(q--) { char c[27]; scanf("%s",c+1); for(int i=1;i<=26;i++) big[c[i]-'a'+1]=i; ll ans=0; for(int i=1;i<=26;i++) for(int j=1;j<=26;j++) { if(big[i]>big[j]) ans+=w[i][j]; } cout<<ans+pfx<<"\n"; } return 0; }
#include<bits/stdc++.h> #define ll long long using namespace std; const ll MAXN=5e5+5; const ll inf=1e18; ll Gcd(ll x,ll y) { if(!y) return x; return Gcd(y,x%y); } ll n,k,c[MAXN],Ans=inf; ll vis[MAXN]; struct Edge { ll nxt,to,w; }e[MAXN*2]; ll cnt,h[MAXN]; void Add_edge(ll x,ll y,ll z) { e[++cnt]=(Edge){h[x],y,z}; h[x]=cnt; } ll sum[MAXN],num[MAXN];//the sum of vertex to u ll f[MAXN],g[MAXN]; void Merge(ll &f1,ll &g1,ll f2,ll g2) { if(f1==0&&g1==0) { f1=f2,g1=g2; return ; } if(f2==0&&g2==0) return ; if(f1>=f2) { g1=Gcd( g1 , Gcd(g2,f1-f2) ); f1=f2; } else { g1=Gcd( g1 , Gcd(g2,f2-f1) ); } } void DFS1(ll u,ll fa) { sum[u]=0; f[u]=g[u]=0; if(vis[u]) num[u]=1; for(ll i=h[u];i;i=e[i].nxt) { ll v=e[i].to; if(v==fa) continue; DFS1(v,u); num[u]+=num[v]; sum[u]+=sum[v]+e[i].w*num[v]; if(f[v]!=0) Merge(f[u],g[u],f[v]+e[i].w,g[v]); if(vis[v]) Merge(f[u],g[u],e[i].w,0); } } void DFS2(ll u,ll fa,ll F,ll G,ll Sum,ll Num,ll W) { ll f_new=f[u],g_new=g[u],sum_new=sum[u],num_new=num[u]; sum_new+=Sum+W*Num; num_new+=Num; if(F!=0) Merge(f_new,g_new,F+W,G); if(vis[fa]) Merge(f_new,g_new,W,0); if(Gcd(f_new,g_new)!=0) { ll ans=sum_new/Gcd(f_new,g_new); if(Ans>ans) Ans=ans; } if(sum_new<Ans) Ans=sum_new; ll siz=0; vector<ll> a; a.push_back(0); vector<ll> ww; ww.push_back(0); for(ll i=h[u];i;i=e[i].nxt) { ll v=e[i].to; if(v==fa) continue; a.push_back(v); ww.push_back(e[i].w); siz++; } vector<ll> pre_f(siz+5); vector<ll> pre_g(siz+5); vector<ll> bac_f(siz+5); vector<ll> bac_g(siz+5); for(ll i=1;i<=siz;i++) { ll v=a[i]; ll ft=f[v]+ww[i],gt=g[v]; if(f[v]==0) ft=gt=0; Merge(ft,gt,pre_f[i-1],pre_g[i-1]); if(vis[v]) Merge(ft,gt,ww[i],0); pre_f[i]=ft; pre_g[i]=gt; } for(ll i=siz;i>=1;i--) { ll v=a[i]; ll ft=f[v]+ww[i],gt=g[v]; if(f[v]==0) ft=gt=0; Merge(ft,gt,bac_f[i+1],bac_g[i+1]); if(vis[v]) Merge(ft,gt,ww[i],0); bac_f[i]=ft; bac_g[i]=gt; } for(ll i=1;i<=siz;i++) { ll v=a[i]; ll f_tmp,g_tmp,sum_tmp,num_tmp; f_tmp=pre_f[i-1]; g_tmp=pre_g[i-1]; if(F!=0) Merge(f_tmp,g_tmp,F+W,G); if(vis[fa]) Merge(f_tmp,g_tmp,W,0); Merge(f_tmp,g_tmp,bac_f[i+1],bac_g[i+1]); sum_tmp=sum_new-sum[v]-num[v]*ww[i]; num_tmp=num_new-num[v]; DFS2(v,u,f_tmp,g_tmp,sum_tmp,num_tmp,ww[i]); } } int main() { scanf("%lld%lld",&n,&k); for(ll i=1;i<=k;i++) scanf("%lld",&c[i]),vis[c[i]]=1; for(ll i=1;i<n;i++) { ll x,y,z; scanf("%lld%lld%lld",&x,&y,&z); Add_edge(x,y,z); Add_edge(y,x,z); } DFS1(1,0); DFS2(1,0,0,0,0,0,0); cout<<Ans*2; return 0; }
标签:ICPC2022,return,int,ll,MAXN,补题,new,杭州,sum From: https://www.cnblogs.com/yzjblogs/p/16990577.html