您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

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[n] a[n],对于数组的每个元素 a i a_i ai 都可以使之除以二(向下取整),没除以2一次就算是一次操作,问最少需要对元素进行多少次这样的操作,才能使得数组成为严格上升数组,即: a 0 < a 1 < . . . < a n − 1 a_0 < a _1 < ... < a_{n-1} a0<a1<...<an1

思路

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

因为操作后的最大值为 a n − 1 a_{n-1} an1,那就使得它最大就好了,然而使得它最大的方法就是:不改变 a n − 1 a_{n-1} an1的值。

所以正解就是逆向遍历数组,数组最后一个值不变,对于之后遍历的任意 a i a_i ai都使其刚刚好比 a i + 1 a_{i + 1} ai+1小,就好了。在改变的过程中,主要 a i a_i ai被变成0时,如果此时 i ! = 0 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";
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进