A. Even But Not Even
time limit per test1 second memory limit per test256 megabytes
Let's define a number ebne (even but not even) if and only if its sum of digits is divisible by 2 but the number itself is not divisible by 2. For example, 13, 1227, 185217 are ebne numbers, while 12, 2, 177013, 265918 are not. If you're still unsure what ebne numbers are, you can look at the sample notes for more clarification.
You are given a non-negative integer s, consisting of n digits. You can delete some digits (they are not necessary consecutive/successive) to make the given number ebne. You cannot change the order of the digits, that is, after deleting the digits the remaining digits collapse. The resulting number shouldn't contain leading zeros. You can delete any number of digits between 0 (do not delete any digits at all) and n-1.
For example, if you are given s=222373204424185217171912 then one of possible ways to make it ebne is: 222373204424185217171912 \rightarrow 2237344218521717191. The sum of digits of 2237344218521717191 is equal to 70 and is divisible by 2, but number itself is not divisible by 2: it means that the resulting number is ebne.
Find any resulting number that is ebne. If it's impossible to create an ebne number from the given number report about it.Input
The input consists of multiple test cases. The first line contains a single integer \(t (1 \le t \le 1000)\) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer \(n (1 \le n \le 3000) \) — the number of digits in the original number.
The second line of each test case contains a non-negative integer number s, consisting of n digits.
It is guaranteed that s does not contain leading zeros and the sum of n over all test cases does not exceed 3000.Output
For each test case given in the input print the answer in the following format:
- If it is impossible to create an ebne number, print "-1" (without quotes);
- Otherwise, print the resulting number after deleting some, possibly zero, but not all digits. This number should be ebne. If there are multiple answers, you can print any of them. Note that answers with leading zeros or empty strings are not accepted. It's not necessary to minimize or maximize the number of deleted digits.
ExampleinputCopy
4 4 1227 1 0 6 177013 24 222373204424185217171912
outputCopy
1227 -1 17703 2237344218521717191
Note
In the first test case of the example, 1227 is already an ebne number (as 1 + 2 + 2 + 7 = 12, 12 is divisible by 2, while in the same time, 1227 is not divisible by 2) so we don't need to delete any digits. Answers such as 127 and 17 will also be accepted.
In the second test case of the example, it is clearly impossible to create an ebne number from the given number.
In the third test case of the example, there are many ebne numbers we can obtain by deleting, for example, 1 digit such as 17703, 77013 or 17013. Answers such as 1701 or 770 will not be accepted as they are not ebne numbers. Answer 013 will not be accepted as it contains leading zeroes.
Explanation:
- 1 + 7 + 7 + 0 + 3 = 18. As 18 is divisible by 2 while 17703 is not divisible by 2, we can see that 17703 is an ebne number. Same with 77013 and 17013;
- 1 + 7 + 0 + 1 = 9. Because 9 is not divisible by 2, 1701 is not an ebne number;
- 7 + 7 + 0 = 14. This time, 14 is divisible by 2 but 770 is also divisible by 2, therefore, 770 is not an ebne number.
In the last test case of the example, one of many other possible answers is given. Another possible answer is: \(222373204424185217171912 \rightarrow 22237320442418521717191\) (delete the last digit).
签到，选两个奇数
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n;
char s[maxn];
void solve(){
scanf("%d%s",&n,s+1);
int cnt=0,ans=0;
rep(i,1,n){
if((s[i]-'0')%2) cnt++,ans=ans*10+s[i]-'0';
if(cnt==2) return (void)printf("%d\n",ans);
}
puts("-1");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. Array Sharpening
time limit per test1 second memory limit per test256 megabytes
You're given an array \(a_1, \ldots, a_n \)of n non-negative integers.
Let's call it sharpened if and only if there exists an integer \(1 \le k \le n\) such that\( a_1 < a_2 < \ldots < a_k and a_k > a_{k+1} > \ldots > a_n\). In particular, any strictly increasing or strictly decreasing array is sharpened. For example:
- The arrays [4], [0, 1], [12, 10, 8] and [3, 11, 15, 9, 7, 4] are sharpened;
- The arrays [2, 8, 2, 8, 6, 5], [0, 1, 1, 0] and [2, 5, 6, 9, 8, 8] are not sharpened.
You can do the following operation as many times as you want: choose any strictly positive element of the array, and decrease it by one. Formally, you can choose any \(i (1 \le i \le n)\) such that \(a_i>0 \)and assign \(a_i := a_i - 1\).
Tell if it's possible to make the given array sharpened using some number (possibly zero) of these operations.Input
The input consists of multiple test cases. The first line contains a single integer\( t (1 \le t \le 15\ 000) \) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer \(n (1 \le n \le 3 \cdot 10^5)\).
The second line of each test case contains a sequence of n non-negative integers \(a_1, \ldots, a_n (0 \le a_i \le 10^9)\).
It is guaranteed that the sum of n over all test cases does not exceed \(3 \cdot 10^5\).Output
For each test case, output a single line containing "Yes" (without quotes) if it's possible to make the given array sharpened using the described operations, or "No" (without quotes) otherwise.ExampleinputCopy
10 1 248618 3 12 10 8 6 100 11 15 9 7 8 4 0 1 1 0 2 0 0 2 0 1 2 1 0 2 1 1 3 0 1 0 3 1 0 1
outputCopy
Yes Yes Yes No No Yes Yes Yes Yes No
Note
In the first and the second test case of the first test, the given array is already sharpened.
In the third test case of the first test, we can transform the array into [3, 11, 15, 9, 7, 4] (decrease the first element 97 times and decrease the last element 4 times). It is sharpened because 3 < 11 < 15 and 15 > 9 > 7 > 4.
In the fourth test case of the first test, it's impossible to make the given array sharpened.
其实问题就是能否找到一个中心点使得他向两端延伸都合法，那么就正着跑一次反着跑一次就可以了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)4e5+100;
const int mod=(int)1e9+7;
int n,a[maxn],l[maxn],r[maxn];
void solve(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]),l[i]=r[i]=0;
rep(i,1,n){
if(a[i]>=i-1) l[i]=1;
else break;
}
dep(i,n,1){
if(a[i]>=n-i) r[i]=1;
else break;
}
rep(i,1,n) if(l[i]*r[i]) return (void)puts("Yes");
puts("No");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
C. Mind Control
time limit per test1 second memory limit per test256 megabytes
You and your n - 1 friends have found an array of integers \(a_1, a_2, \dots, a_n\). You have decided to share it in the following way: All n of you stand in a line in a particular order. Each minute, the person at the front of the line chooses either the first or the last element of the array, removes it, and keeps it for himself. He then gets out of line, and the next person in line continues the process.
You are standing in the m-th position in the line. Before the process starts, you may choose up to k different people in the line, and persuade them to always take either the first or the last element in the array on their turn (for each person his own choice, not necessarily equal for all people), no matter what the elements themselves are. Once the process starts, you cannot persuade any more people, and you cannot change the choices for the people you already persuaded.
Suppose that you're doing your choices optimally. What is the greatest integer x such that, no matter what are the choices of the friends you didn't choose to control, the element you will take from the array will be greater than or equal to x?
Please note that the friends you don't control may do their choice arbitrarily, and they will not necessarily take the biggest element available.Input
The input consists of multiple test cases. The first line contains a single integer\( t (1 \le t \le 1000) \)— the number of test cases. The description of the test cases follows.
The first line of each test case contains three space-separated integers n, m and \(k (1 \le m \le n \le 3500, 0 \le k \le n - 1) \) — the number of elements in the array, your position in line and the number of people whose choices you can fix.
The second line of each test case contains n positive integers \(a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) \) — elements of the array.
It is guaranteed that the sum of n over all test cases does not exceed 3500.Output
For each test case, print the largest integer x such that you can guarantee to obtain at least x.ExampleinputCopy
4 6 4 2 2 9 2 3 8 5 4 4 1 2 13 60 4 4 1 3 1 2 2 1 2 2 0 1 2
outputCopy
8 4 1 1
Note
In the first test case, an optimal strategy is to force the first person to take the last element and the second person to take the first element.
- the first person will take the last element (5) because he or she was forced by you to take the last element. After this turn the remaining array will be [2, 9, 2, 3, 8];
- the second person will take the first element (2) because he or she was forced by you to take the first element. After this turn the remaining array will be [9, 2, 3, 8];
- if the third person will choose to take the first element (9), at your turn the remaining array will be [2, 3, 8] and you will take 8 (the last element);
- if the third person will choose to take the last element (8), at your turn the remaining array will be [9, 2, 3] and you will take 9 (the first element).
Thus, this strategy guarantees to end up with at least 8. We can prove that there is no strategy that guarantees to end up with at least 9. Hence, the answer is 8.
In the second test case, an optimal strategy is to force the first person to take the first element. Then, in the worst case, both the second and the third person will take the first element: you will end up with 4.
看到n，m的范围就知道可以暴力乱搞；
令\(k=min(k,m-1)\)表示的是我前面还有k个人可以控制，那么也就是还有m-1-k个人不能控制，那我们就枚举我可以控制的k个人中取第一个元素的人的个数，确定了这个之后我们再去枚举剩下不能控制的人选第一个还是最后一个的所有可能，更新最大值即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)4e5+100;
const int mod=(int)1e9+7;
int n,m,k,a[maxn];
void solve(){
scanf("%d%d%d",&n,&m,&k);
rep(i,1,n) scanf("%d",&a[i]);
k=min(k,m-1);
int ans=0;
rep(i,0,k){
int tmp=mod;
rep(j,0,m-1-k){
tmp=min(tmp,max(a[i+j+1],a[n-m+1+i+j]));
}
ans=max(ans,tmp);
}
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
D. Irreducible Anagrams
time limit per test2 seconds memory limit per test256 megabytes
Let's call two strings s and t anagrams of each other if it is possible to rearrange symbols in the string s to get a string, equal to t.
Let's consider two strings s and t which are anagrams of each other. We say that t is a reducible anagram of s if there exists an integer k \ge 2 and 2k non-empty strings \(s_1, t_1, s_2, t_2, \dots, s_k, t_k\) that satisfy the following conditions:
- If we write the strings \(s_1, s_2, \dots, s_k\) in order, the resulting string will be equal to s;
- If we write the strings\( t_1, t_2, \dots, t_k\) in order, the resulting string will be equal to t;
- For all integers i between 1 and k inclusive, \(s_i\) and \(t_i\) are anagrams of each other.
If such strings don't exist, then t is said to be an irreducible anagram of s. Note that these notions are only defined when s and t are anagrams of each other.
For example, consider the string s = "gamegame". Then the string t = "megamage" is a reducible anagram of s, we may choose for example \(s_1\) = "game", \(s_2\) = "gam",\( s_3\) = "e" and \(t_1\) = "mega",\( t_2\) = "mag",\( t_3\) = "e":
On the other hand, we can prove that t = "memegaga" is an irreducible anagram of s.
You will be given a string s and q queries, represented by two integers \(1 \le l \le r \le |s|\) (where |s| is equal to the length of the string s). For each query, you should find if the substring of s formed by characters from the l-th to the r-th has at least one irreducible anagram.Input
The first line contains a string s, consisting of lowercase English characters (\(1 \le |s| \le 2 \cdot 10^5\)).
The second line contains a single integer \(q (1 \le q \le 10^5) \) — the number of queries.
Each of the following q lines contain two integers l and \(r (1 \le l \le r \le |s|)\), representing a query for the substring of s formed by characters from the l-th to the r-th.Output
For each query, print a single line containing "Yes" (without quotes) if the corresponding substring has at least one irreducible anagram, and a single line containing "No" (without quotes) otherwise.ExamplesinputCopy
aaaaa 3 1 1 2 4 5 5
outputCopy
Yes No Yes
inputCopy
aabbbbbbc 6 1 2 2 4 2 2 1 9 5 7 3 5
outputCopy
No Yes Yes Yes No No
Note
In the first sample, in the first and third queries, the substring is "a", which has itself as an irreducible anagram since two or more non-empty strings cannot be put together to obtain "a". On the other hand, in the second query, the substring is "aaa", which has no irreducible anagrams: its only anagram is itself, and we may choose \(s_1\) = "a",\( s_2\) = "aa",\( t_1\) = "a",\( t_2\) = "aa" to show that it is a reducible anagram.
In the second query of the second sample, the substring is "abb", which has, for example, "bba" as an irreducible anagram.
先说结论，l=r 或 首尾不相等 或 字母种数大于2 就是Yes，否则为No；
对于第一种情况l=r，显然是Yes；
第二种首尾不相等的情况，假设头是a，尾是b，那么我们先放全部的b，然后随便放字母，就可以构造出来；
第三种情况稍复杂，假设三种字母中最后出现的是c，首尾是a，那么我们先放所有的c，再放所有的a，那么可以构造出来一个；
其他情况就都是No了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
char s[maxn];
int pre[maxn][30];
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
rep(i,1,n) rep(j,0,25) pre[i][j]=pre[i-1][j]+(s[i]-'a'==j);
int q;scanf("%d",&q);
while(q--){
int l,r;scanf("%d%d",&l,&r);
int num=0;
rep(i,0,25) if(pre[r][i]-pre[l-1][i]) num++;
if(l==r||s[l]!=s[r]||num>=3) puts("Yes");
else puts("No");
}
}
E. Prefix Enlightenment
time limit per test3 seconds memory limit per test256 megabytes
There are n lamps on a line, numbered from 1 to n. Each one has an initial state off (0) or on (1).
You're given k subsets \(A_1, \ldots, A_k of \{1, 2, \dots, n\}\), such that the intersection of any three subsets is empty. In other words, for all \(1 \le i_1 < i_2 < i_3 \le k, A_{i_1} \cap A_{i_2} \cap A_{i_3}\) = \varnothing.
In one operation, you can choose one of these k subsets and switch the state of all lamps in it. It is guaranteed that, with the given subsets, it's possible to make all lamps be simultaneously on using this type of operation.
Let \(m_i\) be the minimum number of operations you have to do in order to make the i first lamps be simultaneously on. Note that there is no condition upon the state of other lamps (between i+1 and n), they can be either off or on.
You have to compute \(m_i\) for all \(1 \le i \le n\).Input
The first line contains two integers n and k \((1 \le n, k \le 3 \cdot 10^5)\).
The second line contains a binary string of length n, representing the initial state of each lamp (the lamp i is off if s_i = 0, on if s_i = 1).
The description of each one of the k subsets follows, in the following format:
The first line of the description contains a single integer \(c (1 \le c \le n) \) — the number of elements in the subset.
The second line of the description contains c distinct integers \(x_1, \ldots, x_c (1 \le x_i \le n) \) — the elements of the subset.
It is guaranteed that:
- The intersection of any three subsets is empty;
- It's possible to make all lamps be simultaneously on using some operations.
Output
You must output n lines. The i-th line should contain a single integer m_i — the minimum number of operations required to make the lamps 1 to i be simultaneously on.ExamplesinputCopy
7 3 0011100 3 1 4 6 3 3 4 7 2 2 3
outputCopy
1 2 3 3 3 3 3
inputCopy
8 6 00110011 3 1 3 8 5 1 2 5 6 7 2 6 8 2 3 5 2 4 7 1 2
outputCopy
1 1 1 1 1 1 4 4
inputCopy
5 3 00011 3 1 2 3 1 4 3 3 4 5
outputCopy
1 1 1 1 1
inputCopy
19 5 1001001001100000110 2 2 3 2 5 6 2 8 9 5 12 13 14 15 16 1 19
outputCopy
0 1 1 1 2 2 2 3 3 3 3 4 4 4 4 4 4 4 5
Note
In the first example:
- For i = 1, we can just apply one operation on \(A_1\), the final states will be 1010110;
- For i = 2, we can apply operations on \(A_1\) and \(A_3\), the final states will be 1100110;
- For \(i \ge 3\), we can apply operations on \(A_1, A_2\) and \(A_3\), the final states will be 1111111.
In the second example:
- For\( i \le 6\), we can just apply one operation on \(A_2\), the final states will be 11111101;
- For \(i \ge 7\), we can apply operations on \(A_1, A_3, A_4, A_6\), the final states will be 11111111.
第一个条件是任意三个集合的并是空集，那么很容易转换到每个点至多关联两个集合；
我们令\(x_i\)表示第i个集合是否选取(0不选1选)
对于没有集合关联的点（显然初始状态为1），我们不用管
那么对于只关联一个集合的点，\(x_i = 1 \oplus s_a\)
对于关联两个集合的点，\(x_i = s_a \oplus s_b\)
想到并查集拆点，这个模型很经典；把每个\(x_i\)拆成\(x_{i,0}\)和\(x_{i,1}\)，表示i这个集合选或者不选，那么显然对于所有的\(x_{i,1}\)点的花费是1，\(x_{i,0}\)花费为0；
至于怎么连边，我们先考虑关联两个集合的情况；
假设关联的集合为a和b，如果\(s_i = 1\)，那也就是说\(x_a\)和\(x_b\)必须相等，那我们就连一条\(x_{a,0}\)到\(x_{b,0}\)的边，和一条\(x_{a,1}\)到\(x_{b,1}\)的边；
\(s_i = 0\)同理；
那么如何处理只关联一个集合的点呢，很显然这时候\(x_i\)选什么是确定的，我们设一个超级点0，并把这个点的权值设为INF，意思就是和这个点相连的点都是不能选的；那么假设i这个集合必须选，我们只需要把\(x_{i,0}\)连到0号点即可；
现在，我们所有的边都连完了，统计答案就只需要得到并查集内联通块权值和的最小值即可；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,k,fa[maxn],tot[maxn],ans;
char s[maxn];
vector<int> v[maxn];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void join(int x,int y){
x=find(x);y=find(y);
if(x!=y) fa[x]=y,tot[y]+=tot[x];
}
int get(int x){return min(tot[find(x)],tot[find(x+k)]);}
int main(){
scanf("%d%d%s",&n,&k,s+1);
rep(i,1,k){
int x,c;scanf("%d",&c);
while(c--) scanf("%d",&x),v[x].pb(i);
}
rep(i,1,2*k+1) fa[i]=i,tot[i]=(i<=k);//[1,k]选，[k+1,2k]不选
tot[2*k+1]=mod;
rep(i,1,n){
if(v[i].size()==1){
int tmp=v[i][0]+(s[i]=='0')*k;
ans-=get(v[i][0]);join(tmp,2*k+1);ans+=get(v[i][0]);
}
if(v[i].size()==2){
int x=v[i][0],y=v[i][1];
if(s[i]=='1'&&find(x)!=find(y)){
ans-=(get(x)+get(y));join(x,y);join(x+k,y+k);ans+=get(x);
}
if(s[i]=='0'&&find(x)!=find(y+k)){
ans-=(get(x)+get(y));join(x,y+k);join(x+k,y);ans+=get(x);
}
}
printf("%d\n",ans);
}
}
