某岛

… : "…アッカリ～ン . .. . " .. .
February 15, 2023

The 1st Universal Cup, Stage 3, Poland

Problem B. Bars

n 个人排成一排开酒吧，每个人可以选择开或不开，且每个人会去自己以外的左右最近 2 个开业酒吧各 1 次（没有则不去），第 i 个人的酒吧每招待一个顾客得 p_i 元，最大化总利润。

先写个暴力压压惊。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;

LL f[N]; int p[N];
int n;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    Rush {
        RD(n); REP(i, n) RD(p[i]);
        fill(f, f+n, 0);
        FOR(i, 1, n) {
            REP(j, i) checkMax(f[i], f[j] + (LL)(p[i]+p[j]) * (i-j));
        }
        cout << f[n-1] << endl;
    }
}

第一反应是凸壳 dp… 但是经过一番化简貌似我们需要求一个三维向量的点积的最值。。
这个就给我整不会了。。。

看了一下 maspy 的题解，原来这个东西可以类比梯形求和。。。（这堆东西叠起来的形状大概像是《魔神英雄传》里的创界山。。）
然后只要保留外面的凸壳就可以了。。做法也和求凸包类似。。。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;

int p[N], s[N], sn;
int n;

LL w(int j, int i) {
    return (LL)(p[i]+p[j])*(i-j);
}

bool bad(int a, int b, int c) {
    return w(a, b) + w(b, c) <= w(a, c);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    Rush {
        RD(n); REP(i, n) RD(p[i]);

        sn = 0; REP(i, n) {
            while (sn > 1 && bad(s[sn-1], s[sn], i)) --sn;;
            s[++sn] = i;
        }

        LL z = 0; REP_1(i, sn) z += w(s[i-1], s[i]);
        cout << z << endl;
    }
}

Problem C. Ctrl+C Ctrl+V

给定一个字符串，问至少修改几个字符，使得字符串中不存在 “ania” 模式串。

签到题。可以 kmp 不过没必要（因为模式串太短且固定）。
每次匹配到 ania 时，直接把末尾的 a 修改成一个不存在的字符即可。
也可以记录连续匹配的段数 c，然后每次增加 (c+1) / 2。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;

char p[5] = "ania";
char s[N];
int n, z, c;


int main() {
#ifndef ONLINE_JUDGE
     // freopen("in.txt", "r", stdin);
#endif

    Rush {
        n = strlen(RS(s));
        z = 0; c = 0;

        int j = 0;
        for (int i=0;i<n;++i) {
            if (s[i] == p[j]) {
                ++j; if (j == 4) {
                    ++c;
                    j = 1;
                }
            }
            else {
                z += (c+1)/2; c = 0;
                if (s[i] == 'a') j = 1;
                else j = 0;
            }
        }
        z += (c+1)/2;
        cout << z << endl;
    }
}

Problem D. Dazzling Mountain

给定一颗有根数，问有哪些满足条件的 x，使得所有子树 size 等于 x 的节点向下覆盖了所有的叶子。

显然根节点满足，最后所有的叶子节点也满足，
我们不妨枪坦推进，开个 map<int, VI> 记录当前每种不同覆盖面积的根节点。
每次取出面积最大的 VI 依次取出并往孩子移动，当每层扇形的面积都相等时，既此时 map 的 size 恰好为 1 时，则得到一组符合条件的答案，如果此时扇形面积为 1, 说明已经到了叶子，算法结束。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;

VI adj[N]; int sz[N], fa[N];
int n;

void dfs(int u = 1, int p = 0) {
    sz[u] = 1;
    for (auto v: adj[u]) if (v != p) {
        fa[v] = u; dfs(v, u);
        sz[u] += sz[v];
    }
}


int main() {
#ifndef ONLINE_JUDGE
     //freopen("in.txt", "r", stdin);
#endif

    Rush {
        RD(n); REP_1(i, n) adj[i].clear();

        DO(n-1) {
            int a, b; RD(a, b);
            adj[a].PB(b);
            adj[b].PB(a);
        }

        dfs(); VI z; z.clear();
        map<int, VI> H; H[sz[1]].PB(1);

        while (true) {
            int s = H.begin()->fi; z.PB(s); if (s == 1) break;

            do {
                auto it = H.end(); --it;
                VI U = it->se; H.erase(it);
                for (auto u: U) {
                    for (auto v: adj[u]) if (v != fa[u]) {
                        H[sz[v]].PB(v);
                    }
                }
            } while (SZ(H) != 1);
        }


        SRT(z); cout << SZ(z) << endl;
        for (auto zi : z) printf("%d ", zi);
        puts("");
    }
}

Problem E. Euclidean Algorithm

如果 a, b 在，且 2a-b>0，则 2a-b 也在，重复这个操作得到的最小的数是 gcd 的 1-n 内的整数 pair有多少个。

不会。

Problem G. Great Chase

警察抓小偷。小偷出生在数轴原点，开始向右以速度 v0 移动，它左右分别有一些警察 (pi, vi)，pi 表示警察的位置，vi 表示警察的速度，左边的警察向右追，右边的警察向左追，保证小偷的速度大于所有警察，且数轴两边都存在警察。当小偷遇上警察时，小偷会向反向移动，直到被两个警察包夹。问被包夹时，小偷移动的总距离。

小偷的运动相对比较复杂，我们考虑不管，直接二分时间，看两边的警察是否能相遇即可。

Problem I. Investors

给定 n 个数列，你可以从中筛选出 m 段连续的子序列，将它们整体 offset 一段数，最小化最后的逆序对。

显然最优解一定是每次都选一些后缀进行操作，让原序列分割成 m+1 段互不干扰的区间，分别统计这些段的逆序对和，代价函数即为每一段的逆序对。

那么显然逆序对函数符合经典四边形不等式，由此推出决策单调性。
利用队列维护当前可行决策，并用二分计算出相邻决策的分割点即可（决策不劣的最早时刻）。
（参考诗人小 G）

似乎还存在很多神奇的做法，例如 直接二分每一段代价的上界？
另外瞄了一眼 maspy 的代码，什么，这居然也有 板子？

#include <lastweapon/io>
#include <lastweapon/fenwicktree>
using namespace lastweapon;

const int N = int(6e3) + 9;

int a[N], f[2][N], w[N][N]; VI A; int p = 0, q = 1;
int Q[N], P[N]; int cz, op;
int n, m;

int calc(int l, int r) {
    return f[q][l] + w[l+1][r];
}

int left(int a, int b) {
    int l = a, r = n;
    while (l < r) {
        int m = (l + r) / 2;
        if (calc(b, m) <= calc(a, m)) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return l;
}

int main() {
#ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
#endif

    Rush {

        RD(n, m); A.clear(); REP(i, n) A.PB(RD(a[i]));

        if (m >= n-1) {
            puts("0");
            continue;
        }

        UNQ(A); REP(i, n) a[i] = LBD(A, a[i]);

        REP(i, n) {
            fenwick_tree<int> T(SZ(A));
            FOR(j, i+1, n) {
                T.add(a[j-1], 1);
                w[i][j] = w[i][j-1] + (j-i) - T.sum(a[j]+1);
            }
        }

        FOR(i, 1, n) f[p][i] = w[0][i];

        REP_1(s, m) {
            swap(p, q); cz = 0, op = 0; Q[0] = s-1;

            FOR(i, s, n) {
                //f[p][i] = INF; FOR(j, s-1, i) checkMin(f[p][i], calc(j, i))；
                while (cz < op && P[cz] <= i) ++cz;
                f[p][i] = calc(Q[cz], i);
                int j = left(Q[op], i);
                while (cz < op && j <= P[op-1]) j = left(Q[--op], i);
                P[op] = j; Q[++op] = i;
            }
        }

        cout << f[p][n-1] << endl;
    }
}

Problem M. Minor Evil

给定 1 到 n，n 个数和 m 组操作（ai, bi），每组操作表示，当序列中存在 ai 时，可以删除 bi，你必须按照顺序决定每个操作是否执行，问是否能将给定集合中的数都删除。

每个数要尽可能久的做跳板，我们应该要找到它能被删除时的最晚时刻。
第一反应可以类比 Dijkstra()，做法也确实如此。
(上次遇到类似的套路应该是在 Codeforces Round #800 (Div. 1+2) 的 C 题。)

d[i] 现在定义为：i 位置可被删除的最晚时刻。
那么对于所有不需要被删除的位置，初始 d[i] = k+1 即可。
最后只要没有 d[i] = 0 说明所有的点都可以在某个时刻被删除。

所以和原版 Dijkstra 相比，只是变成了时光倒流，以及边多了时间的限制而已。。。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;
set<int> Q[N]; VII adj[N]; char s[N]; int d[N];
int n, k;

bool dijkstra() {
    REP_1(i, k+1) Q[i].clear();
    REP_1(i, n) if (d[i] == k+1) Q[k+1].insert(i);

    DWN_1(i, k+1, 2) {
        for (auto u: Q[i]) {
            for (auto e: adj[u]) {
                int v = e.fi, w = e.se;
                if (d[v] < w && w < i) {
                    if (d[v]) Q[d[v]].erase(Q[d[v]] .find(v));
                    Q[d[v] = w].insert(v);
                }
            }
        }
    }

    REP_1(i, n) if (!d[i]) return 0;
    return 1;
}

int main() {

#ifndef ONLINE_JUDGE
     //freopen("in.txt", "r", stdin);
#endif

    Rush {

        RD(n, k); REP_1(i, n) adj[i].clear();

        REP_1(i, k) {
            int a, b; RD(a, b);
            adj[a].PB({b, i});
        }

        REP_1(i, n) d[i] = k+1;
        Rush d[RD()] = 0;

        if (!dijkstra()) {
            puts("NIE");
        } else {
            puts("TAK");
            REP(i, k) s[i] = 'N';
            REP_1(i, n) s[d[i]-1] = 'T'; s[k] = 0;
            puts(s);
        }
    }
}

Posted by xiaodao
Category: 日常

« | »

  • Archives

    open all | close all