Codeforces Round #616 (Div. 2) -A,B,C,D 2020/05/13 补题 codeforces-1291-A. Even But Not Even codeforces-1291-B. Array Sharpening codeforces-1291-C. Mind Control codeforces-1291-D. Irreducible Anagrams
codeforces-1291-A. Even But Not Even
传送门 https://codeforces.com/contest/1291/problem/A
题意：定义“偶数”是数字每一位之和为偶数，但尾数是奇数，给你一串数字，让你通过删除这串数字的某些位，不能改变数字位置，让这串数变成“偶数”
其实不用考虑位数之和啊结尾是奇数还是偶数，直接找串中的两个奇数输出就可以，因为要求结尾是奇数（get一个了），又因为和是偶数，所以至少还存在一个奇数，输出即可，找不到两个奇数就是不可能
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define lowbit(a) ((a)&-(a)) 5 #define clean(a,b) memset(a,b,sizeof(a)) 6 const int mod = 1e9 + 7; 7 const int inf=0x3f3f3f3f; 8 const int maxn = 2e5+9; 9 10 inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();} 11 int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;} 12 13 int _; 14 //================================================================== 15 int a[maxn]; 16 //================================================================== 17 int main() 18 { 19 vector<int>ve; 20 // freopen("in.in","r",stdin); 21 scanf("%d",&_); 22 while(_--) 23 { 24 ve.clear(); 25 int n; 26 scanf("%d",&n); 27 int cnt=0,cnt_=0; 28 for(int i=1;i<=n;i++) 29 { 30 scanf("%1d",&a[i]); 31 if(a[i]%2) ve.push_back(i); 32 } 33 if(ve.size()<2) puts("-1"); 34 else 35 { 36 printf("%d%d ",a[ve[0]],a[ve[1]]); 37 } 38 } 39 return 0; 40 }
codeforces-1291-B. Array Sharpening
传送门：https://codeforces.com/contest/1291/problem/B
题意：我们定义“山峰”为存在一个k(1<=k<=n) 使得 ，给你一个序列，可以给每个正数-n问你能不能把他变成“山峰”
假设是最有可能是“山峰”的情况，那就是把他变成0，1，2，3，4…… 和 ……4，3，2，1，0 （分别是k在开头和结尾），然后我们“枚举”k的位置，看可不可行，用a[i]减掉最小的情况，得到你要减1的次数n，如果小于0，这个方案就是不可行的，因为这个题没问有多少种情况，只要有一种可行就是yes，所以我们得到减完最小情况的两个数组，分别从前往后（从后往前）找一下最右（左）的>=0的位置fr和la，如果fr>=la就是yes啦
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define lowbit(a) ((a)&-(a)) 5 #define clean(a,b) memset(a,b,sizeof(a)) 6 const int mod = 1e9 + 7; 7 const int inf=0x3f3f3f3f; 8 const int maxn = 3e5+9; 9 10 inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();} 11 int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;} 12 13 int _; 14 //================================================================== 15 int fron[maxn],last[maxn],a[maxn]; 16 //================================================================== 17 int main() 18 { 19 // freopen("in.in","r",stdin); 20 scanf("%d",&_); 21 while(_--) 22 { 23 int n=read(); 24 for(int i=0;i<n;i++) 25 { 26 scanf("%d",&a[i]); 27 fron[i]=a[i]-i; 28 last[i]=a[i]-(n-1-i); 29 } 30 int fr=0,la=0; 31 for(int i=0;i<n;i++) 32 { 33 if(fron[i]<0) break; 34 fr=i; 35 } 36 for(int i=n-1;i>=0;i--) 37 { 38 if(last[i]<0) break; 39 la=i; 40 } 41 if(fr<la) puts("No"); 42 else puts("Yes"); 43 } 44 return 0; 45 }
codeforces-1291-C. Mind Control
传送门：https://codeforces.com/contest/1291/problem/C
题意：一共有n个人和n个数字，排成两列，你站在第m个位置，按顺序从序列里拿数（只能拿开头或者结尾），你有k次机会劝你前面的人拿走你想让他们拿走的数，当然其他人拿走哪里的就不归你管了，你想拿到的数越大越好，问这些情况里你拿到的最小值是多少
感觉最近都念不懂题了呢，w(ﾟДﾟ)w，你有k次机会劝别人，首先如果k>m-1，那多出来的都没用，先k=min(k,m-1)，然后这k个人是按照你的意愿来的，是确定的那就有m-1-k个人是不受控制的，数据范围挺小的，可以考虑暴力解决，枚举前K个人有i个选了前面，有j个不确定的人选了前面，然后到他自己的时候指定是有选前面和后面两种选择取最优，因为j个是不确定的，所以应该考虑最坏的情况，取最小值，最外层循环受自己控制，取最大值
然后算你选完了的时候剩下n-m，也就是说当轮到你时如果开头是a[i+j]那么结尾就是a[i+j+n-m]
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define lowbit(a) ((a)&-(a)) 5 #define clean(a,b) memset(a,b,sizeof(a)) 6 const int mod = 1e9 + 7; 7 const int inf=0x3f3f3f3f; 8 const int maxn = 3e5+9; 9 10 inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();} 11 int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;} 12 13 int _; 14 //================================================================== 15 int a[maxn]; 16 //================================================================== 17 int main() 18 { 19 // freopen("in.in","r",stdin); 20 scanf("%d",&_); 21 while(_--) 22 { 23 int n=read(),m=read(),k=read(); 24 for(int i=0;i<n;i++) 25 { 26 scanf("%d",&a[i]); 27 } 28 k=min(k,m-1); 29 int ans=0; 30 for(int i=0;i<=k;i++) 31 { 32 int temp=inf; 33 for(int j=0;j<=m-k-1;j++) 34 { 35 temp=min(temp,max(a[i+j],a[i+j+n-m])); 36 } 37 ans=max(ans,temp); 38 } 39 printf("%d ",ans); 40 } 41 return 0; 42 }
codeforces-1291-D. Irreducible Anagrams
传送门：https://codeforces.com/contest/1291/problem/D
题意：我们定义“字谜”是两个字符串的长度和内容一样，但字母的顺序不一样，“可约字谜”是这两个字符串可以分成k个部分，每个部分都是“字谜”，现在给你一个串 s，每次询问一个子串，问是否至少存在一个串使得该串与子串是一对“字谜”但不是“可约字谜”
同 题好难翻译啊
首先长度为1的子串一定 yes，因为分不成k个
如果开头和结尾字母不同，那也yes，构造时把所有和尾字符相同的移到开头，头字符相同的移到结尾那也yes，无法分成k个串，你一分，开头和结尾的数量指定对不上
如果字符种类数不小于3，并且头尾字符相同，我们可以将除头尾字符外的任意两种字符分别全部移到头尾，显然 Yes 原理同上
其他就no
然后你暴力的遍历l-r查字符种类会t掉
所以想到这问题变成了，怎么快速找l-r字符种类
先想什么时候r-l字符种类减少了，当然是1-r中这个字符的数量和1-l中这个字符的数量相等，所以利用前缀和的知识，我们开个二维数组mp[i][j]第i个字符的字母j出现的次数，mp[r][j]-mp[l-1][j]>0 cnt++
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define lowbit(a) ((a)&-(a)) 5 #define clean(a,b) memset(a,b,sizeof(a)) 6 const int mod = 1e9 + 7; 7 const int inf=0x3f3f3f3f; 8 const int maxn = 2e5+9; 9 10 inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();} 11 int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;} 12 13 int _; 14 //================================================================== 15 char s[maxn]; 16 int mp[maxn][30]; 17 //================================================================== 18 int main() 19 { 20 // freopen("in.in","r",stdin); 21 scanf("%s",s+1); 22 int l=strlen(s+1); 23 for(int i=1;i<=l;i++) 24 { 25 for(int j=0;j<26;j++) 26 { 27 if(j==s[i]-'a') mp[i][j]=mp[i-1][j]+1; 28 else mp[i][j]=mp[i-1][j]; 29 } 30 } 31 int n; 32 scanf("%d",&n); 33 for(int i=1;i<=n;i++) 34 { 35 int l=read(),r=read(); 36 if(l==r) puts("Yes"); 37 else if(s[l]!=s[r]) puts("Yes"); 38 else 39 { 40 int cnt=0; 41 for(int j=0;j<26;j++) 42 { 43 if(mp[r][j]-mp[l-1][j]>0) cnt++; 44 45 } 46 if(cnt>=3) puts("Yes"); 47 else puts("No"); 48 } 49 } 50 return 0; 51 }