Educational Codeforces Round 163 (Rated for Div. 2)（A,B,C,D,E）

比赛链接

好忙好忙好忙，慢慢补老比赛的题解了。

这场没啥算法，全是思维。有也是BFS，屎。

---

A. Special Characters

题意：

您将得到一个整数 $n$ 。

您的任务是构建一串大写的拉丁字母。此字符串中必须正好有 $n$ 个特殊字符。让我们称一个字符为特殊字符，如果它恰好等于它的一个邻居。

例如，AAABAACC字符串中有 $6$ 个特殊字符（位置为： $1$ 、 $3$ 、 $5$ 、 $6$ ， $7$ 和 $8$ ）。

打印任何合适的字符串或报告没有这样的字符串。

思路：

发现如果是 AABBAABB 这样子的序列的话，每个字符都会是特殊字符。但是这样的只能构造出 $n$ 为偶数时候的情况。考虑能否构造出 $n$ 为奇数时候的情况。

因为一个字符为特殊字符只和它的左右相邻的字符有关，再往前是什么它是不在意的。所以我们构造 $n$ 为奇数时候的情况时，前面的部分仍然用类似 AABB 这种形式来构造，因为三个及以上连续的字符挨在一起时，中间的字符就不是特殊字符，不会产生贡献了，只有两头的字符会产生贡献，它就和两个字符的等价，所以我们不妨规定挨在一起的相同字符最多有两个。

于是，如果前面的部分结尾为 $AA$ 时，我们后面会补上 $B$，这时这个 $B$ 不是特殊字符，因此这时凑不出奇数情况。然后我们继续向后补字符，如果我们补 $A$，这个 $A$ 也不是特殊字符，凑不出奇数情况，如果补 $B$，这时补的两个 $B$ 都同时成为了特殊字符，相当于上面说的 $AABB$ 形式，仍然凑不出奇数情况。

如果我们在补上 $BA$，然后继续向后补字符，就会重复上面的讨论。因此无论怎么补，我们都凑不出奇数情况。这就意味着 $n$ 为奇数时是无解的。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=55;int T,n;
char s[maxn];int main(){cin>>T;while(T--){cin>>n;if(n&1){cout<<"NO"<<endl;continue;}else cout<<"YES"<<endl;for(int i=1;i<=n;i+=4)s[i]=s[i+1]='A';for(int i=3;i<=n;i+=4)s[i]=s[i+1]='B';for(int i=1;i<=n;i++)cout<<s[i];cout<<endl;}return 0;
}

---

B. Array Fix

题意：

您将得到一个长度为 $n$ 的整数数组 $a$ 。

您可以执行以下操作任意次数（可能为零）：取数组 $a$ 中至少为 $10$ 的任何元素，将其删除，然后在相同位置插入该元素所包含的数字，按它们出现在该元素中的顺序。例如：

• 如果我们将此操作应用于数组 $[12,3,45,67]$ 的第 $3$ 个元素，则数组将变为 $[12,3,4,5,67]$ 。

• 如果我们将此操作应用于数组 $[2,10]$ 的第 $2$ 个元素，则数组将变为 $[2,1,0]$ 。

您的任务是确定是否可以使用上述操作任意次数使 $a$ 按非降序排序。换句话说，您必须确定是否可以将数组 $a$ 转换为 $a_1\le a_2\le \cdots \le a_k$ ，其中 $k$ 是数组 $a$ 的当前长度。

思路：

先注意一下题目说了 $0\le a_i\le 99$，因此 $a_i$ 最多就是个两位数。

因为是非降序的，所以从某一位开始，也许后面就都变成了两位及以上的数，这时这些数不能被拆数位，否则变成一位数之后就会变小。反之，在此之前，所有的数都得是一位数，否则某个两位数后面出现了一位数，就不满足非降序的条件了。因此我们找到这个分界点，把分界点之前的所有数都拆掉，然后看满不满足条件就行了。

根据上面的分析，这个分界点之后的数都是不拆数位就满足非降序的，所以我们从后向前找到第一个不满足条件的位置，这个位置就是分界点了。从这个位置向前拆数。一个数拆开后，个位放在后面，十位放在前面。所以我们没必要真的把两个新的数插入到当前位置，这样比较麻烦。

判断这个数是否和后一个数满足非降序的关系，我们直接看一下当前数的十位不小于个位，并且个位不小于后一个数，之后用十位代替这个数，再向前找即可。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=55;int T,n,a[maxn];int main(){cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int idx;for(idx=n-1;idx>=1;idx--)if(a[idx]>a[idx+1])break;//		cout<<"***"<<idx<<endl;bool flag=true;for(int i=idx;i>=1;i--){if(a[i]/10>a[i]%10 || a[i]%10>a[i+1]){flag=false;break;}if(a[i]>10)a[i]/=10;}puts((flag)?"YES":"NO");}return 0;
}

---

C. Arrow Path

题意：

有一个网格，由 $2$ 行和 $n$ 列组成。这些行从上到下从 $1$ 到 $2$ 进行编号。列从左到右从 $1$ 到 $n$ 进行编号。网格的每个单元格都包含一个指向左侧或右侧的箭头。没有箭头指向网格外。

有一个机器人在单元格 $(1,1)$ 中启动 。每一秒钟，都有以下两个动作相继发生：

1. 首先，机器人向左、向右、向下或向上移动（它不能尝试走出网格，也不能跳过这次移动）

2. 然后，它沿着放置在当前单元格（移动后结束的单元格）中的箭头移动。

您的任务是确定机器人是否可以到达单元 $(2,n)$ 。

思路：

比较明显的BFS。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define pii pair<int,int>
using namespace std;
const int maxn=2e5+5;int T,n;
string mp[5];int fx[]={1,-1,0,0},fy[]={0,0,1,-1};int main(){cin>>T;while(T--){cin>>n;cin>>mp[1]>>mp[2];mp[1]=" "+mp[1];mp[2]=" "+mp[2];queue<pii> q;vector<vector<bool> > vis(5,vector<bool>(n+5,false));q.push(pii(1,1));vis[1][1]=true;bool flag=false;while(!q.empty()){int ux=q.front().first,uy=q.front().second;q.pop();if(ux==2 && uy==n){flag=true;break;}for(int i=0,x,y;i<4;i++){x=ux+fx[i],y=uy+fy[i];if(x<1 || x>2 || y<1 || y>n)continue;if(mp[x][y]=='<')y--;else y++;if(!vis[x][y]){q.push(pii(x,y));vis[x][y]=true;}}}puts((flag)?"YES":"NO");}return 0;
}

---

D. Tandem Repeats?

题意：

您将得到一个字符串 $s$ ，它由小写的拉丁字母以及问号组成。

串联重复序列（tandem repeat）是指长度为偶数的串，满足其前一半等于其后一半。

您的目标是将每个问号替换为某个小写拉丁字母，求出最大可能的串联重复序列子串的长度。

思路：

考虑到这个串联重复序列比如 $abcabc$，说白了就是第 $1$ 个字符向后 $3$ 个长度的子串与第 $4$ 个字符向后 $3$ 个长度的子串相同。那么一定第 $2$ 个字符向后 $2$ 个长度的子串与第 $5$ 个字符向后 $2$ 个长度的子串相同，前者可以由后者推出来。

所以我们设 $dp[i][j]$ 表示从第 $i$ 个字符开始的子串和第 $j$ 个字符开始的子串最长匹配长度是多少。当第 $i$ 个字符和第 $j$ 个字符相同时（两个字符真的相同，或者其中一个为 $?$，可以万能匹配），$dp[i][j]$ 就可以从 $dp[i+1][j+1]+1$ 推过来。因为是从 $i+1,j+1$ 推来的，因此 $i,j$ 的枚举需要反着，从 $n$ 到 $1$。

不过 $i\sim i+dp[i][j]-1$ 与 $j\sim j+dp[i][j]-1$ 两个区间的子串匹配不一定就是串联重复序列，它需要正好是 $i+dp[i][j]-1=j-1$ 即 $j-i=dp[i][j]$（也就是前后两个子串正好相接）。$dp[i][j]$ 如果大于 $j-i$，这时可以直接截取长为 $j-i$ 的一段作为串联重复序列，反之就一定无法成为串联重复序列。

code：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;int T,n;
string s;int main(){cin>>T;while(T--){cin>>s;n=s.length();s=" "+s;vector<vector<int> > dp(n+5,vector<int>(n+5,0));for(int i=n;i>=1;i--){for(int j=i-1;j>=1;j--){if(s[i]=='?' || s[j]=='?' || s[i]==s[j])dp[i][j]=dp[i+1][j+1]+1;}}int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<i;j++){int t=dp[i][j];if(t>=i-j)t=i-j;else continue;ans=max(ans,t);}}cout<<ans*2<<endl;}return 0;
}

---

E. Clique Partition

题意：

给出两个整数 $n$ 和 $k$ 。在 $n$ 个顶点上有一个图，编号从 $1$ 到 $n$ ，它最初没有边。你必须给每个顶点分配一个整数，设 $a_i$ 是顶点 $i$ 上的整数。所有 $a_i$ 都应该是从 $1$ 到 $n$ 的不同整数。

指定整数后，对于每对顶点 $(i,j)$ ，如果 $|i-j|+|a_i-a_j|\le k$ ，则在它们之间添加一条边。

您的目标是创建一个图，该图可以划分为最小可能（对于给定的 $n$ 和 $k$ 值）数量的团（Clique）。

图的每个顶点应该恰好属于一个团。

团是一组顶点，其中的每一对顶点都与一条边相连。由于布莱德斯特没有真正提高他的编程技能，他无法解决问题 “给一个图，将其划分为最小数量的团”。因此，我们要求您打印分区本身。

思路：

构造题，构造方法不好想。如果想出了构造方法，写是比较容易的。

要团的个数最少，那么就考虑让团包含的点最多。因为 $a_i$ 互不重复，所以 $|a_i-a_j|$ 至少会是 $1$，那么 $|i-j|$ 最大就是 $k-1$，这时 $j-i+1$ 最大就是 $k$。也就是说，团最多可能包含 $k$ 个点。

考虑如果一个团能否塞入 $k$ 个点，不妨使用顶点 $1\sim k$。而且为了不影响到其他团，所以我们尽量给它们分配 $1\sim k$ 的编号。

首先第 $1$ 个数和第 $k$ 个数必须差 $1$，否则这一对一定不满足条件。同理，第 $1$ 个数和第 $k-1$ 个数必须差 $\le 2$，第 $2$ 个数和第 $k$ 个数必须差 $\le 2$。考虑把第一个数置为中间数 $k/2$，这样中间数两边都有空间，我们把中间数前面的数降序放在前半部分，中间数后面的数降序放在后半部分。即：$$k/2,k/2-1,\dots ,1,k,k-1\dots ,k/2+2,k/2+1$$

还是比较好验证这么构造的正确性的：前半部分一定满足条件，后半部分一定满足条件。前半部分取一个数，后半部分取一个数的情况也满足条件。综合一下，所有情况都满足条件。

这样 $1\sim k$ 的情况就构造出来了，因为相对位置和相对大小是不变的，所以后面的每个团也是这样构造就可以了。

有时候会剩下一些点不足 $k$ 个。构造方式同理，把上面的序列截掉后面部分即可，大概就是这样：

1. 如果 $n\le k/2$，则$$n,n-1,\dots ,1$$
2. 如果 $k/2<n<k$，则$$k/2,k/2-1,\dots ,1,n,n-1\dots ,k/2+2,k/2+1$$

团的个数也就很显然了，是 $\lceil \frac{n}{k}\rceil$。第 $i$ 个点所属的团显然就是第 $\lceil \frac{i}{k}\rceil$ 个团。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=45;int T,n,k;
int a[maxn];int main(){cin>>T;while(T--){cin>>n>>k;for(int i=1,len=k;i<=n;i+=k){if(i+k-1<=n){for(int j=i;j<i+len;j++)a[j]=j;reverse(a+i,a+i+len/2);reverse(a+i+len/2,a+i+len);}else {if(i+len/2>=n){for(int j=i;j<=n;j++)a[j]=j;reverse(a+i,a+n+1);}else {for(int j=i;j<=n;j++)a[j]=j;reverse(a+i,a+i+len/2);reverse(a+i+len/2,a+n+1);}}}
//		cout<<"***";for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");cout<<(n+k-1)/k<<endl;for(int i=1;i<=n;i++){printf("%d ",(i+k-1)/k);}puts("");}return 0;
}