[C++知识库]Codeforces Round #787 (Div. 3) （A-C 明早起来再补题QAQ)

	哎菜鸡的cf复健日常

A Food for Animals

水题。。。

int T;  cin >> T;
while (T--) {
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    x -= a;
    x = max(0, x);
    y -= b;
    y = max(0, y);
    if (x + y <= c)
        cout << "YES\n";
    else
        cout << "NO\n";
}

B Make It Increasing

水题。。不知道为什么小学妹小学弟一直wa QAQ，写过思路吧还是。

题意

给出一个数组$a[n]$，对于数组的每个元素 $a_i$ 都可以使之除以二（向下取整），没除以2一次就算是一次操作，问最少需要对元素进行多少次这样的操作，才能使得数组成为严格上升数组，即：$a_0<a_1<...<a_{n?1}$

思路

题目重点在最少，既然想要操作最小，那么就一定使得操作后的最大值最大，然后其他值依次刚刚好大于后一个值就好了。

因为操作后的最大值为$a_{n?1}$，那就使得它最大就好了，然而使得它最大的方法就是：不改变$a_{n?1}$的值。

所以正解就是逆向遍历数组，数组最后一个值不变，对于之后遍历的任意$a_i$都使其刚刚好比$a_{i+1}$小，就好了。在改变的过程中，主要$a_i$被变成0时，如果此时$i！=0$，说明后面的元素都会变成0，所以输出-1。

int T;
cin >> T;
while (T--) {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 0;
    bool flag = 0;
    for (int i = n - 2; i >= 0; i--) {
        while (a[i] >= a[i + 1]) {
            a[i] >>= 1;
            if (a[i] == a[i + 1] && a[i] == 0) {
                flag = 1;
                break;
            }
            ans++;
        }
        if (flag)
            break;
    }
    if (flag)
        cout << "-1\n";
    else
        cout << ans << "\n";
}

C Detective Task

模拟题。。。。又是一亿次漏判。。。

依次判断 0 、1、 ？是否存在与s中的情况，然后判断其位置就行了。
需要注意的是，0必然在1之后，否则不成立。
· 当只有 01时，答案一定为2，就因为1一定在0后面，所以能怀疑的只能是相邻的10，因为在第一个0之后，后面的只能全是0；
· 当只有0？时，那只可能是 x个？+ 1个0这种 情况才值得怀疑，所以答案是 x + 1;
· 当只有1？时，那就只可能是1个1+ y个？且 这里的1为字符串中最后一个1这个时候才可以怀疑，因为…11???111…这种的话因为？后面还有1，所以可以断定？一定可以替换为1。所以答案应该为1 + y；
· 当只有1时，只能怀疑最后一个1，答案为1；
· 当只有0时，只能怀疑第一个0，答案为1；
· 当只有？时，全部都值得怀疑，答案为n；
· 当01？都存在时，因为1一定在0 前面，所以我们只需要讨论？的位置。当出现顺序为 1 0 ？ 或者 ？0 1，说明？一定能被替换成0（01？的顺序时），或者替换成1（10？的顺序时），则答案为2。当出现顺序为1？0时，只需要判断第一出现0之前，？的个数z‘，在加上？前后相邻的一个1和0，则答案为z’+2。

int T; cin >> T;
while (T--) {
    int ans = 0;
    string s; cin >> s;
    bool flag = 0;
    n = s.size();
    if (n == 1) {
        cout << "1\n";
        continue;
    }
    int x = -1, y = -1, z = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0' && x == -1) x = i;
        else if (s[i] == '1' && y == -1) y = i;
        else if (s[i] == '?' && z == -1) z = i;
    }
    if (z == -1) {
        if (y == -1 || x == -1) ans = 1;
        else ans = 2;
    } 
    else if (x == y && x == -1) ans = n;
    else if (x == -1) {
        if (s[n - 1] == '1') ans = 1;
        else {
            for (int i = n - 1; i >= 0; i--) {
                if (s[i] == '1') {
                    y = i;
                    break;
                }
            }
            ans = n - y;
        }
    } else if (y == -1) {
        if (z == 0)  ans = x + 1;
        else
            ans = 1;
    } else if (z > x && z > y)
        ans = 2;
    else {
        for (int i = x; i >= 0; i--) {
            ans++;
            if (s[i] == '1') break;
        }
    }
    cout << max(1, ans) << "\n";
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖