A - Circle of Students
题意：判断是否是1,2,3...n的排列或者n,n-1...2,1的排列
思路1：分类讨论，如果是递增的，ai-i的值固定，如果递减，ai+i的值固定
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int T,n,a[101010],flag; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { T=rd(); while(T--) { n=rd(); flag=1; rep(i,1,n) a[i]=rd(); rep(i,2,n) { if((a[i]-a[1]+n)%n!=(i-1)) flag=0; } if(flag) { printf("YES "); continue; } flag=1; rep(i,2,n) { if((a[i]+i)%n!=(a[1]+1)%n) flag=0; } if(!flag) printf("NO "); else printf("YES "); } }
思路2：直接做
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int T,n,a[101010],flag; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { T=rd(); while(T--) { n=rd(); flag=1; rep(i,1,n) a[i]=rd(); rep(i,2,n) { if(a[i]-1==a[i-1]) continue; else if(a[i]==1&& a[i-1]==n) continue; flag=0; } if(flag) { printf("YES "); continue; } flag=1; rep(i,2,n) { if(a[i]+1==a[i-1]) continue; else if(a[i]==n&& a[i-1]==1) continue; flag=0; } if(!flag) printf("NO "); else printf("YES "); } }
B - Equal Rectangles
题意：给你4*n个木棍，问你是否能组成n个面积相等的矩形
思路：按照边长排序，每次取头上的两根和尾巴的两根进行判断。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int T,n,a[101010],flag; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { T=rd(); while(T--) { n=rd();n=4*n; int ans=0; rep(i,1,n) a[i]=rd(); sort(a+1,a+1+n); flag=1; for(int i=1;i<=n/2;i+=2) { if(a[i]!=a[i+1]||a[n-i]!=a[n-i+1]) flag=0; if(ans==0) ans=a[i]*a[n-i]; else if(ans!=a[i]*a[n-i]) flag=0; } if(flag) printf("YES "); else printf("NO "); } }
C - Common Divisors
题意：求n个数的gcd的因子个数
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int T,n,a[101010],flag; ll x,ans; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll gcd(ll a,ll b ) { if(a==0) return b; return gcd(b%a,a); } int main() { while(~scanf("%d",&n)) { rep(i,1,n) { x=rd(); if(i==1) { ans=x; } else { ans=gcd(x,ans); } } int an=0; rep(i,1,sqrt(ans)) if(ans%i==0) { if(ans%i==0) an++; if(ans/i!=i) an++; } printf("%d ",an); } }
D2 - Remove the Substring (hard version)
题意：删掉T中最长的子串使得T仍然是S的子序列
思路：pre[i]记录T[i]这个字符最早出现的位置，nt[i]则是最晚位置，剪一下即可。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; char s[1010000],t[1010000]; int l1,l2,ans,pos,pre[1010000],nt[10000100]; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { scanf("%s",&s); scanf("%s",&t); l1=strlen(s); l2=strlen(t); int pos=0; rep(i,0,l1-1) { if(s[i]==t[pos]) { pre[pos]=i; pos++; if(pos>=l2) break; } } pos=l2-1; dep(i,0,l1-1) { if(s[i]==t[pos]) { nt[pos]=i; pos--; if(pos==-1) break; } } ans=nt[0]; nt[l2]=l1; rep(i,0,l2-1) { ans=max(ans,nt[i+1]-pre[i]-1); } printf("%d ",ans); }
E - Boxers
题意：给你一些数，每个数可以加1，减一或者不变，问你最多能变成几个不同的数。
思路：优先变小，然后变大，统计答案
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int n,ans; int b[301010],a[301010]; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll gcd(ll a,ll b ) { if(a==0) return b; return gcd(b%a,a); } int main() { n=rd(); rep(i,1,n) a[i]=rd(); sort(a+1,a+1+n); b[0]=1; rep(i,1,n) { if(b[a[i]-1]!=1) { b[a[i]-1]=1; ans++; } else if(b[a[i]]!=1) { b[a[i]]=1; ans++; } else if(b[a[i]+1]!=1) { b[a[i]+1]=1; ans++; } } printf("%d ",ans); }
F1 - Complete the Projects (easy version)
题意：有n个工程，每个工程有ai和bi的属性，表示做这个工程至少有ai的值，做完之后会加上bi，问你怎么安排使得所有工程能做完。
思路1：贪心，假设如果b>=0那么按照a从小到大排序，如果b<0那么按照a+b从大到小排序
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; struct node{ int a,b,len,c; }p[3010],q[3010]; int c[1010]; int n,r,a,b,flag,len,len1; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool cmp(node a,node b) { return a.a<b.a; } bool cmp1(node a,node b) { return a.c>b.c; } int main() { while(~scanf("%d",&n)) { r=rd(); len=0; len1=0; rep(i,1,n) { a=rd();b=rd(); if(b>=0) { p[++len].a=a; p[len].b=b; } else{ q[++len1].a=a; q[len1].b=b; q[len1].c=a+b; } } sort(p+1,p+1+len,cmp); flag=0; rep(i,1,len) { if(r>=p[i].a) r+=p[i].b; else { flag=1; break; } } if(flag==1) { printf("NO "); continue; } sort(q+1,q+1+len1,cmp1); rep(i,1,len1) { if(r>=q[i].a) r+=q[i].b; else { flag=1; break; } if(r<0) { flag=1; break; } //printf("%d ",r); } if(flag) printf("NO "); else printf("YES "); } }
思路2：搜索，b>=0和思路一一样，b<0 搜索答案。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int n,r,a,b,flag,len,len1; struct node{ int a,b; }p[3010],q[3010]; int c[1010]; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool cmp(node a,node b) { return a.a<b.a; } bool cmp1(node a,node b) { return a.b>b.b; } bool check() { if(r<0) return 1; rep(i,1,len1) if( c[i]==0&& q[i].a>r) { return 1; } return 0; } bool solve(int pos) { if(check()) return 0; if(pos==len1) return 1; int p=0; rep(i,1,len1) if(c[i]==0) { // if(q[i].a>p) { p=q[i].a; r+=q[i].b; c[i]=1; if( solve(pos+1)) return 1; c[i]=0; r-=q[i].b; } } return 0; } void work() { rep(i,1,len1) c[i]=0; int sum=0; rep(i,1,len1) sum+=q[i].b; //printf("%d %d ",sum,r); if(sum+r<0) { printf("NO "); return ; } //printf("1111"); if(solve(0)) printf("YES "); else printf("NO "); } int main() { while(~scanf("%d",&n)) { flag=0,len=0,len1=0; r=rd(); rep(i,1,n) { a=rd();b=rd(); if(b>=0) { p[++len].a=a; p[len].b=b; } else{ q[++len1].a=a; q[len1].b=b; } } sort(p+1,p+1+len,cmp); rep(i,1,len) { if(r>=p[i].a) r+=p[i].b; else { flag=1; break; } } if(flag==1) { printf("NO "); continue; } sort(q+1,q+1+len1,cmp1); work(); } }
F2 - Complete the Projects (hard version)
题意：有n个工程，每个工程有ai和bi的属性，表示做这个工程至少有ai的值，做完之后会加上bi，问你你可以安排所有工程的顺序，问你最多能做的工程数量。
思路1：搜索（TLE 72）
https://codeforces.com/contest/1203/my
思路2：dp
DP[I][J]表示做到第i个工程，等级为j的最大方案数是多少。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int maxm=70000; const int mod = 998244353; struct node{ int a,b,len,c; }p[3010],q[3010]; int c[1010]; int n,r,a,b,flag,len,len1; int dp[2][70000]; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool cmp(node a,node b) { return a.a<b.a; } bool cmp1(node a,node b) { return a.c>b.c; } int main() { while(~scanf("%d",&n)) { r=rd(); len=0; len1=0; rep(i,1,n) { a=rd();b=rd(); if(b>=0) { p[++len].a=a; p[len].b=b; } else{ q[++len1].a=a; q[len1].b=b; q[len1].c=a+b; } } sort(p+1,p+1+len,cmp); sort(q+1,q+1+len1,cmp1); int ans=len; rep(i,1,len) { if(r>=p[i].a) r+=p[i].b; else { ans=i-1; break; } } fill(dp[0],dp[0]+maxm,-n); dp[0][r]=ans; rep(i,1,len1) { int v=i&1,u=v^1; fill(dp[v],dp[v]+maxm,-n); rep(j,0,maxm-1) { dp[v][j]=max(dp[v][j],dp[u][j]); if(j>=q[i].a && j+q[i].b>=0) { dp[v][j+q[i].b]=max(dp[v][j+q[i].b],dp[u][j]+1); } } } cout<<*max_element(dp[len1&1],dp[len1&1]+maxm); } }