传送门
题目大意：
给定一个字符串，你可以给任意位置插入一个‘a’，
如果可以使字符串不为回文串，那么输出YES并输出
任意满足的情况
如果不可以，输出NO

思路：
如果字符串全为a，则输出NO
否则输出YES.
从左到右直到第一个不为a找左边有多少个a,记为l,
从右到左直到第一个不为a找右边有多少个a,记为r
如果l == r ,则将a加在字符串末尾
否则，将a加在字符串a多的那一边

代码：

#include<bits/stdc++.h>
using namespace std;#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)void slove()
{string s;cin >> s;bool ans = false;int left = 0,right = 0;for(int i = 0;i < s.length();++i){if(s[i] != 'a') {ans = true;left = i+1;break; }}if(!ans) cout << "NO" << endl;else {for(int i = s.length()-1;i >= 0;--i){if(s[i] != 'a') {right = s.length() - i;break; }}if(left == right) s+='a';else if(left > right) s = 'a' + s;else s = s + 'a';cout << "YES" << endl;cout << s << endl;}
}int main()
{IO;int t;cin >> t;while(t--){slove();}return 0;
}

题目总结：
思维水题，确定思维证明无误后，再顺畅的敲代码，
这不仅是一种成功，更是一种享受

传送门
题目大意：
给定a,b两个字符串
如果a的前n个字符满足0的个数和1的个数相等
则可以将a的前n个字符0->1和1->0
可以进行任意此操作，判断是否可以将a变成b

思路：
从后往前，我们从第一个不相等的位置将a字符串前部翻转
翻转之后，接着往前找相等的位置将字符串a前部翻转
重复前两个操作，直到结束
注意特判结束的情况
主要记录判断每次字符串是否可以翻转

代码：

#include<bits/stdc++.h>
using namespace std;#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)void slove()
{int n;cin >> n;string s1,s2;cin >> s1 >> s2;int l1=0,r1=0,l2=0,r2=0;for(int i = 0;i < s1.length();++i){if(s1[i] == '0') l1++;else r1++;if(s2[i] == '0') l2++;else r2++;}if(l1 != l2){cout << "NO" << endl;return ;}bool ans = false,sign = true;for(int i = s1.length()-1;i >= 0 && sign;--i){if(!ans){if(s1[i] == s2[i]){if(s1[i] == '0') l1--;else r1--;}else {ans = true;if(l1 == r1) {if(s1[i] == '0') l1--;else r1--;}else sign = false;}}else {if(s1[i] != s2[i]){if(s1[i] == '0') l1--;else r1--;}else {ans = false;if(l1 == r1) {if(s1[i] == '0') l1--;else r1--;}else sign = false;}}}if(sign) cout << "YES" << endl;else cout << "NO" << endl;
}int main()
{IO;int t;cin >> t;while(t--){slove();}return 0;
}

题目总结：
思维中等题，从后往前遍历是一个比较常用的思路。
这个题虽然没有用到前缀和，但是和前缀和有一些相像的地方。
比如：记录从前到翻转位置0,1的数量

传送门
题目大意：
给定一个01串，
我们来构造左右括号的匹配情况，
如果可以出现两种左右括号情况
使得1对应的位置相等
使得0对应的位置不相等
那么输出YES并输出那两种情况
否则输出NO

思路：
如果0字符的个数为偶数或者第一个或最后一个字符为0则输出NO
否则输出YES
这时候我们确定了第一个位置和最后一个位置是1。
令它们分别为（）
然后对于剩余1我们进行一左一右的编码，对于0进行一左一右编码
第二种情况1进行一左一右编码，对于0进行一右一左编码
那么它们一定满足上面的情况

#include<bits/stdc++.h>
using namespace std;#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)void slove()
{int n;cin >> n;string s;cin >> s;int nm = 0;for(int i = 0;i < s.length();++i) if(s[i] == '0') nm++;if(nm%2 != 0 || s[n-1]=='0' || s[0]=='0') {cout << "NO" << endl;return ;}cout << "YES" << endl;bool l1=true,r1=true;cout << '(';for(int i = 1;i < s.length()-1;++i){if(s[i] == '1') {if(l1) cout << '(';else cout << ')';l1 = !l1;}else {if(r1) cout << '(';else cout << ')';r1 = !r1;}}cout << ')' << endl;l1=true,r1=false;cout << '(';for(int i = 1;i < s.length()-1;++i){if(s[i] == '1') {if(l1) cout << '(';else cout << ')';l1 = !l1;}else {if(r1) cout << '(';else cout << ')';r1 = !r1;}}cout << ')' << endl;
}int main()
{IO;int t;cin >> t;while(t--){slove();}return 0;
}

题目总结：
思维拐弯题，如果我们注意力集中在一左一右的匹配那就进入死胡同了
这时候我们的思维指向10的区分处理，也就是“分治”思想，
那这个题就豁然开朗了，1处理自己的，0处理自己的
化繁为简，大道使然

传送门
题目大意：
用不超过三种颜色填满n*n的格子使得相邻的格子颜色不同。
交互题，一个输出立马给出一个结果
Alice给出一个颜色，然后使用不是这个颜色的颜色去填空格
输出颜色和位置

思路：
我们用两个队列将所有格子空开，用1，2分别去填满其中一种再用3去填没满的队列。当其中一个队列填满剩下未填满的格子都是隔开的用3去填不会出现任何问题

#include<iostream>
#include<vector>
using namespace std;#define IO ios::sync_with_stdio(0),cin.tie(0)
#define LL long long
LL n;
vector<LL> A,B;void slove()
{cin >> n;for(int i = 0;i < n;++i){for(int j = 0;j < n;++j){if((i+j)%2 == 0)A.push_back(i*n+j);else B.push_back(i*n+j);}}LL x = A.size();LL y = B.size();LL p = 0;LL q = 0;LL a;for(int i = 0;i < n*n;++i){cin >> a;if(p < x && q < y){if(a == 1){cout << 2 << " " << B[q]/n+1 << " " << B[q]%n+1 << endl;q++;}else {cout << 1 << " " << A[p]/n+1 << " " << A[p]%n+1 << endl;p++;}}else if(p == x){if(a == 2) {cout << 3 << " " << B[q]/n+1 << " " << B[q]%n+1 << endl;q++;}else {cout << 2 << " " << B[q]/n+1 << " " << B[q]%n+1 << endl;q++;}}else {if(a == 1){cout << 3 << " " << A[p]/n+1 << " " << A[p]%n+1 << endl;p++;}else {cout << 1 << " " << A[p]/n+1 << " " << A[p]%n+1 << endl;p++;}}}
}int main()
{IO;slove();
}

题目总结：
第一次做交互题，没有接触经验，导致考虑的时候漏洞百出。
没有良好的思维变化。对于交互题可以理解成出错处理来思考。
例如队列填满了，填不了了就出错了，填副对角线，副对角线怎么填，用3来填。

传送门
题目大意：
每个城市有一个ai和ci
从第i个城市到第j个城市需要花费
max(a[j],a[i]-a[j])
问从第一个城市出发回到第一个城市的最小花费
旅行商问题

思路：
我们走一圈至少花费c[i]的总和
然后排序补齐a[j]-a[i]-c[i]的花费

#include<bits/stdc++.h>
using namespace std;#define LL long long
const int maxn = 1e5+5;
struct stu{LL l,r;
}a[maxn*2];bool cmp(struct stu a,struct stu b)
{if(a.l == b.l) return a.r < b.r;else return a.l < b.l;
}int main()
{int n;cin >> n;for(int i = 1;i <= n;++i) cin >> a[i].l >> a[i].r;sort(a+1,a+n+1,cmp);
//	for(int i = 1;i <= n;++i) cout << a[i].l << " " <<  a[i].r << endl;LL sum = 0;for(int i = 1;i <= n;++i) sum+=a[i].r;LL naj = a[1].l+a[1].r;for(int i = 2;i <= n;++i){if(naj < a[i].l){sum += (a[i].l - naj);}naj = max(naj,a[i].l+a[i].r);}cout << sum << endl;return 0;
}

题目总结：
思维题转换题，要对于题意有一定的理解
大胆猜测，小心检验

传送门

题目大意：
左边从小到大，右边从大到小
每行数据符合l[i],r[i]的位置上相同

思路：

无：

#include<bits/stdc++.h>
using namespace std;int n;
int a[200000+20],b[200000+20];
int ano[200000*2+20];
bool is[200000*2+20];
bool bad[200000*2+20];pair<int,int> gao(int l,int r,int &val)
{val = !is[l];int l_,r_;l_ = l,r_ = ano[l];int prel=l,prer=ano[l];bad[ano[l]] = 1;r += 1;while(l < l_ || r > r_){if(l < l_){while(l < l_){++l;if(!bad[l]){val += !is[l];if(ano[l] > prer){return make_pair(-1,-1);}bad[ano[l]] = 1;prer = ano[l];}}if(prer < l_) return make_pair(-1,-1);r_ = prer;}else{while(r > r_){--r;if(!bad[r]){val += !is[r];if(ano[r] < prel){return make_pair(-1,-1);}bad[ano[r]] = 1;prel = ano[r];}if(prel > r_)return make_pair(-1,-1);l_ = prel;}}}return make_pair(l_,r_);
}int slove(int A,int B)
{if(A > B) return 0;int z = 0;pair<int,int> seg = gao(A,B,z);if(seg.first == -1) return -1;int cnt = B-seg.second+1+seg.first-A+1;int tmp = slove(seg.first+1,seg.second-1);if(tmp == -1) return -1;return tmp+min(cnt/2-z,z);
}int main()
{cin >> n;for(int i = 1;i <= n;++i){cin >> a[i] >> b[i];ano[a[i]] = b[i];ano[b[i]] = a[i];is[a[i]] = 1;}cout << slove(1,n+n) << endl;return 0;
}