[21.02.23]codeforces 704 div2（补题完成度【4/5】）

复健选手的第一场cf，rating0-575。
现在的cf竟然是从灰名往上爬升了。还是说我已经是掉到灰名水平了。震惊。

A是签到
B是算结论题。有样例就是方便，公式没推，注意细节想清楚。
C是字符串双向遍历。这次的代码下标和写法我还是比较满意的，还是细节有点马虎，注意边界。
D是构造题。比赛时候最后十几分钟，找了一个二进制减法计算起才发现万能的构造做法，没交上去。以前打acm的时候不会犯这种错误的。
E从感觉上像dp/搜索/构造成图论或网络流，暂时没做出来。

D.Genius’s Gambit

题意：两个二进制串s,t，每个串都是a个0和b个1组成，希望使他们二进制相减后有k个1，判断是否存在，存在则任意构造。
思路：

众所周知，二进制数某一位做减法时0-0=0，1-1=0。仅0-1或者1-0的时候相减会出现1。
- 当1-0时，仅此位为1，对题意构造的k比较浪费。
- 当0-1时借位，导致之前的所有相等的位全部变成1，直到再碰到对应位不同的位置。
  - 如果碰到0-1，当位为0，继续向前借位。
  - 如果碰到1-0，之后所有相等的位都是0.
  - s>t且位数相同，所以总会碰见1-0的情况，因为s和t的0/1个数都相同，所以多余0-1对使构造复杂，应尽可能避免干扰。
列出基本的两种构造，不需要用的位都相等的列在前边，后面从右往左一组0-1，中间相等，直到碰到一组1-0停止。（不是最终答案）
- 1x..x10000减1x..x00001，得到4个1
- 1x..x11110减1x..x01111，得到4个1
- 只要能拿出一些0和1构造这样的序列前面多少个按位对其x都行。因此，k<a和k<b-1的时候一定可构造。（s和t的首位都必须是1）
  那么，k>a and b一定不行吗？并不是（这段当时差几分钟没交上去）
只要是s和t形如1x..x0和0x..x1，只要s和t按位对齐，这个过程中x是0或者1可以穿插出现。
- 构造：s’=11..1 00..0。
- 按k从右到左找到01交换位:如果位置是1则和尾巴的0交换，
- 则作为t’=1..101..1 00..01。
- s’和t’就符合要求啦。

例子：

但这个方法有个问题：如果找到的位置的数字是0就没办法和末尾0交换了。
为了避免这种情况，可以在之前把对应位置和第二位往后任意一个1提前交换作为s，保证待交换位是1。这样只要k<a+b-1，都可行。

例子：

4 5 2
// 111110000 需要交换倒数第3位和倒数第1位
// 101110100 倒数第3位是0，和正数第2位的1交换

Yes
101110100
101110001

而k=a+b-1，k+00..1=100..0 (a+b位)，需要交换第一个数字，而第一个数字必须是1，总之不存在。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int ans[200005];
int main()
{
    int a,b,k;
    scanf("%d%d%d", &a, &b, &k);  // (0, 1, k)
    if(k == 0){
        printf("Yes\n");
        for(int i = 0; i < b; i++)printf("1");
        for(int i = 0; i < a; i++)printf("0");
        printf("\n");
        for(int i = 0; i < b; i++)printf("1");
        for(int i = 0; i < a; i++)printf("0");
        printf("\n");
    }
    else if(k == a+b || a==0 || b==1){
        printf("No\n");
    }
    else if(k < a+b-1){
        printf("Yes\n");
        for(int i = 0; i < b; i++)ans[i] = 1;
        for(int i = b; i < b+a; i++)ans[i] = 0;
        k = a+b-k-1;
        int change = ans[k];
        if(change == 1){
            for(int i = 0; i < b+a; i++)printf("%d", ans[i]);printf("\n");
            ans[k] = 0;
            ans[b+a-1] = 1;
            for(int i = 0; i < b+a; i++)printf("%d", ans[i]);printf("\n");
        }
        else{
            ans[1] = 0;
            ans[k] = 1;
            for(int i = 0; i < b+a; i++)printf("%d", ans[i]);printf("\n");
            ans[k] = 0;
            ans[b+a-1] = 1;
            for(int i = 0; i < b+a; i++)printf("%d", ans[i]);printf("\n");
        }

    }
    else{
        printf("No\n");
    }
}

C. Maximum width

题意：长度为n的字符串s，长度为m的字符串t。找到s的子序列等于t。定义wideth为子序列中任意两字母相距位置的最大值。找到所有符合条件的子序列最大的width。
思路：贪心。从左到右遍历s找一个最左边的子序列a，从右到左遍历s找一个最右边的子序列b，则答案的子序列为a的左半边和b的右半边拼接的结果，拼接位置遍历一遍。
代码如下：

#include<bits/stdc++.h>
using namespace std;
char s[200005];
char t[200005];
int ans1[200005];
int ans2[200005];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    scanf("%s", s);
    scanf("%s", t);
    int pointt=0;
    for(int points=0; points < n; points++)
    {
        if(s[points] == t[pointt]){ans1[pointt++]=points;if(pointt == m)break;}
    }
    pointt = m-1;
    for(int points=n-1; points > -1; points--)
    {
        if(s[points] == t[pointt]){ans2[pointt--]=points;if(pointt == -1)break;}
    }
    
    int ans = 0;
    for(int i = 1; i < n; i++){
        ans = max(ans, ans2[i]-ans1[i-1]);
    }
    printf("%d\n", ans);
    return 0;
}

Starry Wintersky

20210223 Codeforces Round 704 (Div. 2)

[21.02.23]codeforces 704 div2（补题完成度【4/5】）

D.Genius’s Gambit

C. Maximum width