Codeforces Round 753 (Div. 3)

比赛链接：https://codeforces.com/contest/1607

A. Linear Keyboard

暴力模拟题

void solve() {
    int T; cin >> T; while (T--) {
        string t; cin >> t;
        string s; cin >> s;
        vector<int> pos(100);
        for (int i = 0; i < t.size(); i++) {
            pos[t[i]-'a'] = i;
        }
        int ans = 0, now = pos[s[0]-'a'];
        for (int i = 1; i < s.size(); i++) {
            ans += abs(pos[s[i]-'a'] - now);
            now = pos[s[i]-'a'];
        }
        cout << ans << endl;
    }
}

B. Odd Grasshopper

打表找一下规律，发现每4次操作会回到原地

void solve() {
    int T; cin >> T; while (T--) {
        ll x, n; cin >> x >> n;
        if (x % 2 == 0) {
            ll tmp = n / 4 * 4;
            ll now = 0;
            for (ll i = tmp+1; i <= n; i++) {
                if (now % 2 == 0) now -= i;
                else now += i;
            }
            cout << now + x << endl;
        } else {
            if (n <= 2) {
                for (int i = 1; i <= n; i++) {
                    if (x % 2 == 0) x -= i;
                    else x += i;
                }
                cout << x << endl;
            } else {
                for (int i = 1; i <= 2; i++) {
                    if (x % 2 == 0) x -= i;
                    else x += i;
                }
                ll tmp = (n-2)/4*4+2;
                for (ll i = tmp+1; i <= n; i++) {
                    if (x % 2 == 0) x -= i;
                    else x += i;
                }
                cout << x << endl;
            }
        }
    }
}

C. Minimum Extraction

从小到大枚举当前数作为最小值，最后取max

int a[N];
void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        if (n == 1) {
            cout << a[1] << endl;
        } else {
            sort(a+1, a+n+1);
            ll sum = 0, ma = -1e9;
            for (int i = 1; i <= n; i++) {
                ma = max(ma, a[i] + sum);
                sum -= (a[i] + sum);
            }
            cout << ma << endl;
        }
    }
}

D. Blue-Red Permutation

我们将题目转化一下，变成每个数都有一个范围的取值，问是否存在取值满足$[1,n]$都存在。

直接将区间排序，然后贪心从前往后扫一遍就可以了。

int a[N];
char s[N];
struct node {
    int l, r;
    bool operator < (const node &rhs) const {
        if (rhs.l == l) return r < rhs.r;
        return l < rhs.l;
    }
}p[N];
void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        cin >> (s + 1);
        int f = 0;
        for (int i = 1; i <= n; i++) {
            if (s[i] == 'B') {
                if (a[i] < 1) f = 1;
                p[i] = {1, min(n, a[i])};
            } else {
                if (a[i] > n) f = 1;
                p[i] = {max(1, a[i]), n};
            }
        }
        if (f) cout << "NO" << endl;
        else {
            sort(p+1, p+n+1);
            int now = 1;
            for (int i = 1; i <= n; i++) {
                if (now >= p[i].l && now <= p[i].r) now++;
                else {
                    f = 1;
                    break;
                }
            }
            if (f) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
    }
}

E. Robot on the Board 1

首先考虑什么时候必定无法满足，也就是当前最大最小的坐标差大于地图时。

然后我假设起点位于$(1, 1)$的位置，如果当前位置位于地图外，我们调整起始位置将当前位置扭回来。

void solve() {
    int T; cin >> T; while (T--) {
        int n, m; cin >> n >> m;
        string s; cin >> s;
        int nowx = 1, nowy = 1;
        int ansx = 1, ansy = 1;
        int Mix = 1, Miy = 1, Max = 1, May = 1;
        int x = 1, y = 1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == 'L') y--;
            else if (s[i] == 'R') y++;
            else if (s[i] == 'D') x++;
            else x--;
            Mix = min(Mix, x);
            Max = max(Max, x);
            May = max(May, y);
            Miy = min(Miy, y);
            if (Max - Mix >= n) break;
            if (May - Miy >= m) break;
            if (s[i] == 'L') nowy--;
            else if (s[i] == 'R') nowy++;
            else if (s[i] == 'D') nowx++;
            else nowx--;
            if (nowx == 0) {
                if (ansx + 1 <= n) {
                    ansx++;
                    nowx = 1;
                } else break;
            } else if (nowx == n+1) {
                if (ansx - 1 >= 1) {
                    ansx--;
                    nowx = n;
                } else break;
            } else if (nowy == 0) {
                if (ansy + 1 <= m) {
                    ansy++;
                    nowy = 1;
                } else break;
            } else if (nowy == m + 1) {
                if (ansy - 1 >= 1) {
                    ansy--;
                    nowy = m;
                } else break;
            }
        }
        cout << ansx << ' ' << ansy << endl;
    }
}