首页 > 其他分享 >「解题报告」The 1st Universal Cup. Stage 3: Poland

「解题报告」The 1st Universal Cup. Stage 3: Poland

时间:2023-09-26 09:33:05浏览次数:54  
标签:le Cup int Universal -- while MAXN 1st top

大概按难度排序。签到题没写。

QOJ

M. Minor Evil

有 \(n\) 个球与 \(k\) 个操作,初始所有球都是白色的。第 \(i\) 个操作为如果 \(a_i\) 是白色的,那么就将 \(b_i\) 染成黑色,否则什么都不做。你可以选择每个操作执行或不执行,但是不能改变操作之间的相对顺序。现在你有一个球的集合 \(S\),问是否存在一种操作的选择方案,使得操作完后 \(S\) 中的所有球的颜色都是黑色。
\(n, k \le 4 \times 10^6\)。

首先容易发现,如果 \(b_i\) 不在 \(S\) 中,那么这个操作一定不会进行。那么也就是说,最后所有 \(S\) 的球都是黑色,其它的都是白色。

正着考虑不好考虑,可以反过来做。先将 \(S\) 中的所有球看做黑色,将操作看做是:若 \(a_i\) 是白色的,\(b_i\) 是黑色的,则将 \(b_i\) 变成白色,问能不能使得最后所有球全部是白色。发现这样每次操作肯定能操作就操作会更优,于是直接贪心做即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000006;
int T;
int n, k;
int a[MAXN], b[MAXN];
int s, p[MAXN];
bool alive[MAXN];
bool ans[MAXN];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= k; i++) {
            scanf("%d%d", &a[i], &b[i]);
            ans[i] = 0;
        }
        for (int i = 1; i <= n; i++) alive[i] = 1;
        scanf("%d", &s);
        for (int i = 1; i <= s; i++) scanf("%d", &p[i]), alive[p[i]] = 0;
        for (int i = k; i >= 1; i--) {
            if (alive[a[i]] && !alive[b[i]]) alive[b[i]] = 1, ans[i] = 1;
        }
        bool flag = true;
        for (int i = 1; i <= s; i++) if (!alive[p[i]]) {
            flag = false;
            break;
        }
        if (flag) {
            printf("TAK\n");
            for (int i = 1; i <= k; i++) putchar(ans[i] ? 'T' : 'N');
            putchar('\n');
        } else {
            printf("NIE\n");
        }
    }
    return 0;
}

I. Investors

给定一个序列 \(\{a_i\}\),你可以进行至多 \(k\) 次操作,每次操作可以将一个区间加一个正整数,最小化逆序对数。
\(n, k \le 6000\)

很简单,但是我脑瘫了。

首先发现,进行的操作一定会对一个后缀进行。因为如果某次操作不是后缀,那么将右端点扩展为最右一定不会更劣,原因显然。

而容易发现,如果每次操作都是后缀,那么显然令加的数极大最优,这样将序列划分成了若干块,每块之间不存在逆序对。这样就变成了将区间划分成 \(k+1\) 段,使得每段逆序对和最小。众所周知区间逆序对数满足四边形不等式,直接决策单调性优化即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 6005;
int T, n, k;
int a[MAXN];
int f[MAXN][MAXN], c[MAXN][MAXN];
void solve(int l, int r, int L, int R, int k) {
    if (l > r) return;
    int mid = (l + r) >> 1, M = L;
    for (int i = L; i <= R && i <= mid; i++) {
        if (f[k][mid] > f[k - 1][i] + c[i + 1][mid]) {
            f[k][mid] = f[k - 1][i] + c[i + 1][mid];
            M = i;
        }
    }
    solve(l, mid - 1, L, M, k), solve(mid + 1, r, M, R, k);
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        k++;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) c[i][j] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) if (a[i] > a[j]) c[i][j]++;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j < n; j++) c[i][j + 1] += c[i][j];
        }
        for (int i = n; i > 1; i--) {
            for (int j = i + 1; j <= n; j++) c[i - 1][j] += c[i][j];
        }
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = INT_MAX / 2;
            }
        }
        for (int i = 1; i <= n; i++) f[1][i] = c[1][i];
        for (int i = 2; i <= k; i++) solve(1, n, 1, n, i);
        printf("%d\n", f[k][n]);
    }
    return 0;
}

B. Bars

数轴上有 \(n\) 个点,你可以选若干个点为关键点,令一个点 \(i\) 靠左的第一个关键点为 \(l_i\),靠右的第一个关键点为 \(r_i\)(均不包含自己),那么这个点造成的贡献为 \(p_{l_i} + p_{r_i}\),最大化总贡献。
\(n \le 5 \times 10^5, p_i \ge 0\)

考虑一个简单 DP:设 \(f_i\) 为选中 \(i\) 为关键点的贡献,那么考虑中间的数的贡献,就有:

\[f_i = \max_{j < i} \{f_j + (i - j)(p_i + p_j)\} \]

看起来像是斜率优化的形式,但是拆开之后发现斜率优化并做不了。

首先发现第一个点与最后一个点选上一定不劣,那么贡献相当于就是 \(\sum_{i=2}^m(w_i - w_{i - 1})(p_{w_i} + p_{w_{i - 1}})\)。后者发现是与梯形面积公式是很像的,我们如果先全部除以一个 \(2\),发现贡献就变成了若干个点形成的封闭图形的面积。那么这就是个很显然的问题了,选若干个点使得封闭图形面积最大,肯定是选一个凸包最优,那么直接求凸包即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int T, n;
int p[MAXN];
int stk[MAXN], top;
long long slope(int i, int j, int k) {
    return 1ll * (j - i) * (p[k] - p[i]) - 1ll * (k - i) * (p[j] - p[i]);
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
        top = 0;
        for (int i = 1; i <= n; i++) {
            while (top >= 2 && slope(stk[top - 1], stk[top], i) >= 0) top--;
            stk[++top] = i;
        }
        long long ans = 0;
        for (int i = 1; i < top; i++) {
            ans += 1ll * (stk[i + 1] - stk[i]) * (p[stk[i + 1]] + p[stk[i]]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

L. Line Replacements

给定一个 \(n\) 个点的树,有 \(p\) 个关键点,边有边权。定义一个状态合法为,可以进行若干次操作使得所有边的边权变为零,其中一次操作为将一条路径上的所有边权减 \(1\),路径需要满足两个端点均为关键点。给定一个边集,你需要给这个边集排序,使得按顺序依次删除每条边后,任意状态都是合法的。判断是否有解,若有解,输出一组合法方案。
\(2 \le p \le n \le 500000, c_i \le 10^9\)

首先考虑什么状态下是合法的。

首先发现,如果一条路径跨过了一个关键点,那么我们可以将这个路径拆成两条路径,那么相当于我们可以在关键点的地方将树分开,看做几个子问题。每个子问题相当于路径两个端点必须是叶子(若存在一个叶子不是关键点显然是无解)。直接考虑路径不好考虑,我们直接考虑穿过某个点的所有路径。由于我们知道每条边有多少路径,那么对于某个点来说,问题可以看做将若干路径两两配对,是否能够全部匹配。这是一个经典问题,若存在一个子树路径数大于总数一半那么一定不可能全部匹配,否则如果为偶数则能够全部匹配。容易发现,如果对于每一个点都满足这样的条件,那么一定是合法的。

考虑原问题。每次删边不好考虑,反过来变成加边。那么我们先把所有边删掉,看剩下的每个连通块是否满足条件,如果不满足那就直接无解。然后考虑按照什么顺序加边。我们加边肯定是要尽可能满足条件。发现限制条件有两个:最大值不超过总数的一半,不能是奇数。如果某条要加的边的边权是奇数,那么直接就一定无解了,否则后面的条件一定可以满足。最大值不超过总数一半,那么肯定是让最大值尽可能小,那么我们按照边权从小到大的顺序加边即可。如果出现不合法装填就是无解。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int T;
int n, p, k;
bool vis[MAXN], steal[MAXN];
int u[MAXN], v[MAXN], c[MAXN];
vector<pair<int, int>> e[MAXN];
int deg[MAXN], mx[MAXN];
int ed[MAXN];
long long sum[MAXN];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &p);
        for (int i = 1; i <= n; i++) vis[i] = deg[i] = 0, e[i].clear(), steal[i] = 0;
        for (int i = 1; i <= n; i++) mx[i] = sum[i] = 0;
        for (int i = 1; i <= p; i++) {
            int x; scanf("%d", &x);
            vis[x] = 1;
        }
        for (int i = 1; i < n; i++) {
            scanf("%d%d%d", &u[i], &v[i], &c[i]);
            e[u[i]].push_back({ v[i], i });
            e[v[i]].push_back({ u[i], i });
            deg[u[i]]++, deg[v[i]]++;
        }
        scanf("%d", &k);
        for (int i = 1; i <= k; i++) {
            int x; scanf("%d", &x);
            ed[i] = x;
            deg[u[x]]--, deg[v[x]]--;
            steal[x] = 1;
        }
        for (int i = 1; i <= k; i++) {
            if ((c[ed[i]] & 1) && (!vis[u[ed[i]]] || !vis[v[ed[i]]])) {
                printf("NIE\n");
                goto nxt;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (deg[i] <= 1 && !vis[i]) {
                printf("NIE\n");
                goto nxt;
            }
        }
        for (int u = 1; u <= n; u++) if (!vis[u]) {
            for (auto [v, i] : e[u]) {
                if (!steal[i]) sum[u] += c[i], mx[u] = max(mx[u], c[i]);
            }
            if (mx[u] * 2 > sum[u] || (sum[u] & 1)) {
                printf("NIE\n");
                goto nxt;
            }
        }
        sort(ed + 1, ed + 1 + k, [&](int x, int y) { return c[x] < c[y]; });
        for (int i = 1; i <= k; i++) {
            int x = ed[i];
            if (!vis[u[x]]) {
                mx[u[x]] = max(mx[u[x]], c[x]), sum[u[x]] += c[x];
                if (mx[u[x]] * 2 > sum[u[x]]) {
                    printf("NIE\n");
                    goto nxt;
                }
            }
            if (!vis[v[x]]) {
                mx[v[x]] = max(mx[v[x]], c[x]), sum[v[x]] += c[x];
                if (mx[v[x]] * 2 > sum[v[x]]) {
                    printf("NIE\n");
                    goto nxt;
                }
            }
        }
        printf("TAK\n");
        for (int i = k; i >= 1; i--) {
            printf("%d ", ed[i]);
        }
        printf("\n");
        nxt:;
    }
    return 0;
}

E. Euclidean Algorithm

考虑这样一个算法:给定一个数对 \((x, y)\),初始集合 \(S\) 里只有这两个数,每次可以取集合中的任意两个数 \(a, b\),若 \(2a-b > 0\),那么将 \(2a-b\) 加入集合。令这个算法能够得到的最小的数为 \(f(x, y)\),问有多少 \(1 \le x < y \le n\) 的数对 \((x, y)\) 满足 \(f(x, y) = \gcd(x, y)\)。
\(n \le 10^{11}\),30 秒时间限制,8 MB 空间限制

可以发现,\(2a-b\) 就是 \(a\) 关于 \(b\) 的对称点,那么也就容易发现,这种算法能够得到的最小的数为 \(x \bmod (y-x)\)(或等于 \(x\))。

那么也就是令 \(d = \gcd(x, y), k \ge 1, p \ge 0\),则所有合法数对必须形如 \((pk+d, (p+1)k+d)\) 且满足 \(\gcd(pk+d, (p+1)k+d) = d\)。

容易发现这等价于 \(\gcd(k, d) = d\),即 \(d | k\),那么合法数对就一定形如 \((pkd+d, (p+1)kd+d)\),满足 \(k \ge 1, p \ge 0, d \ge 1\)。

计数就很容易了,这实际上就是要求 \((pk+1)d \le n\) 的正整数 \((p, k, d)\) 对数(这里令 \(p \gets p + 1\) 了),直接枚举 \(d, p\) 计算合法 \(k\),答案就是:

\[ans=\sum_{i=1}^n f\left(\left\lfloor\frac{n}{i}\right\rfloor\right), f(n) = \sum_{i=1}^{n - 1} \left\lfloor\frac{n - 1}{i}\right\rfloor \]

直接整除分块套整除分块就能做到 \(O(n^\frac{3}{4})\),由于时限 30 秒,可以通过。好像枚举 \(p, k, d\) 中最小值然后再做就是 \(O(n^\frac{2}{3})\) 了,咕了。

最小值一定是 \(O(n^\frac{1}{3})\) 级别的,于是就有:

\[\int_{1}^{\sqrt[3]{n}}\sqrt{\frac{n}{x}} \mathrm{d} x = O(n^\frac{2}{3}) \]

#include <bits/stdc++.h>
using namespace std;
int T;
long long n;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld", &n);
        long long ans = 0;
        for (long long l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l);
            long long N = n / l - 1;
            if (N) {
                long long tmp = 0;
                for (long long L = 1, R; L <= N; L = R + 1) {
                    R = N / (N / L);
                    tmp += (R - L + 1) * (N / L);
                }
                ans += (r - l + 1) * tmp;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

H. Hyperloop

给定一张无向连通图,边有边权,求 \(1 \to n\) 的最短路。若路径长度相等,那么将路径经过的边权按照从大到小的顺序排序,定义字典序更大的路径更短。输出方案。
\(n \le 10^5, m \le 3 \times 10^5, c_i \le 5 \times 10^4\),时间限制 45 秒,空间限制 64 MB,请注意空间限制。

做法其实很简单,这就是个很直接的最短路问题,路径字典序最大容易拿主席树维护哈希实现,与 CF464E The Classic Problem 做法类似,不过这个题不用处理进位问题,直接维护哈希即可。

稍微恶心点的是空间限制,如果直接在每次尝试松弛的时候都进行一次线段树操作,空间复杂度是 \(O(m \log \max\{c_i\})\) 的,由于线段树空间大致是 \(16\) 个字节的常数(记录左右儿子与哈希值),空间正好是开不下的。但是实际上,我们并不需要每次松弛的时候都进行线段树操作,在二分哈希的过程中我们是可以直接计算出加入一个数后的哈希值的,所以我们只需要在每个点的最优决策确定后再修改当前节点的线段树,这样空间复杂度就是 \(O(n \log \max\{c_i\})\) 的了,可以通过。

(实际上由于没有卡哈希,而且我也不知道好不好卡,所以开单模也是能过的,所以直接写 \(O(m \log \max\{c_i\})\) 可能也是能过的)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, MAXD = 50005;
int T;
int n, m, k;
vector<pair<int, int>> e[MAXN];
typedef unsigned long long hash_t;
typedef __uint128_t ui;
const hash_t P = 0xffffffff00000001, B = 19260817;
hash_t BASE[MAXN];
struct SegmentTree {
    struct Node {
        int lc, rc;
        hash_t hs;
    } t[MAXN * 17];
    int tot;
    void clear() { tot = 0; }
    void insert(int &p, int d, int l = 1, int r = k) {
        t[++tot] = t[p], p = tot;
        t[p].hs = ((ui) t[p].hs + BASE[d - l]) % P;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (d <= mid) insert(t[p].lc, d, l, mid);
        else insert(t[p].rc, d, mid + 1, r);
    }
    bool cmp(int p, int q, int d, int e, int l = 1, int r = k) {
        if (l == r) return t[p].hs + (d == l) > t[q].hs + (e == r);
        int mid = (l + r) >> 1;
        if (((ui) t[t[p].rc].hs + (mid < d && d <= r ? BASE[d - mid - 1] : 0)) % P == 
            ((ui) t[t[q].rc].hs + (mid < e && e <= r ? BASE[e - mid - 1] : 0)) % P)
            return cmp(t[p].lc, t[q].lc, d, e, l, mid);
        else
            return cmp(t[p].rc, t[q].rc, d, e, mid + 1, r);
    }
} st;
int dis[MAXN], root[MAXN], pre[MAXN];
bool vis[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int main() {
    BASE[0] = 1;
    for (int i = 1; i < MAXN; i++) BASE[i] = (ui) B * BASE[i - 1] % P;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) e[i].clear();
        k = 0;
        for (int i = 1; i <= m; i++) {
            int u, v, c; scanf("%d%d%d", &u, &v, &c);
            k = max(k, c);
            e[u].push_back({ v, c });
            e[v].push_back({ u, c });
        }
        st.clear();
        for (int i = 1; i <= n; i++) root[i] = 0, dis[i] = INT_MAX / 2, pre[i] = 0, vis[i] = 0;
        dis[1] = 0; q.push({ 0, 1 });
        while (!q.empty()) {
            int u = q.top().second; q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            if (u != 1) {
                root[u] = root[pre[u]];
                st.insert(root[u], dis[u] - dis[pre[u]]);
            }
            for (auto [v, c] : e[u]) if (!vis[v]) {
                if (dis[v] > dis[u] + c) {
                    dis[v] = dis[u] + c;
                    pre[v] = u;
                    q.push({ dis[v], v });
                } else if (dis[v] == dis[u] + c) {
                    if (st.cmp(root[u], root[pre[v]], c, dis[v] - dis[pre[v]])) pre[v] = u;
                }
            }
        }
        vector<int> ans;
        int u = n;
        while (u) {
            ans.push_back(u);
            u = pre[u];
        }
        reverse(ans.begin(), ans.end());
        printf("%lu\n", ans.size());
        for (int i : ans) printf("%d ", i);
        printf("\n");
    }
    return 0;
}

F. Flower Garden

你需要构造一个长为 \(3n\) 的 \(\texttt{01}\) 序列,满足以下要求:

  • \(q\) 个限制:\([a_i, b_i]\) 内的所有数全是 \(\texttt{0}\) 或者 \([c_i, d_i]\) 内的所有数全是 \(\texttt{1}\);
  • \(\texttt{0}\) 的个数与 \(\texttt{1}\) 的个数均不超过 \(2n\)。

判断是否有解,若有解,给出一种方案。

多测,\(n \le 30000, q \le 10^5, \sum n \le 3 \times 10^5, \sum q \le 10^6\)。

发现题目给的限制很像一个 2-sat 问题。

考虑转化一下第一条限制,\([a_i, b_i]\) 内的所有数全是 \(\texttt{0}\) 或者 \([c_i, d_i]\) 内的所有数全是 \(\texttt{1}\),意味着如果 \([a_i, b_i]\) 中任意一个数为 \(1\),那么 \([c_i, d_i]\) 中的所有数就都必须为 \(1\),那么我们建一张图,让 \([a_i, b_i]\) 中的所有点全部连向 \([c_i, d_i]\) 中的每一个点,那么一种 \(\texttt{01}\) 序列合法当且仅当 \(\texttt{1}\) 对应的点在这张图上为一个闭合子图。

第二个限制相当于这个闭合子图的大小 \(\in [n, 2n]\)。发现选中一个点后这个点所在的强连通分量一定都选,那么缩点得到一张 DAG,在 DAG 上选一个闭合子图使得权值和在 \([n, 2n]\) 内。那么我们分两种情况:

  • 选择的点中权值全部在 \([1, n)\) 内:那么容易发现可以随意选直到权值和落到 \([n, 2n]\) 内,如果可以选那么一定可以选到这个区间内;
  • 选择的点中权值有 \([n, 2n]\) 内的:那么权值和一定 \(\ge n\),那么我们需要选尽可能少的点使得其能够进入 \([n, 2n]\) 的范围内,于是只选这个点的后继节点即可。这样的点不超过 \(3\) 个,所以直接暴力即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1200005;
int T;
int n, q, tot;
int t1[MAXN], t2[MAXN];
vector<int> e[MAXN], t[MAXN], tr[MAXN];
int dfn[MAXN], low[MAXN], dcnt, inStack[MAXN], stk[MAXN], top;
int scc[MAXN], scccnt, siz[MAXN];
bool vis[MAXN];
#define lc (i << 1)
#define rc (i << 1 | 1)
void build(int i = 1, int l = 1, int r = 3 * n) {
    if (l == r) {
        t1[i] = t2[i] = l;
        return;
    }
    t1[i] = ++tot, t2[i] = ++tot;
    int mid = (l + r) >> 1;
    build(lc, l, mid), build(rc, mid + 1, r);
    e[t1[lc]].push_back(t1[i]), e[t1[rc]].push_back(t1[i]);
    e[t2[i]].push_back(t2[lc]), e[t2[i]].push_back(t2[rc]);
}
void add1(int a, int b, int v, int i = 1, int l = 1, int r = 3 * n) {
    if (a <= l && r <= b) {
        e[t1[i]].push_back(v);
        return;
    }
    int mid = (l + r) >> 1;
    if (a <= mid) add1(a, b, v, lc, l, mid);
    if (b > mid) add1(a, b, v, rc, mid + 1, r);
}
void add2(int a, int b, int v, int i = 1, int l = 1, int r = 3 * n) {
    if (a <= l && r <= b) {
        e[v].push_back(t2[i]);
        return;
    }
    int mid = (l + r) >> 1;
    if (a <= mid) add2(a, b, v, lc, l, mid);
    if (b > mid) add2(a, b, v, rc, mid + 1, r);
}
void tarjan(int u) {
    stk[++top] = u;
    inStack[u] = 1;
    dfn[u] = low[u] = ++dcnt;
    for (int v : e[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        int id = ++scccnt;
        while (stk[top] != u) {
            int p = stk[top--];
            inStack[p] = 0, scc[p] = id;
        }
        inStack[u] = 0, scc[u] = id, top--;
    }
}
int deg[MAXN];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &q);
        tot = 3 * n;
        build();
        for (int i = 1; i <= q; i++) {
            int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
            int v = ++tot;
            add1(a, b, v), add2(c, d, v);
        }
        for (int i = 1; i <= tot; i++) if (!dfn[i]) tarjan(i);
        for (int i = 1; i <= 3 * n; i++) siz[scc[i]]++;
        for (int u = 1; u <= tot; u++) {
            for (int v : e[u]) {
                if (scc[u] != scc[v]) t[scc[u]].push_back(scc[v]), tr[scc[v]].push_back(scc[u]);
            }
        }
        // case 1:
        queue<int> q;
        for (int i = 1; i <= scccnt; i++) deg[i] = t[i].size();
        for (int i = 1; i <= scccnt; i++) if (!deg[i]) q.push(i);
        int sum = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (siz[u] >= n) continue;
            sum += siz[u];
            vis[u] = 1;
            if (n <= sum && sum <= 2 * n) {
                vis[0] = 1;
                goto nxt;
            }
            for (int v : tr[u]) {
                if (!--deg[v]) q.push(v);
            }
        }
        // case 2:
        for (int p = 1; p <= scccnt; p++) if (siz[p] >= n) {
            for (int i = 1; i <= scccnt; i++) deg[i] = vis[i] = 0;
            vis[p] = 1;
            for (int i = 1; i <= scccnt; i++) for (int j : t[i]) deg[j]++;
            while (!q.empty()) q.pop();
            for (int i = 1; i <= scccnt; i++) if (!deg[i]) q.push(i);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : t[u]) {
                    vis[v] |= vis[u];
                    if (!--deg[v]) q.push(v);
                }
            }
            sum = 0;
            for (int i = 1; i <= scccnt; i++) if (vis[i]) sum += siz[i];
            if (n <= sum && sum <= 2 * n) {
                vis[0] = 1;
                goto nxt;
            }
        }
        nxt:;
        if (vis[0]) {
            puts("TAK");
            for (int i = 1; i <= 3 * n; i++) putchar("RF"[vis[scc[i]]]);
            putchar('\n');
        } else {
            puts("NIE");
        }
        vis[0] = 0;
        while (!q.empty()) q.pop();
        for (int i = 1; i <= tot; i++) {
            e[i].clear(), t[i].clear(), tr[i].clear();
            dfn[i] = low[i] = scc[i] = siz[i] = 0;
            deg[i] = 0;
            vis[i] = 0;
        }
        dcnt = scccnt = 0;
    }
    return 0;
}

J. Job for a Hobbit

有 \(n+2\) 个柱子,编号 \([0, n + 1]\),初始 \([1, n]\) 上有 \(k\) 个环,每个环都有颜色。每次你可以将一个柱子最上面的环移动到相邻的一个柱子的最上面,但是必须满足任意时刻每个柱子上的环数不超过 \(k\)。问是否存在一种移动方案,使得最后每个柱子上所有环的颜色全部相同。要求移动次数不超过 \(10^6\) 次。
\(n \le 50, k \le 10\)

首先判断无解,考虑每个颜色的个数 \(c_i\),那么如果 \(\sum \lceil\frac{c_i}{k}\rceil > n + 2\) 那么显然无解,否则一定可以构造解。

最终状态一定会有若干柱子上不是满的,但是如果不是满的会导致固定完一行之后后面的空位减少,可能构造会很困难。所以我们先考虑构造出一种满的方案,然后再将这个满的方案变成最终状态。容易发现,如果我们按照从左往右,从下往上的顺序依次将颜色相同的环填入,这样我们就可以从右往左,从上往下将每个环放到最靠右的位置,就能构造出最后的方案了。

那么我们现在的问题变成了,要将 \(n\) 个柱子上的环重排列成给定的方案。发现每次构造完一个柱子后,空柱子仍然是 \(2\) 个,于是我们就可以这样递归去构造,那么我们只考虑如何构造一个柱子。考虑将所有柱子全部移动到最右边,将左边第一个柱子作为要构造的位置,第二个柱子为空。那么每次我们找到一个需要移动的环,我们将这个环移动到第一个柱子上,这样就能构造出来了。

具体来说,我们可以先将第二个空柱子移动到需要移动的环的前一个柱子,然后将这个环的上面所有环(包括这个环)全部移动到空柱子上,然后将左边的柱子上的所有环全部移动到右边(显然一定能移动空),这样就将所需移动的柱子和空柱子向左移动了一位,一直重复即可。有一种特殊情况,就是当柱子是满的且所需环在最底下时,移动完之后左边的柱子没法移动到右边,但是由于没有移动完,左边必定存在一个柱子不满,那么可以将顶元素整体向左移一位,将这个柱子变成非满,然后按照上面的做法做就可以了,最后把顶元素再右移回去。

更具体的可以看代码。移动次数大概是 \(O(n^2k^2)\) 级别的。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
int T;
int n, k;
int a[MAXN][MAXN];
int top[MAXN];
int b[MAXN][MAXN];
int main() {
    scanf("%d", &T);
    while (T--) {
        int sum = 0;
        map<int, int> cnt;
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) scanf("%d", &a[i][j]), cnt[a[i][j]]++;
        }
        top[0] = top[n + 1] = 0;
        for (int i = 1; i <= n; i++) top[i] = k;
        for (auto p : cnt) sum += (p.second + k - 1) / k;
        if (sum > n + 2) { printf("NIE\n"); continue; }
        int x = 1, y = 1;
        for (auto p : cnt) {
            while (p.second--) {
                b[x][y] = p.first;
                y++;
                if (y == k + 1) y = 1, x++;
            }
        }
        if (k == 1) {
            printf("TAK\n0\n");
            continue;
        }
        vector<pair<int, int>> ans;
        getchar();
        auto opt = [&](int i, int j) {
            assert(abs(i - j) == 1);
            assert(top[i]);
            assert(top[j] < k);
            a[j][++top[j]] = a[i][top[i]--];
            ans.push_back({ i, j });
        };
        for (int i = n; i >= 1; i--) {
            for (int j = 1; j <= k; j++) opt(i, i + 1);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                int v = b[i][j];
                int x = 0, y = 0;
                for (int p = i + 1; p <= n + 1; p++) {
                    for (int q = 1; q <= top[p]; q++) {
                        if (a[p][q] == v) {
                            x = p, y = q;
                            goto nxt;
                        }
                    }
                }
                nxt:;
                for (int p = i + 1; p < x; p++) {
                    while (top[p]) opt(p, p - 1);
                }
                for (int p = x; p > i + 1; p--) {
                    if (y == 1 && top[p] == k) {
                        int w;
                        for (w = p - 2; w >= 0; w--) {
                            if (top[w] != k) break;
                        }
                        for (int q = w + 1; q <= p - 2; q++) opt(q, q - 1);
                        opt(p, p - 1), opt(p - 1, p - 2);
                        while (top[p]) opt(p, p - 1);
                        while (top[p - 2]) opt(p - 2, p - 1), opt(p - 1, p);
                        for (int q = p - 3; q >= w; q--) opt(q, q + 1);
                        while (top[p - 2]) opt(p - 2, p - 1);
                        y = k - 1;
                    } else {
                        while (top[p] != y - 1) opt(p, p - 1);
                        y = top[p - 1];
                        while (top[p - 2]) {
                            opt(p - 2, p - 1);
                            if (top[p] != k) opt(p - 1, p);
                        }
                    }
                }
                while (top[i + 1] != y) opt(i + 1, i);
                opt(i + 1, i), opt(i, i - 1);
                while (top[i]) opt(i, i + 1);
            }
            for (int p = n; p >= i; p--) {
                while (top[p] && top[p + 1] != k) {
                    int x = p;
                    while (x != n + 1 && top[x + 1] != k) {
                        opt(x, x + 1);
                        x++;
                    }
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            while (top[i]) {
                int x = i;
                while (x != n + 1 && top[x + 1] != k && (!top[x + 1] || a[x + 1][1] == a[x][top[x]])) {
                    opt(x, x + 1);
                    x++;
                }
                if (x == i) break;
            }
        }
        printf("TAK\n");
        printf("%lu\n", ans.size());
        for (auto p : ans) {
            printf("%d %d\n", p.first, p.second);
        }
    }
    return 0;
}

标签:le,Cup,int,Universal,--,while,MAXN,1st,top
From: https://www.cnblogs.com/apjifengc/p/17723973.html

相关文章

  • The 2nd Universal Cup. Stage 2- SPb
    A.MixedMessagesdp[i][j]表示前i位,选择\(j\)个移动到一起的最小花费。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstexprintinf=1E9;int32_tmain(){intn;strings;cin>>n>>s;conststringt="......
  • Ubuntu 23.10/24.04 LTS 放弃默认使用 snap 版 CUPS 打印堆栈
    导读Canonical的开发者、OpenPrinting的项目负责人TillKamppeter今年5月表示,计划在Ubuntu23.10(ManticMinotaur)上默认使用Snap版本的CUPS打印堆栈。不过经过数月的测试,官方放弃了这项决定。Ubuntu23.10(ManticMinotaur)和Ubuntu24.04LTS发行版默认还是......
  • The 2nd Universal Cup. Stage 2: SPb
    链接:https://contest.ucup.ac/contest/1356A.MixedMessages#include"bits/stdc++.h"usingnamespacestd;usingi64=longlong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;strings;cin>>n......
  • armbian安装cups打印服务器
    一、安装cups服务1、apt-getinstallcupsavahi-daemon-y2、安装驱动HP驱动:apt-getinstallhplip-y爱普生驱动:apt-getinstallprinter-driver-gutenprint兄弟驱动:apt-getinstallprinter-driver-brlaser3、systemctlrestartcups二、修改配置文件1、找到:Listenlocalhos......
  • 洛谷 AT_maximum_cup_2018_a フィギュアスケート界の貴公子埼大選手 の 题解
    这道题是一道水题,所以你的代码很可能与我相似或相同,如果你的代码出现了问题,你很可能在我的题解里找出答案。这道题大概思路是一旦$10$秒后运动员会接触到毛绒玩具,那么就加上在这个点上毛绒玩具的数量。但是!这道题有一道巨坑的点!由于这道题比较远古,所以说你即使是正解,你也要在......
  • * Dytechlab Cup 2022 A. Ela Sorting Books
    \(n\)本书必须分成\(k\)部分在书架(\(k\midn\)),每本书用一个小写的拉丁字母\([a,y]\)表示。每部分必须有严格\(\frac{n}{k}\)本书。当所有书分配完成后,对于每个部分编号为\(1,2,\cdots,k\),每部分的有\(\frac{n}{k}\)本书,他们的\(MEX\)表示这个部分,作为代表字符......
  • The 2nd Universal Cup. Stage 1: Qingdao
    GDescription给定一个数列,每次ban一个位置,在每次ban之前,求连续子序列逆序对数的最大值,强制在线。(6s)\(n\leq10^5,\sumn\leq10^6\)Solution先考虑用权值线段树来维护区间逆序对数,不难支持在原数列前后加或删除一个数。然后考虑原题的分裂过程,将一段\([l,r]\)分裂成\([l,p-......
  • Java 服务器cup占用率过高 以及 内存泄漏排查方法
    cup占用率过高常见能够引起CPU100%异常的情况都有哪些?Java 内存不够或者溢出导致GCoverheadlimitexceeded。代码中互相竞争导致的死锁。特别耗费计算资源的操作,比如正则匹配,Java中的正则匹配默认有回溯问题,复杂的正则匹配引起的CPU异常。死循环引起的CPU高度密集计算。针对第1......
  • 学习笔记-流畅的Python 1st
    P31和*都遵循不修改原有的操作对象,而是创建一个新的序列>>>a=[1,2,3]>>>c=a*2>>>a[0]=3>>>c[1,2,3,1,2,3]如果在a*n这个语句中,序列a里的元素是对其他可变对象的引用的话,你就需要格外注意了,因为这个式子的结果可能会出乎意料。比如,你想用my......
  • Linux打印服务-CUPS的安装、配置和使用
    原文:https://blog.csdn.net/limelove/article/details/121988838 CUPS(CommonUNIXPrintingSystem,即通用Unix打印系统)是苹果公司所有,一个打印集成服务。包括了前端接收打印命令的相关程序,后端控制打印机硬件的程序,中间则是打印驱动。首先来看看CUPS驱动打印机的方式。这里要......