训练小结

hymcr052024-09-222024-12-15

2024.7.11

序言

这次比赛只拿了 $10$ 分，为什么呢？第三题打爆搜，原本可以拿 $30$ 分，但是没打freopen爆 $0$ 了。第二题输出循序错了，也爆 $0$ ，只有第四题骗了 $10$ 分。

作业调度方案

这是一道模拟，虽然是模拟，但是由于题目描述过于~~模糊（语文不好）~~，所以没有读懂题目。

题意

给你一个 $m$ , $n$ 分别表示：机器数与工件数。
前 $n$ 行依次表示每个工件的每个工序所使用的机器号，第 $1$ 个数为第 $1$ 个工序的机器号，第 $2$ 个数为第 $2$ 个工序机器号，等等。
最后让你求最小的加工时间。

解法

#include <bits/stdc++.h>
using namespace std;
int m, n;
int gx[30]/*工序数*/ , last[30]/*第 i 个工件制成的时间*/; 
int a[42000], ans;
bool mt[25][10050]; // 第 i 个机器时间的是否占用
struct GG
{
    int num/*工件的工序*/, time/*需要的时间*/;
} s[220][220];
int main()
{
#ifdef ONLINE_JUDGE
    freopen("jsp.in", "r", stdin);
    freopen("jsp.out", "w", stdout);
#endif
    cin >> m >> n;
    for (int i = 1; i <= m * n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j].num;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j].time;
    for (int i = 1; i <= n * m; i++)
    {
        int z = 0, j = last[a[i]] + 1;
        gx[a[i]]++;//下一个工序
        int x = s[a[i]][gx[a[i]]].num;
        int v = s[a[i]][gx[a[i]]].time;
        while (z != j)
        {
            if (!mt[x][j]) z++;//空挡的长度
            else z = 0;
            j++;
        }
        for (int k = j - v + 1; k <= j; k++)
            mt[x][k] = 1;
        last[a[i]] = j;
        ans = max(ans, last[a[i]]);
    }
    cout << ans;
    return 0;
}

火柴棒等式

考场时并没有想到枚举数字的范围，发现时间复杂度非常高： $\mathcal {O(10000^4)}$ ，于是打表，但是打表时认为 $n < 13$ 时答案为 $0$ ，再加上一些奇奇怪怪的 $\textrm {BUG}$ ，就爆 $0$ 了。事实上，我们的 $a$ ， $b$ , $c$ 只需要枚举到 $1000$ 即可，最后使用函数计算出 $a$ ， $b$ ， $c$ 使用的火柴数量是否符合题意即可。
过于简单，就不贴代码了。

传纸条

题意

给出一个 $n \times m$ 矩阵，要求从 $(1,1)$ 走到 $(n,m)$ 中经过的数值最大，再从 $(n,m)$ 走到 $(1,1)$ ，也是求数值最大的走法，但是走过的路不能重复。

解法

考场一眼就可以看出来是 $\textrm {DP}$ ,但是有一个比较难处理的地方：走过的路不能重复走。
题目中的从 $(1,1)$ 走到 $(n,m)$ ，再从 $(n,m)$ 走到 $(1,1)$ ，我们就可以看作从 $(1,1)$ 走到 $(n,m)$ 走两遍。
于是设定状态： $\large f_{i,j,k,l}$ 表示第一个纸条走到了 $(i,j)$ ，第二个纸条走到了 $(k,l)$ 。
转移方程：
$\large{ f_{i,j,k,l} = \max_{i=1}^n\max_{j=1}^n(\max_{k=1}^n(\max_{l=1}^n(f_{i-1,j,k-1,l} , f_{i,j-1,k-1,l} , f_{i-1,j,k,l-1} , f_{i,j-1,k,l-1}))) }$

树网的核

很简单，跑一遍Floyd,再用一些奇妙的公式即可：

#include <bits/stdc++.h>
using namespace std;
int n, s, ans = INT_MAX;
int g[700][700];
void floyd()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                if (i != j && j != k && i != k)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]), g[j][i] = g[i][j];
}
int main()
{
#ifdef ONLINE_JUDGE
    freopen("core.in", "r", stdin);
    freopen("core.out", "w", stdout);
#endif
    cin >> n >> s;
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= n; i++)
        g[i][i] = 0;
    for (int i = 1; i <= n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = g[y][x] = z;
    }
    floyd();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (g[i][j] <= s)
            {
                int p = INT_MIN;
                for (int k = 1; k <= n; k++)
                    p = max(p, (g[i][k] + g[j][k] - g[i][j]) / 2);
                ans = min(ans, p);
            }
    cout << ans;
    return 0;
}

你问我公式怎么来？好比这个图
alt text
$\large{ik+jk=in+kn+jn+kn}$
$\large{ij+2kw=ik+jk}$
$\large{kw=(ik+jk-ij) \div 2}$

2024.7.12

比赛传送门

潜伏者

纯水题，看懂题目都做得对。

Hankson 的趣味题

暴力做法：枚举 $x$ 到 $b_1$ ，按题目计算即可，期望得分: $50$ 分。
已知： $b_1≤2,000,000,000$ , $n≤2000$ ，于是暴力的时间复杂度是 $\mathcal {O(2,000,000,000 ^ {2000})}$ 。
于是我们枚举到 $\sqrt{b_i}$ ，因为两个数议定书两个数的最小公倍数的因子，于是我们将 $b_i \div x$ 和 $x \div b_i$ 分开计算。
注意：计算的前提条件是 $b_i \mod x = 0$ 的，且如果 $b_i \div x = x \div b_i$ 时，只能计算一次。

最优贸易

此题奆说要使用 $\textrm {tarjan}$ ，但是其实可以使用 $\textrm {SPFA}$ 进行解题。
我们分别跑两次 $\textrm {SPFA}$ 分别是从前往后，从后往前，注意，如果是从后往前，就需要反向建边，最后正常 $\textrm {SPFA}$ 即可。
松弛部分（SPFA2相反即可）：

int v = g1[i].to;
if (dis1[v] > min(dis1[u], a[v]))
{
    dis1[v] = min(dis1[u], a[v]);//我们设dis1为MAX值
    if (!bz[v])
    {
        q.push(v);
        bz[v] = 1;
    }
}

$答案=\max_{i=1}^n(dis2_i-dis1_j)$

靶形数独

没有所谓正解，暴搜期望得分： $80$ ，模拟赛时因为一些奇奇怪怪的 $\textrm {BUG}$ 没有拿到 $80$ 分。
$100$ 分也只是在 $80$ 分的基础上优化而已：我们优先选择每行 $0$ 少的点，因为数独的特性， $0$ 少也就意味着可选择的数字少，递归层数也少，自然就可以过了。

处理小方块有点难想，但是画个图即可理解：
alt text
我们可以把 $3 \times 3$ 的格子压成 $1 \times 1$ 的格子，就像这样：

long long xx, yy;
if (x % 3 == 0)
    xx = x / 3;
else
    xx = x / 3 + 1;
if (y % 3 == 0)
    yy = y / 3;
else
    yy = y / 3 + 1;

2024.7.15

数位DP

【ZJOI2010】数字计数

数位 $\textrm {DP}$ 板子题，问的是两个正整数 $a$ 和 $b$ ，求在 $[a,b]$ 中的所有整数中，分别表示 $0 \thicksim 9$ 在 $[a,b]$ 中出现了多少次。

怎么做呢？

由于 $a \le b \le 10^{12}$ ， $a$ 和 $b$ 太大了，如果暴力枚举肯定不能拿满分，于是我们需要新的算法：数位 $\textrm {DP}$
。

什么是数位 $\textrm {DP}$ ?

数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 $0 \thicksim 9$ ，其他进制可类比十进制。

数位 $\textrm {DP}$ ：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

要求统计满足一定条件的数的数量（即，最终目的为计数）
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
上界很大（比如 $10^{18}$ ），暴力枚举验证会超时。

数位 DP 的基本原理：

考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。

Code(注释版)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20, D = 9;
int L, R;
int f[N + 2][D + 2][3][3] /*1~i中，j这个数出现的次数*/, g[N + 2][3]/*可以获得的方案总数*/, ans[D + 2], Pow[N + 10];
int dfs(int x /*当前的填出的数*/, int h, int d /*第h位填的是什么数*/, bool flag /*高位标记*/, bool f0 /*是否出现前导零*/)
{
    if (h == 0) // 当位数等于0时
    {
        g[h][flag] = 1; // 1 ^ 0是1
        return 0;
    }
    if (f[h][d][flag][f0] != -1) // 记忆化，如果已经被搜过了，就不搜了直接返回
        return f[h][d][flag][f0];
    f[h][d][flag][f0] = g[h][flag] = 0;           // 设为0，初始化
    int up = flag == 1 ? x / Pow[h - 1] % 10 : 9; // 如果没有高位标记，直接顶到9，x / Pow[h - 1]就是x这个数的第h位，
    for (int i = 0; i <= up; i++)                 // 从0枚举到up，填数
    {
        f[h][d][flag][f0] += dfs(x, h - 1, d, flag && (i == up) /*如果有高位标记，且当前这一位也顶到最高为了，下一次递归也要加上高位标记*/, f0 && (i == 0) /*前导零*/);
        g[h][flag] += g[h - 1][flag && (i == up)]; // 同上转移
        if (i == d /*枚举到了d*/ && (d != 0 || !f0) /*不是前导零*/)
            f[h][d][flag][f0] += g[h - 1][flag && (i == up)]; // 转移
    }
    return f[h][d][flag][f0];
}
int calc(int x) // 求一个数有多少位
{
    int ans = 0;
    while (x)
        x /= 10, ans++;
    return ans;
}
main()
{
    scanf("%lld %lld", &L, &R);
    Pow[0] = 1; // pow[0] = 1,pow[1]=10,pow[2]=100……
    for (int i = 1; i <= 18; i++)
        Pow[i] = Pow[i - 1] * 10; // 预处理POW数组
    memset(f, -1, sizeof(f)) /*用于记忆化搜索*/, memset(g, 0, sizeof(g));
    int len = calc(R);                        // 查看R有多少位
    for (int i = 0; i <= 9; i++)              // 枚举第i位可以填的数字
        ans[i] += dfs(R, len, i, true, true); // 前缀和思想，把l~r全部存起来
    if (L != 0)
    {
        memset(f, -1, sizeof(f)), memset(g, 0, sizeof(g));
        len = calc(L - 1);
        for (int i = 0; i <= 9; i++)
            ans[i] -= dfs(L - 1, len, i, true, true); // 去除前面的，只留下自己的答案
    }
    for (int i = 0; i <= 9; i++)
        printf("%lld ", ans[i]);
    return 0;
}

链表模板

#include<bits/stdc++.h>
using namespace std;
struct Node{ //单向链表 
    int value;//节点编号 
    Node *next;//下一个节点的位置 
};
void insertNode(int i/*节点编号*/,Node *p){
    /* 
    插入流程： 
    1.初始化待插入的数据 node；
    2.将 node 的 next 指针指向 p 的下一个结点；
    3.将 p 的 next 指针指向 node。
    */
    Node *node = new Node;//构建一个新点 
    node -> value = i; 
    node -> next = p -> next;
    p -> next = node;
}
void deleteNode(Node *p){
    //删除 p 
    p -> value = p -> next -> value;//把p这个位置让给p的下一个 
    Node *t = p -> next;//把p的下一个取出来 
    p -> next = p -> next -> next;//把p的下一个指向下一个的下一个 
    delete t;
}
int main() {
    return 0;
}

2024.7.29

【NOIP2010tj】机器翻译

纯水题，模拟队列就过了。

乌龟棋

比赛时动态规划没有打出来，暴搜拿了 $20$ 分，实际上十分简单：

观察题目可得：每种类型的卡片上只有 $1$ 、 $2$ 、 $3$ 、 $4$ 四个数字之一

于是可以得出状态：
$f_{i_1,i_2,i_3,i_4}表示数值为1的的卡牌用了i_1次，数值2的卡牌用了i_2次，以此类推\dots$ 那么我们很轻松就可以得出转移方程（ $a$ 表示输入的第二行）：
$f_{i_1,i_2,i_3,i_4}=\max(f_{i_1,i_2,i_3,i_4},f_{i_1-1,i_2,i_3,i_4}+a_{(1 + i_1 + i_2 \times 2 + i_3 \times 3 + i_4 \times 4)})$
剩下的可以以此类推：

f[0][0][0][0] = a[1];//初值
   for (int a1 = 0; a1 <= _[1]; a1++)
       for (int a2 = 0; a2 <= _[2]; a2++)
           for (int a3 = 0; a3 <= _[3]; a3++)
               for (int a4 = 0; a4 <= _[4]; a4++) {
                   if (a1 > 0) f[a1][a2][a3][a4] = max(f[a1 - 1][a2][a3][a4] + a[1 + a1 + a2 * 2 + a3 * 3 + a4 * 4], f[a1][a2][a3][a4]);
                   if (a2 > 0) f[a1][a2][a3][a4] = max(f[a1][a2 - 1][a3][a4] + a[1 + a1 + a2 * 2 + a3 * 3 + a4 * 4], f[a1][a2][a3][a4]);
                   if (a3 > 0) f[a1][a2][a3][a4] = max(f[a1][a2][a3 - 1][a4] + a[1 + a1 + a2 * 2 + a3 * 3 + a4 * 4], f[a1][a2][a3][a4]);
                   if (a4 > 0) f[a1][a2][a3][a4] = max(f[a1][a2][a3][a4 - 1] + a[1 + a1 + a2 * 2 + a3 * 3 + a4 * 4], f[a1][a2][a3][a4]);
               }

引水入城

这是一道搜索题，实现不难，但是比较难想。

第一步

我们先对第一行的每一个点进行 DFS ,把走过的点进行标记，看最后一行是否全都被标记，如果没有，输出 $0$ 。

第二步

接下来我们要在 DFS 中进行 $r$ 数组和 $l$ 数组的维护：

$r_{x,y}$ 表示的是以坐标为 $x,y$ 的点出发，可以到达的最右侧的点
$l_{x,y}$ 表示的是以坐标为 $x,y$ 的点出发，可以到达的最坐侧的点

alt text
例如在这个图中: $l_{x,y}=2$ 就是蓝色那个点， $r_{x,y}=4$ 就是红色那个点。
这个 DFS 过程中求即可

跳数

int k = 1;//当前跳到的点
while (k <= m) {//保证在 m 内
    int cmp = 0;//临时变量
    ans++;
    for (int i = 1; i <= m; i++)
        if(l[1][i]<=k)//在l的右边，表示在l和r的区间内
            cmp = max(cmp, r[1][i]);//找到最大的右端点
    k = cmp + 1;//跳
}

关押罪犯

这是一道并查集，我们将人分为两类，一类是互相是仇人，一类是互相是 “友人” ，我们通过并查集进行维护：

先将输入的数组的权值进行从大到小的排序，然后开始维护：

for (int i = 1; i <= m; i++) {
    int fx = find(g[i].a);
    int fy = find(g[i].b);
    if (fx == fy) {//如果两人的仇人是同一个人，俗话说：敌人的敌人是朋友，我们便将权值输出
        cout << g[i].c;
        return 0;
    }
    if (fx != fy) {
        f[fx] = find(g[i].b + n);//将他们划分为仇人，n就表示仇人的那一类
        f[fy] = find(g[i].a + n);
    }
}
cout << 0;//处理没有冲突的情况

2024.7.31

【NOIP2012提高组】同余方程

这题是一道数论题，考时没有学过，暴力拿了 $60$ 分（谁说信息学与数学无关），下面开始解题：
$\begin{aligned} ax~+~by~&=~c（a,~b~为常数）\\ \gcd\left(a,~b\right)+\left(\frac{a}{\gcd(a,~b)}x + \frac{b}{\gcd(a,~b)}y\right)~&=~c（乘法分配律）\\ \because z~+~ax~+~by~&=~\gcd(a,~b)~+~z~=~c（z~是一个常数）\\ \therefore ax~+~by~=~\gcd(a,~b)\\ ax~+~by~&=~\gcd(a,~b)①\\ ax~\equiv 1(x\mod b)\\ ax~+~by~&=~1\\ ax~+~by~&=~\gcd(a,b)\\ \gcd(a,~b)~&=~\gcd(b,a\mod b)\\ ax+by&=\gcd(a,b)\\ bx'+(a\mod b)y'&=\gcd(a,b)\\ bx'+(a-\lfloor\frac{a}{b}b\rfloor) y'&=\gcd(a,b)\\ bx'+ay'-\lfloor\frac{a}{b}b\rfloor y' &=\gcd(a,b)\\ ay'-(x'-\lfloor\frac{a}{b}\rfloor y')b&=\gcd(a,b) = 1\\(这个和公式①很像，于是可以得出：&x=y',y=x'-\lfloor\frac{a}{b}\rfloor y') \end{aligned}$

借教室

赛时 $90$ 分，卡卡常就可以过，线段树板子。

2024.8.3

D - AtCoder Janken 3题解

题意

高桥和青木要玩石头剪刀布，给你一个长度为 $n$ 的字符串 $s$ ， $s$ 表示青木在第 $i$ 局游戏中的动作（R 表示石头，P 表示布，S 表示剪刀）。

高桥不可以在任何一局中输给青木（即：高桥和青木只可以平局或高桥赢青木），且高桥第 $i$ 局出的和第 $i-1$ 局出的不能一样，现在，问你高桥可以胜几局？

解题思路

很明显是一道 DP 题。

定义状态

$f_{i,j}$ 表示第 $i$ 局出 $j$ 时最多可以获胜的局数（ $j = 1$ 时表示出石头， $j = 2$ 时表示出布， $j = 3$ 时表示出剪刀）。

初始化：

if (s[0] == 'R') {
        f[0][1] = 0; // 两人一起出石头，不计分
        f[0][2] = 1; // 高桥出布，高桥加一分
        // 注意：高桥不可以输给青木，所以 f[0][3] 不可以初始化为 -1
    }
    if (s[0] == 'P') {
        f[0][2] = 0; // 同理
        f[0][3] = 1;
    }
    if (s[0] == 'S') {
        f[0][1] = 1;
        f[0][3] = 0;
}

转移方程：

当 $s_i =\textrm{R}$ 时：
$f_{i,1} = \max(f_{i-1,2}, f_{i-1,3})\\ f_{i,2} = \max(f_{i-1,1}, f_{i-1,3}) + 1$ （注意： $f_{i,1}$ 是被 $f_{i-1,2}$ 和 $f_{i-1,3}$ 转移过来的，因为高桥第 $i$ 局出的和第 $i-1$ 局出的不能一样，
高桥不可以输给青木，所以 $j$ 不可以取 $3$ ，即：不可以出剪刀）。
当 $s_i =\textrm{P}$ 时：
$f_{i,2} = \max(f_{i-1,1}, f_{i-1,3})\\ f_{i,3} = \max(f_{i-1,2}, f_{i-1,3}) + 1$ 当 $s_i =\textrm{S}$ 时：
$f_{i,1} = \max(f_{i-1,2}, f_{i-1,3}) + 1\\ f_{i,3} = \max(f_{i-1,1}, f_{i-1,2})$ 答案就取 $\max(f_{n - 1,1},f_{n - 1,2},f_{n - 1,3})$ ，（我的字符串 $s$ 下标从 $0$ 开始存）。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, ans, f[N][10];
string s;
main() {
    cin >> n >> s;
    if (s[0] == 'R') {
        f[0][1] = 0;
        f[0][2] = 1;
    }
    if (s[0] == 'P') {
        f[0][2] = 0;
        f[0][3] = 1;
    }
    if (s[0] == 'S') {
        f[0][1] = 1;
        f[0][3] = 0;
    }
    for (int i = 1; i < n; i++) {
        if (s[i] == 'R') {
            f[i][1] = max(f[i - 1][2], f[i - 1][3]);
            f[i][2] = max(f[i - 1][1], f[i - 1][3]) + 1;
        }
        if (s[i] == 'P') {
            f[i][2] = max(f[i - 1][1], f[i - 1][3]);
            f[i][3] = max(f[i - 1][1], f[i - 1][2]) + 1;
        }
        if (s[i] == 'S') {
            f[i][1] = max(f[i - 1][2], f[i - 1][3]) + 1;
            f[i][3] = max(f[i - 1][1], f[i - 1][2]);
        }
    }
    cout << max({f[n - 1][1], f[n - 1][2], f[n - 1][3]});
    return 0;
}