Codeforces Round 986 (Div. 2)

https://codeforces.com/contest/2028

A. Alice's Adventures in "Chess"

思路：因为数据范围很小，可以暴力遍历。

void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;
    int x = 0, y = 0;
    for (int z = 0; z < 110; z++){
        for (int i = 0; i < n; i++){
            if (s[i] == 'N') y++;
            else if (s[i] == 'S') y--;
            else if (s[i] == 'E') x++;
            else if (s[i] == 'W') x--;
            if (x == a && y == b){
                cout << "YES" << endl;
                return ;
            }
        }
    }
    cout << "NO" << endl;
}

B. Alice's Adventures in Permuting

思路：注意分类讨论即可

void solve()
{
    int n, b, c;
    cin >> n >> b >> c;
    if (b == 0){
        if (c >= n){
            cout << n << endl;
        }
        else if (c >= n-2){
            cout << n-1 << endl;
        }
        else cout << -1 << endl;
    }
    else{
        if (c >= n){
            cout << n << endl;
        }
        else cout << n-max(0ll, 1+(n-c-1)/b) << endl;
    }
}

C. Alice's Adventures in Cutting Cake

思路：对于可以取中间的任意，而两边需要保证一定的条件的题，可以分成前缀和后缀来做，然后枚举要满足的两边。

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n+1), pre(n+1);
    for (int i = 1; i<=n; i++){
        cin >> a[i];
        pre[i] = pre[i-1]+a[i];
    }
    vector<int> Prefix(m+1), Suffix(m+1);
    for (int i = 1, j = 1; i<=m; i++){
        while (j<=n && pre[j]-pre[Prefix[i-1]] < k){
            j++;
        }
        Prefix[i] = j;
    }
    Suffix[0] = n;
    for (int i = 1, j = n; i<=m; i++){
        while (j>=0 && pre[Suffix[i-1]]-pre[j] < k){
            j--;
        }
        Suffix[i] = j;
    }
    int ans = -1;
    for (int i = 0; i<=m; i++){
        if (Prefix[i] <= Suffix[m-i]){ // 相等表示Alice为空，其余正好满足
            ans = max(ans, pre[Suffix[m-i]]-pre[Prefix[i]]);
        }
    }
    cout << ans << endl;
}