Codeforces Round #616 (Div. 2) 题解

Codeforces Round #616 (Div. 2) 题解

**A. **

题意：
定义一个数所有位置的和为偶数它本身不为偶数的数为ebne,现在给你一个数字字符串，你可以删除任意位置上的数字使其变为ebne输出任意改变后的结果，如果不能则输出-1
分析：
如果奇数的个数>=2，则输出前两个奇数
代码：

#include<iostream>
#include<algorithm>
#include<string>
 using namespace std;
 int main()
 {
     int t,n;
     scanf("%d",&t);
     while(t--){
         string a,b;
         cin>>n>>a;
         for(int i=0;i<n;i++){
             if((a[i]-'0')%2)
                 b+=a[i];
         }
        if(b.length()<2)    cout<<"-1"<<endl;
        else    cout<<b.substr(0,2)<<endl;
     }
    return 0;
  }

**B. **

题意：
给你一个数组，你可以对任意位置上的元素进行任意次的减1操作(不能使元素小于0)，使得该数组变成一个先严格递增再严格递减的数组(也可以只升不降，只降不升)
分析：
从左右两边构造上升序列，a1 = an = 0， 公差为1。如果两个序列有交集，则合法。
代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int nbTests; cin >> nbTests;
    while (nbTests--) {
	    int nbElem; cin >> nbElem;
	    vector<int> tab(nbElem);

	    for (int i = 0; i < nbElem; ++i)
		    cin >> tab[i];

	    int prefixEnd = -1, suffixEnd = nbElem;

	    for (int i = 0; i < nbElem; ++i) {
		    if (tab[i] < i) break;
		    prefixEnd = i;
	    }
	    for (int i = nbElem-1; i >= 0; --i) {
		    if (tab[i] < (nbElem-1)-i) break;
		    suffixEnd = i;
	    }

	    if (suffixEnd <= prefixEnd) // Non-empty intersection
		    cout << "Yes\n";
	    else
		    cout << "No\n";
    }
}

**C. **

题意：
n个元素，n个人轮流取数，可以取数组头或尾元素，你在第m轮取，并且你可以控制k个人取什么元素，问你能取得最大元素是多少(前面的人不一定都取最大的)
分析：
k一定是用于在自己前面的人的身上，至于用于前面哪些人身上其实无关紧要。影响最终结果的是数列左右两边数的取走数量。对于左边：从0-k枚举听从命令的人，对于每次枚举，再枚举剩余的不听命令的人，对于内层枚举取最坏情况，对于外层枚举，取最好情况。
代码：

#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
 using namespace std;
 const int maxn=3510;
 int a[maxn],t,n,m,k;
 int main()
 {
     scanf("%d",&t);
     while(t--){
         scanf("%d%d%d",&n,&m,&k);
         for(int i=0;i<n;i++)    scanf("%d",&a[i]);
         k=min(m-1,k);
         int ans=-inf;
         for(int i=0;i<=k;i++){
             int x=inf;
             for(int j=0;j<m-k;j++)    x=min(x,max(a[i+j],a[n+i+j-m]));
            ans=max(ans,x);
         }
        cout<<ans<<endl;    
     }
    return 0;
 }

**D. **

题意：
若两个字符串中每个字符的个数都是一样的，则称他们互为anagrams。现在定义两个字符串s,t是reducible anagram的，必须满足下面的条件：
将s、t两个字符串分别拆成k(k>=2)个连续子串
s1,s2⋯sk 按顺序排列构成s
t1,t2⋯tk 按顺序排列构成t
∀i∈[1,k],都有si是ti的anagrams
现在给了一个字符串，每次询问它的一个字串是否存在一个irreducible anagram（请注意这些概念必须是以s是t的anagrams前提下进行的）
分析：
对于每个询问的字符串s，是否存在一个字符串t，使得t是s的irreducible anagram.分析题目条件可以将问题转换为：在t和s的任意等长前缀中，它们的字符集的个数必须是不同的（也就是确保它们不是anagrams)
我们声明满足下面条件的字符串存在irreducible anagram
1、长度等于1
2、首字符和尾字符不同
3、字符串包含至少三种不同的字符
求证这些条件后，利用前缀和的技巧可以很容易的解决本题。下面试证一下：

长度等于1，那么就无法找到一个 k(k>=2) ，所以它的irreducible anagram就是它本身
s[1]≠s[n] 即首字符和尾字符不同，我们可以尽量靠前的将所有同s[n]一样的字符写在前面。然后剩下的字符随便放置即可。可以想到对于任意的k∈[1,n−1],都满足s[1..k]与t[1..k]的字符集不同。
字符串包含至少三种不同的字符，并且s[1]=s[n]。可以找到一个最大的j满足s[j]≠s[n]。可以把所以同s[j]一样的字符放到最前面，然后紧挨着中间放置所有同s[n]的字符，因为不同字符个数大于等于3，所以现在最后面肯定还有空位，将剩余的字符随意放置在最后面即可。可以想到构成的这样的一个串，一定满足任意前缀字符集不等。
到此为止就可以放心做题了，但试图证明一下为何s[1]=s[n] and 不同字符个数等于2的情况为何找不到。
假设字符只有a和b两种，而且s[1]=s[n]=a,那么我们构造出来的串必须满足任意前缀中b的个数，都大于s对应前缀中b的个数。那么考虑s中最后出现b的位置x,可以想到s[1..x−1]前缀比t[1..x−1]少一个b，而s[x]=b得出现使得t[x]必须再放置一个b,这样才能满足任意前缀中b得个数都要比s多，但此时已经没有b可以放了（因为s[1..x−1]就已经多放了一个b）所以在x这个位置，无法构造。
代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
char s[maxn];
int pre[maxn][27];

int main()
{
	ios::sync_with_stdio(false);
  	cin.tie(0);
	cin >> (s + 1);
	int len = strlen(s + 1);
	for(int i = 1; i <= len; i++)
	{
		memcpy(pre[i], pre[i - 1], sizeof(pre[i]));
		pre[i][s[i] - 'a' + 1]++;
	}
	int q; cin >> q;
	while(q--)
	{
		int l, r; cin >> l >> r;
		if(l == r)
			cout << "Yes" << endl;
		else if(s[l] != s[r])
			cout << "Yes" << endl;
		else
		{
			int cnt = 0;
			for(int i = 1; i <= 26; i++)
				cnt += (pre[r][i] - pre[l][i]) > 0;
			if(cnt >= 3)
				cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
}