Codeforces Global Round 12 [date:12.6]
反思：cf题目需要抓住问题的根来解题。
A.
发现为了不让trygub出现只需要对字符串排一下序即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
string s;
cin >> s;
sort(s.begin(), s.end());
cout << s << endl;
}
}B.
可以令某个点充电，然后让周围所有曼哈顿距离小于等于k的点都聚拢到这一点，发现答案只有-1和1两种，枚举所有点，看一下所有点是否能靠拢到这一点即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector<int> x(n), y(n);
for(int i=0; i<n; i++) cin >> x[i] >> y[i];
int ans = -1;
for(int i=0; i<n; i++){
int mx = 0;
for(int j=0; j<n; j++){
mx = max(mx, abs(x[i]-x[j])+abs(y[i]-y[j]));
}
if(mx <= k) ans = 1;
}
cout << ans << '\n';
}
}C1.
解法很有意思的一道题，并不是什么暴力，cf哪有sb暴力题啊喂
我们可以观察i+j，任何连续三个都可以对应模三余0，模三余1，模三余2，这里面只要把任意一组全部改掉，自然就不会出现连续三个都是X了，统计一下，改最少的那一组即可。
还认识了一个min_element，max_element函数,返回最小值最大值索引，具体用法见下图
#include<bits/stdc++.h>
using namespace std;
string s[310];
void solve()
{
int n;
cin >> n;
for(int i=0; i<n; i++){
cin >> s[i];
}
int cnt[3]={0,0,0};
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(s[i][j]=='X'){
cnt[(i+j)%3]++;
}
}
}
int mx=1e8, val;
for(int i=0; i<3; i++){
if(cnt[i] < mx){
val = i;
mx = cnt[i];
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(s[i][j]=='X'&& (i+j)%3 == val){
s[i][j]='O';
}
}
}
for(int i=0; i<n; i++){
cout << s[i] << endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
}C2.
明显是考虑(i + j) % 3, 记 ++cnt[(i + j) % 3][s[i][j] == 'X']
无非选择c[i][0]+c[j][1]使得c[i][0]+c[j][1] <= k/3即可。连续三个相邻标记中有两个不同的标记。
#include<bits/stdc++.h>
using namespace std;
string s[300];
int c[3][2];
void solve()
{
int n, k = 0;
cin >> n;
for(int i=0; i<n; i++){
cin >> s[i];
}
memset(c, 0, sizeof(c));
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(s[i][j]!='.'){
c[(i+j)%3][s[i][j]=='X']++; k++;
}
}
}
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
if(i != j && (c[i][1]+c[j][0]) <= k/3)
{
for(int ii = 0; ii < n; ii++){
for(int jj =0; jj < n; jj++){
if(s[ii][jj] == 'X'){
if((ii+jj)%3 == i){
s[ii][jj] = 'O';
}
}
else if(s[ii][jj] == 'O'){
if((ii+jj)%3 == j){
s[ii][jj] = 'X';
}
}
}
}
for(int i=0; i<n; i++){
cout << s[i] << endl;
}
return ;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--)
{
solve();
}
}D.
题意：对于一个给定数组，对于任意k从1到n，问能否满足获得的数组是一个排列，比如1 5 3 4 2当k=2时获得的数组是1 3 3 2则不满足排列，对于任意len，一个排列是指所有数从1~len都各只出现一次。
k=1和n特判，发现1只能出现在边界，并且只能出现一次，(如果出现在中间，肯定会得到有多个1)，然后开始迭代，维护l和r，是个类似递推。
回过头来思考一下为什么这样迭代是对的？
第一次，k=n-i的两个区间一个有1，一个有2，ans[n-i]=1,迭代下去，k=n-i-1的三个区间....
#include<bits/stdc++.h>
using namespace std;
#define N 300010
int a[N], cnt[N], ans[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
memset(cnt, 0, sizeof(cnt));
memset(ans, 0, sizeof(ans));
for(int i=1; i<=n; i++){
cin >> a[i]; cnt[a[i]]++;
}
if(cnt[1]){
ans[n] = 1;
}
bool flag = 1;
for(int i=1; i<=n; i++){
if(cnt[i]!=1){
flag = 0; break;
}
}
if(flag) ans[1] = 1;
int l=1, r=n;
for(int i=1; i<n; i++){
if(cnt[i] != 1) break;
if(a[l] == i && cnt[i+1])
{
l++;
ans[n-i]=1;
}
else if(a[r] == i && cnt[i+1])
{
r--;
ans[n-i]=1;
}
else
{
break;
}
}
for(int i=1; i<=n; i++){
cout << ans[i];
}
cout << '\n';
}
}E.
