Educational Codeforces Round 70 (Rated for Div. 2)
题目链接：https://codeforces.com/contest/1202
A - You Are Given Two Binary Strings...
题意：给一个二进制串x，另一个二进制串y，把y串左移若干位（可以是0位），使得他们的和倒过来的字典序最小。
题解：倒过来的字典序最小，意思就是没倒过来之前末尾要有尽可能多的0。大概想了想应该不会出现前缀都相同，某个字符串更短，这样的情况。那么y串最后的0是没什么不良影响的，就把他的最后一个1移动到与x串的某个1对齐就好了，假如y串最后一个1已经超过了x串的长度，那么就不需要移动了。
char x[100005];
char y[100005];
void test_case() {
int xlen, ylen;
scanf("%s%s", x + 1, y + 1);
xlen = strlen(x + 1);
ylen = strlen(y + 1);
int last1 = 0;
for(int j = 1; j <= ylen; ++j) {
if(y[j] == '1')
last1 = j;
}
int k = 0;
for(int i = xlen - (ylen - last1); i >= 1; --i) {
if(x[i] == '1') {
k = (xlen - i) - (ylen - last1);
break;
}
}
printf("%d
", k);
}
好像对下标的加减关系逐渐拥有直觉。
*B - You Are Given a Decimal String...
这题不仅做过，还印象非常深刻，我是用bfs的，嗷带哥使用floyd的。
题意：有一种x-y计数器，他的初始值永远是0。每次输入只能输入x或者输入y，当输入v时，会输出当前值的最低位，然后把当前值+=v。给一个数字序列，要求从中插入最少的数字，使得这个序列变成某个x-y计数器的合法输出，对于所有的x∈[0,9]，y∈[0,9]，都进行一次求解。
题解：既然有当时做的印象，就不搞这么多奇奇怪怪的了，用bfs或者floyd预处理出连接两个数字时需要插入的点的数量，然后假如原序列的开头不是0则固定在原序列的开头添加0。把最短路加起来即可。这道题关键是要注意到，题目要求的插入最少数字的情况，当且仅当所给的数字序列中相邻两个位置之间都是插入最少数字才成立。需要注意一些细节，比如某个点自己到自己的最短距离并不是0。而且统计答案的时候相邻字符之间的距离要-1。
int ans[10][10];
int dis[10][10];
int n;
char s[2000005];
void test_case() {
scanf("%s", s + 1);
n = strlen(s + 1);
for(int x = 0; x <= 9; ++x) {
for(int y = x; y <= 9; ++y) {
for(int i = 0; i <= 9; ++i) {
for(int j = 0; j <= 9; ++j)
dis[i][j] = INF;
}
for(int i = 0; i <= 9; ++i) {
dis[i][(i + x) % 10] = min(dis[i][(i + x) % 10], 1);
dis[i][(i + y) % 10] = min(dis[i][(i + y) % 10], 1);
}
for(int k = 0; k <= 9; ++k) {
for(int i = 0; i <= 9; ++i) {
for(int j = 0; j <= 9; ++j)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
/*printf("x=%d y=%d
", x, y);
for(int i = 0; i <= 9; ++i) {
for(int j = 0; j <= 9; ++j)
printf("dis[%d][%d]=%d
", i, j, dis[i][j]);
}*/
int tmpans = 0, cur = 0, st = 2;
if(s[1] != '0') {
++tmpans;
cur = 0;
st = 1;
}
for(int i = st; i <= n; ++i) {
int nxt = s[i] - '0';
if(dis[cur][nxt] == INF) {
tmpans = -1;
break;
}
tmpans += dis[cur][nxt] - 1;
cur = nxt;
}
ans[x][y] = ans[y][x] = tmpans;
}
}
for(int x = 0; x <= 9; ++x) {
for(int y = 0; y <= 9; ++y)
printf("%d%c", ans[x][y], "
"[y == 9]);
}
}
总结：用floyd算法可以方便且正确地得到“自己到自己的距离不是0”情况下的最短路。
*C - You Are Given a WASD-string...
题意：给一个WASD串，让一个机器人沿着这个串移动，然后求出最小的包围整个路径的矩形。在恰当的位置插入恰好一个字符，只能是W、A、S或者D，使得这个矩形最小。
题解：嗷带哥当时说的解法，好像我印象还是蛮深刻的。这种插入恰好一个的解法，经常是维护前后缀的。前缀很好维护，处理出当前的位置和历史的最上最下最左最右位置即可。但是仔细想想好像后缀并不是有必要的，处理出全局最值之后貌似可以通过统计到过几次最值来解决。然后突然有个邪恶的想法，会不会是在即将第一次更新全局最值的之前，加入一个反方向字符呢？易知这样会使得这个方向的最值-1，但是很有可能会使得反方向的最值+1（假如反方向的全局最值在后面仍有更新）。
注意不是只有++之后才更新“最后一次全局最值的位置”，而是每次相等都要更新。最后再根据样例减个1（确实，假如前一步操作反方向依然是维持全局最值，那么是没有机会通过加入一个反方向来减少包围矩形的面积的，因为这样虽然缩小了这个方向的偏移，却增加了反方向的偏移）。
char s[200005];
int U, L, D, R;
int U1, U2, L1, L2, D1, D2, R1, R2;
void test_case() {
scanf("%s", s + 1);
int n = strlen(s + 1);
int x = 0, y = 0;
U = 0, L = 0, D = 0, R = 0;
U1 = 0, L1 = 0, D1 = 0, R1 = 0;
U2 = 0, L2 = 0, D2 = 0, R2 = 0;
for(int i = 1; i <= n; ++i) {
if(s[i] == 'W') {
++y;
if(y > U) {
U = y;
U1 = i;
}
}
if(s[i] == 'A') {
--x;
if(x < L) {
L = x;
L1 = i;
}
}
if(s[i] == 'S') {
--y;
if(y < D) {
D = y;
D1 = i;
}
}
if(s[i] == 'D') {
++x;
if(x > R) {
R = x;
R1 = i;
}
}
if(y == U)
U2 = i;
if(x == L)
L2 = i;
if(y == D)
D2 = i;
if(x == R)
R2 = i;
}
ll area = 1ll * (R - L + 1) * (U - D + 1);
if(L1 - 1 > R2 || R1 - 1 > L2)
area = min(area, 1ll * (R - L) * (U - D + 1));
if(U1 - 1 > D2 || D1 - 1 > U2)
area = min(area, 1ll * (R - L + 1) * (U - D));
printf("%lld
", area);
}
*D - Print a 1337-string...
题意：构造一个只有'1','3','7'三种字符串的的串，使得他恰好有n(<=1e9)个子串是"1337"，且长度不能超过1e5。
题解：看见这个长度，大概是平方，所以很自然就应该从中间的"33"入手，假如构造了一个"1333...37"，若中间有x个'3'，就有x(x-1)/2个子串。按套路构造的x应该使得x(x-1)/2<=n且x最大。用程序可求出当n=1e9时，x取到最大值且xmax=44721，易知余项不会超过f(xmax)-f(xmax-1)=44720，看一下这个长度是不是刚刚好？这道题被精心设计成用平方来构造。但是有一种更简单的思路，从中间插'7'进去，假如插入的'7'前面有x个'3'，那么又会增加x(x-1)/2个子串。也就是说，核心思想是控制只有一个'1'，然后用'7'来每次加一个组合数。易知这样是只用一个'1'的比较好的构造，假如使用更多的'1'，可以变得更短，但是极有可能会使得程序变得复杂，一种思路是构造"1331333...3"，这样始终有一个位置可以一次只加入1个子串，不过这样会导致在后面增加'7'的算法变得非常复杂。
具体实现时，用pos7数组记录每个7前面需要的3的个数。
int pos7[100005], top;
void test_case() {
ll n;
scanf("%lld", &n);
top = 0;
while(n) {
ll L = max(1ll, (ll)(sqrt(2ll * n)) - 10), R = min(n + 1ll, (ll)(sqrt(2ll * n)) + 10), X;
for(ll x = L; x <= R; ++x) {
if(x * (x - 1ll) / 2ll <= n)
X = x;
}
pos7[++top] = X;
n -= X * (X - 1ll) / 2ll;
}
putchar('1');
int cnt3 = 0;
sort(pos7 + 1, pos7 + 1 + top);
for(int i = 1; i <= top; ++i) {
while(cnt3 < pos7[i]) {
putchar('3');
++cnt3;
}
putchar('7');
}
putchar('
');
}
启示：ACM中的构造问题，正解一般都是比较好写的，不会是一些很恶心的构造。比如当时camp写的一道要求构造一个牌型恰好胡m种牌，正解就非常优美。
E - You Are Given Some Strings...
突然发现时津风过了这个2500的题，他行我也行。仔细一看，就是随便哈希一下嘛！不过细节奇多，我肯定是不能跟时津风比的。
因为总长是2e5，不同的长度至多有640种左右，他们两两组合出的结果最多就1280种左右，对于每种长度，在t中尺取转移出哈希值，用个常数小的容器统计一下。遍历所有的si，对于某个si，规定其在这次统计中必须在右侧，计算出它左侧需要的长度，然后在那个长度中取出所有的sj哈希值和si的哈希值进行组合，然后在容器中寻找。假如容器还带二分的话，复杂度极高，干脆牺牲正确概率，反正是2e5的字符串，选一个1e7的质数，然后用数组强行存应该就可以了。注意到这样仍然让每两个数对都匹配了一次，所以复杂度还是错的。
收获：总长为n的若干个数，长度至多有sqrt(n)种。