A 签到
#include<bits/stdc++.h> using namespace std; int a[123456]; int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); int f=0; int t=-1; int z=0; int maxn=-1; for(int i=0;i<=n-1;i++){ scanf("%d",&a[i]); if(a[i]>maxn){ maxn=a[i]; z=i; } }int i; if(z==0||z==n-1){puts("No");continue;} for(i=0;i<z;i++)if(a[i+1]<=a[i])f=1; for(i=z;i<n-1;i++)if(a[i]<=a[i+1])f=1; if(!f)puts("Yes"); else puts("No"); } }
B签到
#include<bits/stdc++.h> using namespace std; int a[123456]; int b[123456]; int c[2000000]; int main(){ int t; scanf("%d",&t); while(t--){ memset(c,0,sizeof c); int n;scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); } for(int i=0;i<n;i++){ scanf("%d",&b[i]); } for(int i=0;i<n;i++){ int k=b[i]-a[i]; c[k+200000]++; } int maxn=-1; for(int i=0;i<400001;i++){ if(c[i]>maxn)maxn=c[i]; } printf("%d ",maxn); } }
C 组合数
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; ll c[100][10]; ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; } int num[N]; void init(){ for(int i=0;i<=50;i++){ c[i][0]=1; for(int j=1;j<=i&&j<=4;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; } } int get(string s){ if(s.size()==2){ return 10; } if(s[0]=='A') return 1; if(s[0]=='J') return 11; if(s[0]=='Q') return 12; return (s[0]-'0'); } int main(){ int t; cin>>t; int m=48; init(); while(t--){ int n; cin>>n; int i; m=48; for(i=1;i<=12;i++){ num[i]=0; } for(i=1;i<=n;i++){ string s; cin>>s; int x=get(s); num[x]++; } for(i=1;i<=12;i++){ m-=num[i]; } int n1=4-num[1]; for(i=1;i<=12;i++){ int x=4-num[i]; if(i==1){ cout<<1<<" "; continue; } else if(n1==0){ if(i==12){ if(x==0){ cout<<1<<endl; } else{ cout<<0<<endl; } continue; } else{ if(x==0){ cout<<1<<" "; } else{ cout<<0<<" "; } continue; } } ll a=c[m][n1]*c[m-n1][x]; ll tmp=0; for(ll j=x+n1;j<=m;j++){ tmp+=c[j-1][n1-1]*c[j-n1][x]; } ld=gcd(a,tmp); a/=d; tmp/=d; if(i==12){ if(a==tmp) cout<<1<<endl; else cout<<tmp<<"/"<<a<<endl; } else{ if(tmp==a) cout<<1<<" "; else cout<<tmp<<"/"<<a<<" "; } } } return 0; }
D dp设计状态为第i个移到第j个以后，这样可以降维
#include<iostream> #include<string> #include<algorithm> #include<cstdio> #include<cstring> #define LL long long using namespace std; char s[1005]; int a[1005]; LL dp[1005][1005]; LL k[1005]; LL res[1005][1005]; int main() { int T; cin>>T; while(T--) { int n; scanf("%d",&n); getchar(); for(int i=1;i<=n;i++) scanf("%c",&s[i]); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); memset(k,0,sizeof(k)); for(int i=1;i<=n;i++) { if(s[i]==')') continue; for(int j=i+1;j<=n;j++) { if(s[j]==')') dp[i][j]=dp[i][j-1]+(a[i]*a[j]); else dp[i][j]=dp[i][j-1]; } } LL ans=0; for(int i=1;i<=n;i++) { LL maxx=0; for(int j=1;j<=n;j++) { maxx=max(dp[i-1][j],maxx); dp[i][j]+=maxx; } } for(int i=1;i<=n;i++) { ans=max(dp[n][i],ans); } printf("%lld ",ans); } return 0; }
E 差分约束系统，找到所有不等关系后跑一遍最短路就是答案
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e6+10; const int inf=0x3f3f3f3f; int h[N],ne[N],e[N],w[N],idx; int n,f[N],l[N],r[N]; int last[N]; int st[N]; ll dis[N]; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void spfa(){ queue<int> q; q.push(n+1); dis[n+1]=0; for(int i=1;i<=n+1;i++) st[i]=0; st[n+1]=1; while(q.size()){ auto t=q.front(); q.pop(); st[t]=0; for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(dis[j]>dis[t]+w[i]){ dis[j]=dis[t]+w[i]; if(!st[j]){ q.push(j); st[j]=1; } } } } for(int i=1;i<n;i++) cout<<dis[i]<<" "; cout<<dis[n]<<endl; } int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ cin>>n; int i; idx=0; for(i=0;i<=n+1;i++){ h[i]=-1; last[i]=0; dis[i]=1e18; } for(i=1;i<=n;i++){ cin>>f[i]; } for(i=1;i<=n;i++){ cin>>l[i]>>r[i]; } for(i=1;i<=n;i++){ add(i,n+1,-l[i]); add(n+1,i,r[i]); if(last[f[i]]){ add(last[f[i]],i,0); } if(f[i]){ add(i,last[f[i]-1],-1); } last[f[i]]=i; } spfa(); } return 0; }
F dp
#include<iostream> #include<cstring> #include<cstdio> #include<map> #include<algorithm> #include<queue> #define ull unsigned long long using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=5e5+10; const int mod=1e9; int sum[N]; int f[31][N]; int a[N]; int p[N]; int cnt[N]; int n,m; void init(){ int i,j; for(i=1;i<=30;i++){ f[i][0]=0; for(j=1;j<=n;j++){ f[i][j]=(f[i][j-1]+a[j]/i)%mod; } } } int main(){ int t; cin>>t; while(t--){ cin>>n>>m; int i; for(i=1;i<=n;i++){ scanf("%d",&a[i]); } for(i=1;i<=m;i++){ scanf("%d",&p[i]); } sort(a+1,a+1+n); init(); ll sum=0; for(i=1;i<=m;i++){ ll tmp=1; int idx=0; ll ans=0; while(tmp*p[i]<=a[n]){ tmp*=p[i]; int l=0,r=n; while(l<r){ int mid=l+r+1>>1; if(a[mid]<=tmp) l=mid; else r=mid-1; } cnt[++idx]=r; } if(cnt[idx]<n){ cnt[++idx]=n; } for(int j=1;j<=idx;j++){ ans=(ans+f[j][cnt[j]]-f[j][cnt[j-1]]+mod)%mod; } sum=(sum+ans*i)%mod; } cout<<(sum+mod)%mod<<endl; } }
G 哈希+最小循环节
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; char s[N],t[N]; const int mod1=1e9+7; const int mod2=1e9+9; const int base=131; map<ll,int> m1; int n,m,q; int nxt[N]; ll p1[N],p2[N]; struct node{ ll l,r; }h[N]; int pos[N]; void Hash(){ p1[0]=1,p2[0]=1; for(int i=1;i<=n;i++){ p1[i]=p1[i-1]*base%mod1; p2[i]=p2[i-1]*base%mod2; h[i].l=(h[i-1].l*base%mod1+(s[i]-'0'))%mod1; h[i].r=(h[i-1].r*base%mod2+(s[i]-'0'))%mod2; } } ll get(int l,int r){ ll h1=(h[r].l-(h[l-1].l*p1[r-l+1]%mod1)+mod1)%mod1; ll h2=(h[r].r-(h[l-1].r*p2[r-l+1]%mod2)+mod2)%mod2; return h1+h2; } int main(){ int T; cin>>T; while(T--){ int i; scanf("%d%d%d",&n,&m,&q); scanf("%s",s+1); scanf("%s",t+1); m1.clear(); nxt[0]=-1; int cnt=0; for(int i=1;i<=m;i++){ int p=nxt[i-1]; while(p>=0&&t[p+1]!=t[i]) p=nxt[p]; nxt[i]=p+1; } int len=m-nxt[m]; if(nxt[m]*2<m) len=m; Hash(); node x={0,0}; for(i=1;i<=m;i++){ ll h1=(x.l*base%mod1+(t[i]-'0')+mod1)%mod1; ll h2=(x.r*base%mod2+(t[i]-'0')+mod2)%mod2; x={h1,h2}; } for(i=1;i<=m;i++){ ll h1=(x.l*base%mod1+(t[i]-'0')-(ll)(t[i]-'0')*p1[m]%mod1+mod1)%mod1; ll h2=(x.r*base%mod2+(t[i]-'0')-(ll)(t[i]-'0')*p2[m]%mod2+mod2)%mod2; x={h1,h2}; if(!m1[h1+h2]){ m1[h1+h2]=++cnt; pos[cnt]=i; } } while(q--){ ll x,y; scanf("%lld%lld",&x,&y); auto tmp=get(x,x+m-1); if(!m1[tmp]){ printf("0 "); } else{ int d=m1[tmp]; printf("%lld ",(ll)(y-pos[d])/len+1); } } } return 0; }
I 赵文泽牛逼
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod =1e9; ll a[512345]; int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); if(n==2){ printf("0 2 1 3 "); continue; } if(n==3) { printf("1 4 2 5 3 6 "); continue; } for(int i=0;i<n-1;i++) printf("%d %d ",i,i+n); printf("%d %d ",3*n-4,4*n-5); } }
J 贪心
#include<bits/stdc++.h> using namespace std; typedef long long ll; int vis[123456]; int main(){ int t; scanf("%d",&t); while(t--){ memset(vis,0,sizeof vis); ll n; scanf("%lld",&n); string s; cin>>s; if(((1ll+n)*n/2)%2!=0){ puts("-1"); continue; } ll t=(1ll+n)*n/2/2; for(int i=n;i>=1;i--){ if(i<=t){vis[i]=1;t-=i;} } for(int i=0;i<(int)s.size();i++){ if(s[i]=='0'){ if(vis[i+1]){ printf("1"); }else{ printf("2"); } }else{ if(vis[i+1]){ printf("3"); }else printf("4"); } } printf(" "); } }
K 简单模拟
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=4e5+10; int g[N]; int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; int i; int flag=0; for(i=1;i<=n;i++){ char c; int x; cin>>c; if(c=='W'){ g[i]=3*m+1; flag=i; } else{ cin>>x; if(c=='C'){ g[i]=x; } else if(c=='B'){ g[i]=m+x; } else{ g[i]=2*m+x; } } } g[n+1]=3*m+1; if(!flag){ if(g[1]>g[2])cout<<1<<endl; else cout<<3*m-n+1<<endl; } else{ if(flag==1){ cout<<g[2]-1<<endl; } else if(flag==2){ cout<<g[3]-g[1]<<endl; } else{ if(g[1]>g[2])cout<<1<<endl; else cout<<g[flag+1]-g[flag-1]-1<<endl; } } } }
L 签到
#include<iostream> #include<string> #include<algorithm> #define LL long long using namespace std; struct word { string s; LL f; }w[105]; bool cmp(word a,word b) { if(a.f==b.f) return a.s<b.s; return a.f>b.f; } int main() { int T; cin>>T; while(T--) { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>w[i].s>>w[i].f; sort(w+1,w+n+1,cmp); LL ans=0; for(int i=1;i<=m;i++) { ans+=((m-i+1)*w[i].f); } cout<<ans; for(int i=1;i<=m;i++) cout<<" "<<w[i].s; cout<<endl; } return 0; }
M 签到
#include<bits/stdc++.h> using namespace std; int a[123456]; int main(){ int t; scanf("%d",&t); while(t--){ int n;int x; scanf("%d%d",&n,&x); int f=0; for(int i=0;i<n;i++){ int y;scanf("%d",&y); if((x+y) % 7==0)f=1; } if(f)puts("Yes"); else puts("No"); } }