欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Educational Codeforces Round 53 (Rated for Div. 2)

程序员文章站 2024-03-06 21:25:14
...

C. Vasya and Robot 【二分】
暴力左端点,二分右端点。在[L,R]区间内任意填方向,根据区间外的方向值和终点(x,y)计算出此区间需要能否填成。
判断式:r - l >= abs(res1) + abs(res2) && (r - l - abs(res1) - abs(res2)) % 2 == 0.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int MAXN = 2e5 + 10;
char str[MAXN];
int dp1[MAXN], dp2[MAXN];
int n, x, y;

bool so(int l, int r) {
    int res1 = dp1[n] - dp1[r - 1] + dp1[l - 1];
    int res2 = dp2[n] - dp2[r - 1] + dp2[l - 1];
    res1 = y - res1, res2 = x - res2;
    if(r - l >= abs(res1) + abs(res2) && (r - l - abs(res1) - abs(res2)) % 2 == 0) return true;
    return false;
}

int main() {
    scanf("%d", &n);
    scanf("%s", str + 1);
    scanf("%d %d", &x, &y);
    for(int i = 1; i <= n; ++i) {
        dp1[i] = dp1[i - 1], dp2[i] = dp2[i - 1];
        if(str[i] == 'U') dp1[i]++;
        else if(str[i] == 'D') dp1[i]--;
        if(str[i] == 'R') dp2[i]++;
        else if(str[i] == 'L') dp2[i]--;
        //printf("## %d %d %d\n", i, dp1[i], dp2[i]);
    }
    int ans = MAXN;
    for(int i = 1; i <= n; ++i) {
        int l = i, r = n + 1;
        while(r - l >= 0) {
            int mid = (l + r) >> 1;
            if(so(i, mid)) ans = min(ans, mid - i), r = mid - 1;
            else l = mid + 1;
        }
        //printf("# %d %d\n", l, r);
    }
    if(ans == MAXN) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

D. Berland Fair 【链表+暴力剪枝】
按照题意用链表模拟,每次删除的过程中,改变总和sum。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int MAXN = 2e5 + 10;
char str[1010];
LL a[MAXN]; int pre[MAXN];
int n; LL sum = 0, m;
LL ans = 0; int id = 1, son = n;

void so() {
    while(1) {
        if(m >= a[id]) {
            ans++;
            m -= a[id];
            son = id;
            id = pre[id];
        } else {
            sum -= a[id];
            pre[son] = pre[id];
            id = pre[id];
            n--;
            return ;
        }
    }
}

int main() {
    LL res = 1e9 + 7;
    scanf("%d %lld", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        pre[i] = i + 1;
        sum += a[i];
        res = min(res, a[i]);
    }
    pre[n] = 1; bool flag = true;
    while(m >= res) {
        if(m >= sum) { //剪枝,sum实时改变
            ans += (m / sum * n);
            m %= sum;
            so();
        } else so();
    }
    printf("%lld\n", ans);
    return 0;
}