打得很烂，预计 1500 只拿到了 700，甚至比 VP 打得还要差。

A

一遍 AC。

int main() {
    int x = read();
    if (x % 100 == 0 && x > 0) puts("Yes");
    else puts("No");
    return 0;
}

B

一遍 AC。

const int MAXN = 2000 + 10;

std::string ss;
std::string strs[MAXN];

int main() {
    cin >> ss;
    strs[1] = ss;
    for (int i = 2; i <= ss.length(); ++i) {
        strs[i] = strs[i - 1];
        char last = strs[i][0];
        strs[i].erase(strs[i].begin());
        strs[i] += last;
    }
    std::sort(strs + 1, strs + 1 + ss.length());
    cout << strs[1] << endl;
    cout << strs[ss.length()] << endl;
    return 0;
}

C. Doukasen

垃圾解方程题，我被卡在第三个样例上了，没调出来，换了题解的写法才过。

其实这种解方程题并不用非得去找到特定位置然后列数据解方程，可以直接去把等式的值求出来，然后用这个值去求解，比如这个题的方程就是 \(\mathrm{ltime} + \frac{x}{B} = \mathrm{rtime} + \frac{A - x}{B}\)，等式的意义是两边烧的时间相等（都是 \(\frac{1}{2}\sum\frac{A}{B}\)，于是可以直接求这个东西，再带回原式求解。

const int MAXN = 1e5 + 10;

int n;
double aa[MAXN], bb[MAXN];
double burntime[MAXN];
double prefix[MAXN], suffix[MAXN];

int main() {
    n = read();
    for (int i = 1; i <= n; ++i){
        aa[i] = read(); bb[i] = read();
        burntime[i] = (double) aa[i] /(double) bb[i];
    }
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + burntime[i];
    }
    double len = 0;
    double tim = prefix[n] / 2.0;
    rep (i, 1, n) {
        if (prefix[i] > tim) {
            double dt = tim - prefix[i - 1];
            len += bb[i] * dt;
            printf("%.6lf\n", len);
            return 0;
        }
        len += aa[i];
    }
    return 0;
}

D. Restricted Permutation

第一眼看过去和《菜肴制作》差不多，其实还有些不一样，令最小的最靠前和令字典序最小这两个是不同的，前者需要建反图反着跑，后者建正图就可以了。核心思想都是利用优先队列代替普通队列。

const int MAXN = 2e5 + 10;

int n, m;

std::vector<int> G[MAXN];
int ind[MAXN];

int main() {
    n = read(); m = read();
    rep (i, 1, m) {
        int u = read(); int v = read();
        G[u].push_back(v);
        ++ind[v];
    }
    std::vector<int> ord;
    std::priority_queue<int, std::vector<int>, std::greater<int> > q;
    for (int i = 1; i <= n; ++i) {
        if (!ind[i]) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.top(); q.pop();
        ord.push_back(u);
        std::sort(ALL(G[u]));
        forall (G[u], i) {
            int v = G[u][i];
            --ind[v];
            if (!ind[v]) {
                q.push(v);
            }
        }
    }
    if (ord.size() != n) printf("-1");
    else for (auto v : ord) printf("%d ", v);
    puts("");
    return 0;
}

F. Parenthesis Checking

也是套路了，把左括号看成 \(+1\) 右括号看成 \(-1\)，一个括号串合法等价于整个串的和为 \(0\) 且中间没有掉到负数（相对值），所以需要对原序列维护一个区间和，前缀和的最小值，后面这个东西有点反直觉但是也能直接维护。

考场上我懒得去费劲想这个东西了，所以我选择用线段树维护前缀和数组，一次操作等价于修改两个后缀 \([l, n]\) 和 \([r, n]\)，查询就是查 \(r\) 和 \(l - 1\) 两个点的值和 \(l\) 到 \(r\) 的区间最小值。

然后区间最值写挂了，调一场没调出来。

#错误警示：想清楚区间修改到底是怎么修改的。基础题不要写错。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define forall(G,i) for (int i = 0, __for_siz__ = (int) (G).size(); i < __for_siz__; ++i)
#define DEBUG(x) std::cerr << #x << " = " << x << endl;
#define rep(i_,a_,b_) for (int i_ = (a_); (i_) <= (b_); (i_) = (i_) + 1)
#define ALL(x) (x).begin(), (x).end()
#define MP std::make_pair
#define se second
#define endl '\n'
#define fi first

using std::cin;
using std::cout;

typedef long long int lli;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

inline lli readll() {
    lli s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 4e5 + 10;

int n, q;
char ss[MAXN];

namespace Segt {
lli minx[MAXN << 2], sum[MAXN << 2];
lli tag[MAXN << 2];

#define ls (p << 1)
#define rs (p << 1 | 1)

void Update(int p) {
    sum[p] = sum[ls] + sum[rs];
    minx[p] = std::min(minx[ls], minx[rs]);
}
void buildTree(int p, int l, int r, lli *seq) {
    if (l == r) { minx[p] = sum[p] = seq[l]; return;  }
    int mid = (l + r) >> 1;
    buildTree(ls, l, mid, seq); buildTree(rs, mid + 1, r, seq);
    Update(p);
}
void Add(int p, lli l, lli r, lli k) {
    sum[p] += k * (r - l + 1);
    minx[p] += k;
    tag[p] += k;
}
void Pushdown(int p, int l, int r) {
    if (!tag[p]) return;
    int mid = (l + r) >> 1;
    Add(ls, l, mid, tag[p]); Add(rs, mid + 1, r, tag[p]);
    tag[p] = 0;
}
void Modify(int p, int l, int r, int ll, int rr, lli k) {
    if (l == ll && rr == r) { Add(p, l, r, k); return;  }
    int mid = (l + r) >> 1;
    Pushdown(p, l, r);
    if (rr <= mid) Modify(ls, l, mid, ll, rr, k);
    else if (mid + 1 <= ll) Modify(rs, mid + 1, r, ll, rr, k);
    else {
        Modify(ls, l, mid, ll, mid, k);
        Modify(rs, mid + 1, r, mid + 1, rr, k);
    }
    Update(p);
}
std::pair<lli, lli> Query(int p, int l, int r, int ll, int rr) {
    if (rr < 1) return {0, 0};
    if (l == ll && rr == r) return {sum[p], minx[p]};
    Pushdown(p, l, r);
    int mid = (l + r) >> 1;
    if (rr <= mid) return Query(ls, l, mid, ll, rr);
    else if (mid + 1 <= ll) return Query(rs, mid + 1, r, ll, rr);
    else {
        std::pair<lli, lli> lt = Query(ls, l, mid, ll, mid), rt = Query(rs, mid + 1, r, mid + 1, rr);
        return {lt.first + rt.first, std::min(lt.second, rt.second)};
    }
}
}

lli seq[MAXN];

int main() {
    scanf("%d %d", &n, &q);
    scanf("%s", ss + 1);
    rep (i, 1, n) {
        if (ss[i] == '(') seq[i] = 1;
        else seq[i] = -1;
        seq[i] += seq[i - 1];
    }
    Segt::buildTree(1, 1, n, seq);
    while (q --> 0) {
        int pos, l, r; scanf("%d %d %d", &pos, &l, &r);
        if (pos == 1) {
            lli tl = Segt::Query(1, 1, n, l, l).first - Segt::Query(1, 1, n, l - 1, l - 1).first;
            lli tr = Segt::Query(1, 1, n, r, r).first - Segt::Query(1, 1, n, r - 1, r - 1).first;
            Segt::Modify(1, 1, n, l, n, -tl + tr);
            Segt::Modify(1, 1, n, r, n, -tr + tl);
        } else {
            std::pair<lli, lli> fx = Segt::Query(1, 1, n, r, r), pref = Segt::Query(1, 1, n, l - 1, l - 1), px = Segt::Query(1, 1, n, l, r);
            if ((fx.first - pref.first) || (px.second - pref.first)) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}