Znzryb's Blog

题目大意

题目描述
给定一个长度为 $n$ 的正整数序列 $a$。
求该序列中有多少个连续子段的和为素数。换言之，计算满足 $1 \le l \le r \le n$ 且 $\sum_{i=l}^r a_i$ 为素数的数对 $(l, r)$ 的数量。

输入格式
第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。
每个测试用例包含两行：
第一行为一个整数 $n$（$1 \le n \le 10^6$），表示序列的长度。
第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$，且单组测试数据内 $\sum a_i \le 10^6$），表示序列的元素。
保证同一个文件内所有测试用例的 $n$ 的总和不超过 $10^6$，所有测试用例的 $\sum a_i$ 的总和不超过 $10^6$。

输出格式
对于每个测试用例，输出一行一个整数，表示和为素数的子段数量。

样例

输入：

1
2
3
4
5

2
4
1 2 3 4
12
1 1 4 5 1 4 1 9 1 9 8 10

输出：

1
2

5
16

样例解释
在第一个样例中，满足条件的 $(l,r)$ 数对如下：
$l=1, r=2$：该子段的和为 $3$。
$l=2, r=2$：该子段的和为 $2$。
$l=2, r=3$：该子段的和为 $5$。
$l=3, r=3$：该子段的和为 $3$。
$l=3, r=4$：该子段的和为 $7$。

思路讲解

AC代码

1

心路历程（WA，TLE，MLE……）

题目大意

题目描述

在一个 $n \times m$ 的网格平面上，有一个关键区域。该区域是一个闭矩形，其四个顶点的坐标分别为 $(a,b)$、$(a,d)$、$(c,d)$、$(c,b)$，其中 $0 \le a < c \le n$ 且 $0 \le b < d \le m$。

现在会随机选择一条从 $(0,0)$ 到 $(n,m)$ 的合法路径。合法路径是指每一步只能向右（$x$ 坐标加 $1$）或向上（$y$ 坐标加 $1$）的格点路径。

这条路径必定会将整个平面分成“左上”和“右下”两部分（允许其中一部分为空）。我们关注的是该关键区域是否会被这条路径切断。如果整个闭矩形区域完全位于路径的同一侧（完全在“左上”部分或完全在“右下”部分），则称该关键区域保持“完整”；否则视为被路径切断。

求在所有等概率选择的合法路径中，关键区域保持“完整”的概率。答案需要对 $998244353$ 取模。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。

接下来每行代表一个测试用例，包含六个整数 $n, m, a, b, c, d$（$1 \le n \le 10^3$，$1 \le m \le 10^6$，$0 \le a < c \le n$，$0 \le b < d \le m$），其含义如题目描述所示。

输出格式

对于每个测试用例，单独输出一行一个整数，表示关键区域保持“完整”的概率对 $998244353$ 取模后的结果。

样例输入

1
2
3
4

3
3 3 1 1 2 2
3 3 0 0 3 3
3 3 0 1 3 2

样例输出

1
2
3

1
299473306
199648871

样例解释

在第一个测试用例中，关键区域的大小为 $1 \times 1$。它永远不会被任何路径切断，因此保持完整的概率为 $1$。

在第二个测试用例中，关键区域的大小为 $3 \times 3$，即覆盖了整个纸张。由于除非其中一部分为空，否则撕裂路径总是将纸张分成两个非空部分，因此关键区域保持完整的概率为 $\frac{2}{20}$，即 $\frac{1}{10}$。对 $998244353$ 取模后输出 $299473306$。

在第三个测试用例中，关键区域保持完整的概率为 $\frac{8}{20}$，即 $\frac{2}{5}$。对 $998244353$ 取模后输出 $199648871$。

思路讲解

完全理解隔板法（stars and bars）（插板法应用的特征）

我觉得是类似于这样子思考。

隔板法的思想就是，把 a 插入 d 个空格当中，换为给 a 加上 d-1 个隔板。

AC代码

1

心路历程（WA，TLE，MLE……）

https://qoj.ac/contest/2646

题目大意

题目描述
给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，其初始边权（遍历代价）为 $w_i$。

你可以将所有边的边权同时增加一个非负实数 $k$。
请问：存在多少条从顶点 $1$ 到顶点 $n$ 的不同路径，使得至少存在一个 $k$ 的值，能够让该路径成为从顶点 $1$ 到顶点 $n$ 的最短路之一？

两条路径被认为是不同的，当且仅当它们包含的边数不同，或者在某一步经过了不同编号的边（即使连接的顶点相同）。
由于答案可能很大，请输出可能成为最短路的不同路径数量对 $998244353$ 取模后的结果。

输入格式
第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 5000$，$1 \le m \le 5000$），分别表示图的顶点数和边数。
接下来的 $m$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$），描述了一条连接 $u_i$ 和 $v_i$、边权为 $w_i$ 的无向边。
保证所有测试用例的 $n$ 之和不超过 $5000$，$m$ 之和不超过 $5000$。

输出格式
对于每个测试用例，输出一个整数，表示符合条件的路径数量对 $998244353$ 取模的值。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3
3 4
1 2 1
1 2 1
2 3 1
2 3 1
5 6
1 5 3
1 2 1
2 5 2
1 3 1
3 4 1
4 5 1
8 9
1 2 1
1 3 5
2 6 1
6 4 1
3 4 1
3 5 1
4 8 5
5 7 1
7 8 1

样例输出

1
2
3

4
3
4

样例解释
以第一个测试用例为例，图中有 $3$ 个顶点和 $4$ 条边。
顶点 $1$ 和 $2$ 之间有两条权值为 $1$ 的平行边。
顶点 $2$ 和 $3$ 之间有两条权值为 $1$ 的平行边。
无论非负实数 $k$ 取何值，从 $1$ 到 $3$ 的最短路径一定由一条连接 $1, 2$ 的边和一条连接 $2, 3$ 的边组成（共经过 $2$ 条边，总权值为 $2+2k$）。包含边的组合情况共有 $2 \times 2 = 4$ 种不同路径，因此答案为 $4$。

对于第二个测试用例：
有三条从 $1$ 到 $5$ 的主要路径方案：
路径一：直接走边 $1 \leftrightarrow 5$，包含 $1$ 条边，初始总权值为 $3$。当所有边权增加 $k$ 时，该路径的总代价为 $3 + k$。
路径二：依次经过 $1 \leftrightarrow 2 \leftrightarrow 5$，包含 $2$ 条边，初始总权值为 $1 + 2 = 3$。当所有边权增加 $k$ 时，该路径的总代价为 $3 + 2k$。
路径三：依次经过 $1 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 5$，包含 $3$ 条边，初始总权值为 $1 + 1 + 1 = 3$。当所有边权增加 $k$ 时，该路径的总代价为 $3 + 3k$。
可以发现，当 $k=0$ 时，这三条路径的总代价都是 $3$，均能够成为从 $1$ 到 $5$ 的最短路。因此可能的路径总数为 $3$。

对于第三个测试用例，答案经过相同的逻辑推导，共有 $4$ 条路径有可能在某个 $k$ 值下成为最短路。

思路讲解

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

vector<ll> mndis(N + 2, INF);
mndis[1] = 0;
vector<ll> cntRoute(N + 2);
// 起始值
cntRoute[1] = 1;
// 说白了，由于我们采用一维数组设计，因此就是滚动数组
// 如果开两维，就是有一维是 step
vector<ll> step_mndis(N + 2, INF), step_sp_cnt(N + 2);
for (int step = 1; step <= N - 1; ++step) {
  // 在 step 步下，到达该点所需的最短路径长度
  // 在 step 步下，到达该点的最短路径长度
    vector<ll> lmndis(N + 2, INF), lcntRoute(N + 2);
    for (int u = 1; u <= N; ++u) {
        for (auto [to,w]: g[u]) {
            if (mndis[u] + w > lmndis[to]) {
                continue;
            }
            if (mndis[u] + w == lmndis[to]) {
                lcntRoute[to] += cntRoute[u];
                lcntRoute[to] %= mod;
                continue;
            }
            if (mndis[u] + w < lmndis[to]) {
                lcntRoute[to] = cntRoute[u];
                // lcntRoute[to] %= mod;
                lmndis[to] = mndis[u] + w;
            }
        }
    }
    swap(lcntRoute, cntRoute);
    swap(lmndis, mndis);
    step_mndis[step] = mndis[N];
    step_sp_cnt[step] = cntRoute[N];
}

超出可能成为最小值的那些直线，可以使用凸包 $O(n)$ 的解决，也可以使用 naive 的方法 $O(n^2)$ 解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

vector<Point> hull;
for (int step = 1; step <= N - 1; ++step) {
    hull.push_back(Point(step, step_mndis[step]));
}
hull = make_convex_hull(hull, true);
ll ans = 0;
for (int i = 0; i < SZ(hull); ++i) {
    auto [step,dummy] = hull[i];
    if (i == 0) {
        ans += step_sp_cnt[step];
        ans %= mod;
        continue;
    }
    // 我们只要下凸包
    if (dummy > hull[i - 1].y) {
        break;
    }
    ans += step_sp_cnt[step];
    ans %= mod;
}

AC代码

AC
https://qoj.ac/submission/2147487
AC
https://codeforces.com/gym/106139/submission/367332908

1

心路历程（WA，TLE，MLE……）

感觉最近的 ai 属于是纯纯傻逼啊，这么简单的 bfs 都不会，非要用 dp，真的是纯纯傻逼，问题是 dp 很难解决这个问题！！！

也不能说是他们的问题。

题目大意

题目描述
给定一个 $n \times m$ 的初始为空的网格，你可以进行以下两种操作：

1. 选择一个格子 $(x, y)$，在其所在的整行和整列的所有空格子中放置小球。

2. 选择一个格子 $(x, y)$，在经过该格子的两条对角线的所有空格子中放置小球。

即使一个格子中已经有小球，你依然可以选择该格子进行操作。
你需要求出填满整个网格所需的最少操作次数，并输出对应的具体操作方案。

输入格式
第一行为测试用例数量 $T$（$1 \le T \le 10^4$）。
每个测试用例包含一行两个整数 $n, m$（$1 \le n, m \le 10^3$），代表网格的行数和列数。
保证所有测试用例的 $n \times m$ 之和不超过 $10^6$。

输出格式
对于每个测试用例：
第一行输出最少操作次数 $p$（$1 \le p \le n \times m$）。
随后 $p$ 行，每行输出三个整数 $op, x, y$（$1 \le x \le n, 1 \le y \le m$），代表一次操作：

• 当 $op = 1$ 时，代表在格子 $(x, y)$ 进行行列的操作；

• 当 $op = 2$ 时，代表在格子 $(x, y)$ 进行对角线的操作。

样例数据

1
2
3
4
5
6
7
8
9
10
11
12
13

Input
2
3 4
2 2

Output
3
2 2 2
2 2 3
1 2 4
2
1 1 1
1 2 2

样例解释针对第一组测试数据（$3 \times 4$ 的网格）：
最少需要 $3$ 次操作。输出提供的方案如下：

• 第 $1$ 次操作：2 2 2，对 $(2, 2)$ 使用对角线操作。

• 第 $2$ 次操作：2 2 3，对 $(2, 3)$ 使用对角线操作。

• 第 $3$ 次操作：1 2 4，对 $(2, 4)$ 使用行列操作。
  这 $3$ 次操作结束后，整个 $3 \times 4$ 的网格均会被小球覆盖。

针对第二组测试数据（$2 \times 2$ 的网格）：
最少需要 $2$ 次操作。输出提供的方案如下：

• 第 $1$ 次操作：1 1 1，对 $(1, 1)$ 使用行列操作，此时第 $1$ 行和第 $1$ 列被填满。

• 第 $2$ 次操作：1 2 2，对 $(2, 2)$ 使用行列操作，此时第 $2$ 行和第 $2$ 列被填满。
  这 $2$ 次操作结束后，全部 $4$ 个格子均被填满。

思路讲解

赛时这个队友的这个思路，还是很厉害的。

不难注意到，只有在 3*3 的网格上，对角线操作才可以减少操作数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void Solve() {
    ll N, M;
    cin >> N >> M;
    ll opN = N, opM = M;
    vector<array<ll,3>> ops;
    for (int i = 1; i <= min(N, M); ++i) {
		    // 不难注意到，只有在 3*3 的网格上，对角线操作才可以减少操作数量
        if (opN == 3 && opM == 3) {
            // cout<<
            ops.push_back({2,i+1,i+1});
            ops.push_back({1,i+1,i+1});
            break;
        }
        // cout << 1 << " " << i << " " << i << "\n";
        ops.push_back({1,i,i});
        opM--;
        opN--;
    }
    cout<<SZ(ops)<<"\n";
    for (auto [a,b,c]:ops) {
        cout<<a<<" "<<b<<" "<<c<<"\n";
    }
}

AC代码

AC
https://codeforces.com/gym/106139/submission/367213905

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

/**
 * Problem: D. Box
 * Contest: The 21st Hunan Provincial Collegiate Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106139/problem/D
 * Created: 2026-03-18 17:27:21
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT, testcase;

/*
 *
 */

void Solve() {
    ll N, M;
    cin >> N >> M;
    ll opN = N, opM = M;
    vector<array<ll,3>> ops;
    for (int i = 1; i <= min(N, M); ++i) {
        if (opN == 3 && opM == 3) {
            // cout<<
            ops.push_back({2,i+1,i+1});
            ops.push_back({1,i+1,i+1});
            break;
        }
        // cout << 1 << " " << i << " " << i << "\n";
        ops.push_back({1,i,i});
        opM--;
        opN--;
    }
    cout<<SZ(ops)<<"\n";
    for (auto [a,b,c]:ops) {
        cout<<a<<" "<<b<<" "<<c<<"\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106139/submission/367213905

*/

心路历程（WA，TLE，MLE……）