专栏文章

困难关键例题

OOIer_ACMer
休闲·娱乐参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mineaeop
此快照首次捕获于
2025/12/02 01:00
3 个月前
此快照最后确认于
2025/12/02 01:00
3 个月前
查看原文

扫描线的第一次初遇：CF526F Pudding Monsters

关键点：

将寻找一个数列所有满足要求子串化为枚举右端点并用线段树存左端点的范围，计算贡献，变量val计算最小值，cnt存出现多少次（左端点均在线段树维护的范围内）。

做题过程：

  1. 发现性质：将x排序后，MAX-MIN=R-L是答案。
  2. 移项，将答案转化成MAX-MIN+R-L=0的区间。
  3. 由于我们要枚举所有的区间，所以我们要固定一个右端点（否则就是n^2），将左端点打包成一个节点用数据结构维护。
  4. 因为一整段左端点与R形成的子串的val值大部分的差距就是l的大小，也就是+1-1的关系，且一整段L和一个R对应序列的MAX和MIN大部分都是一样的的，一变也是变的一整段（区间修改），因此我们考虑线段树。

Trick:

  1. 由于我们的R不同对应的MAX和MIN也会不同，所以我们在枚举时要统计当前这个数会修改前面哪几段的MAX或者MIN,这个方法也叫扫描线！！！
  2. 由于我们在更新区间右端点时组左端点l不会变，时可以直接将l存在一开始build的val中，反正不变。

初遇三元环计数：P1989

核心技巧：

由于我们不能暴力从每个点出去搜三次，不然会超时，因为消耗时间最多的是出度，所以我们可以确定边的方向，用“度数小的连度数大的，否则按照编号喜好连边”的规则确定方向，减少枚举次数。

思考过程：

  1. 我一开始思考暴力30分部分，但是已经无法优化；
  2. 之后考虑减少枚举次数，因为核心要素是要降低出度，所以我们要确定边的方向;
  3. 想到这就简单了，我们这么做可以让枚举次数由一开始的每个点每个方向三次，变成只用整体遍历一次（由于出度限制只有根号m次），加上O(1)判断，简直完美。

Trick：

证明上述连边方式减少时间复杂度至根号m的过程： 7xYE60.png

恐怖容斥一命速通：CF985G

关键点：

我们发现反向建边太麻烦就可以考虑和它思想差不多（去除不合格的留下合格的）但更难却更高效的方法——容斥。

思考步骤：

  1. 首先，我们既然要做容斥，就要知道容斥的公式：总体方案数-最多可能重复的种类数+次多可能重复的种类数……；
  2. 尽管公式不会证，但我们首先来考虑我们这几种分别是什么，怎么算；
  3. 首先，最多可能的，也就是总体方案，肯定是任选三个点组成的三元组的答案，由于我们很容易发现(1,2,3)和(2,3,1)都会在枚举过程中出现，但它们属于一种，所以我们默认a<b<c，下面也是一样，防止重复，这样我们很快就能知道a,b,c在各自的位子上的贡献是多少；
  4. 当我们考虑要求一条边的情况时，也会有重复，我们就钦定u<v，那么剩下的就是再在这个分类讨论里分析下一个点w的大小，因为w的大小的确无法判定；
  5. 接下来是两条边，因为我们只能确定一个点，所以剩下两个点v和w又会有重复情况，所以钦定v<w，之后就是判断u<v<w，u>w>v，v<u<w，这几种的答案怎么算；
  6. 最后一种就是三条边都选，就是三元组问题，和上一道差不多；
  7. 最后公式就是总方案数-至少有一条边+至少至少两条边-至少三条边=ans！

Trick：

容斥原理实在是太困难了，为防止以后回顾这些题傻了，就放个通俗易懂的方法增援未来： 7xiHTL.png

分层图关键例题：P4822

关键点：

由于题目中明确说了会有对边权大小改变(1)的操作，且操作完直接体现在图上(2)，而且还有限制(3)，三点完全满足对于分层图的应用。

思考过程：

  1. 一开始想的DP，因为K不大，N不大，可以考虑二维图上DP，但是不会写，尽管题解有；
  2. 之后，复习分层图的三个重要特征，发现完全符合，便尝试考虑分层图；
  3. 我们首先将/2操作变为改变状态，一个状态也就是一层图，我们每层图之间都会连单向边，表示将原有的边的边权减半，同时保证不能再从这一层爬回去（这个问题有点绕，我想了好久才知道怎么解决），表示进入了使用第~张牌的状态。
  4. 在上面做Dij就行了，只不过最后的结果要对每一层的终点求最小值（因为不一定用的牌越多越好）。

Trick：

7X6llx.png，还有，分层图还可以实现这个功能： 7X80YU.png

跳楼机教你复建同余最短路：P3403

关键原理：

由于我们可以发现我们的式子很像d[x]+val>=d[y]，且要求的d是最小值，所以可以用同余最短路计算。

思考过程：

  1. 发现有三个未知量，所以不能直接暴力，要首先确定1-2两个值；
  2. 由于题目要求的是“这个几个数无限个能够组成哪几种数这一类问题”，属于同余最短路经典解决问题，所以我们可以往这方面考虑；
  3. 首先，我们既然要用同余最短路，那么我们要确定一个除数，所以我们以x为除数（不过任选y，z都可以），要确定的是y，z的个数；
  4. 我们设f(i)表示mod x余数为i最小的by+cz，那么我们可以发现这个玩意可以变成f(i)+y>=f((i+y)%x)，也是同余最短路的标准方程，那么我们就变成将i和(i+y)%x连边，得到的图用来跑最短路，就能得到每个f的值；
  5. 最后，答案就是f的函数值与h的差距值对x求商的结果，说人话就是在这个最小值之上还能加多少个x。

Trick:

同余最短路可以处理哪些情况： 7Xl0oh.png

多层贡献用DP：P3554

关键点：

你这个涂色可以分层涂，那么贡献是多层加的，而且问的是最大值，那么二分+DP。

做题思路：

  1. 一开始觉得肯定是将每一层最多儿子的father捞出来，将他的大小一一比较找最大。
  2. OK，然后G了，但是22分很爽
  3. 深度思考+题解辅助后，发现其实涂色不一定局限于同一层，可以增员未来，将下面的点也涂上色。
  4. 由于贡献开始向着最优解的方向转变，那么我们就要考虑贪心之上的做法——DP。
  5. 首先，我们发现我们的痛点就是有时一层涂不完，需要借力，那么我们就将状态设置为我们这一个点的子树之下没涂（或者还需要在k之外涂多少个点）的点的个数。
  6. 每次，我们都将子节点需要涂的需求上交给父亲，如果父亲有能力完成，就和k做差值，发现小于0，但实际意义是这些点全部满足，所以和0取max就可以了；
  7. 如果没能力完成，差值大于0，那么就再往上传值，直到1号节点；
  8. 二分的话，就是二分我们的答案，毕竟我也没想到其它二分的维度，每次将答案扔进去DFS，判断根节点的需求是否满足就可以了。

初遇二进制优化DP：CF755F

关键点：

我们的环在处理最小值时情况太多，而且或有多种不同贡献最终的次数相同，背包会炸，所以要二进制优化……

做题思路：

  1. 一开始大家都会很开心，因为发现最大值很好求，每次的贡献要么加二，要么加一，非常朴素。
  2. 但是重点是如何处理最小值，我们发现最小值和最大值差不多，唯一的区别就是在一个环上第一次和最后一次的贡献不同罢了，但是加起来还是等于环的长度。
  3. 好，那么接下来，我们考虑如何取到最小值，因为我们每次都会以一个加二贡献的操作开头，之后我们的操作都是加一，直到我们达到最后一个点没有贡献，那么我们可以这样考虑：既然我们一共 kk 次操作，那么我们均摊到每次上得到的最终结果之和要么是 k+1k + 1，要么是 kk，其中，没有加一的那次对应的就是所有的环都是完结撒花，有加一的那次对应的就是多了一条链。
  4. 我们为了保证最小，肯定优先从一整个环考虑，既然是要最优，那么考虑动态规划；
  5. 不过有个问题，因为我们的点太多，可能满足操作结果只有环的数量、种类依然很多，而且不同组合情况数组无法装下，面对装不下的问题，我们可以用 bitset 背包，反正都是一维，和普通的动态规划数组差不多，不过对于物品多的问题，我们可以用二进制优化，毕竟这种优化也是专门针对这个的。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m;
int goal[1000009];
int du[1000009];
int fa[1000009];
int find(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = find(fa[x]);
}
int siz[1000009];
void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx == fy)
    {
        return;
    }
    fa[fx] = fy;
    siz[fy] += siz[fx];
}
int now[1000009], l = 0, ooo = 0;
int solvemax(int x)
{
    sort(now + 1, now + l + 1, [](int a, int b) { return a > b;});
    int ans = 0;
    for (int i = 1; i <= l; i++)
    {
        if (x >= (now[i] / 2))
        {
            ans += (now[i] / 2) * 2;
            x -= (now[i] / 2);
        }
        else
        {
            ans += x * 2;
            x = 0;
            break;
        }
    }
    if (x)
    {
        ans += min(x, ooo) * 1;
    }
    return ans;
}
int cnt[1000009], ll = 0;
int cz[1000009];
bitset<1000009> dp;
short vis[1000009];
int solvemin(int x)
{
    for (int i = 1; i <= l; i++)
    {
        cz[now[i]]++;
    }
    for (int i = 1; i <= n; i++)
    {
        int v = 1;
        while (cz[i])
        {
            if (v <= cz[i])
            {
                cnt[++ll] = i * v;
                cz[i] -= v;
                v *= 2;
            }
            else
            {
                cnt[++ll] = i * cz[i];
                break;
            }
        }
    }
    // vis[0] = 1;
    // for (int i = 1; i <= ll; i++)
    // {
    //     if (vis[cnt[i]] == 0)
    //     {
    //         vis[cnt[i]] = 1;
    //     }
    // }
    dp[0] = 1;
    for (int i = 1; i <= ll; i++)
    {
        dp |= (dp << cnt[i]);
    }
    return x + (!vis[x]);
}
signed main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
    {
        siz[i] = 1;
        fa[i] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        goal[i] = read();
        merge(i, goal[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (fa[i] == i)
        {
            now[++l] = siz[i];
            if (siz[i] % 2)
            {
                ooo++;
            }
        }
    }
    cout << solvemin(m) << ' ' << solvemax(m) << endl;
    return 0;
}

Trick：

优质背包问题讲解合集

和决策单调性+分治优化斗智88回：LOJ 6039

关键点：

欸，c最大只有300，我靠，那不直接分门别类，然后在他们内部找有哪些转移得到的贡献最大……

做题思路：

  1. emmm，这道题似乎就是01背包，不过，为啥n^2只有10分？
  2. 好吧，我们来考虑点别的。
  3. 首先，我们发现，我们的价格种类最多只有300种，但是我们要输入整整一百万个物品，那么就会意味着会有很多价格重复的玩意，可以给一个价格分个类。
  4. 由于我们的01背包DP只会在-3w，-2w，-w……之类w的整数倍之间转移，那么我们在同一个物品种类里面，我们的转移是很容易被发现是存在策略单调性的，也就是，我们决定一个状态下从k转移过来最优，那么在这个状态之前的的最优转移点肯定是要比k小的，之后也肯定是要比k大的。
  5. OK，你问我为什么，很简单，假设我们现在的体积是10，从7这个状态转移过来得到的物品价值是20，那么如果你告诉你可以在体积为8的时候找到5转移过来的最终价值是200，那我是个傻子，我为什么不从5转移到10呢，亦或者从5到7再到10，更好，这样不是更优秀嘛？
  6. 处理完这个问题后，我们再来考虑怎么快速找到最优点，因为我们是单调的，那么单调+DP，这是分治优化DP非常经典的情况，这一点清楚后就差不多了，反正我们都是在w的倍数之间转移，那么为了考虑到所有的体积，我们枚举%w的余数r，用余数r加倍数得到每一种%w=r的体积，用数组存起来，再在这个数组上分治；
  7. 我们确定一个mid中间值，将这个值的DP值更新完后记录下来转移点，下一次坐边的转移点肯定不会超过这个点，右边也不会大于这个点，将全部体积点枚举的时间复杂度优化到nlog，不会超时，但可能超空间。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
long long dp[1000009], g[1000009];
long long qzh[309][100009];
int zu[309][100009];
int siz[309];
int reall[1000009], l;
void solve(int w, int rl, int l, int r, int fwl, int fwr, long long *dpnew, long long *dpold, long long *qzh)
{
    if (l > r)
    {
        return;
    }
    int mid = l + r >> 1;
    int i = reall[mid];
    int t = i / w, poswz = 0;
    // cout << "l=" << l << " r=" << r << " mid=" << mid << " i=" << i << " t=" << t << " fwl=" << fwl << " fwr=" << fwr << endl;
    long long maxn = -1e18;
    for (int k = fwl; k <= min(t, fwr); k++)
    {
        if (k > rl)
        {
            break;
        }
        int qian = i - k * w;
        if (qian < 0)
        {
            continue;
        }
        long long now = dpold[qian] + qzh[k];
        // cout << "qian=" << qian << " now=" << now << endl;
        if (now > maxn)
        {
            maxn = now;
            poswz = k;
        }
    }
    // cout << "k=" << poswz << endl;
    if (maxn > dpnew[i])
    {
        dpnew[i] = maxn;
    }
    solve(w, rl, l, mid - 1, fwl, poswz, dpnew, dpold, qzh);
    solve(w, rl, mid + 1, r, poswz, fwr, dpnew, dpold, qzh);
}
int n, W;
signed main()
{
    n = read();
    W = read();
    int maxw = 0;
    for (int i = 1; i <= n; i++)
    {
        int w = read();
        int v = read();
        maxw = max(maxw, w);
        zu[w][++siz[w]] = v;
    }
    for (int w = 1; w <= maxw; w++)
    {
        if (siz[w])
        {
            sort(zu[w] + 1, zu[w] + 1 + siz[w], greater<int>());
            qzh[w][0] = 0;
            for (int i = 1; i <= siz[w]; i++)
            {
                qzh[w][i] = qzh[w][i - 1] + zu[w][i];
            }
        }
    }
    // cout << "qzh:\n";
    // for (int i = 1; i <= maxw; i++)
    // {
    //     for (int j = 1; j <= siz[i]; j++)
    //     {
    //         cout << qzh[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    for (int w = 1; w <= maxw; w++)
    {
        if (siz[w])
        {
            memcpy(g, dp, sizeof(long long) * (W + 1));
            for (int ys = 0; ys < w; ys++)
            {
                l = 0;
                for (int i = ys; i <= W; i += w)
                {
                    reall[++l] = i;
                }
                if (l == 0)
                {
                    continue;
                }
                // cout << "real:";
                // for (int i = 1; i <= l; i++)
                // {
                //     cout << reall[i] << ' ';
                // }
                // cout << endl;
                solve(w, siz[w], 1, l, 0, W / w, g, dp, qzh[w]);
            }
            memcpy(dp, g, sizeof(long long) * (W + 1));
        }
    }
    for (int i = 1; i <= W; i++)
    {
        cout << dp[i] << ' ';
    }
    return 0;
}

Trick：

最后，未来的你要记住一个要点，大部分时候我们都可以对一串等差数列般的体积做分治，类似归并排序的过程，同时他们也满足决策单调性。

初遇WQS二分：CF739E

关键点：

欸，这玩意要个三维DP，我超，不过，如果你把第三维，压掉，是不是，我超，好像我们的答案随着数组的变大，增值变小……

做题想法：

  1. 首先，我们一拿到题肯定是读题，因为将期望和题目结合起来还是很麻烦的……
  2. 我们一开始肯定想到的是 dpi,j,kdp_{i, j, k}，表示目前到了第i只宝可梦，但是我们只对i只使用了A球，j只使用了B球，求此时的期望，方程肯定是考虑只用A，只用B，AB都用，以及什么都不用直接跳过四种情况，你此时很开心，推出了，方程，但是n<=2000。
  3. 我们尝试压掉一维，我们保留1、2维，将B球的情况单独考虑，我们发现，当我们保持i，j不变时，我们的dp数值会随着k的变化而使增长率逐渐变缓，这不难理解，假如我们前面有个更优的球与宝可梦搭配，我们在之前肯定已经用了，而我们的题目中每个球只能用一次，那么之后的期望涨幅肯定会逐渐下降，那么就造成dp值逐渐趋于平缓。
  4. 上述情况也就对应着我们今天要学的知识点——WQS二分，简而言之，当我们的图像是个凸包时，我们要求dp值，到那时，我们可以用（也是一定）斜率k作为突破口，为什么呢，因为我们对应斜率k的直线穿过凸包时会和y轴交于一个点，这个点的纵坐标为dp-k*x，x是dp值的横坐标，那么，我们就可以弄一个全新的DP数组，名字就叫DP，这个DP数组可以用来将每次的x和减少的c对应，我们对这个值进行动态规划，便可以求出我们的此时i,j固定时DP最大值。
  5. 好奇的你可能要问了，这玩意和啥有关，因为我们知道切线对应着斜率，我们在一个斜率下计算出与y轴的截距最大时，也就对应着这个斜率此时的切线，也就是我们此时的x大小，也就对应着i,j固定时用多少B球最优，这个也是我们dp想求得的，我们记录下最终时用了多少个B球，也就是顶点在哪，如果此时的顶点横坐标比我们的要求小，那么我们的二分斜率就要下降，因为切线斜率大小随着我们的x递增而递减，反之上升。
  6. 最后输出答案，别忘了要在DP数组的基础上加上要求数乘上斜率，因为DP存的时截距。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, dp = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            dp = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * dp;
}
int n;
int a, b;
// int a[1000009], b[1000009];
double p[1000009], q[1000009];
double dp[2009][2009];
int cnt[2009][2009];
bool check(double mid)
{
    memset(dp, 0, sizeof(dp));
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= a; j++)
        {
            cnt[i][j] = cnt[i - 1][j];
            dp[i][j] = dp[i - 1][j];
            if (j && p[i] + dp[i - 1][j - 1] >= dp[i][j])
            {
                dp[i][j] = dp[i - 1][j - 1] + p[i];
                cnt[i][j] = cnt[i - 1][j - 1];
            }
            if (j != 0 && dp[i - 1][j - 1] + q[i] + p[i] - q[i] * p[i] - mid >= dp[i][j])
            {
                dp[i][j] = dp[i - 1][j - 1] + q[i] + p[i] - q[i] * p[i] - mid;
                cnt[i][j] = cnt[i - 1][j - 1] + 1;
            }
            if (dp[i - 1][j] + q[i] - mid >= dp[i][j])
            {
                dp[i][j] = dp[i - 1][j] + q[i] - mid;
                cnt[i][j] = cnt[i - 1][j] + 1;
            }
        }
    }
    return cnt[n][a] <= b;
}
signed main()
{
    n = read();
    a = read();
    b = read();
    // m = read();
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> q[i];
    }
    double l = 0, r = 1.0;
    for (int i = 0; i < 60; i++)
    {
        double mid = (l + r) / 2;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    // cout << "l=" << l << " r=" << r << endl;
    double ans = dp[n][a] + l * b;
    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}
/*
4 1 3
0.100 0.500 0.500 0.600
0.100 0.500 0.900 0.400
2.16
*/

初遇子集动态规划：P12407 「CZOI-R3」数字变换

关键点：

其实，还是 nn 的枚举范围太大了，我们可以发现我们只关心之前的状态和目前的状态，这个状态和我们目前的下标有关，还和……还和x值本身的大小有关！

做题思路：

  1. 一开始很快写出方程，令 dpj,idp_{j, i} 表示操作 jj 步使得 aa 变成 ii，但是时间复杂度很明显是 nn 方乘上 mm 的，必定超时，于是就引发了上述的思考。
  2. 我们可以发现我们的 xx 最大只有 6553665536，那么我们可以将一开始的循环中枚举 nn 的那几层改为枚举 xix_i 的大小。
  3. 我们想好这点后，就要对原始的方程做操作，我们令 AvA_v 表示所有等于 vv 的 xx 数组对应下标的 dpdp 值的最小值，那么我们就将原先的转移方程转化为用 AA 数组减去双倍的按位求与值。
  4. 现在我们来考虑怎么使后面的那个玩意最小，因为和 kk 和 ii 有关，所以我们重点关注被改变过一次的 kk（在之前我们的 AA 数组有涉及到它），可能聪慧的你很快就想到了每次寻找 (Av−2×v)(A_{v} - 2 \times v) 的最小值，毕竟我们的 vv 在减数上，按位求与的结果要么比原数小，要么和原数一样大，嘻嘻，我真聪明；
  5. 不过你很快发现这样写连样例都过不了，因为，如果你看文章很仔细，就会读到我们在之前已经提到过我们的 AA 也和 kk 有关，你也不知道如果减数 vv 变小是否会让 AvA_v 变得更小，所以你不能只局限于这几个情况中，而是要全部搜索一遍，只要你的减数满足既在 vv 的二进制子集中，也要保证在 xix_i 的子集中，这样才不会错，而且时间复杂度一直是变成两倍了而已，可以接受。
  6. 我们先考虑贡献的方向和顺序，我们设 rr 为按位求与的结果，我们要保证 rr 是 vv 的子集，这样才能保证我们的结果是可以由 vv 和另外一个数按位求与得来的，因为这一关键条件的限制，我们便可以考虑用子集动态规划求，具体实现在代码的第 8282 行至 9191 行；
  7. 下一步就是我们要考虑那些包括 rr 的 xix_i，这个就只能反过来用从大集合到小集合的方法寻找，并且查找的对象使我们已经处理过一遍的 AA 数组；
  8. 至于，你问我为什么不能反过来先遍历子集到大集合，这个嘛，因为我们的 AvA_v 直接和 rr 相关，所以放在内侧方便编写程序一些。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, p, k, x[3000009];
int c, y[65536];
int w[2000009][19], L;
unsigned long long seed;
int get_rand(int mod)
{
    seed ^= seed << 14;
    seed ^= seed >> 7;
    seed ^= seed << 19;
    seed ^= seed << 23;
    return seed % mod;
}
void get_input()
{
    for (int i = 1; i <= n; i++)
    {
        x[i] = y[get_rand(c)];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            w[i][j] = get_rand(1000000);
        }
    }
}
int A[3000009], J[3000009], dp[18][200009], G[3000009];
signed main()
{
    n = read();
    p = read();
    k = read();
    c = read();
    seed = read();
    for (int i = 0; i < c; i++)
    {
        y[i] = read();
    }
    get_input();
    for (int i = 1; i <= n; i++)
    {
        L = max(L, x[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        dp[0][i] = 1e18;
    }
    dp[0][p] = 0;
    for (int j = 1; j <= k; j++)
    {
        for (int v = 0; v <= 65536; v++)
        {
            A[v] = 1e18;
        }
        for (int i = 1; i <= n; i++)
        {
            // if (dp[j - 1][i] < 1e18)
            // {
            A[x[i]] = min(A[x[i]], dp[j - 1][i]);
            // }
        }
        for (int j = 0; j < 16; j++)
        {
            for (int k = 0; k <= 65536; k++)
            {
                if ((k >> j) & 1)
                {
                    A[k ^ (1 << j)] = min(A[k ^ (1 << j)], A[k]);
                }
            }
        }
        for (int j = 0; j <= 65536; j++)
        {
            A[j] -= 2 * j;
        }
        for (int j = 0; j < 16; j++)
        {
            for (int k = 0; k <= 65536; k++)
            {
                if ((k >> j) & 1)
                {
                    A[k] = min(A[k ^ (1 << j)], A[k]);
                }
            }
        }

        // for (int o1 = 0; o1 < 16; o1++)
        // {
        //     for (int u =0; u <= 65536; u++)
        //     {
        //         if (u & (1 << o1))
        //         {
        //             G[u] = min(G[u], G[u ^ (1 << o1)]);
        //         }
        //     }
        // }
        for (int i = 1; i <= n; i++)
        {
            dp[j][i] = 2 * L + w[i][j] + A[x[i]];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << dp[k][i] << " ";
    }
    return 0;
}

置换环和拓扑为什么等于紫题：CF1682E Unordered Swaps

关键点：

反正我们这道题是有关序列交换次序的问题，肯定和置换环有关，那么我们要求的是怎么交换才能换出正确序列，嗯……

做题思路：

  1. 其实我一开始根本没想到置换环，因为也是第一次学，就来做，不过一开始想的随机化，但是由于数据范围太大所以只好作罢；
  2. 我们根据题目操作，发现就是置换环所考虑的问题，那么我们首先根据建环规则建环，也发现这道题想要得到正确答案一定是在同一个环上操作，且每次操作都要拆出两个小环，也符合置换环的性质，不过这道题的数据都可以满足交换正确，那么重点来看怎么交换；
  3. 我们可以先用样例自己模拟几遍，发现首先，我们的情况肯定不能涉及跨环的情况，也就是我们的操作无向边不能处于两个环之间，那么根据这一点，我们发现我们的操作只会局限于一种菊花图形式，也就是一个点连着很多边，那么操作也就是这几条边根据转圈顺序排序得到的，这样操作肯定不会有问题；
  4. 什么，你问我会不会这几条边组成封闭图形，或者两条相交的行不行，当然不行，你会很容易发现这几种情况会出现拆一条边发生剩余边存在跨环现象，使我们极力避免的。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m;
int a[1000009];
struct node
{
    int l, r, id;
} q[1000009];
// int fa[1000009], siz[1000009];
// int find(int x)
// {
//     return fa[x] == x? x : fa[x] = find(fa[x]);
// }
// void merge(int x, int y)
// {
//     int fx = find(x), fy = find(y);
//     if (fx != fy)
//     {
//         fa[fx] = fy;
//         siz[fy] += siz[fx];
//     }
// }
int len[1000009], bh[1000009], rk[1000009];
vector<pair<int, int>> g[1000009];
struct node1
{
    int to, next;
} edge[1000009];
int head[1000009], tot;
void add(int u, int v)
{
    edge[++tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot;
}
int deg[1000009];
void topu()
{
    queue<int> q;
    for (int i = 1; i <= m; i++)
    {
        if (deg[i] == 0)
        {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        cout << x << " ";
        for (int i = head[x]; i; i = edge[i].next)
        {
            int y = edge[i].to;
            if (!--deg[y])
            {
                q.push(y);
            }
        }
    }
}
// unordered_map<int, int> mp;
signed main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
    {
        rk[i] = -1;
        a[i] = read();
    }
    for (int i = 1; i <= m; i++)
    {
        q[i].l = read();
        q[i].r = read();
        q[i].id = i;
        g[q[i].l].push_back({q[i].r, i});
        g[q[i].r].push_back({q[i].l, i});
        // merge(q[i].l, q[i].r);
    }
    int num = 0;
    for (int i = 1, j = 0, k = 0; i <= n; i++)
    {
        if (rk[i] == -1)
        {
            rk[i] = 0;
            bh[i] = ++num;
            j = 0, k = 0;
            for (j = a[i], k = 1; j != i; j = a[j], k++)
            {
                rk[j] = k;
                bh[j] = num;
            }
            len[num] = k;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int l = len[bh[i]];
        int rknow = rk[i];
        sort(g[i].begin(), g[i].end(), [&](pair<int, int> x, pair<int, int> y)
             {
            int rx = rk[x.first] <= rknow ? rk[x.first] + l : rk[x.first];
            int ry = rk[y.first] <= rknow ? rk[y.first] + l : rk[y.first];
            return rx < ry; });
        for (int j = 1; j < g[i].size(); j++)
        {
            add(g[i][j - 1].second, g[i][j].second);
            deg[g[i][j].second]++;
        }
    }
    topu();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...