A. Déjà Vu
A palindrome is a string that reads the same backward as forward. For example, the strings “z”, “aaa”, “aba”, and “abccba” are palindromes, but “codeforces” and “ab” are not. You hate palindromes because they give you déjà vu.
There is a string s
. You must insert exactly one character ‘a’ somewhere in s
. If it is possible to create a string that is not a palindrome, you should find one example. Otherwise, you should report that it is impossible.
For example, suppose s=
“cbabc”. By inserting an ‘a’, you can create “acbabc”, “cababc”, “cbaabc”, “cbabac”, or “cbabca”. However “cbaabc” is a palindrome, so you must output one of the other options.
Input
The first line contains a single integer t
(1≤t≤104
) — the number of test cases.
The only line of each test case contains a string s
consisting of lowercase English letters.
The total length of all strings does not exceed 3⋅105
.
Output
For each test case, if there is no solution, output “NO”.
Otherwise, output “YES” followed by your constructed string of length |s|+1
on the next line. If there are multiple solutions, you may print any.
You can print each letter of “YES” and “NO” in any case (upper or lower).
Example
Input
Copy
The first test case is described in the statement.
In the second test case, we can make either “aab” or “aba”. But “aba” is a palindrome, so “aab” is the only correct answer.
In the third test case, “zaza” and “zzaa” are correct answers, but not “azza”.
In the fourth test case, “baa” is the only correct answer.
In the fifth test case, we can only make “aa”, which is a palindrome. So the answer is “NO”.
In the sixth test case, “anutforajaroftuna” is a palindrome, but inserting ‘a’ elsewhere is valid.
题意：
给你一个字符串，然后你可以通过在任意位置上+‘a’，然后让这个字符串不是回文字符串，如果实在无法让字符串变成非回文，则输出NO。
思路：
我们可以判断出只有全为a的回文字符串才会+‘a’后无法变成非回文串，其他的都可以在任意位置上“a”，使字符串变成非回文串，那我们可以直接在首或者尾“a”，然后循环判断是否为回文，输出非回文的那一种就可以了。
代码：
#include<bits/stdc++.h>
using namespace std;
bool judge(string p)
{for(int i=0,j=p.size()-1;i<j;i++,j--){if(p[i]!=p[j])return true;}return false;
}
int main ()
{int t;cin>>t;while(t--){string ch;cin>>ch;int f=0;for(int i=0;i<ch.size();i++){if(ch[i]!='a'){f=1;break;} }if(f==0){cout<<"NO"<<endl;}else{string ch1,ch2;ch1="a"+ch;ch2=ch+"a";if(judge(ch1)){cout<<"YES"<<endl;cout<<'a';for(int i=0;i<ch.size();i++) cout<<ch[i];cout<<endl;}else{if(judge(ch2)) {cout<<"YES"<<endl;for(int i=0;i<ch.size();i++) cout<<ch[i];cout<<'a';cout<<endl;}elsecout<<"NO"<<endl;} }}return 0;
}
B. Flip the Bits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
There is a binary string a
of length n. In one operation, you can select any prefix of a with an equal number of 0 and 1 symbols. Then all symbols in the prefix are inverted: each 0 becomes 1 and each 1 becomes 0
For example, suppose a=0111010000
since it has four 0’s and four 1’s: [01110100]00→[10001011]00
In the second operation, we can select the prefix of length 2
since it has one 0 and one 1: [10]00101100→[01]00101100
It is illegal to select the prefix of length 4
for the third operation, because it has three 0’s and one
Can you transform the string a
into the string b
using some finite number of operations (possibly, none)?
Input
The first line contains a single integer t
(1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n
(1≤n≤3⋅105) — the length of the strings a and b
The following two lines contain strings a
and b of length n, consisting of symbols 0 and 1
The sum of n
across all test cases does not exceed 3⋅105
Output
For each test case, output “YES” if it is possible to transform ainto b, or “NO” if it is impossible. You can print each letter in any case (upper or lower).
Example
Input
Copy
5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100
Output
Copy
YES
YES
NO
YES
NO
Note
The first test case is shown in the statement.
In the second test case, we transform a
into b
by using zero operations.
In the third test case, there is no legal operation, so it is impossible to transform a
into b
.
In the fourth test case, here is one such transformation:
Select the length 2
prefix to get 100101010101
.
Select the length 12
prefix to get 011010101010
.
Select the length 8
prefix to get 100101011010
.
Select the length 4
prefix to get 011001011010
.
Select the length 6
prefix to get 100110011010
In the fifth test case, the only legal operation is to transform a
into 111000. From there, the only legal operation is to return to the string we started with, so we cannot transform a into b
题意：
给你一个字符串a，b，由0,1组成，然后只有在字符串下标i前面的0,1个数相同时，你可以进行把0->1,1->0,然后看是否能进行一些操作把字符串a变成b。
思路：
这题思路有点难想，你看，它每次个数相同时，都可以进行操作，所以我们从后往前进行操作，因为如果从前往后，小区间会影响大区间的，所以从大区间向小区间进行，然后遍历字符串，将每一位的0,1的个数进行计算，然后将a，b不相同的下标进行标记为1，代表需要改变。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
int s0[N],s1[N];
int a[N],b[N],p[N];
int main ()
{int t;cin>>t;while(t--){int n;cin>>n;string a,b;cin>>a>>b;memset(p,0,sizeof p);for(int i=0;i<n;i++){if(a[i]=='0'){s0[i]=s0[i-1]+1;s1[i]=s1[i-1];}else{s1[i]=s1[i-1]+1;s0[i]=s0[i-1];}if(a[i]!=b[i]){p[i]=1;//是否相同的标记} }int cnt=0;int f=0;for(int i=n-1;i>=0;i--){if(cnt%2==1){//奇数次才会被变化p[i]=1-p[i];}//而且必须在前面判这一步，因为你得先看后面的区间将这一位变成了什么if(p[i]){if(s0[i]==s1[i]) cnt++;//0,1相同时才可以进行一次变化else {f=1;break;} }}if(f==1){cout<<"NO"<<endl;}else{cout<<"YES"<<endl;} }return 0;
}//这个就利用了一个标记来判断当前为被影响成了什么
/*
01 01 01 01 01 01
10 01 10 01 10 10100101010101
011010101010
100101011010
011001011010
100110011010
Select the length 12
prefix to get
.
Select the length 8
prefix to get
.
Select the length 4
prefix to get
.
Select the length 6
prefix to get01 110100 00
01 001011 00
*/
C. Balance the Bits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters ‘+’ and ‘1’. For example, sequences ‘(())()’, ‘()’, and ‘(()(()))’ are balanced, while ‘)(’, ‘(()’, and ‘(()))(’ are not.
You are given a binary string s
of length n. Construct two balanced bracket sequences a and b of length n such that for all 1≤i≤n if si=1, then ai=bi
if si=0, then ai≠bi
If it is impossible, you should report about it.
Input
The first line contains a single integer t
(1≤t≤104) — the number of test cases.
The first line of each test case contains a single integer n
(2≤n≤2⋅105, nis even).
The next line contains a string sof length n, consisting of characters 0 and 1.The sum of nacross all test cases does not exceed 2⋅105.
Output
If such two balanced bracked sequences exist, output “YES” on the first line, otherwise output “NO”. You can print each letter in any case (upper or lower).
If the answer is “YES”, output the balanced bracket sequences a and b satisfying the conditions on the next two lines.If there are multiple solutions, you may print any.
Example
Input
Copy
3
6
101101
10
1001101101
4
1100
Output
Copy
YES
()()()
((()))
YES
()()((()))
(())()()()
NO
Note
In the first test case, a=
“()()()” and b="((()))". The characters are equal in positions 1, 3, 4, and 6, which are the exact same positions where si=1
.In the second test case, a=
“()()((()))” and b="(())()()()". The characters are equal in positions 1, 4, 5, 7, 8, 10, which are the exact same positions where si=1
In the third test case, there is no solution.
题意：
一个n代表01串的长度，构造两个长度为n的括号序列，给你一个01串，代表着a，b两个序列串字符不相同。然后你来判断是否有合理的a，b串。有的话输出。
思路：
这题想了很久想不明白，看了大佬的题解，迷迷糊糊差不多理解吧。这题是这样的，就是：
（1）第一步得合法的字符串，所以首尾得是相同的且都为1
（2）第二步，因为01串长度为偶数，所以如果合法的话，得（ 的个数= ) 的个数，然后你想呀，假如为 ()()()()吧，然后你有一个0破坏了一个括号，但如果合法的话，是不是得还有一个0再破坏一个括号，然后被破坏的这俩个进行分配才能合理，所以如果合法的话，01串得0的个数为偶数，1的个数自然而然为偶数吧。
（3）最后一步构造，既然1的个数为偶数，首尾又都为1，所以1的个数前sum1/2个1构造为‘（ ’，后sum1/2个构造为‘）’，然后我们1的所有的目前是合法的，然后剩下的0也是偶数的，然后如果让他们合法进行分配就（ ）间接进行就可以了，然后我们根据01串将b构造出来。合法的核心就是当前位的（个数大于等于），所以我们在循环进行判断一下a，b串是否都满足，（其实我觉得这么构造出来，a必然合理呀，其实就判b就行了，我保险起见都判了）。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7;
char a[N],b[N];
int main ()
{int t;cin>>t;while(t--){int n;cin>>n;string s;cin>>s;if(s[0]!=s[n-1]&&s[0]!='1'){cout<<"NO"<<endl;}else{int sum1=0,sum0=0;for(int i=0;i<s.size();i++){if(s[i]=='1') sum1++;else sum0++;}if(sum1%2!=0||sum0%2!=0){cout<<"NO"<<endl;}else{int cnt1=0,cnt0=1;for(int i=0;i<n;i++){if(s[i]=='1'&&cnt1<sum1/2){a[i]='(';cnt1++;}else if(s[i]=='1'&&cnt1>=sum1/2){a[i]=')';cnt1++;}else if(s[i]=='0'&&cnt0%2==1){a[i]='(';cnt0++;}else if(s[i]=='0'&&cnt0%2==0){a[i]=')';cnt0++;}//cout<<a[i]<<endl;}for(int i=0;i<n;i++){if(s[i]=='0'){if(a[i]=='(') b[i]=')';else b[i]='(';}else{b[i]=a[i];}//cout<<b[i]<<endl;}// cout<<"YES"<<endl;int f=0;int s0=0,s1=0;for(int i=0;i<n;i++){if(a[i]=='(') s0++;else if(a[i]==')') s1++;if(s0<s1) {f=1;break;} }s0=0,s1=0;for(int i=0;i<n;i++){if(b[i]=='(') s0++;else if(b[i]==')') s1++;if(s0<s1) {f=1;break;} }if(f==0){cout<<"YES"<<endl;for(int i=0;i<n;i++) cout<<a[i];cout<<endl;for(int i=0;i<n;i++) cout<<b[i];cout<<endl;}else{cout<<"NO"<<endl;} }} }return 0;
}
/*
01 01 01 01 01 01
10 01 10 01 10 10100101010101
011010101010
100101011010
011001011010
100110011010
Select the length 12
prefix to get
.
Select the length 8
prefix to get
.
Select the length 4
prefix to get
.
Select the length 6
prefix to get01 110100 00
01 001011 00
*/
ACM国际大学生程序设计竞赛（ACM-ICPC）：ACM-ICPC是一项全球范围内的高水平大学生计算机编程竞赛，由美国计算机协会（Association for Computing Machinery, ACM）主办。该竞赛旨在展示并提升大学生在算法分析、问题解决、编程技巧及团队合作等方面的能力。在文章中提到，此类竞赛经常出现与回文串相关的题目，参赛者需灵活运用算法知识来解决实际问题。