小乖乖的妙妙屋
0%

发表于 分类于
本文字数： 3.9k 阅读时长 ≈ 7 分钟

原题链接：https://codeforces.com/contest/1701/problem/E

题目大意

给你一个字符串 s，要你通过下面的操作变成字符串 t，同时要求操作数最小。（光标初始在 s 的最后一个字符的右边）

  1. home 光标移动到第一个字符左边
  2. left 和 right 光标移动一个单位距离
  3. backspace 删除光标前的那个字符
  4. end 光标移动到最后一个字符右边

思路分析

比赛时统计答案的部分没调出来。

一眼 dp。有一个很明显的结论：在确定了你要留下的东西之后，你先把右边该删的删完再去删左边要删的，显然是更优的。所以我们可以分开 dp，然后把从左往右的答案和从右往左的答案拼起来。

用 表示光标在i的右边，且从右往左匹配到第j个字母的最小操作数， 表示光标在i的左边，且从左往右匹配到第j个字母的最小操作数。于是有下面的方程：

从左到右扫求出 g，从右往左扫求出 f。直接枚举 k 的话是 。加一个数组来存下对于每个 j， 和 的最小值，就可以优化到 。

然后统计答案。

统计答案的细节如下：

最直观的，我们需要取 。

对于从右往左一路删到底的情况，我们在从右往左匹配到第一个字符后，还要考虑它前面是不是还有多余的字符要删，如果有，那我们需要 left 一次，然后删掉多余的字符。

即：。

然后，还有一种较为麻烦的情形：我们在 dp 时是默认光标跟着匹配过程移动的，可有的时候，中间那个连续段，我们并不需要把光标移进去，因为那段中间没有任何需要删的内容。我们删到那一段右边后就可以直接润去删它的左边了。

即：，当 时。

以及在这种情形下也有一个特判： 且 ，并不需要 里的那次 home。

即：

我们统计答案用的必须是有效的 和 ，也就是说这两个数不可以是 。

对于前面几种情形，直接 的枚举就可以统计。

对于中间有一段不需要把光标移进去的情形，我们可以想到一个很直观的三重循环：枚举 i, j 和 k。这样会 tle on test 20。所以我们需要加一点优化。

一个很明显的贪心结论：既然你中间要弄出一段来，那这一段一定是能弄多长就弄多长吧。

以及另一个明显的结论：如果 ，根据我们的转移方程， 显然不可能不是 ，不然它可以往左边的 i+k 转移使得前者不是 。

由于我们是从左往右枚举 i 的。那如果从 i, j 这里凑出了一段来，那后面枚举到 i+1, j+1 的时候再去枚举 k 就没有必要了，因为不可能会比前面更优。

所以我们直接把扫过的用上的 设成 。及时中断不需要的循环。

代码

不要吐槽为什么 rep 和 for 混着用。因为是比赛时敲的，顺手就敲进去了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int N = 5e3 + 5, INF = 0x3f3f3f3f;
int n, m; char s[N], t[N]; int f[N][N], mi[N], g[N][N];
int main() {
    //freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) g[i][j] = f[i][j] = INF;
        scanf(" %s %s", s + 1, t + 1);
        rep(i, 1, m) mi[i] = INF;
        for(int i = n; i >= 1; i--) {
            for(int j = m; j >= 1; j--) {
                if(s[i] != t[j]) continue;
                if(j == m) {
                    f[i][j] = n - i;
                    continue;
                }
                /*for(int k = i + 1; k <= n; k++) {
                    if(s[k] == t[j + 1]) f[i][j] = min(f[i][j], f[k][j + 1] + k - i);
                }*/
                if(mi[j + 1] != INF) f[i][j] = min(f[i][j], mi[j + 1] - i);
                else break;
            }
            for(int j = 1; j <= m; j++) mi[j] = min(mi[j], f[i][j] + i);
        }
        rep(i, 1, m) mi[i] = INF;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(s[i] != t[j]) continue;
                if(j == 1) {
                    g[i][j] = 1 + (i - 1) * 2;
                    continue;
                }
                /*for(int k = 1; k <= i - 1; k++) {
                    if(s[k] == t[j - 1]) g[i][j] = min(g[i][j], g[k][j - 1] + i - k + i - k - 1);
                }*/
                if(mi[j - 1] != INF) g[i][j] = min(g[i][j], mi[j - 1] + 2 * i);
                else break;
            }
            rep(j, 1, m) {
                if(g[i][j] == INF) continue;
                mi[j] = min(mi[j], g[i][j] - 2 * i - 1);
            }
        }
        int res = INF;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(s[i] != t[j]) continue;
                //printf("i=%d j=%d f=%d g=%d\n", i, j, f[i][j], g[i][j]);
                res = min(res, g[i][j] + f[i][j]);
                if(j == 1 && g[i][j] != INF) {
                    int d = i == 1 ? 0 : 1;
                    res = min(res, f[i][j] + d + i - 1); // 顺着删到后面去
                }
                /*if(j == m && f[i][j] != INF) {
                    res = min(res, g[i][j] + n - i); // 其实会被算过，不需要这个也行
                }*/
            }
        }
        //printf("ss%d\n", res);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(s[i] != t[j]) continue;
                for(int k = j + 1; k <= m; k++) {
                    if(s[i + k - j] != t[k]) break;
                    if(g[i][j] == INF || f[i + k - j][k] == INF) break;
                    //printf("i=%d %d j=%d %d: g=%d f=%d\n", i, i + k - j, j, k, g[i][j], f[i + k - 1][k]);
                    if(j == 1) {
                        int d = i == 1 ? 0 : 1;
                        res = min(res, f[i + k - j][k] + d + (i - 1) * 2);
                    }
                    /*if(k == m) {
                        res = min(res, g[i][j] + n - (i + k - j));
                    }*/
                    res = min(res, g[i][j] + f[i + k - j][k]);
                    f[i + k - j][k] = INF;
                }
            }
        }
        if(res == INF) printf("-1\n");
        else printf("%d\n", res);
    }
    return 0;
}

发表于 更新于 分类于
本文字数： 2.1k 阅读时长 ≈ 3 分钟

原题链接：https://codeforces.com/contest/1700/problem/E

题目大意

给你一个排列 A 和排列 B，你要通过下面的操作把 A 弄成 B。你有一个“力量”值 ，对于每个 ，选择一个 ，交换 和 的位置。例如 1 3 2 交换 1 和 2，结果是 2 3 1。问你 A 能变成的不同 B 有多少种（给出了 B 的部分位置的值，其它位置的值可以随便取，只要是个排列就行）。

思路分析

这题太抽象了。比赛时连怎么换的都绕不清楚，一直满脑子的什么连有向边什么环什么链什么玩意，更别提计数了。

首先，因为从头到尾换的都是值，所以我们可以把其中一个排列“标准化”。让我们来想一想，如果手头有确定的排列 A 和排列 B，我要怎么把 A 换到 B 呢？

例如：A: 5 4 2 3 1, B: 3 1 4 2 5

将 B 标准化后：A: 4 3 5 2 1, B: 1 2 3 4 5

此时我们从左往右看，首先要把 1 弄到正确的位置上，于是我们交换且只能交换 1 和 4（因为每个值只能进行一个操作，且这个操作的对象必须是比它大的数，如果你现在不换 1，后面 1 就不会再被换到了）。此时变成了：A: 1 3 5 2 4, B: 1 2 3 4 5

换完 1 之后，1 显然是不会再被动的（因为只能往大的方向换），所以我们无视 1。这个时候 2 又变成了最小，我们再去用同样的道理去换 2。直到所有数字都到达正确的位置上。

通过上面的例子，我们不难看出，对于确定的 A 和 B，我们有且只有一个固定的替换方式，来使得 A 变成 B。

而我们要问的是 B 的种数，那我们就需要确认，这个替换过程中，是否一直都满足 。

这里有一个结论：必须有 。

结合上面的标准化后的例子很容易理解：首先 是肯定要的。而我们的替换过程一直是在让 和此时的 替换，因此 是必要的。

而如果 ，那这个 肯定会被前面某个 的 替换。而由于 k 在 i 前面，所以显然有 ，这个点不考虑也罢。因此， 的要求是充分且必要的。

接下来考虑计数的问题。有了这个结论之后，问题就变得简单了不少。我们的问题转化为求满足 的排列数量。

我们把没有确定对应的 弄出来排个序，然后我们从小到大枚举缺的 ，这样就保证了后面枚举到的 的可选位置范围比前一个大。每个 的可选位置数乘起来就是我们要的答案了。

具体看代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 2e5 + 5;
int n, A[N], B[N], s, C[N], cc, D[N], cd; bool vis[N];
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &s);
        for(int i = 1; i <= n; i++) scanf("%d", A + i), vis[i] = 0;
        cc = cd = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", B + i);
            if(B[i] == -1) C[++cc] = A[i];
            else vis[B[i]] = 1;
        }
        bool fail = 0;
        for(int i = 1; i <= n && !fail; i++) {
            if(B[i] != -1) {
                if(A[i] - B[i] > s) fail = 1;
                continue;
            }
        }
        if(fail) {
            puts("0"); 
            continue;
        }
        sort(C + 1, C + cc + 1);
        for(int i = 1; i <= n; i++) {
            if(!vis[i]) D[++cd] = i;
        }
        int p = 0; ll ans = 1;
        for(int i = 1; i <= cd; i++) {
            while(p < cc && D[i] >= C[p + 1] - s) p++;
            if(p - i + 1 <= 0) {
                ans = 0;
                break;
            }
            ans = ans * (ll)(p - i + 1) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

发表于 更新于 分类于
本文字数： 3k 阅读时长 ≈ 5 分钟

原题链接：https://codeforces.com/contest/1700/problem/F

题目大意

给你两个 2*n 的矩阵。上面只有 0 和 1。你每次操作能交换两个相邻位置上的数字。问你最少需要多少次操作才能把矩阵 1 转换成矩阵 2。

思路分析

一道需要仔细观察和猜结论的贪心题。

首先，如果两个矩阵 1 的数量不一样，无解。

然后，这个所谓的交换，可以直接看成 1 的移动。我们假设 1 的数量为 m。

然后你会发现，问题转化成了这样：有 m 个目标点和 m 个起点构成的二分图，边权是曼哈顿距离，要你求一个权值和最小的完美匹配。

这有什么意义嘛。没有。所以我比赛没写出来。

我们再思考一下：单论列的分配，我们可以发现，前 i 个目标，分配给前 i 个起点，肯定不会亏。也就是说，只有一行时，起点和目标点应该是按从左到右的顺序一一对应的。

此外，有一个非常重要且明显的结论：一个点如果要变行，最多只会变一次。

这里就产生了一种非常暴力的做法：枚举每个点是否要变行，先变完行再按上面的贪心策略求解。

我们再进一步观察一下，变行后，答案会发生什么变化。

假如你用一种变行方式求出来的解是 ，那么你换另一种变行方案，它肯定要一个上去一个下来（因为行的数量要对应）。

我们用 表示初始矩阵第一行的 m 个点，用 表示第二行的 n 个点。

同理用 和 表示目标矩阵的。并且记上下移动的次数为 。

此时有：

题解的贪心策略我压根就没看懂。所以我们来看看能不能 dp 吧。

我们可以用 f[i] 表示上面已经匹配了 i 个点，此时的最小步数。我们是从左往右扫的，这个玩意显然是没有后效性的。而且假如我们当前已经扫了 k 个点，那下面就匹配了 k - i 的点。可以得到一个转移方程（当前点为 ）：

或者说

但是这样是 的啊，直接 dp 是自然不行的。

算了，还是看看题解的做法是什么吧。

题解把 的答案做了更进一步的转换：我们记 表示初始矩阵第 i 行前 j 个位置共有多少个 1， 表示目标矩阵的对应值。

于是，我们有 。

用心去感受一下，这个式子是对的。

重要的是，这个式子把难以处理的点坐标差值变化转化成了很好处理的前缀和的区间变化。

例如，如果 的点被挪到了 ，那它会使得 全部减少 1，而 全部加 1。

我们记 ，则有

当 的点被挪到了 ，它会使得 全部减少 1，而 全部加 1。

我们这个式子里面的 都是以绝对值出现的，而由移动引起的变化方向是相反的。并且，从定义上不难看出，随着 i 的移动， 值一次的变化不会超过 1。

所以，我们可以这样贪心：每当我们扫到一个位置，它的 和 异号时，我们进行交换（因为每次变化都最多是 1，所以此处一定有点可换），把点从正的那一行换到负的那一行（首先 s 加一，然后 i 后面的 delta 都要变）。

因为你的 s 只会加 1，而这两个数的绝对值分别少了 1，是赚的。这样至少在当前位置上看，它是赚的。

至于为什么这个策略在全局是对的，题解的证明太长了。我感性地理解一下：

首先你这两 delta 到最后肯定都是 0，因为数量会对上。

另外，这样换的话，你的 delta 绝对值是在减少的。我们知道 delta 每次变化最多是 1。

如果你这里减少了绝对值，那下一次变化也是不会亏的（减到 0，后面变成 1，如果你不减的话原本也是 1，这个 1 还可能多影响了几步，不亏；没减到 0，后面要么加回来要么变得更少，不可能比不减的代价多，不亏）。

总之不懂啊，好难。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n, A[2][N], B[2][N], d[2][N];
inline int sgn(int x) {
    if(x == 0) return 0;
    return x > 0 ? 1 : -1;
}
int main() {
    scanf("%d", &n);
    int cn = 0;
    for(int i = 0; i < 2; i++) for(int j = 1; j <= n; j++) {
        scanf("%d", A[i] + j), cn += A[i][j];
        A[i][j] += A[i][j - 1];
    }
    for(int i = 0; i < 2; i++) for(int j = 1; j <= n; j++) {
        scanf("%d", B[i] + j), cn -= B[i][j];
        B[i][j] += B[i][j - 1];
    }
    if(cn != 0) {
        puts("-1");
        return 0;
    }
    int up = 0, down = 0; ll res = 0;
    for(int i = 1; i <= n; i++) {
        d[0][i] = A[0][i] - B[0][i] + up;
        d[1][i] = A[1][i] - B[1][i] + down;
        if(sgn(d[0][i]) * sgn(d[1][i]) == -1) {
            if(d[0][i] > 0) up--, down++, d[0][i]--, d[1][i]++;
            else up++, down--, d[0][i]++, d[1][i]--;
            res++;
        }
        res += abs(d[0][i]) + abs(d[1][i]);
    }
    printf("%lld\n", res);
    return 0;
}

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 5 分钟

原题链接：https://codeforces.com/contest/1700/problem/E

题目大意

给你一个 n*m 的矩阵，矩阵上的元素是 nm 的排列。要求：能够找到一条路径遍历所有的点（每个点可经过多次），记每个点在第 xi 步第一次被访问，要求有 x1 < x2 < x3 ...。现在问你：原本的矩阵是否满足要求？如果不满足，能否通过1次交换使得它满足要求，可能的交换种类有多少种？

思路分析

一道简单的暴力题。比赛时没想清楚。

一个很明显的结论：1 肯定是起点，对于每个大于 1 的点，它的周围至少要有一个小于它的点。如果所有的点都可以满足这个要求，那么矩阵满足要求。

再考虑交换会发生什么：它只会改变交换的点自身和它周围的点的这个状态。

这意味着：我们的交换至少要包含一个不满足要求的点（或是那个点周围的点），每次交换最多只会影响 10 个点（两个被交换点和它的相邻点）的状态。

所以，我们找到一个不满足要求的点之后，直接枚举它和它周围的这 5 个点作为其中一个交换点，然后枚举所有点作为另外一个交换点，动态地维护、计算图上有多少个点满足要求就行了。复杂度大概是 的。

去重什么的就自己看着办就行了。我是存起来排序 unique 的。直接记录然后减也是可以的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 4e5 + 5;
const int zl[5][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {0, 0}};
int n, m, A[N], f[N], tot, cc;
inline int id(int x, int y) {
    return x * m + y;
}
inline int isBad(int x, int y) {
    if(A[id(x, y)] == 1) return 0;
    int v = A[id(x, y)];
    if(x > 0 && A[id(x - 1, y)] < v) return 0;
    if(y > 0 && A[id(x, y - 1)] < v) return 0;
    if(x < n - 1 && A[id(x + 1, y)] < v) return 0;
    if(y < m - 1 && A[id(x, y + 1)] < v) return 0;
    return 1;
}
inline bool inSqu(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
bool vis[N];
inline bool judge(int x, int y, int p, int q) {
    int i1 = id(x, y), i2 = id(p, q), del = 0;
    int tx, ty, d, i3;
    swap(A[i1], A[i2]);
    for(int i = 0; i < 5; i++) {
        // for i1
        tx = x + zl[i][0], ty = y + zl[i][1];
        if(inSqu(tx, ty)) {
            i3 = id(tx, ty);
            if(!vis[i3]) {
                vis[i3] = 1, d = isBad(tx, ty);
                if(d ^ f[i3]) {
                    if(d > 0) del--;
                    else del++;
                }
            }
        }
        // for i2
        tx = p + zl[i][0], ty = q + zl[i][1];
        if(!inSqu(tx, ty)) continue;
        i3 = id(tx, ty);
        if(!vis[i3]) {
            vis[i3] = 1, d = isBad(tx, ty);
            if(d ^ f[i3]) {
                if(d > 0) del--;
                else del++;
            }
        }
    }
    // clear
    for(int i = 0; i < 5; i++) {
        // for i1
        int tx = x + zl[i][0], ty = y + zl[i][1];
        if(inSqu(tx, ty)) vis[id(tx, ty)] = 0;
        // for i2
        tx = p + zl[i][0], ty = q + zl[i][1];
        if(!inSqu(tx, ty)) continue; // 注意上面不能 continue 哦，因为下面的还要算的
        vis[id(tx, ty)] = 0;
    }
    swap(A[i1], A[i2]);
    return del == tot;
}
struct Op {
    int a, b;
    Op(int s = 0, int t = 0): a(s), b(t) {
        if(a > b) swap(a, b);
    }
    bool operator < (const Op &B) const {
        if(a != B.a) return a < B.a;
        return b < B.b;
    }
    bool operator == (const Op &B) const {
        return a == B.a && b == B.b;
    }
}L[N * 5];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n * m; i++) scanf("%d", A + i);
    int bx = -1, by = -1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(isBad(i, j)) {
                tot += (f[i * m + j] = 1);
                bx = i, by = j;
            }
        }
    }
    if(bx == -1) return puts("0"), 0;
    for(int i = 0; i < 5; i++) {
        int x = bx + zl[i][0], y = by + zl[i][1];
        if(x < 0 || x >= n || y < 0 || y >= m) continue;
        for(int p = 0; p < n; p++) {
            for(int q = 0; q < m; q++) {
                if(judge(x, y, p, q)) {
                    // printf("(%d, %d) - (%d, %d)\n", x, y, p, q);
                    L[++cc] = Op(id(x, y), id(p, q));
                }
            }
        }
    }
    if(cc == 0) return puts("2"), 0;
    sort(L + 1, L + cc + 1);
    cc = unique(L + 1, L + cc + 1) - L - 1;
    printf("1 %d\n", cc);
    return 0;
}

发表于 分类于
本文字数： 2.8k 阅读时长 ≈ 5 分钟

原题链接：https://codeforces.com/contest/1695/problem/D2

题目大意

给你一棵树。要求你指定一组基准点（询问） ，对于树上的每一个点 u，u 对基准点的最短距离形成的 k 元组 两两不同。问基准点（询问）至少要有多少个。

思路分析

这题比赛的时候没想清楚。

首先，一个很明显的结论，如果一个点有 n 个直接儿子，那么至少需要有 n - 1 个询问才能区分它的所有直接儿子。如果只有这个点本身，则不需要添加询问来区分。

于是，我们这样考虑：对于节点 u，我们试图去求区分以 u 的子树内的点需要多少个询问（我们默认 u 会有更上层的点来区分好，因此不去考虑根节点 u，只考虑它的直接和间接子节点）。我们将这个值记为 f[u]。

首先，我们需要区分儿子的子树，因此 f[u] += sum(f[v])。此外，对于 f[v] > 0 的点，意味着这个子节点可以被 u 上面的那个查询和 v 子树内本身已经有的查询来区分。因此，我们记录下 f[v] = 0 的儿子数量 c，我们需要给其中的 c - 1 个儿子进行询问。

故有转移方程：

dp 后得到的 f[u]，是在默认根节点 u 已经由非子树内节点区分的情况下，区分子树内点所需要的最小询问数。或者说默认 u 或 u 的某个父亲上有一个询问（这个询问不记在 f[u] 中，只是假设它存在）的情况下，区分子树内节点的最小询问数。

也因此，我们最终求出的这个 f[rt] 还需要加上 1 （也就是根节点上的询问）才是答案。枚举所有的根节点算一遍，取个 min，就是我们要的解。

然后 D1 与 D2 的区别就是换不换根而已了。

换根其实就是在换到 v 前，把当前这个根 u 的值重新算一遍（去掉 v 的影响，因为 v 已经不是 u 的儿子了），然后换到 v 时把 v 的值按着 dp 方程重新算一遍就行。典。具体参考代码。

代码

D1 O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int head[N], nex[N << 1], to[N << 1], n, cc;
inline void addEdge(int u, int v) {
    nex[++cc] = head[u], head[u] = cc, to[cc] = v;
}
int f[N];
void dfs(int u, int fa) {
    int c = 0;
    f[u] = 0;
    for(int i = head[u]; i; i = nex[i]) {
        if(to[i] == fa) continue;
        dfs(to[i], u);
        f[u] += f[to[i]];
        if(!f[to[i]]) c++;
    }
    if(c) f[u] += c - 1;
}
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n); cc = 0;
        for(int i = 1; i <= n; i++) head[i] = 0;
        for(int i = 1; i < n; i++) {
            int u, v; scanf("%d%d", &u, &v);
            addEdge(u, v), addEdge(v, u);
        }
        int res = n - 1;
        for(int i = 1; i <= n; i++) {
            dfs(i, 0);
            res = min(res, f[i] + 1);
        }
        printf("%d\n", res);
    }
    return 0;
}

D2 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int head[N], nex[N << 1], to[N << 1], n, cc;
inline void addEdge(int u, int v) {
    nex[++cc] = head[u], head[u] = cc, to[cc] = v;
}
int f[N], res, hav[N];
void dfs1(int u, int fa) {
    int c = 0;
    f[u] = hav[u] = 0;
    for(int i = head[u]; i; i = nex[i]) {
        if(to[i] == fa) continue;
        dfs1(to[i], u);
        f[u] += f[to[i]];
        if(!f[to[i]]) c++;
    }
    if(c) {
        f[u] += c - 1;
        if(c > 1) hav[u] = 1;
    }
}
void dfs2(int u, int fa) {
    if(fa) {
        int c = 0; f[u] = 0;
        for(int i = head[u]; i; i = nex[i]) {
            f[u] += f[to[i]];
            if(!f[to[i]]) c++;
        }
        if(c) f[u] += c - 1;
        if(c > 1) hav[u] = 1; // 记住这个 hav 也是会变的
    }
    int fu = f[u];
    res = min(res, f[u] + 1);
    for(int i = head[u]; i; i = nex[i]) {
        if(to[i] == fa) continue;
        if(f[to[i]]) f[u] = fu - f[to[i]];
        else f[u] = fu - hav[u];
        dfs2(to[i], u);
    }
}
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        for(int i = 1; i <= n; i++) head[i] = 0;
        scanf("%d", &n); cc = 0;
        for(int i = 1; i < n; i++) {
            int u, v; scanf("%d%d", &u, &v);
            addEdge(u, v), addEdge(v, u);
        }
        res = n - 1;
        dfs1(1, 0);
        dfs2(1, 0);
        printf("%d\n", res);
    }
    return 0;
}

发表于 分类于
本文字数： 2.7k 阅读时长 ≈ 5 分钟

原题链接：https://codeforces.com/contest/1695/problem/C

题目大意

给你一个 n * m 的矩阵 (n, m < 1001)。每个元素都是 1 或 -1。你每次只能往下或往右，问你能否找到一条路径使得路上的权值和为 0。

思路分析

比赛的时候只想到了 的做法。

首先，很显然的，步数是 n + m - 1。如果这是个奇数，无解。

然后，转换模型，权值和为 0，其实就是要有一半踩到 1。所以，用一个 n 位的二进制数 f[i][j] 表示从 (1, 1) 走到 (i, j)，手上的 1 可能是多少个。于是可以得到这样的 dp 方程：

1
2
if(A[i][j] == 1) f[i][j] = (f[i - 1][j] << 1) | (f[i][j - 1] << 1);
else f[i][j] = f[i - 1][j] | f[i][j - 1];

套上 bitset，可以通过此题。

但这个不是正解。我们仔细想一想，如果 (i, j) 处最多有 b 个 1，最少有 a 个 1。那么是不是意味着 [a, b] 以内的所有值都能在 (i, j) 找到呢？

我们可以感性的这样想：对于任意一条从左上角到右下角的路径，我们一定能找到另一条路径，使得这两条路径只有一个格子不一样。换句话说，通过挪动路径上的某个格子，你可以得到另外一条路径；任意两条路径间一定可以通过若干次的单格子变化得到。

而我们知道，每次只变化一个格子，那就意味着这条路径上 1 的变化量要么是 0 要么是 1。

因此，如果存在 a 个 1 的路径和 b 个 1 的路径，那么我们一定能够凑出 a 到 b 间的所有数目。

代码

bitset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <iostream>
using namespace std;
const int N = 1e3 + 5;
int n, m, A[N][N];
bitset<N> f[N][N];
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
            scanf("%d", A[i] + j);
            if(A[i][j] == -1) A[i][j] = 0;
            f[i][j].reset();
        }
        if((n + m - 1) & 1) {
            puts("No");
            continue;
        }
        int aim = (n + m - 1) / 2;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(i == 1 && j == 1) {
                    if(A[1][1]) f[i][j].set(1, 1);
                    else f[i][j].set(0, 1);
                    continue;
                }
                //cout << i << " " << j << " " << f[i][j] << endl;
                if(i - 1 > 0) {
                    if(A[i][j] != 0) f[i][j] |= f[i - 1][j] << A[i][j];
                    else f[i][j] |= f[i - 1][j];
                }
                if(j - 1 > 0) {
                    if(A[i][j] != 0) f[i][j] |= f[i][j - 1] << A[i][j];
                    else f[i][j] |= f[i][j - 1];
                }
                //cout << i << " " << j << " " << f[i][j] << endl;
            }
        }
        if(f[n][m].test(aim)) puts("Yes");
        else puts("No");
    }
    return 0;
}

正解

代码的逻辑和上面分析的不太一样，这里是直接用了权值和而不是 1 的数量。但原理是一样的。都是利用了路径构造的特点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e3 + 5;
int A[N][N], f[N][N], g[N][N], n, m;
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) scanf("%d", A[i] + j);
        }
        if((n + m - 1) & 1) {
            puts("No");
            continue;
        }
        for(int i = 1; i <= n; i++) {
            if(i == 1) {
                f[i][1] = g[i][1] = A[i][1];
                for(int j = 2; j <= m; j++) f[i][j] = g[i][j] = f[i][j - 1] + A[i][j];
                continue;
            }
            f[i][1] = f[i - 1][1] + A[i][1];
            g[i][1] = g[i - 1][1] + A[i][1];
            for(int j = 2; j <= m; j++) {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + A[i][j];
                g[i][j] = min(g[i - 1][j], g[i][j - 1]) + A[i][j];
            }
        }
        if(g[n][m] <= 0 && f[n][m] >= 0) puts("Yes");
        else puts("No");
    }
    return 0;
}

发表于 分类于
本文字数： 433 阅读时长 ≈ 1 分钟

傻逼错误

此处收录了 debug 时发现的一些血压飙升的错误。警钟长鸣。

  1. 注意 n 和 m 的读入顺序和在 for 循环里的使用，别把 n m 弄成 n n。
  2. 小心 1 和 '1'，这是一个情急下很容易写错且难以意识到的问题。
  3. 注意多测的清空，尤其是多测下前向星数组的 head 和 cc。
  4. 注意数组的初始化。特别是 dp 的时候如果懒得写边界特判的时候。
  5. 注意 continue 的位置。如果你只是想跳过中间的某一段代码，后面还有另外的要执行，就不能 continue。这个问题在一开始没有考虑清楚逻辑，后续补上其它代码段时非常容易出现。
  6. 记得删 freopen。
  7. 小心 i*j n*i 之类的东西爆 int。
  8. 线段树大小是 0 的 build 会死循环。小心边界特判。
  9. queue 的初始化非常的慢，空间非常的玄学，不要开大的 queue 数组。

经验

  1. 理清程序逻辑
  2. 看清题目要求（例如昆明那道面积覆盖的矩形，写成了格点覆盖，死活没想到这个问题痛失银牌）
  3. 注意边界特判
  4. 检查傻逼错误（变量名、多测清空、初始化等）
  5. 对于复杂度玄学的 dp，尝试尽可能减少状态比卡常更有效

发表于 更新于 分类于
本文字数： 486 阅读时长 ≈ 1 分钟

学期小结

  • 呜呜，好久没有写博客了。最近可算是考完了，但是还要等个十来天才能搬去网安基地。这几天无所事事，每天 vp 一下写写题解，打打游戏逛逛本校，顺便收收东西，看看找点什么东西学一学。

  • 之前数据库实验学了 django 框架，一个人写完了前后端（一个非常简单的网页），也许可以找个时间分享一下学习经验。还有好多整理的一半一半的各个学科的学习资料，也得找个时间编排一下比较好。

  • 这学期有点小摆，基本靠着 namomo 的每日一题在苟命。不过也算是有进步吧？cf 终于还是突破了 2000，可惜还没橙。昆明拿了个铜，因为一个傻逼错误没搞出 dp，非常蛋疼。然后换了队友，省赛拿了 rk2。

  • 顺便入坑了 arcaea。不过拇指玩起来好蛋疼，得找个机会入个平板。顺便平板也能记笔记什么的。嗯。绝对不是为了玩音游才想买平板的。嗯。

  • 这学期也开始学到一些比较底层的东西了，操作系统和编译原理。老师有布置过几个让我们去阅读底层代码的任务，但是我真的看不懂，而且也没什么时间，完成的不是很好，暑假该找时间更细致的学一下。毕竟 acm 也就图一乐，还得干干正事。

  • 以及发现博客园的延迟有点小大，想换个博客玩玩了，所以搭了个新的

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 2 分钟

Qing-LKY 的个人博客

前言

博客园不知道为什么不能实时更新了。感觉很蛋疼。所以想试着自己搭一个博客。

使用的是 github.io + hexa 的经典组合。暂时选了 next 作为主题。

本文整理了在搭建过程中遇到的问题和解决的思路。

问题与解决过程记录

  1. npm 显示如下警告信息，但仍可正常使用：

    npm WARN config global --global, --local are deprecated. Use --location=global instead

    首先尝试更新 npm 版本 npm install -g npm。

    查阅资料，发现 github 上有过这个 issue

    我选择的解决方法如下：

    用管理员权限打开记事本，然后用带管理员权限的记事本去修改 nodejs/npm 和 nodejs/npm.cmd。

    把里面 prefix -g 替换成 prefix --location=global。

  2. hexo 的工作目录与 github.io 应该是两个不同的仓库

    一开始没有注意到这个问题，直接把 hexo 新建好的工作目录推到我的 github.io 仓库里了。

    后面完成基本配置 deploy 的时候才发现部署时会用生成的静态文件完全覆盖 github.io 那个仓库。

    github.io 这个仓库放的是你的网页，hexo 的工作目录需要放到另外的一个仓库里。

    于是我新创了一个 MyBlog 的远端仓库，改了 .git/config 里的 remote 地址。

  3. 添加 next 主题后，git 提示你套了一个 repository

    我是直接在 themes 里 clone 的。所以弄下来的这个会带有 .git 文件夹，就变成了仓库套仓库了。

    我没有按提示的设置子模块。而是先取消追踪，然后直接删掉了next 里的 .git 文件夹。

    如果想要设置子模块的话，fork 一个到自己的账户下会比较好。而且修改配置的时候会比较麻烦。我懒得弄了。

  4. latex 在本地预览时正常渲染，推到远端时无法渲染

    我一开始只用的 next 和 hexo-renderer-pandoc。

    卸掉 hexo-renderer-marked，装了 hexo-renderer-pandoc，改了下 next 里的配置（enable）。

    这时候本地已经能渲染出来了（hexo s）。

    但是推到远端去看不到。所以我陆陆续续采用了下面的手段尝试补救。我不知道哪个是关键的，所以我全部记录了下来：

    首先，我重新安装了 pandoc。然后，我又安装了 hexo-math。然后，我又安装了 hexo-filter-mathjax。然后，我把 next 配置里面 mathjax 的 mhchem 设成了 true。然后我又把它改回了 false。然后我又重启电脑重复了一遍上述的某些操作。

    最后我查阅资料发现以前版本的 next 的 math 配置长得和现在不太一样。（参考的是这篇文章）

    把 cdn:xxxxx 那一行配置复制到 next 的配置文件的对应位置上，再次部署。发现它好了。