A：http://codeforces.com/contest/1462/problem/A
#include<iostream> #include<cstring> #include<map> #include<stack> #include<queue> #include<algorithm> #include<cstdio> #include<cmath> #include<string.h> using namespace std; typedef long long ll; const int maxn=2e4+10; const int inf=99999999; int a[maxn]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int cnt=0; int l=1; int ok=0; int md=n-1; while(1) { if(cnt==n) break; if(!ok) { cout<<a[l]<<" "; l=l+md; md--; ok=1; } else { cout<<a[l]<<" "; l=l-md; md--; ok=0; } cnt++; } cout<<endl; } }
B：http://codeforces.com/contest/1462/problem/B
题意：
给定一个字符串，能否最多删除一段连续的一段使得剩下的为“2020”
解析：
无非就六种情况，直接列一遍就好了
#include<iostream> #include<cstring> #include<map> #include<stack> #include<queue> #include<algorithm> #include<cstdio> #include<cmath> #include<string.h> using namespace std; typedef long long ll; const int maxn=2e4+10; const int inf=99999999; int a[maxn]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; string s; cin>>s; int le=s.length(); if(s=="2020") { cout<<"YES"<<endl; } else { if(s[0]=='2'&&s[1]=='0'&&s[2]=='2'&&s[3]=='0') { cout<<"YES"<<endl; } else if(s[0]=='2'&&s[1]=='0'&&s[2]=='2'&&s[le-1]=='0') { cout<<"YES"<<endl; } else if(s[0]=='2'&&s[1]=='0'&&s[le-2]=='2'&&s[le-1]=='0') { cout<<"YES"<<endl; } else if(s[0]=='2'&&s[le-3]=='0'&&s[le-2]=='2'&&s[le-1]=='0') { cout<<"YES"<<endl; } else if(s[le-4]=='2'&&s[le-3]=='0'&&s[le-2]=='2'&&s[le-1]=='0') { cout<<"YES"<<endl; } else cout<<"NO"<<endl; } } }
C：http://codeforces.com/contest/1462/problem/C
题意：
输出最小的数位和等于x并且各个数位都不一样的值
解析：
在纸上写了一下，发现每一个存在的答案，都是从个位开始，数字越来越小。所以从9开始枚举即可。
#include<iostream> #include<cstring> #include<map> #include<stack> #include<queue> #include<algorithm> #include<cstdio> #include<cmath> #include<string.h> using namespace std; typedef long long ll; const int maxn=2e4+10; const int inf=99999999; int a[maxn]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; if(n<=9) { cout<<n<<endl;continue; } if(n>45) { cout<<"-1"<<endl;continue; } int sum=0; int num[111]; int tot=0,ok=0; int all=n; for(int i=9;i>=1;i--) { if(sum+i>n) continue; sum+=i; num[tot++]=i; if(sum==n) { ok=1;break; } } if(ok) { for(int i=tot-1;i>=0;i--) cout<<num[i]; cout<<endl; } else cout<<"-1"<<endl; } }
D：http://codeforces.com/contest/1462/problem/D
题意：
给出一个序列，每个数可以与左或右合并，这算一个操作。求使得所有数相同的最少操作数。
解析：
其实所谓所有数相同，就是把整个原数分成几份，每一份加和相等。
所以先求出总和sum，枚举它的因子x，求一下每份和为x , sum / x的所需操作数，求个最小值即可。
#include<iostream> #include<cstring> #include<map> #include<algorithm> #include<stack> #include<queue> #include<cstdio> #include<cmath> #include<string.h> using namespace std; typedef long long ll; const int maxn=3e3+10; const int inf=99999999; int a[maxn]; int n; ll num[maxn]; ll sum=0; int ac(int x) { int all=sum/x; int ans=0; int cnt=0; int ok = 0 ; for(int i=1;i<=n;i++) { if(a[i]>x) return -1; if(a[i]==x&&ans<x&&ans>0) return -1; if(ans+a[i]==x) { if(ans>0) cnt++; ans=0; } else if(ans+a[i]<x) { if(ans>0) cnt++; ans+=a[i]; } else { return -1; } } return cnt; } int main() { int t; scanf("%d",&t); while(t--) { cin>>n; sum = 0 ; for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i]; int no=0; for(int i=1;i<n;i++) { if(a[i]!=a[i+1]) { no=1;break; } } if(!no) { cout<<"0"<<endl;continue; } // cout<<ac(sum/2)<<endl; int ok = 0; int an=inf; for(int i=2;i*i<=sum;i++) { if(sum%i==0) { int md1=ac(i); int md2=ac(sum/i); if(md1!=-1) { an=min(an,md1); // cout<<i<<"--1"<<endl; ok=1; } if(md2!=-1) { an=min(an,md2); // cout<<i<<"--2"<<endl; ok=1; } } } if(!ok) cout<<n-1<<endl;//不存在，那么全合并即可 else cout<<an<<endl; } }
E1：http://codeforces.com/contest/1462/problem/E1
题意：
求有多少组ai,aj,az，max(ai,aj,az)-min(ai,aj,az)<=2
解析:
由于这三个数并不需要挨着，所以顺序无所谓。那么可以先从小到大排个序。
枚举最小值ai，向右找到第一个aj-ai>2的位置，那么i~j之间的数字随便选两个和ai组合就是一组答案，那么答案就是C(j-i-1,2)，累加即可。
#include<iostream> #include<cstring> #include<map> #include<algorithm> #include<stack> #include<queue> #include<cstdio> #include<cmath> #include<string.h> using namespace std; typedef long long ll; const int maxn=2e5+10; const int inf=99999999; int a[maxn]; int n; int main() { int t; scanf("%d",&t); while(t--) { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); ll sum = 0 ; int r=2; for(int i=1;i<=n;i++) { while(a[r]-a[i]<=2&&r<=n) r++; ll cnt=(r-i-1); if(cnt>=2) sum+=cnt*(cnt-1)/2; } cout<<sum<<endl; } }
E2：http://codeforces.com/contest/1462/problem/E2
与E1不同的是，所选数目以及最大差值可以自定义。
与E1思路相同，只是难点在求组合数这边。考虑m只有100，那么提前预处理一下组合数即可。
#include<iostream> #include<cstring> #include<map> #include<algorithm> #include<stack> #include<queue> #include<cstdio> #include<cmath> #include<string.h> using namespace std; typedef long long ll; const int maxn=2e5+10; const int inf=99999999; const int mod=1e9+7; int a[maxn]; int n,m,k; int c[maxn][130]; void init() { c[0][0]=1; c[1][0]=1;c[1][1]=1; for(int i=2;i<maxn;i++) { for(int j=0;j<=105&&j<=i;j++) { c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } } } int main() { int t; init(); scanf("%d",&t); while(t--) { cin>>n>>m>>k; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); ll sum=0; int r=1; for(int i=1;i<=n;i++) { while(a[r]-a[i]<=k&&r<=n) r++; ll cnt=(r-i-1); if(cnt>=m-1) { sum=(sum+c[cnt][m-1])%mod; } } cout<<sum<<endl; } }
F：http://codeforces.com/contest/1462/problem/F
题意：
给你n个线段，代表线段的左右端点，问最少删几条线段，使得剩下当中存在一个线段与所有剩下的所有线段都有交集。
解析：
考虑枚举每一条线段，求以此线段与所有线段都有交集，需要删除的线段数。
那么对于此线段[L,R]，右端点小于L的，与它无交集，需要全删掉。同理左端点大于R的线段，也需要都删掉。
那么剩下的问题，就是需要删几个了。
预存一下所有的L，R，放到x[]，y[]里面。对它们进行从小到大的排序。
对于当前枚举到的[L,R]，求小于L的右端点不好求，那就先求>=L的，就是：lower_bound(y+1,y+1+n,a[i])-y; 再减1，就是小于L的了：lower_bound(y+1,y+1+n,a[i])-y-1;
然后求大于R的左端点，n-(upper_bound(x+1,x+1+n,b[i])-x)+1;
加起来，每次取最小即可。
#include<iostream> #include<cstring> #include<map> #include<algorithm> #include<stack> #include<queue> #include<cstdio> #include<cmath> #include<string.h> using namespace std; typedef long long ll; const int maxn=2e5+10; const int inf=99999999; const int mod=1e9+7; int a[maxn],b[maxn],x[maxn],y[maxn]; int main() { int t; scanf("%d",&t); while(t--) { int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]>>b[i]; x[i]=a[i]; y[i]=b[i]; } sort(x+1,x+1+n); sort(y+1,y+1+n); ll minn = inf; for(int i=1;i<=n;i++) { ll l=lower_bound(y+1,y+1+n,a[i])-y-1; ll r=n-(upper_bound(x+1,x+1+n,b[i])-x)+1; minn=min(minn,l+r); } cout<<minn<<endl; } }