跳转至

算法竞赛中的程序性思维

计数？所有子集？

对所有子集（包含集合的子集，也包含抽象概念上“事件”的子集）的统计，我们有两种方法：dp和组合计数（通常是容斥）。注 注意！dp应该作为我们首要考虑的方法。

例题 #1 [USACO20FEB] Help Yourself G

题目描述

在一个数轴上有 \(N\) 条线段，第 \(i\) 条线段覆盖了从 \(l_i\) 到 \(r_i\) 的所有实数（包含 \(l_i\) 和 \(r_i\)）。

定义若干条线段的**并**为一个包含了所有被至少一个线段覆盖的点的集合。

定义若干条线段的**复杂度**为这些线段的并形成的连通块的数目。

现在 Bessie 想要求出给定 \(N\) 条线段的所有子集（共有 \(2^N\) 个）的复杂度之和对 \(10^9+7\) 取模的结果。

你也许猜到了，你需要帮 Bessie 解决这个问题。但不幸的是，你猜错了！在这道题中你就是 Bessie，而且没有人来帮助你。一切就靠你自己了！

这道题怎么做呢？我们也许会思考线段与线段之间的关系，我们也许会考虑假设没有重叠，然后再考虑重叠会减去多少答案。

但是上面的思维过程都是非套路化的，这种思路最后会变得很乱，以至于难以解题。

那么怎么样沿着规范的思路取思考呢？我们考虑这道题的子问题：我们很容易计算出N=1的情况，也很容易**依据**N=1的情况计算出N=2的情况。所以我们考虑加入一条线段对答案的影响。

于是我们会考虑到动态规划。并且我们发现，加入一条线段不一定要选它，所以我们由f_i表示前i条线段的所有情况的复杂度之和，先考虑不选的情况

f_i=f_{i-1}

再考虑选。那么也许我们会想，哪些情况时选对之前没影响呢？这样想就复杂了。因为这样我们还要想求出总情况，然后减去无影响的情况。我们不如直接算有影响的情况。

那么怎么样有影响呢？我们设X为那些与i无交的线段，我们发现如果只再X中选择线段，加上i后一定对由影响。所以我们现在只需要求在X中选子集的方案数即可！

这么多变量？头要大了！

在面对这种题目时，我们最好先去洗个脸。因为这种题目需要的是清晰的思路。

注意到这题，我们应该先自己整理一下题目，或者说用自己的话复述一下题面。并且随时要整理一些性质。

[省选联考 2024] 季风

题目描述

给定 \(n,k,x,y\) 和 \(2n\) 个整数 \(x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}\)。

找到最小的**非负整数** \(m\)，使得存在 \(2m\) 个实数 \(x_0',y_0',x_1',y_1',\dots,x_{m-1}',y_{m-1}'\) 满足以下条件，或报告不存在这样的 \(m\)：

  • \(\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})=x\)；

  • \(\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})=y\)；

  • \(\forall 0\leq i\leq m-1,|x_i'|+|y_i'|\leq k\)。

特别地，\(m=0\) 时，认为 \(\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})\) 和 \(\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})\) 均为 \(0\)。

【子任务】

设 \(\sum n\) 为单个测试点内所有测试数据 \(n\) 的和。对于所有测试数据：

  • \(1\leq T\leq 5\times 10^4\)；

  • \(1\leq n\leq 10^5\)，\(1\leq \sum n \leq 10^6\)；

  • \(0\leq |x|,|y|,|x_i|,|y_i|,k\leq 10^8\)。

每一个周期我们会走过一个特定的向量集V，求最小的向量选取个数m使得：终点到目标点的距离不超过mk。

整理我们用到了第一个结论：

  • \(\forall 0\leq i\leq m-1,|x_i'|+|y_i'|\leq k\)。

这个偏移量是对于每一步的，看上去很棘手。但是实际上我们可以把偏移放在最后，假设步数为m，那么我们总的只需要小于km即可。

接下来我们应该找突破口：什么不好确定，就枚举哪个！我们发现，我们的周期数T和最后一个不完整的周期内的步数m-T|V|都是不确定的。那么哪个可以枚举呢？m-T|V|。

因此我们枚举m-T|V|，就得到如下式子

\(x=x_0+(\sum_{x\in V}x)\times T+\sum_{i\in[1,m-T|V|]} x_i+X\)。这里的x都是是矢量，X代表偏移量。y雷同。

我们偏移坐标系，使得目标坐标为(0,0)，所以现在的问题是使得x=0,y=0。

现在我们有3个式子，一个不等式和2个等式，于是我们就可以尝试求解。我们把两个等式相加，移项将含有X,Y的项目移出来，于是我们得到

\(x_0+(\sum_{x\in V}x)\times T+\sum_{i\in[1,m-T|V|]} x_i+X+y_0+(\sum_{y\in V}y)\times T+\sum_{i\in[1,m-T|V|]} y_i+Y=0\)

\(x_0+(\sum_{x\in V}x)\times T+\sum_{i\in[1,m-T|V|]} x_i+y_0+(\sum_{y\in V}y)\times T+\sum_{i\in[1,m-T|V|]} y_i=-X-Y\)

我们讨论X,Y的正负，就可以再来一个不等式。下面假设X,Y>0，那么就有X+Y≤mk。于是又可以写作

\(x_0+(\sum_{x\in V}x)\times T+\sum_{i\in[1,m-T|V|]} x_i+y_0+(\sum_{y\in V}y)\times T+\sum_{i\in[1,m-T|V|]} y_i≥-mk\)。

至此我们就可以解出最小的T了。注意到约束了X,Y>0，所以我们还有

\(0=x_0+(\sum_{x\in V}x)\times T+\sum_{i\in[1,m-T|V|]} x_i+X\)

\(x_0+(\sum_{x\in V}x)\times T+\sum_{i\in[1,m-T|V|]} x_i<0\)，对y也是一样。我们求解出三个T的取值范围，求一下交集即可。

最优策略？找不到最优策略啊？

例题 #3 力

小 S 是 X 宇宙的科学家，他在对 n 个排成一排的粒子进行实验。

初始，两两粒子之间都会有一条边连接。设 coni,j​ 表示 i 与 j 粒子是否连通，连通则 coni,j​=1，否则 coni,j​=0。

现在，小 S 决定断掉一些粒子之间的边。两条粒子 i,j 之间的力为 \(a_{∣i−j∣}​con_{i,j}\)​，其中 ai​ 为给出的力系数，保证 a 单调不降。

定义一个局面的总力为所有 1≤i<j≤n 之间的力之和。求断开 i=0∼n(n−1)/2​ 条边后，局面总力的最小值。

输入格式

第一行两个正整数 t,T，分别表示测试点编号和测试数据组数。

对于每组测试数据：

第一行，一个正整数，表示 n。

第二行，n 个正整数，表示 a1​,a2​,…,an​。

保证 a1​≤a2​≤⋯≤an​。

输出格式

对于每组测试数据：

第一行，2n(n−1)​+1 个非负整数，表示答案。

对于 100% 的数据：1≤n≤100，1≤ai​≤109，1≤T≤5。

我们做这道题会很没有头绪。

注意con是联通而不是直接相连。

我们也许会考虑怎么样断边/加边是最优策略

但是我们发现没有明显的最优策略。

这个时候我们就应该考虑**换一个思路**

n很小，我们可以考虑记忆化搜索。那么我们就需要表示状态，很明显是定义f_{i,j}为选择i个点，连接j条边的最小代价

一开始我们定义一些物品{i,v}，表示选择i个点，且连接成完全图的最小代价。这里的i个点是连续的。

我们发现答案序列是一段段相同的数字连接而成的，并且最靠后的那个位置代表的情况**恰好是若干个完全图的集合**。于是我们就可以像背包选物品一样求解了。

赛时没想到啊。

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 1e2 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

struct node{
    itn x,cnt,sum;
}p[N];
int a[N];
int f[N][N*N];
int ans[N*N];//选i条边的最小代价

void solve(){
    int n=rd;
    for(int i=1;i<=n;i++){
        a[i]=rd;
    }


    for(int i=1;i<=n;i++){
        int cnt=0,sum=0;
        for(int j=1;j<=i;j++){
            for(int k=j+1;k<=i;k++){
                cnt++;sum+=a[k-j];
            }
        }
        p[i]={i,cnt,sum};
        // cdbg(i,sum,cnt);
    }

    memset(f,0x3f3f,sizeof f);
    f[0][0]=0;

            for(int j=1;j<=n;j++){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n*(n-1)/2;i++){
                if(k>=p[j].x&&i>=p[j].cnt)f[k][i]=min(f[k][i],f[k-p[j].x][i-p[j].cnt]+p[j].sum);       
            }
        }
    }

    memset(ans,0x3f3f,sizeof ans);
    for(int i=1;i<=n*(n-1)/2;i++){
        // ans[i]=mn;
        for(int j=1;j<=n;j++){
            ans[i]=min(ans[i],f[j][i]);
        }
    }

    ans[0]=0;
    int mn=INF;
    for(int i=n*(n-1)/2;~i;i--){
        mn=min(mn,ans[i]);
        cout<<mn<<' ';
    }
    cout<<endl;
}

signed main() {
    freopen("force.in","r",stdin);
    freopen("force.out","w",stdout);
    int t=rd;
    int T=rd;
    while(T--){
        solve();
    }
    return 0;
}

什么逻辑？为什么我的逻辑不对？

例题 #4 [NOIP2023] 三值逻辑

题目描述

小 L 今天学习了 Kleene 三值逻辑。

在三值逻辑中，一个变量的值可能为：真（\(\mathit{True}\)，简写作 \(\mathit{T}\)）、假（\(\mathit{False}\)，简写作 \(\mathit{F}\)）或未确定（\(\mathit{Unknown}\)，简写作 \(\mathit{U}\)）。

在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢，只掌握了逻辑非运算 \(\lnot\)，其运算法则为： \(\lnot \mathit{T} = \mathit{F}, \lnot \mathit{F} = \mathit{T}, \lnot\mathit{U} = \mathit{U}.\)

现在小 L 有 \(n\) 个三值逻辑变量 \(x_1,\cdots, x_n\)。小 L 想进行一些有趣的尝试，于是他写下了 \(m\) 条语句。语句有以下三种类型，其中 \(\leftarrow\) 表示赋值：

  1. \(x_i \leftarrow v\)，其中 \(v\) 为 \(\mathit{T}, \mathit{F}, \mathit{U}\) 的一种；

  2. \(x_i \leftarrow x_j\)；

  3. \(x_i \leftarrow \lnot x_j\)。

一开始，小 L 会给这些变量赋初值，然后按顺序运行这 \(m\) 条语句。

小 L 希望执行了所有语句后，所有变量的最终值与初值都相等。在此前提下，小 L 希望初值中 \(\mathit{Unknown}\) 的变量尽可能少。

在本题中，你需要帮助小 L 找到 \(\mathit{Unknown}\) 变量个数最少的赋初值方案，使得执行了所有语句后所有变量的最终值和初始值相等。小 L 保证，至少对于本题的所有测试用例，这样的赋初值方案都必然是存在的。

这道题很容易绕入思维漩涡。本人赛时后加起来6h没绕明白。

这种题目首先要思维缜密，然后需要选择一个好的算法设计入口。