A - Dreamoon and Ranking Collection
题意：（这个题意太难懂了/(ㄒoㄒ)/~~）给n场比赛的排名，n场比赛后还有x场比赛，求n+x场比赛后排名从1开始能连续的最大的排名数
题解：用数组b记录排名出现的次数，来判断这个排名数有没有出现过。然后从排名1开始，如果这个排名没有出现过，x--，用x里的一场比赛来填补这个名次，直到x=0为止；然后从排名1开始找，找到最大的排名
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> using namespace std; int a[110]; int b[210]; int main(){ int t; cin>>t; while(t--){ int n,x; cin>>n>>x; memset(b,0,sizeof(b)); for(int i=1;i<=n;i++){ cin>>a[i]; b[a[i]]++; } for(int i=1;x>0&&i<=200;i++){ if(b[i]==0){ b[i]=1; x--; } } for(int i=1;;i++){ if(b[i]==0){ cout<<i-1<<endl; break; } } } return 0; }
B - Dreamoon Likes Permutations
题意：将一个长度为n的数组从中间断开分为两个全排列，判断能不能把数组分为两个全排列，如果可以输出可能的情况，和每种情况两全排列的长度。
如果m个整数的序列包含从1到m的所有整数，那么这个序列称为全排列。数字m被称为排列的长度。
题解：maxx为最短全排列里的最大值如果能把数组a分成两个全排列p1和p2，那么两全排列的长度一个为maxx,另一个为n-maxx，会有几种情况
1.不能分成两个全排列（可以分成两个以上）如 1 1 1
2.从中间分开只有一个或0个是全排列；如2 1 1 3和1 3 3 1
3.前maxx个，和后n-maxx可以构成；前n-maxx和后maxx也可以构成；如：1 4 3 2 1 （两个全排列可能相同）
4.只有前maxx和后n-maxx可以 或者 只有前n-maxx和后maxx可以构成，如2 4 1 3 2 1
#include<iostream> #include <cstdio> #include<cstring> #include <algorithm> #define maxn 200010 using namespace std; int a[maxn],cnt[maxn],b[maxn],n; int judge(int l,int r){//判断是否能构成一个全排列 int i,m; m=r-l+1; for(i=1;i<=m;i++){ b[i]=a[l+i-1]; } sort(b+1,b+1+m); for(i=1;i<=m;i++){ if(b[i]!=i){ return 0; } } return 1; } int main(){ ios::sync_with_stdio(false); int i,j,maxx,counts; int t,l1,r1,l2,r2; cin>>t; while(t--){ cin>>n; memset(cnt,0,sizeof(cnt)); for(i=1;i<=n;i++){ cin>>a[i]; cnt[a[i]]++; } maxx=0; for(i=1;i<=n;i++){ if(cnt[i]==2){ maxx=i; //找到最短全排列里的最大值 }else{ break; } } if(maxx==0){ cout<<"0"<<endl; }else{ counts=0,l1=0,r1=0,l2=0,r2=0; if(judge(1,maxx)&&judge(maxx+1,n)){ counts++; l1=maxx,r1=n-maxx; } if(judge(1,n-maxx)&&judge(n-maxx+1,n)){ counts++; l2=n-maxx,r2=maxx; } if(counts==2){ if(maxx==n-maxx){//如果分成的两个全排列相同 cout<<"1"<<endl; cout<<maxx<<" "<<n-maxx<<endl; }else{ cout<<2<<endl; cout<<maxx<<" "<<n-maxx<<endl; cout<<n-maxx<<" "<<maxx<<endl; } }else if(counts==1){//情况4 cout<<1<<endl; if(l1){//判断是情况4里面的那种 cout<<l1<<" "<<r1<<endl; }else{ cout<<l2<<" "<<r2<<endl; } }else{ cout<<"0"<<endl; } } } return 0; }
C - Exercising Walk
题意：猫位于（u,v）,你需要总的向左移动a步，向右移动b步，向下移动c步，向上移动d步。可以按任何顺序移动。并且在移动过程中x1<=x<<x2,y1<=y<=y2,开始的位置是（x，y）,判断能否按要求移动
题解：1.当x=x1=x2,且a!=0，b!=0时，需要移动但无移动空间所以不能按要求移动；同理，y=y1=y2，c!=0,d!=0时,也不能；
2.向左a步，向右b步就相当于向左 left=a-b步；向下c步。向上d步，相当于向上up=d-c步；如果满足（x-left<=x2)&&(x-left>=x1)&&(y+up>=y1)&&(y+up<=y2),可以按要求实现移动，否则不可以
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; int main(){ int t ; cin>>t; while(t--){ ll a,b,c,d; cin>>a>>b>>c>>d; ll x,y,x1,y1,x2,y2; cin>>x>>y>>x1>>y1>>x2>>y2; ll left,up; left=a-b,up=d-c; if((x==x1&&x==x2&&a!=0&&b!=0)||(y==y1&&y==y2&&c!=0&&d!=0)){ cout<<"NO"<<endl; }else if((x-left<=x2)&&(x-left>=x1)&&(y+up>=y1)&&(y+up<=y2)){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } return 0; }
D - Composite Coloring
题意：给n个合数的序列a1,a2.....an,为这些数涂色，帮助爱丽丝找到所需的颜色。不需要最小化或最大化颜色的数量，你只需要找到从1到11的m的解。对涂色有以下要求
1.对于从1到m的每一种颜色，该颜色至少有一个元素;
2.每个元素都有颜色，而且颜色只有一种;
3.两个颜色相同的元素的最大公约数大于1，即如果gcd(ai, aj) > 1，则ai,aj被涂为相同的颜色
题解：因为每一合数都可以以唯一形式被写成质数的乘积，所以找到合数的最小的质数因子把他们图为相同的颜色就可以
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int a[1010],flag[1010]; int main(){ int t; cin>>t; while(t--){ memset(flag,0,sizeof(flag)); int n,x,i,j,counts=0; cin>>n; for(i=1;i<=n;i++){ cin>>x; for(j=2;j<=x;j++){ if(x%j==0){ if(flag[j]==0){ counts++; a[i]=counts; flag[j]=counts; }else{ a[i]=flag[j]; } break; } } } cout<<counts<<endl; for(i=1;i<=n;i++){ cout<<a[i]<<" "; } cout<<endl; } return 0; }
E - K-th Beautiful String
题意：对于每组测试样例，给出n和k，表示有n长度的ab串，由n-2个a和2个b组成，k表示输出第k个字典序
题解：通过观察发现倒数第二个b有n-1种形态，第x种形态对应着倒数第一个b的x种形态，找到第k个属于第几大组；
若为第i大组，则倒数第二个b的位置为倒数第i+1个，即正数n-i个；倒数第一个b的位置为倒数 j=（k-（i-1）*（i-1+1）/2）个，即正数n-j+1个
#include<iostream> #include<cstdio> #include<cmath> #include<string> using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll n,k,i,j,sum=0,temp=0; cin>>n>>k; for(i=1;;i++){ if(k>sum&&k<=sum+i){ j=i; break; } sum+=i; } temp=k-j*(j-1)/2; for(i=1;i<=n;i++){ if(i==n-j||i==n-temp+1){ cout<<"b"; }else{ cout<<"a"; } } cout<<endl; } return 0; }
F - Carousel：
题解：n个木马围成圈，编号从1到n,给每个木马涂上一种颜色]，要求相邻属性不同的木马颜色不同，问最少需要多少种颜色，并输出涂色方案
属性相同的木马颜色可以不同也可以相同
题意： 1.如果所有木马属性都相同，最少需要一种颜色（特判）
2.如果n为偶数，两种颜色间隔涂，最少需要两种颜色
3.如果n为奇数，有两个木马类型相同且相邻，把这两个木马看成一个，按偶数涂，最少需要两种颜色
没有两个木马相邻且相同，还是两种颜色交替涂，但最后一个木马涂3，最少需要三种颜色
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<string> using namespace std; typedef long long ll; #define maxn 200010 int a[maxn],c[maxn]; int main(){ int q; cin>>q; while(q--){ int n; cin>>n; int flag=0; for (int i=1;i<=n;i++){ cin>>a[i]; if(a[i]==a[1]){ flag++; } } if(flag==n){ cout<<"1"<<endl; for(int i=1;i<n;i++){ cout<<"1"<<" "; } cout<<"1"<<endl; continue; } c[1]=0; for(int i=2;i<=n-1;i++){ if(c[i-1]==1){ c[i]=0; }else{ c[i]=1; } } if(n&1){ for(int i=2; i<=n-1;i++){ if(a[i]==a[i-1]){ for(int j=i;j<=n-1;j++){ if(c[j]==1) c[j]=0; else c[j]=1; } break; } } } int ans=2; if(c[n-1]==c[1]){ if(c[1]==1){ c[n]=0; }else{ c[n]=1; } }else { if (a[n]!=a[n-1]&&a[n]!=a[1]){ ans=3; c[n]=2; }else{ if(a[n]==a[1]){ c[n]=c[1]; }else{ c[n]=c[n-1]; } } } cout<<ans<<endl; for (int i=1;i<n;i++){ cout<<c[i]+1<<" " ; } cout<<c[n]+1<<endl; } return 0; }