A ⑨的完美绘画教室

题意简述

给一个CMY?序列，要求找到是否存在两种或以上填空方法使得这个字符串满足相邻两个字符不同的要求。

题解思路

其实最好写的做法应该是DFS试图寻找两个方案，找到两个就直接exit。不过我这场的时候头铁写了各种if。
既然写了if的方法就来说说思路吧。我们观察连续?的各种情况：

1. C?C，显然这里有两种填法，出现这种情况就可以Yes了
2. C?M，只能填一个，跳过
3. C??C，有至少两种填法
4. C??M，有至少两种填法
5. C???C，有至少两种填法
6. C???M，填法就比较多了，至少有两种
7. ?更多的情况显然方案数更多

那么可行的情况是：

1. 连续的?不少于2个
2. 只有一个?且左右两边字符相同

接着还有绝对不合法的情况：

1. 两个相邻的字符不是?且相同

判完就能AC了。头还是不够硬，fst了。

代码

// Code by KSkun
#include <cstdio>

int n;
char str[105];

int main() {
    scanf("%d%s", &n, str + 1);
    str[0] = '?';
    str[n + 1] = '?';
    bool success = false;
    for(int i = 1; i <= n + 1; i++) {
        if(str[i] == '?') {
            if(str[i - 1] == '?' || str[i + 1] == '?' || 
                (str[i - 1] != '?' && str[i + 1] != '?' && str[i - 1] == str[i + 1])) {
                success = true;
            }
        } else {
            if(str[i - 1] != '?' && str[i] == str[i - 1]) {
                success = false;
                break; 
            }
        }
    }
    if(success) printf("Yes"); else printf("No");
    return 0;
}

B 东舰共荣和平会议

题意简述

a一类，b一类，c可以转变为a或b类，想让相同数量的a类b类混一起，求最大数量。

题解思路

考虑贪心。
如果a+c < b或者b+c < a答案就是2倍的a、b中较小值加上c。
否则我们把一部分c转换成ab中较少的那一类使得a=b，再平分剩下的c。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

int l, r, a;

int main() {
    l = readint();
    r = readint();
    a = readint();
    if(a >= std::abs(r - l)) {
        a -= std::abs(r - l);
        printf("%d", (std::max(l, r) + a / 2) * 2);
    } else {
        printf("%d", (std::min(l, r) + a) * 2);
    }
    return 0;
}

C 请当心车门与站台之间的隙间

题意简述

琪露诺（就是那个声称幻想乡没有巴士的小妖精）被幻想乡公交公司聘用为调度员，她现在正在管理雾之湖车站的进出站。具体而言，她现在拥有一份这个车站的时刻表，有若干班车按照时刻表的计划进站。每一班车进站需要 1 分钟时间。
不妙的是，有一班紧急班车需要临时进站，她现在想要将它的进站时间安排在某两班车之间的空隙中。这班车的进站也只需要 1 分钟，但是为了安全保证，它进站之前之后 s 分钟内不得有其他班车正在进站。
由于班车很紧急，琪露诺需要找到最早可以插入这班车的时间。不过由于她又去冻青蛙+1s了，所以你要来帮她解决这个问题。

题解思路

就是直接模拟一遍嘛。
注意特判一下是否能放在开头、结尾就行了。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

int n, s, h[105], m[105];

int main() {
    n = readint(); s = readint();
    for(int i = 1; i <= n; i++) {
        h[i] = readint(); m[i] = readint();
    }
    if(h[1] * 60 + m[1] >= s + 1) {
        printf("0 0");
        return 0;
    }
    for(int i = 2; i <= n; i++) {
        int del = (h[i] - h[i - 1] - 1) * 60 + m[i] + 60 - m[i - 1] - 1;
        if(del >= s * 2 + 1) {
            m[i - 1] += s + 1;
            h[i - 1] += m[i - 1] / 60;
            m[i - 1] %= 60;
            printf("%d %d", h[i - 1], m[i - 1]);
            return 0;
        }
    }
    m[n] += s + 1;
    h[n] += m[n] / 60;
    m[n] %= 60;
    printf("%d %d", h[n], m[n]);
    return 0;
}

D 出题人的自我修养

题意简述

有一个只由0和1构成的字符串。我们规定，题目中所有合法的01串都满足以下性质：

1. 只由0和1构成。
2. 没有多余的前导0。

你可以对一个01串进行下列操作：

1. 交换任意两个相邻字符。如101交换后两个字符后变为110。
2. 将两个相邻的1替换成一个1。如110替换后变为10。

我们规定记号 val(s) 是二进制表示为01串 s 的那个数字。而称01串 a 小于01串 b 当且仅当 val(a) < val(b) 。

现在，你要找到一个最小的合法01串且这个01串可以由给定的01串 s 经过上述操作变化而来。

题解思路

实质你可以把一堆1全部转到前面然后消成1个1，因此答案就是1后面跟原来字符串里有的0。
注意如果整个字符串没有1，只需要输出0。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool is01(char c) {
    return c == '0' || c == '1';
}

inline int read01() {
    char c;
    while(!is01(c = fgc()));
    return c - '0';
}

int n, c0, c1;

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        if(read01() == 0) c0++; else c1++;
    }
    if(!c1) {
        puts("0");
        return 0;
    }
    putchar('1');
    while(c0--) {
        putchar('0');
    }
    return 0;
}