Visits: 197

AtCoder Grand Contest 040

><

对于每个 <<...<>>...> 必然是两端 $0$，往中间 $+1$。

头尾特判一下。

const int N = 5e5 + 7;
int n;
char s[N];
ll ans;
vector<pair<char, int>> p;

int main() {
    rds(s, n);
    for (int i = 1, t = 1; i <= n; i++)
        if (i == n || s[i] != s[i+1]) p.pb(mp(s[i], t)), t = 1;
        else ++t;
    if (p.size() == 1u) return print(1ll * p[0].se * (p[0].se + 1) / 2), 0;
    if (p[0].fi == '>') ans += 1ll * p[0].se * (p[0].se + 1) / 2;
    if (p.back().fi == '<') ans += 1ll * p.back().se * (p.back().se + 1) / 2;
    for (ui i = 1; i < p.size(); i++)
        if (p[i].fi == '>') {
            int x = p[i-1].se, y = p[i].se;
            if (x < y) swap(x, y);
            ans += 1ll * x * (x + 1) / 2 + 1ll * y * (y - 1) / 2;
        }
    print(ans);
    return 0;
}

Two Contests

答案只有两种情况：

• 一个区间 + $n-1$ 个区间。
• 按 $l$ 排序之后，某个前缀一个集合，后缀一个集合。

const int N = 1e5 + 7;
int n, ans;
pi a[N];
int l[N], r[N];

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i].fi, a[i].se);
    sort(a + 1, a + n + 1);
    l[0] = r[n+1] = 1e9;
    for (int i = 1; i <= n; i++) l[i] = min(a[i].se, l[i-1]);
    for (int i = n; i; i--) r[i] = min(a[i].se, r[i+1]);
    for (int i = 1; i <= n; i++)
        ans = max(ans, a[i].se - a[i].fi + 1 + max(0, min(l[i-1], r[i+1]) - a[n-(i==n)].fi + 1));
    for (int i = 1; i < n; i++)
        if (a[i].fi <= l[i] && a[n].fi <= r[i+1])
            ans = max(ans, l[i] - a[i].fi + 1 + r[i+1] - a[n].fi + 1);
    print(ans);
    return 0;
}

Neither AB nor BA

将偶数位上的 A 变成 B，B 变成 A，问题等价于不能删 AA 和 BB。

不删 AA 能把 A 删光当且仅当 A 的数量 $\le \frac n2$，B 同理。

于是用总数减去 A 超过 $\frac n2$ 的方案数 $\times 2$ 就是答案。

枚举 A 的个数，时间复杂度 $\mathcal O(n)$。

const int N = 1e7 + 7;
int n;
modint a[N], now;

int main() {
    rd(n), init(n);
    a[0] = 1;
    for (int i = 1; i <= n; i++) a[i] = a[i-1] * 2;
    for (int i = n / 2 + 1; i <= n; i++) now += binom(n, i) * a[n-i];
    print(((modint)3 ^ n) - 2 * now);
    return 0;
}

Balance Beam

首先对于一个排列，合法的起点范围是一段前缀，所以目标就是相当于最大化前缀的右端点。

考虑借助图象，设 $a_i$ 之和为 $s_a$，$b_i$ 之和为 $s_b$，建立时间关于位移的折线图，则形成的是两条从 $(0,0)$ 开始分别到 $(n,s_a),(n,s_b)$ 的折线 $A,B$。

将折线 $B$ 向下平移到恰好与 $A$ 有交点的最低处，此时 $B$ 与 $x$ 轴的交点横坐标就是起点的位置 $(x,0)$。

考虑这样一条折线：从 $(x,0)$ 开始沿着 $B$ 向上走，与 $A$ 相交之后，沿着 $A$ 走到 $(n,s_a)$。

考虑枚举 $(x,0)$ 所在的段 $k$，则目标就是尽可能最大化 $k$ 右侧折线的斜率。显然对于段 $i$ 的斜率为 $\max(a_i, b_i)$，因此按照 $\max(a_i,b_i)$ 从大到小排序之后在 $k$ 右侧的折线一定是一个前缀。

最后计算一下 $k$ 中有多少部分需要放到 $x$ 的后面，对所有答案取 $\max$ 即可。

const int N = 1e5 + 7;
int n, k;
pi p[N];
ll s, ss;

int main() {
    rd(n);
    for (int i = 1; i <= n; i++)
        rd(p[i].fi, p[i].se), s += p[i].fi, p[i].fi = max(p[i].fi, p[i].se);
    sort(p + 1, p + n + 1, [&](pi x, pi y) { return x.fi > y.fi; });
    for (int i = 1; i <= n; i++)
        if ((ss += p[i].fi) >= s) {
            k = i;
            break;
        }
    ll P = 1, Q = 1;
    for (int i = 1; i <= n; i++) {
        ll w = s - (ss - p[min(i,k)].fi);
        if (w <= p[i].se && w * Q < P * p[i].se) P = w, Q = p[i].se;
    }
    P = Q - P + (n - k) * Q, Q *= n;
    ll g = __gcd(P, Q);
    print(P / g, Q / g);
    return 0;
}

Prefix Suffix Addition

设通过操作 $1$ 使第 $i$ 个数增加了 $c_i$，有 $0 \le c_i \le a_i$，操作次数为 $\sum_{i=1}^n ([c_i > c_{i+1}] + [a_i – c_i > a_{i-1} – c_{i-1}])$。

考虑 DP，设 $f_{i,j}$ 表示 $c_i = j$ 时前 $i$ 个数的最小操作次数，有转移 $f_{i+1,j^\prime} \leftarrow f_{i,j} + [j > j^\prime] + [a_{i+1} – j^\prime > a_i – j]$，时间复杂度 $\mathcal O(nw^2)$。

注意到对于 $f_{i,j}$ 相同的状态，只用保留 $j$ 最小的一个。同时若 $f_{i,j^\prime} > f_{i,j}+1$，那么 $f_{i,j^\prime}$ 也没用，于是状态数压缩到了 $\mathcal O(n)$，时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, a[N];
map<int, int> f[N];

inline void upd(int i, int j, int k) {
    if (f[i].find(j) == f[i].end()) f[i][j] = k;
    else f[i][j] = min(f[i][j], k);
}

int main() {
    rd(n), rda(a, n);
    f[0][0] = 0;
    for (int i = 0; i <= n; i++) {
        int x = 1e9;
        for (pi o : f[i]) x = min(x, o.se);
        auto it = f[i].begin();
        bool ok0 = 0, ok1 = 0;
        while (it != f[i].end())
            if ((it -> se) > x + 1) f[i].erase(it++);
            else if ((it -> se) == x + 1) {
                if (ok1) f[i].erase(it++);
                else ok1 = 1, it++;
            } else {
                if (ok0) f[i].erase(it++);
                else ok0 = 1, it++;
            }
        for (pi o : f[i]) {
            int j = o.fi, x = o.se;
            int p = j, q = a[i+1] - a[i] + j;
            if (p > q) swap(p, q);
            if (p > 0) upd(i + 1, 0, x + 2);
            if (p != q && q > 0 && p <= a[i+1]) upd(i + 1, max(p, 0), x + 1);
            if (q >= 0 && q <= a[i+1]) upd(i + 1, max(q, 0), x);
        }
    }
    print(f[n+1][0]);
    return 0;
}

Two Pieces

咕