Codeforces Round #616 (Div. 2)
A Even But Not Even
题意描述
给一个数，问能否去掉一定的位数将数字变为1个 所有数位加起来的和是偶数但是本身是奇数的数字；
题解
只要数字本身所有数位的数字含有两个奇数就可以
B Array Sharpening
题意描述
给定一个数列，问能否通过将数列的每一个元素减去一个任意数（使其本身不小于0），最终使得数列变为一个严格先单增后单减的数列
题解
如果数列长度为奇数 (n),
每个元素都大于等于最小元素即可，特判排除掉偶数的(a_{n/2})(a_{n/2+1})(n/2-1)
C Mind Control
题意描述
对于一个数列，每次可以选择数列的首元素或者尾元素取出，现在对数列进行m次取值操作，但是可以控制前m次的k次取首元素或者尾元素，而其余次不能控制，问能取到的最小元素是多少
题解
直接暴力,模拟每次控制操作取到的位置，再模拟每次任意操作取到的最终的位置，o(n^2);
#include<bits/stdc++.h>
using namespace std;
long long n,m,t,k,l,o,r,ans,max1=0;
long long a[1000001];
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
max1=0;
k=min(k,m-1);
for(int j=0;j<=k;j++)
{
int l=j+1,r=n-(k-j);
ans=1e9+7;
for(int i=0;i<=m-k-1;i++)
{
ans=min(ans,max(a[l+i],a[r-(m-k-1-i)]));
}
max1=max(max1,ans);
}
cout<<max1<<endl;
}
}
D Irreducible Anagrams
题意描述
询问s串第l到r个位置的字符串t,是不是t存在一个排列x使得不存在(i)<|t|,使得t1->ti和x1到xi的字母出现的次数不同
题解
如果字符串t的首字母和尾字母不同，则必可以将首字母放置在末尾使得成立，若首字母和尾字母相同，则判断中间是否存在两个不同的其余字母，将顺序导致放于首尾即可
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+50;
int s[N][26];
char t[N];
int main() {
cin>>t;
int y = strlen(t);
for(int i=1; i<=y; i++) {
for(int j=0; j<=25; j++) {
s[i][j] = s[i-1][j];
}
s[i][t[i-1]-'a']++;
}
int h = 0;
cin>>h;
while(h--) {
int l,r;
cin>>l>>r;
int cnt=0;
for(int i=0; i<=25; i++) {
if(s[r][i]-s[l][i]>0)
cnt++;
}
if(l==r||cnt>=3||t[l-1]!=t[r-1])
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
E Prefix Enlightenment
题意描述
有n盏灯，k个操作，每个操作可以保证使得部分灯亮或暗，使得1个灯变亮变暗的操作数最多只有两个，询问将前n盏灯变为都亮的每次的最小操作数是多少
题解（转自codeforce）
The condition "the intersection of any three subsets is empty" can be easily rephrased in a more useful way: each element appears in at most two subsets.
Let's suppose for the moment that each elements appears in exactly two subsets. We can think of each element as an edge between the subsets, it's a classical point of view. If we see subsets as nodes, we can model the subsets choice by coloring nodes into two colors, "taken" or "non-taken".
If an element is initially off, we need to take exactly one of the subsets containing it. The corresponding edge should have endpoints with different color. If an element is initially on, we must take none or both subsets : endpoints with same color.
We recognize a sort of bipartition, obviously there are at most two correct colorings for each connected component: fixing the color of a node fix the color of all connected nodes.
Hence, the final answer is the sum for each component, of the size of the smaller side of the partition.
Since the answer exists for i=ni=n, there exists a such partition of the graph (into "red" and "blue" nodes). We can find it with usual dfs, and keep it for lower values of ii.
In order to compute all mimi efficiently, we start from a graph with no edges (i=0i=0), and we add edges with DSU, maintaining in each connected component the count of nodes in red side, and the count of nodes in blue side.
Now, how to deal with elements that appears in exactly one subset? They don't add any edge in the graph, but they force to take one of the sides of the connected component. To simulate this, we can use a special forced flag, or just fix the count of the other side to +∞+∞ (but be careful about overflow if you do that).
Final complexity : O((n+k)⋅α(k))