旺崽的博客

要么天赋异禀，要么天道酬勤

0%

发表于 分类于 Valine：

题目链接

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。

人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。

这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。

示例 1:

1
2
3
输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。

示例 2:

1
2
3
输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

并查集~
学过交换排序的肯定都知道，最多只需要 $n-1$ 次交换就能让长为 $n$ 的数组有序，用到这题同理，我们发现最多只需要 $\frac{n}{2}-1$ 次交换就可以让所有情侣配对，那么怎么计算最少交换次数呢？
这里就要用到并查集了，我们考虑每一对情侣就是一个连通分量，最后配对之后的连通分量就是 $\frac{n}{2}$ 对，那么我们只需要计算出开始的连通分量个数 $cnt$，答案就是 $\frac{n}{2}-cnt$ 了，因为每一个配对的情侣编号都是一奇一偶，所以我们可以除 $2$ 来将编号统一，AC代码如下：

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
class Unionset {
public:
    vector<int> father;
    vector<int> sum;
    int cnt = 0;
public:
    void init(int n) {
        father.resize(n);
        for (int i = 0; i < n; i++) father[i] = i;
        sum.resize(n);
        cnt = n;
    }

    int findFather(int x) {
        return x == father[x] ? x : father[x] = findFather(father[x]);
    }

    bool Union(int x, int y) {
        x = findFather(x), y = findFather(y);
        if (x == y) return 0;
        if (sum[x] < sum[y]) swap(x, y);
        father[y] = x;
        sum[x] += sum[y];
        --cnt;
        return 1;
    }
};

class Solution {
public:
    int minSwapsCouples(vector<int> &row) {
        int n = row.size();
        Unionset u = Unionset();
        u.init(n / 2);
        for (int i = 0; i < n; i += 2) u.Union(row[i] / 2, row[i + 1] / 2);
        return n / 2 - u.cnt;
    }
};

发表于 分类于 Valine：

题目链接

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。

int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例：

输入：

1
2
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

输出：

1
2
3
4
5
6
7
8
9
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

堆~
简单数据结构，我们只需要维护一个大小为 k 的小根堆即可，每次 add 操作也只需要比较添加的元素和堆顶元素的大小即可，我写了 C++ 和 Python 的两个代码：

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
class KthLargest {
private:
    priority_queue<int, vector<int>, greater<>> q;
    int siz;
public:
    KthLargest(int k, vector<int> &nums) {
        siz = k;
        for (auto i:nums) {
            if (q.size() < k) q.emplace(i);
            else if (i > q.top()) q.pop(), q.emplace(i);
        }
    }

    int add(int val) {
        if (q.size() < siz) {
            q.push(val);
            return q.top();
        } else {
            if (val < q.top()) return q.top();
            else {
                q.pop();
                q.emplace(val);
                return q.top();
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.siz = k
        self.q = []
        for i in nums:
            if len(self.q) < self.siz:
                heapq.heappush(self.q, i)
            elif i > self.q[0]:
                heapq.heappop(self.q)
                heapq.heappush(self.q, i)

    def add(self, val: int) -> int:
        if len(self.q) < self.siz:
            heapq.heappush(self.q, val)
            return self.q[0]
        else:
            if val < self.q[0]:
                return self.q[0]
            else:
                heapq.heappop(self.q)
                heapq.heappush(self.q, val)
                return self.q[0]

发表于 分类于 Valine：

题目链接

题目描述

长度不超过 $n$，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对 $10^9+7$ 取模。
所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。

例如，”unoacscc” 包含子序列 “us”，但 “scscucu” 则不包含子序列 “us”

输入描述:

一个正整数 $n（2 \leq n \leq 10^6）$

输出描述:

一个正整数，为满足条件的字符串数量对 $10^9+7$ 取模的值

示例1

输入

1
2

输出

1
1

示例2

输入

1
3

输出

1
77

示例3

输入

1
874520

输出

1
16471619

排列组合题~
我们考虑长度为 $n$ 的字符串的排列：

假设某一位置 $pos$ (本题下标默认从 $1$ 开始) 放上字母 $u$，如下：

显然后面字母 $s$ 的放法有 $n-pos$ 种，这 $n-pos$ 个位置为避免出现重复答案在放完 $s$ 后其他位置只能放除 $s$ 外的 $25$ 个字母，即每一种 $s$ 的摆放答案就是 $25^{n-pos-1}$ 种，一共 $(n-pos)*25^{n-pos-1}$ 种~
下面考虑 $pos$ 位置之前的字母放置方案，显然前面的位置可以放任意字母，答案就是 $26^{pos-1}$ 种~
综上所述，只需要遍历每一个位置求和即可得到答案：

但是题目要求所有长度小于等于 $n$ 的答案，所以有两种方案：

  1. 化简上面的公式
  2. 构造递推式，我采取了这种方法，根据上述公式得到如下递推式：

推导过程：

$f{n+1}=\sum{i=1}^{n}26^{i-1}(n+1-i)25^{n-i}$

$\ \ \ \ \ \ \ \ \ =n25^{n-1}+[26(n-1)25^{n-2}+26^2(n-2)*25^{n-3}+\cdots+26^{n-1}]$

$\ \ \ \ \ \ \ \ \ =n25^{n-1}+\sum_{i=1}^{n-1}26^{i}(n-i)*25^{n-i-1}$

$\ \ \ \ \ \ \ \ \ =n25^{n-1}+26\sum_{i=1}^{n-1}26^{i-1}(n-i)25^{n-i-1}$

$\ \ \ \ \ \ \ \ \ =n25^{n-1}+26f_n$

</font>
预处理算出 1e6 内的答案即可，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;

ll power(ll a, ll b) { return b ? power(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }

int main() {
    ll n;
    cin >> n;
    vector<ll> ans;
    ans.push_back(1);
    for (ll i = 2; i <= 1000000; i++) {
        ll sum = (power(25, i - 1) * i % mod + ans[i - 2] * 26 % mod) % mod;
        ans.push_back(sum);
    }
    for (int i = 1; i < ans.size(); i++) ans[i] = (ans[i - 1] + ans[i]) % mod;
    cout << ans[n - 2];
    return 0;
}

发表于 分类于 Valine：

题目链接

题目描述

有一个 $n$ 行 $m$ 列的网格，第 $i$ 行 $j$ 列上有数字 $a_{i,j}$ 。每个位置需要从上下左右四个方向中选择互相垂直的两个。

定义 $w(x)=x+popcnt(x)$ ，其中 $popcnt(x)$ 表示 x 的二进制位中 1 的位的数量。

如果两个相邻的位置 $(x1,y_1),(x_2,y_2)$ 互相位于对方选择的某个方向上，则对答案由 $w(a{x1,y_1}\ xor\ a{x_2,y_2})$ 的贡献，其中 $xor$ 表示二进制中的按位异或。

小 Z 想问你答案的最大值是多少。

输入描述:

第一行，输入 $n,m$ 。

接下来 $n$ 行 $m$ 列，输入这个网格。

输出描述:

输出答案的最大值。

示例1

输入

1
2
3
4
3 3 
1 3 6
3 2 4
7 4 0

输出

1
38

动态规划~
因为选定的两个方向必须垂直，所以我们可以将竖直方向和水平方向分开计算，假设先计算水平方向的最大值，对某一行 $i$，用 $dp[j][0/1]$ 表示这一列的最大值，$0$ 表示选左边，$1$ 表示选右边，则有如下状态转移方程：

  • $dp[j][0]=max(dp[j-1][0],dp[j-1][1]+w(a[i][j-1]\oplus a[i][j])$
  • $dp[j][1]=max(dp[j-1][0],dp[j-1][1])$

每一行的最大值就是 $max(dp[m][0],dp[m][1])$，累加即可，对竖直方向同理，AC代码如下：

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
#include <bits/stdc++.h>

using namespace std;
int n, m, ans, a[1005][1005], dp[1005][2];

int f(int x1, int y1, int x2, int y2) {
    return (a[x1][y1] ^ a[x2][y2]) + __builtin_popcount(a[x1][y1] ^ a[x2][y2]);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            dp[j][0] = max(dp[j - 1][0], dp[j - 1][1] + f(i, j - 1, i, j));
            dp[j][1] = max(dp[j - 1][0], dp[j - 1][1]);
        }
        ans += max(dp[m][0], dp[m][1]);
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= m; i++) {
        for (int j = 2; j <= n; j++) {
            dp[j][0] = max(dp[j - 1][0], dp[j - 1][1] + f(j - 1, i, j, i));
            dp[j][1] = max(dp[j - 1][0], dp[j - 1][1]);
        }
        ans += max(dp[m][0], dp[m][1]);
    }
    cout << ans;
    return 0;
}

发表于 分类于 Valine：

题目链接

题目描述

在算法竞赛中”hack”一般指用一组测试数据触发程序的缺陷，从而导致本来通过题目的 AC 代码无法通过该测试数据。
一般情况见得比较多的是用 hack 数据导致别人 WA 掉，当然也有一些会导致原本的 AC 代码 TLE 和 MLE。
牛牛在一些简单的练习题时遇到了这样一个问题。
给定一个大小为 $n$ 的数组 $a(1 \leq a_i \leq 10^9)$，然后请你判断数组元素是否能够从中选出三个组成一个三角形。

牛牛发现AC通过的代码中有这样一种暴力逻辑，该逻辑的伪代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
FOR i = 1 ... n
    FOR j = i + 1 ... n
        FOR k = j + 1 ... n
            IF isTriangle(a[i],a[j],a[k])
                print("yes")
                EXIT
            END IF
        END FOR
    END FOR
END FOR
print("no")
EXIT

其实就是三重循环枚举数组的三个元素，检查是否为三角形。这段代码很取巧的地方在于它存在一种“短路”逻辑，一旦发现存在三角形就立刻终止程序。

这样在随机数据下其实很容易发现三角形，所以如果数据纯随机，显然这就是一段 AC 代码。

牛牛当然知道这个代码很明显就存在缺陷，如果数据构造的好的话应该可以卡 TLE，但是牛牛发现，他并不会构造出能够 hack 这个暴力算法的数据，所以他请你来帮他。

我们以这段程序调用 isTriangle 的次数作为时间复杂度的计算依据，请你构造数据 hack 这段暴力程序，使它 TLE 掉。

输入描述:

第一行输入一个正整数 $n(3 \leq n \leq 10^5)$ 表示需要你构造的数组大小。

输出描述:

输出 $n$ 个正整数，正整数的范围在 $[1,10^9]$ 之间，要求该暴力程序在运行过程中调用 isTriangle 函数的次数不得少于 $min(C_n^3,n^2\left \lfloor log_2n \right \rfloor)$

示例1

输入

1
3

输出

1
2 2 2

示例2

输入

1
10

输出

1
1 2 4 8 16 32 64 128 256 512

思维~

其实没必要深究用啥序列，因为不论等比数列抑或是斐波那契数列最多不过几十项就爆 int 了，所以这题的关键在于构造，我们要卡一个 $n^2log(n)$，则这个数列迭代的最大项数 $a$ 必须满足 $2^{a-1}\geq n$，根据这一点我们可以选定一个等比数列(怕麻烦就直接选斐波那契数列😂)，那么怎么构造呢，我们可以把数列的后 $a-1$ 项提到前面，后面全放第一项，这样第一重循环选择前 $a-1$ 个数时，后面两重循环无论怎么选都无法构成三角形，此时循环次数就是 $O((a-1)n^2)$，而上面又满足 $2^{a-1}\geq n$，所以此时符合题意，AC 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>

using namespace std;
int n, s = 2;

int main() {
    cin >> n;
    for (int i = 1; i <= 29; i++) {
        cout << s << " ";
        s *= 2;
    }
    for (int i = 29; i <= n; i++)
        cout << 1 << ' ';
    return 0;
}

发表于 分类于 Valine：

题目链接

题目描述

整除分块，又称数论分块。是数论算法中的重要技巧，你可以在各种需要枚举因子的连续求和类问题中见到它的身影。如杜教筛，莫比乌斯反演化简后的整除分段求和等。
整除分块基于这样一个数学现象：对于任意正整数 $N$，集合 $S=\left { x:x=\left \lfloor \frac{N}{i} \right \rfloor ,i\in 1,2,3…N \right }$ 的大小总是严格小于 $2 \sqrt N$ 。
例如当 $N=10$ 时 $S={10,5,3,2,1}$，这就使得对于 $\left \lfloor \frac{N}{i} \right \rfloor$ 类型的求和类问题，只要快速枚举 $S$ 集合，就能在 $\sqrt N$ 级别的复杂度内解决问题。

$\left \lfloor \; \; \right \rfloor$ 符号是向下取整符，$\left \lfloor x \right \rfloor$ 表示不大于 $x$ 的最大正整数

牛牛在学习整除分块这一算法后提出了一个新的问题，对于给定正整数 $N,x$，令$S=\left { x:x=\left \lfloor \frac{N}{i} \right \rfloor ,i\in 1,2,3…N \right }$，时 $\left \lfloor \frac{N}{x} \right \rfloor$在 $S$ 中是第几大呢（去重降序排序后第几个）？

输入描述:

第一行输入一个正整数 $T(1 \leq T \leq 10^6)$，表示测试案例的数目，对于每组案例。
一行两个正整数 $N,x(1 \leq x \leq N \leq 10^9)$

输出描述:

对于每个案例，输出一个正整数，即 $\left \lfloor \frac{N}{x} \right \rfloor$ 在集合 $S$ 中降序排第几大。

示例1

输入

1
2
3
2
25 9
1000000000 1000000000

输出

1
2
8
63244

数论+打表~
我一开始直接上分块，但是 $O(T\sqrt n)$ 的复杂度显然不行，所以只能打表找规律~
打表很容易发现 $k\leq \sqrt n$ 时答案就是 $k$，而另一半正好对称，我们可以假设 $\sqrt n$ 为一条对称轴，那么对于所有大于 $\sqrt n$ 的数 $num$，都有 $num+\lfloor \frac{n}{num}\rfloor=2\sqrt n$，注意当 $n$ 为完全平方数的时候，对称轴会往左移一个单位，加一个 $bool$ 变量判断即可，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>

using namespace std;
int t, n, k;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        int s = sqrt(n);
        printf("%d\n", k <= s ? k : 2 * s - n / k + (s != n / s));
    }
    return 0;
}

发表于 分类于 Valine：

题目链接

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例 1：

1
2
3
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例 2：

1
2
输入: s1= "ab" s2 = "eidboaoo"
输出: False

这题暴力的复杂度达到了阶乘级别，显示不可取，首先我们考虑如果有两个等长的字母字符串，如何判断其中一个是另一个的排列~
其实换种思路就简单了，我们可以统计每个字母出现的次数，然后一一比较每个字母的次数是否一样即可，假设字符串长为 $n$，则暴力的复杂度为 $O(n!)$，优化后复杂度变为 $O(26*n)$~
那如果两个字符串长度不相等(一个为 $m$，一个为 $n$)呢，很简单，我们开设一个大小为 $m$ 的滑窗即可，每次右移只需要将左端点弹出，右端点压入即可，AC代码如下：

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
class Solution {
private:
    int cnt1[30] = {0}, cnt2[30] = {0};
public:
    bool check() {
        int flag = 1;
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] != cnt2[i]) flag = 0;
        }
        return flag;
    }

    bool checkInclusion(string s1, string s2) {
        if (s1.size() > s2.size()) return 0;
        int n = s1.size(), m = s2.size();
        for (int i = 0; i < n; i++) cnt1[s1[i] - 'a']++, cnt2[s2[i] - 'a']++;
        if (check()) return 1;
        for (int i = n; i < m; i++) {
            cnt2[s2[i - n] - 'a']--;
            cnt2[s2[i] - 'a']++;
            if (check()) return 1;
        }
        return 0;
    }
};

发表于 分类于 Valine：

2021牛客寒假算法基础集训营5 B.比武招亲（上）

题目链接

题目描述

众所周知，天姐姐只喜欢天下最聪明的人，为了找到这样的人，她决定比武招亲！

只见天姐姐在榜上留下了这样一道问题，谁做出来了就可以俘获她的芳心！

爱慕天姐姐已久的泽鸽鸽问询赶来，只见榜上写着：

给定 $n,m$，定义一种序列，构造方法如下：

  1. 在 $[1,n]$ 中任意选择 $m$ 次，得到了 $m$ 个整数（显然数字可能相同）;

  2. 将选出的 $m$ 个数字排序之后得到一个序列 ${ a{1},a{2},…,a_{m} }$。

定义一个序列的贡献为 $max{ a{1},a{2},…,a{m} }-min{ a{1},a{2},…,a{m}}$，求所有本质不同的序列的贡献和。

为了防止结果过大，将答案为 $998244353$ 取模后输出。

（对于两个序列长度为 $m$ 的序列 A、B，若 ${\exists}i∈[1,m]$，$A_i\neq B_i$，则序列 A、B 本质不同）

泽鸽鸽心有余而力不足，而你作为他最好的基友决定帮助泽鸽鸽俘获美人心！

现在，这个重任就交给你啦！

输入描述:

一行输入两个正整数 $n$，$m$

输出描述:

一行一个整数，为答案对 $998244353$ 取模后的结果。

输入

1
3 2

输出

1
4

数论~
这种题目最简单的方法就是打表找规律，除非你是数论大师😂
很容易发现出现的差值就是 $[0,n-1]$ 一共 $n$ 种情况，关键点就在于这些插值出现了多少次，当 $m=2$ 时，我们很容易找到如下规律：

1
2
3
4
5
0:n
1:n-1
2:n-2
......
n-1:1

而当 $m>2$ 时，出现的次数就是乘上一个 $C^{m-2}_{i+1+m-3},i\in[0,n-1]$，那么我们只需要预处理 $1e6$ 内的组合数，就可以在 $O(n)$ 的时间内算出答案了，AC代码如下：

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 1e6 + 5;
ll n, m, F[N + 1], I[N + 1];

ll power(ll a, ll b) { return b ? power(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }

void init() {
    F[0] = 1;
    for (ll i = 1; i <= N; i++) F[i] = F[i - 1] * i % mod;
    I[N] = power(F[N], mod - 2);
    for (ll i = N; i--;) {
        I[i] = I[i + 1] * (i + 1) % mod;
    }
}

ll C(ll n, ll k) {
    return F[n] * I[n - k] % mod * I[k] % mod;
}

int main() {
    init();
    cin >> n >> m;
    ll ans = 0;
    for (ll i = 0; i <= n - 1; i++) {
        ans = (ans + (n - i) % mod * C(i + 1 + m - 3, m - 2) % mod * i) % mod;
    }
    cout << ans << endl;
    return 0;
}

发表于 分类于 Valine：

2021牛客寒假算法基础集训营5 D.石子游戏

题目链接

题目描述

叶妹妹很喜欢玩石头，于是这天泽鸽鸽给她出了一道石子游戏，规则是这样的：有 $n$ 堆石子排成一行，其中第 $i$ 堆石子有 $a_i$ 个，叶妹妹可以选择做无数次这种操作：每次操作把连续相邻的 $k$ 个石子堆中的每堆石子数目加一，请问叶妹妹能否让每堆石子的数目都相同呢？叶妹妹觉得这题太简单了，于是丢给了聪明的你，快来解决这个问题吧！

输入描述:

第一行输入样例组数 $T$

对于每组样例来说，第一行输入两个数 $n$ 和 $k$

第二行输入 $n$ 个数，其中第 $i$ 个数为 $a_i$

输出描述:

输出总共 $T$ 行，对于每组样例来说，如果能使每堆石子的数目都相同则输出一个整数 $x$，$x$ 表示达到相同时的最少的操作数；否则输出 $-1$

示例1

输入

1
2
3
1
4 3
1 1 1 2

输出

1
1

思维+差分~
这题我一开始想的是模拟，后来发现复杂度上天，忽然发现，可以用两遍差分来判断，我们先从左往右差分，在遍历的过程中记录最大值，并不断将小于最大值的数修正，不难发现，一遍差分之后该数列下标 $[1,n-k+1]$ 的部分（因为限定连续 $k$ 个数，所以右端点只能到 $n-k+1$）会变成非严格上升子序列，此时只需要再从右往左再进行一遍差分，判断数组是否修正成一样的数即可~
想法很简单，但是一边差分一边修正这个过程真的很难写，一不小心就挂了，我具体讲一下用到的两个变量：

  • diff 数组，记录所有位置的操作次数
  • sum，记录差分的前后缀和

这些变量的位置尤为重要，首先我们要先更新 sum，其次更新 a[i]，最后再更新 diff 数组，详见代码：

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int t, n, k;
ll a[N], diff[N], mx, sum, ans;

void init() {
    mx = sum = 0;
    memset(diff, 0, sizeof(diff));
}

int main() {
    scanf("%d", &t);
    while (t--) {
        ans = 0;
        scanf("%d%d", &n, &k);
        for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]);
        init();
        for (ll i = 1; i <= n; i++) {
            sum += diff[i];
            a[i] += sum;
            if (i <= n - k + 1 && mx > a[i]) {
                ans += mx - a[i], diff[i] += mx - a[i], diff[i + k] -= mx - a[i], sum += mx - a[i], a[i] = mx;
            }
            mx = max(mx, a[i]);
        }
        init();
        for (ll i = n; i >= 1; i--) {
            sum += diff[i];
            a[i] += sum;
            if (i >= k && mx > a[i]) {
                ans += mx - a[i], diff[i] += mx - a[i], diff[i - k] -= mx - a[i], sum += mx - a[i], a[i] = mx;
            }
            mx = max(mx, a[i]);
        }
        int flag = 0;
        for (ll i = 1; i <= n - 1; i++) {
            if (a[i] != a[i + 1]) {
                flag = 1;
                break;
            }
        }
        if (flag) printf("-1\n");
        else printf("%lld\n", ans);
    }
    return 0;
}

发表于 分类于 Valine：

AtCoder Beginner Contest 192 E.Train

题目链接

Problem Statement

In the Republic of AtCoder, there are N cities numbered 1 through N and M
railroads numbered 1 through M.

Railroad i connects City $A_i$ and City $B_i$ bidirectionally. At time 0, $K_i$, and all subsequent multiples of $K_i$, a train departs from each of these cities and head to the other city. The time each of these trains takes to reach the destination is $T_i$.

You are now at City X. Find the earliest time you can reach City Y when you start the journey by taking a train that departs City X not earlier than time 0. If City Y is unreachable, report that fact.

The time it takes to transfer is ignorable. That is, at every city, you can transfer to a train that departs at the exact time your train arrives at that city.

Sample Input 1

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

Sample Output 1

1
7

Sample Input 2

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

Sample Output 2

1
5

Sample Input 3

1
3 0 3 1

Sample Output 3

1
-1

Sample Input 4

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

Sample Output 4

1
26

最短路~
我们可以把时间看成距离，对任意两点 $A_i$ 和 $B_i$，已知其中一点的时间 $t$，那么到达另一点的时间就是 $\lceil\frac{t}{K_i}\rceil*K_i+T_i$，知道这一点后就可以套最短路计算了，有两种方法：

  • dijkstra算法+堆优化
  • BFS+堆优化

两者复杂度差不多，我采取的是后者，AC代码如下：

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N = 1e5 + 5;
vector<tuple<int, ll, ll>> G[N];
int n, m, u, v, x, y, vis[N];
ll t, k, d[N];

void bfs() {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
    fill(d, d + N, 1e18);
    d[x] = 0;
    q.push({0, x});
    while (!q.empty()) {
        auto[t, a] = q.top();
        q.pop();
        if (a == y) break;
        if (t > d[a]) continue;
        for (auto[b, t, k]:G[a]) {
            t = (d[a] + k - 1) / k * k + t;
            if (d[b] > t) {
                d[b] = t;
                q.emplace(d[b], b);
            }
        }
    }
}

int main() {
    cin >> n >> m >> x >> y;
    while (m--) {
        cin >> u >> v >> t >> k;
        G[u].emplace_back(v, t, k);
        G[v].emplace_back(u, t, k);
    }
    bfs();
    if (d[y] == 1e18) cout << -1;
    else cout << d[y];
    return 0;
}