Znzryb's Blog
0%

Posted on Edited on

题目大意

题目描述
给定一个包含 nn 个顶点和 mm 条边的无向图。第 ii 条边连接顶点 uiu_i 和 viv_i，其初始边权（遍历代价）为 wiw_i。

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

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

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

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

样例输入

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

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

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

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

思路讲解

image

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)O(n) 的解决，也可以使用 naive 的方法 O(n2)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

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

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

也不能说是他们的问题。

image

Posted on Edited on

题目大意

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

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

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

image

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

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

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

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

  • 当 op=2op = 2 时，代表在格子 (x,y)(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×43 \times 4 的网格）：
最少需要 33 次操作。输出提供的方案如下：

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

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

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

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

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

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

思路讲解

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

不难注意到，只有在 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

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

Posted on Edited on

题目大意

题目描述
给定二维平面上的一个标准椭圆方程：

x2a2+y2b2=1\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1

其中 aa 和 bb 是正实数，分别代表椭圆的半轴。

同时给定平面上的一条直线方程：

y=kx+c y = kx + c

已知该直线一定会将椭圆分割成两个区域，要求计算并输出这两个区域中面积较大的那一部分的面积。

输入格式
第一行包含两个整数 aa 和 bb（1≤a,b≤1031 \le a,b \le 10^3），表示椭圆的两个半轴长。
第二行包含两个整数 kk 和 cc（∣k∣,∣c∣≤103|k|,|c| \le 10^3），定义了直线 y=kx+cy = kx + c。
数据保证直线必定与椭圆相交于两个不同的点。

输出格式
输出一个浮点数，表示椭圆中面积较大那一部分的面积。
你的答案与标准答案的绝对误差或相对误差不超过 10−610^{-6} 即被视为正确。

样例

输入

1
2
2 3
1 1

输出

1
12.709803500

样例解释
在样例中，给定椭圆方程为 x222+y232=1\frac{x^2}{2^2} + \frac{y^2}{3^2} = 1，即 x24+y29=1\frac{x^2}{4} + \frac{y^2}{9} = 1。
给定直线方程为 y=x+1y = x + 1。
整个椭圆的面积为 π×a×b=6π≈18.8495559\pi \times a \times b = 6\pi \approx 18.8495559。
直线 y=x+1y = x + 1 穿过该椭圆将其分成两部分，经过计算，这两部分中面积较大的区域面积约为 12.70980350012.709803500。

思路讲解

椭圆方程 x2a2+y2b2=1\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1，做代换 u=xa,  v=ybu = \frac{x}{a},\; v = \frac{y}{b}，椭圆变成 u2+v2=1u^2 + v^2 = 1（单位圆）。

直线 y=kx+cy = kx + c 变成 bv=ka⋅u+cbv = ka \cdot u + c，即 v=kab u+cbv = \frac{ka}{b}\,u + \frac{c}{b}。

面积缩放关系：这个变换的雅可比行列式是 abab，所以在 (u,v)(u,v) 平面上算出的面积，乘以 abab 就是椭圆上的面积。

具体而言，雅克比行列式是：

u=xa,v=ybu = \frac{x}{a}, \quad v = \frac{y}{b}

反过来就是 x=au,  y=bvx = au,\; y = bv。雅可比矩阵是把所有偏导数摆成矩阵：

J=(∂x∂u∂x∂v∂y∂u∂y∂v)=(a00b)J = \begin{pmatrix} \frac{\partial x}{\partial u} & \frac{\partial x}{\partial v} \\ \frac{\partial y}{\partial u} & \frac{\partial y}{\partial v} \end{pmatrix} = \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}

雅可比行列式 = det⁡(J)=ab−0=ab\det(J) = ab - 0 = ab。

这意味着：(u,v)(u,v) 平面上任何一块面积为 SS 的区域，对应回 (x,y)(x,y) 平面上面积为 ab⋅Sab \cdot S。

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
void Solve() {
    ll a0, b0, k0, c0;
    cin >> a0 >> b0 >> k0 >> c0;
    DB k1 = (DB) (k0 * a0) / b0;
    DB c1 = c0 / DB(b0);
    DB dis = distancePL(Point(0, 0), Line(k1, c1));
    cout << fsp(10);
    // 这个 dis = 0 的特判其实不需要 
    if (dis == 0) {
        DB area = pi * a0 * b0;
        area /= 2;
        cout << area << "\n";
        return;
    }
    // 弦长
    DB xian = 2 * sqrt(1 - dis * dis);
    // 角度大小
    DB angle = 2 * acos(dis / 1);
    DB shan = (angle / (2 * pi)) * pi;
    DB area = shan - 0.5 * dis * xian;

    area *= a0;
    area *= b0;
    area = max(area, pi * a0 * b0 - area);

    cout << area << "\n";
}

AC代码

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

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

这个形式一定要化简到 v=u。。。什么的形式

image