水厂日志

发表于 更新于 分类于 ， ，

题目

和UESTC-2430完全一致，数据量增大。

题解

我觉得没写啥的必要了，和UESTC-2430完全一致，加上二进制优化就行。

代码

AC代码

这是debug之后了的，注意到打开了OPTIMIZE宏。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0
#define OPTIMIZE 1

using namespace std;

class Thing {
public:
    long long weight, value, number;
};

class Special {
public:
    long long x, y, z;

    long long getValue(long long weight) {
        if (weight == 0) {
            return max(0ll, z);
        }
        return x * weight * weight + y * weight + z;
    }
};

Thing things[10007 * 15];
int cnt = 0;
Special specials[6];

long long dp0[10007];
long long dp[10007];

const int pow2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384};

# if OPTIMIZE

// 二进制优化
int optimize() {
    int st = cnt;
    int d = 0;
    while (things[cnt].number > pow2[d]) {
        things[cnt].number -= pow2[d];
        // things[d + 1].number = 1;
        things[cnt + d + 1].weight = things[cnt].weight * pow2[d];
        things[cnt + d + 1].value = things[cnt].value * pow2[d];
        d += 1;
    }
    things[cnt].weight = things[cnt].weight * things[cnt].number;
    things[cnt].value = things[cnt].value * things[cnt].number;
    // things[cnt].number = 1;
    cnt += d + 1;
    return st;
}

#endif

#if DISPLAY_A
int sp[1007];
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m, c;
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i++) {
        cin >> things[cnt].weight >> things[cnt].value >> things[cnt].number;
        // 多重背包
#if OPTIMIZE
        // 二进制优化
        optimize();
#else
        for (int j = 1; j <= c; j++) {
            // 不拿的情况(k=0)已经包含了
            for (int k = 1; k <= things[cnt].number; k++) {
                int weight = k * things[cnt].weight;
                if (j < weight) {
                    break;
                }
                dp[j] = max(dp[j], dp0[j - weight] + things[cnt].value * k);
            }
        }
        memcpy(dp0, dp, sizeof(long long) * (c + 3));
#endif
    }
    for (int i = 0; i < cnt; i++) {
        for (int j = 1; j <= c; j++) {
            if (j < things[i].weight) {
                continue;
            }
            dp[j] = max(dp0[j], dp0[j - things[i].weight] + things[i].value);
        }
        memcpy(dp0, dp, sizeof(long long) * (c + 3));
    }
    for (int i = 1; i <= m; i++) {
        cin >> specials[i].x >> specials[i].y >> specials[i].z;
        // 计算神奇物品
        for (int j = 0; j <= c; j++) {
            for (int k = 0; k <= j; k++) {
#if DISPLAY_A
                if (dp[j] < dp0[j - k] + specials[i].getValue(k)) {
                    dp[j] = dp0[j - k] + specials[i].getValue(k);
                    sp[i] = k;
                }
#else
                dp[j] = max(dp[j], dp0[j - k] + specials[i].getValue(k));
#endif
            }
        }
        memcpy(dp0, dp, sizeof(long long) * (c + 3));
    }
#if DISPLAY_A
    for (int i = 1; i <= m; i++) {
        cout << sp[i] << " ";
    }
    cout << endl;
#endif
    cout << dp[c] << endl;
    return 0;
}

测试例生成（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def G(n, m, c, max=1e3, filename='/Volumes/RD/in'):
    n = int(n)
    m = int(m)
    c = int(c)
    f = open(filename, 'w')
    f.write("{} {} {}\r\n{}\r\n{}".format(
        n, m, c, "\r\n".join([
            "{} {} {}".format(random.randint(1, max), random.randint(1, max), random.randint(1, max))
            for i in range(n)
        ]),
        "\r\n".join([
            "{} {} {}".format(random.randint(-max, max), random.randint(-max, max), random.randint(-max, max))
            for i in range(m)
        ])
    ))
    f.close()

发表于 更新于 分类于 ， ，

题目

给任意一个字符串，求最少插入多少字符可以得到回文串。

题解

参照leetcode 1312。

求该字符串与它的反序的最长公共子序列（LCS）长度，然后用字符串长度减去这个长度，输出答案完事，时间复杂度为字符串长度的平方。签到题。

代码

因为一发入魂，就没写测试例生成和暴力验证。

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
42
43
44
45
46
47
48
49
50
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

const int MAX = 5e3 + 7;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    string inv = s;
    reverse(inv.begin(), inv.end());
    // LCS
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == inv[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    cout << n - dp[n][n] << endl;
    return 0;
}

发表于 更新于 分类于 ， ，

题目

有$n$种普通物品，第$i$种物品的体积为$V_i$，价值$W_i$，数量$D_i$，有$m$件神奇物品，神奇物品的价值由分配的体积$V_i$决定，计算公式为
$$
W_i=x_iV_i^2+y_iV_i+z_i
$$
给一个体积为$C$的背包，求最大价值。

题解

多重背包+泛化物品。

先说多重背包的部分。

其实背包问题没啥好讲的，考虑0-1背包，$dp[i][j]$表示前$i$个物品在容量为$j$的背包下的最大价值，有状态转移方程
$$
dp[i][j]=\max(dp[i-1][j],dp[i-1][j-V_i]+W_i)
$$
这题数据量比较小，直接朴素做法就行，把多重背包考虑为多个相同重量和价值的物品，就可以转变为0-1背包，时间复杂度$O(nCD)$（讲道理这已经达到1e9了，居然没超时）。

再来说一下泛化物品。

参照背包九讲中关于泛化物品的部分。计算完多重背包的部分之后，我们得到了一个在没有神奇物品情况下，任意容量背包能装的最大价值。背包九讲中对于多个泛化物品的操作是两两合并，这样就只有一个泛化物品了，但是我觉得太麻烦，其实泛化物品就相当于有$C$个一般物品，并且将它们放到一个组（也就是只能拿一个，因为泛化物品只有一个），这样就转变为分组背包，遍历容量然后求最大值就行，同样考虑$dp[i][j]$为前$i$个神奇物品在容量为$j$的背包下的最大价值，转移方程为
$$
dp[i][j]=\max{dp[i-1][j-v]+x_iv^2+y_iv^2+z_i|v\in[1,j]}
$$
注意到$j$是两重循环，所以是这部分复杂度是$O(mC^2)$。

代码

暴力测试的程序代码找不到了，嘤嘤嘤。

AC代码

OPTIMIZE是二进制优化，在写这题的时候没有并没有完成这一部分，朴素暴过去的。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0
#define OPTIMIZE 0

using namespace std;

class Thing {
public:
    int weight, value, number;

};

class Special {
public:
    int x, y, z;

    int getValue(int weight) {
        if (weight == 0) {
            return max(0, z);
        }
        return x * weight * weight + y * weight + z;
    }
};

Thing things[1007 * 15];
int cnt = 0;
Special specials[6];

int dp0[1007];
int dp[1007];

const int pow2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};

# if OPTIMIZE
// 二进制优化
int optimize() {
    int st = cnt;
    int d = 0;
    while (things[cnt].number > pow2[d]) {
        things[cnt].number -= pow2[d];
        things[d + 1].number = 1;
        things[d + 1].weight = things[cnt].weight * pow2[d];
        things[d + 1].value = things[cnt].value * pow2[d];
        d += 1;
    }
    things[cnt].weight = things[cnt].weight * things[cnt].number;
    things[cnt].value = things[cnt].value * things[cnt].number;
    things[cnt].number = 1;
    // 考虑不拿的情况
    cnt += d + 2;
    return st;
}
#endif

#if DISPLAY_A
int sp[1007];
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m, c;
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i++) {
        cin >> things[cnt].weight >> things[cnt].value >> things[cnt].number;
        // 多重背包
#if OPTIMIZE
        // 二进制优化
        auto st = optimize();
        for (int k = st; k < cnt; k++) {
            for (int j = 1; j <= c; j++) {
                if (j < things[k].weight) {
                    continue;
                }
                dp[j] = max(dp[j], dp0[j - things[k].weight] + things[k].value);
            }
            memcpy(dp0, dp, sizeof(int) * c + 3);
        }
#else
        for (int j = 1; j <= c; j++) {
            // 不拿的情况(k=0)已经包含了
            for (int k = 1; k <= things[cnt].number; k++) {
                int weight = k * things[cnt].weight;
                if (j < weight) {
                    break;
                }
                dp[j] = max(dp[j], dp0[j - weight] + things[cnt].value * k);
            }
        }
        memcpy(dp0, dp, sizeof(int) * (c + 3));
#endif
    }
    for (int i = 1; i <= m; i++) {
        cin >> specials[i].x >> specials[i].y >> specials[i].z;
        // 计算神奇物品
        for (int j = 0; j <= c; j++) {
            for (int k = 0; k <= j; k++) {
#if DISPLAY_A
                if (dp[j] < dp0[j - k] + specials[i].getValue(k)) {
                    dp[j] = dp0[j - k] + specials[i].getValue(k);
                    sp[i] = k;
                }
#else
                dp[j] = max(dp[j], dp0[j - k] + specials[i].getValue(k));
#endif
            }
        }
        memcpy(dp0, dp, sizeof(int) * (c + 3));
    }
#if DISPLAY_A
    for (int i = 1; i <= m; i++) {
        cout << sp[i] << " ";
    }
    cout << endl;
#endif
    cout << dp[c] << endl;
    return 0;
}

测试例生成（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def G(n, m, c, max=1e3, filename='/Volumes/RD/in'):
    n = int(n)
    m = int(m)
    c = int(c)
    f = open(filename, 'w')
    f.write("{} {} {}\r\n{}\r\n{}".format(
        n, m, c, "\r\n".join([
            "{} {} {}".format(random.randint(1, max), random.randint(1, max), random.randint(1, max))
            for i in range(n)
        ]),
        "\r\n".join([
            "{} {} {}".format(random.randint(-max, max), random.randint(-max, max), random.randint(-max, max))
            for i in range(m)
        ])
    ))
    f.close()

发表于 更新于 分类于 ， ，

题目

和UESTC-2428基本相同，区别在于只能相邻的两个进行交换，询问最少交换次数。

题解

有一说一，这题我没怎么搞懂，基本上全靠出题人的PPT。

这题比较直白了，直接就是$1\sim 20$的数字。继续使用状态压缩，变量$s$二进制表示状态，$dp[s]$表示状态$s$需要的最少交换次数，$w[i][j]$表示原排列i在j前面的对数，状态转移方程
$$
dp[s]=\min{dp[s-(1<<i)]+\sum_{j\in s &j\ne i}w[i][j]}
$$
显然$dp[0]=0$。

$w$直接暴力就行，题解上给的做法也是暴力。（学姐真是太良心了）

代码

虽然没有一发入魂（某个循环的边界写错了），但是调了几下就过了，所以也没有写测试例生成和暴力验证……

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
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
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

const int MAX = 1e5 + 7;

unsigned int s = 1;

int a[MAX];
int cnt[27];
int w[27][27];

const unsigned int full = (1u << 20u) - 1;
long long dp[full + 7];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] -= 1;
    }
    for (int i = 1; i <= n; i++) {
        cnt[a[i]]++;
        for (int j = 0; j < 20; j++) {
            w[j][a[i]] += cnt[j];
        }
    }
    for (; s <= full; s++) {
        dp[s] = 0x7fffffffffffffffll;
        for (int i = 0; i < 20; i++) {
            if (!(s & (1 << i))) {
                continue;
            }
            long long ans = 0;
            for (int j = 0; j < 20; j++) {
                if (i == j || !(s & (1 << j))) {
                    continue;
                }
                ans += w[i][j];
            }
            dp[s] = min(dp[s], dp[s - (1 << i)] + ans);
        }
    }
    cout << dp[full] << endl;
    return 0;
}

发表于 更新于 分类于 ， ，

题目

给一段长度为$n$的序列，包含$1\sim m$的数字，可以任意交换两个数字的位置，目标是让所有相同的数字相邻，问最多可以有几个数字的位置不被交换。

题解

参照出题人的PPT。

把“已经排列好的数字种类的集合”视为状态，不考虑集合中数字的顺序，他们的总数是固定的，记状态为$s$，已经排列的人数为$f[s]$，这个可以在输入的时候直接求出来。$m$最大只有20，直接位运算来实现集合。$dp[s]$表示状态$s$最多能固定的数字数量。

枚举$s$，在每次枚举的时候枚举数字$i$，考虑

  • $i$不在$s$中，则$dp[s|(1<<i)]=\max{dp[s]+sum[r][i]-sum[l-1][i]|i\in[0,m-1]}$
  • $i$在$s$中，则$dp[s]=\max{dp[s\oplus(1<<i)]+sum[r][i]-sum[l-1][i]|i\in[0,m-1]}$

注意我为了方便位运算将输入序列全部减去1。

最后输出$dp[(1<<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
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
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

const int MAX = 1e5 + 7;

unsigned int s;

int n, m;
int dp[1 << 21];
int f[1 << 21];
int a[MAX + 1];
int sum[MAX + 1][20 + 1];

int getSum(int c) {
    int k = 0;
    int ans = 0;
    for (; c; c >>= 1, k++) {
        ans += c & 1 ? sum[n][k] : 0;
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // 从0开始
        a[i] -= 1;
        for (int j = 0; j < m; j++) {
            sum[i][j] = sum[i - 1][j] + (j == a[i]);
        }
    }
    const int full = (1 << m) - 1;
    for (int i = 0; i <= full; i++) {
        f[i] = getSum(i);
    }
    while (s <= full) {
        for (int i = 0; i < m; i++) {
            int l = f[s] + 1;
            int r = f[s | (1 << i)];
            if (s & (1 << i)) {
                dp[s] = max(dp[s], dp[s - (1 << i)] + sum[r][i] - sum[l - 1][i]);
            } else {
                dp[s | (1 << i)] = max(dp[s | (1 << i)], dp[s] + sum[r][i] - sum[l - 1][i]);
            }
        }
        s++;
    }
    cout << dp[full] << endl;
    return 0;
}

发表于 更新于 分类于 ， ，

题目

给一组长度为$n$序列，相邻的数字可以合并为一个数字，合并后的数字等于合并前的数字+1，问合并后的数字最少是多少个。

题解

参照出题人PPT，是区间DP没错了。

$dp[l][r]$表示区间$[l,r]$在合并过之后有多少个数，$ag[l][r]$表示区间$[l,r]$合并成一个（如果可以）的数。

不好解释，直接看代码吧。。。

1
2
3
4
5
6
7
8
9
for (int mid = l; mid <= r; mid++) {
  if (dp[l][mid] == 1 && dp[mid + 1][r] == 1 &&
      ag[l][mid] == ag[mid + 1][r] && ag[l][mid] != 0) {
    // merge
    dp[l][r] = 1;
    ag[l][r] = ag[l][mid] + 1;
  }
  dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
}

对于区间$[l,r]$，将其分为$[l,mid]$和$[mid+1,r]$，看能否合并，然后最小值。

然后枚举长度和$l$即可，复杂度$O(n^3)$。

代码

因为一发入魂，就没写测试例生成和暴力程序了。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

const int MAX = 500 + 7;

int arr[MAX];
int ag[MAX][MAX];
int dp[MAX][MAX];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = n;
        }
    }
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        dp[i][i] = 1;
        ag[i][i] = arr[i];
    }
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len <= n; l++) {
            int r = l + len;
            for (int mid = l; mid <= r; mid++) {
                if (dp[l][mid] == 1 && dp[mid + 1][r] == 1 &&
                    ag[l][mid] == ag[mid + 1][r] && ag[l][mid] != 0) {
                    // merge
                    dp[l][r] = 1;
                    ag[l][r] = ag[l][mid] + 1;
                }
                dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

发表于 更新于 分类于 ， ，

题目

给一颗$n$节点的树，1节点为根节点，求最少减去多少条边可以得到一颗$p$节点的树。

题解

参照洛谷P1272。

基本上是原题了。

$dp[i][j]$表示以$i$为根节点时获得节点数为$p$的树最少需要的修建次数。状态转移方程
$$
dp[i][j]=\min{dp[i][j-k]+dp[son][k]-1|k\in[1,j]}
$$
$son$是$i$的子节点。

考虑到不一定1为根节点（$dp[1][p]$）才是最优，所以我们可以遍历每一个节点作为根节点的情况。注意到除了根节点之外，其他节点为根节点的话需要断开自己与父节点的边，所以遍历的时候+1即可。

还有一个坑是输入。每行输入的是$u$和$v$表示$u$和$v$之间有一条边，然而并不知道哪个是父节点，所以得专门做一次处理，我懒得搞骚操作直接暴力了，速度还行吧。

代码

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
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

const int MAX = 200 + 7;

set<int> nodes[201];

int dp[201][201];

int dfs(int root) {
    int sum = 1;
    for (auto son:nodes[root]) {
        sum += dfs(son);
        // TODO: optimize
        for (int j = sum; j >= 1; j--) {
            for (int k = 1; k < j; k++) {
                dp[root][j] = min(dp[root][j], dp[root][j - k] + dp[son][k] - 1);
            }
        }
    }
    return sum;
}

int dset[201];

struct Edge {
    int u, v;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, p;
    cin >> n >> p;
    int u, v;
    dset[1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = n;
        }
    }
    // 构建单向边
    map<int, Edge> edge;
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        // 干就完事了
        if (u == 1) {
            nodes[u].insert(v);
            dset[v] = u;
        } else if (v == 1) {
            nodes[v].insert(u);
            dset[u] = v;
        } else if (dset[u]) {
            nodes[u].insert(v);
            dset[v] = 1;
        } else if (dset[v]) {
            nodes[v].insert(u);
            dset[u] = 1;
        } else {
            // 姑且记录一下
            edge[cnt].u = u;
            edge[cnt].v = v;
            cnt += 1;
        }
    }
    set<int> af;
    while (!edge.empty()) {
        for (auto &it:edge) {
            if (dset[it.second.u]) {
                nodes[it.second.u].insert(it.second.v);
                dset[it.second.v] = 1;
                af.insert(it.first);
            } else if (dset[it.second.v]) {
                nodes[it.second.v].insert(it.second.u);
                dset[it.second.u] = 1;
                af.insert(it.first);
            }
        }
        for (auto &it:af) {
            edge.erase(it);
        }
        af.clear();
    }
    // init
    for (int i = 1; i <= n; i++) {
        dp[i][1] = nodes[i].size();
    }
    // search
    dfs(1);
    int ans = dp[1][p];
#if DISPLAY_A
    int idx = 1;
#endif
    for (int i = 2; i <= n; i++) {
#if DISPLAY_A
        if (ans > dp[i][p] + 1) {
            ans = dp[i][p] + 1;
            idx = i;
        }
#else
        ans = min(ans, dp[i][p] + 1);
#endif
    }
#if DISPLAY_A
    cout << ans << " " << idx << endl;
#else
    cout << ans << endl;
#endif
    return 0;
}

测试例生成（Python）

1
2
3
4
5
6
7
8
9
10
def N(n, p, filename='in'):
    n = int(n)
    p = int(p)
    f = open(filename, 'w')
    f.write("{} {}\r\n{}\r\n".format(
        n, p,
        "\r\n".join([
            "{} {}".format(random.randint(1, i - 1), i) for i in range(2, n + 1)
        ])
    ))

发表于 更新于 分类于 ， ，

题目

给定$m$个牛头人和$p$个老哥，老哥向一个方向移动，遇到牛头人时牛头人停止活动，现在给出牛头人出现的时间距离，让所有牛头人加起来的活动时间最短，安排老哥的出发时间。

题解

参照出题人PPT的状态转移方程。

首先简化问题，假设所有牛头人都出现在起始位置，直接用时间减去距离即可，为了方便后面的操作再排序一下，设为$a[]$，$dp[i][j]$表示第$i$个老哥在$a[j]$时刻出发前$j$牛头人的最少活动时间，于是有状态转移方程
$$
dp[i][j]=\min{dp[i-1][k]+\sum_{x=k+1}^{j}(a[j]-a[x])|k\in[1,j]}
$$
考虑用前缀和，令
$$
s[j]=\sum_{x=1}^ja[x]
$$
方程可以变为
$$
dp[i][j]=\min{(dp[i-1][k]+s[k])-k\cdot a[j]+(j\cdot a[j]-s[j])|k\in[1,j]}
$$
考虑$i\in[1,p]$，$j\in[1,m]$，直接DP的话复杂度依然高达$O(pm^2)$，因为式子中有一项同时包含$k$和$j$，所以无法用单调队列优化，我们考虑斜率优化。

设$k_1<k_2$且$k_2$比$k_1$更优，即
$$
(dp[i-1][k_2]+s[k_2])-k_2\cdot a[j]+(j\cdot a[j]-s[j])<
(dp[i-1][k_1]+s[k_1])-k_1\cdot a[j]+(j\cdot a[j]-s[j])
$$

$$
(dp[i-1][k_2]+s[k_2])-k_2\cdot a[j]<
(dp[i-1][k_1]+s[k_1])-k_1\cdot a[j]
$$

$$
\frac{(dp[i-1][k_2]+s[k_2])-(dp[i-1][k_1]+s[k_1])}{k_2-k_1}<a[j]
$$

（虽然我不知道变换出这个式子之后有什么用，总之就放这吧）

其实对于斜率优化，我的理解是对于不同的自变量（这里是$k$），取到的值不同，而当$k_1<k_2$且从$k_1$到$k_2$的斜率小于这里的$a[j]$（注意$a[j]$单调不减）时，则后续的状态转移一定不会有$k_1$，因为$k_2$一定比$k_1$更优，同时能取到的点集会有斜率单调不减的特征，也就是一个下凸包，同时那个最优的点就是凸包上第一个斜率大于等于$a[j]$的点，由于$a[j]$单调不减，所以在取了这点之后可以直接将这个点以前的点全部移除。

之后就是代码实现了，我用一个数组来维护下凸包，准确说是一个双向队列（两个变量head和tail，但是STL的deque效率不得行，所以是手写的。

代码

AC代码

这题int会溢出，我吐了。

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
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

const int MAX = 1e5 + 7;

long long a[MAX];
long long sum[MAX];

long long dp[100 + 7][MAX];

float grad(const long long *arr, long long x1, long long x2) {
    return ((float) (arr[x2] + sum[x2] - arr[x1] - sum[x1])) / ((float) (x2 - x1));
}

int ndeq[MAX];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int m, p;
    cin >> m >> p;
    int tmp;
    for (int i = 1; i <= m; i++) {
        cin >> tmp >> a[i];
        a[i] -= tmp;
    }
    sort(a + 1, a + m + 1);
    // 前缀和
    for (int i = 1; i <= m; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    for (int j = 1; j <= m; j++) {
        dp[1][j] = a[j] * j - sum[j];
    }
    for (int i = 2; i <= p; i++) {
        // 斜率优化
        int head = 0, tail = 0;
        // 必然吧
        dp[i][1] = 0;
        ndeq[tail] = 0;
        tail++;
        for (int j = 2; j <= m; j++) {
            // 准备插入j，维护斜率递增，左侧斜率小于右侧斜率
            while (tail - head >= 2 &&
                   grad(dp[i - 1], ndeq[tail - 2], ndeq[tail - 1]) >=
                   grad(dp[i - 1], ndeq[tail - 1], j)) {
                // 出栈
                tail--;
            }
            // 这一点应该是一定会加入的
            ndeq[tail] = j;
            tail++;
            // 找不到情况队处理
            dp[i][j] = dp[i - 1][j];
            // TODO: 二分查找
            // 大概直接查找就完事了
            for (int k = head; k < tail - 1; k++) {
                // 斜率递增，故左斜率<=a[j]&&右斜率>=a[j]时最优
                if (dp[i - 1][ndeq[k + 1]] + sum[ndeq[k + 1]] - dp[i - 1][ndeq[k]] - sum[ndeq[k]] >=
                    a[j] * (ndeq[k + 1] - ndeq[k]) &&
                    dp[i - 1][ndeq[k]] + a[j] * (j - ndeq[k]) - (sum[j] - sum[ndeq[k]]) <= dp[i][j]) {
                    // 是这点了
                    dp[i][j] = dp[i - 1][ndeq[k]] + a[j] * (j - ndeq[k]) - (sum[j] - sum[ndeq[k]]);
                    // 修改队首
                    head = k;
                    break;
                }
            }
            head = min(head, tail - 1);
        }
    }
    cout << dp[p][m] << endl;
    return 0;
}

测试例生成（Python）

为了方便直接将位置都设为0了。

1
2
3
4
5
6
7
8
9
10
11
def e(m, p, max=1e9, filename='in'):
    m = int(m)
    p = int(p)
    fi = open(filename, 'w')
    fi.write("{} {}\r\n{}\r\n".format(
        m, p, "\r\n".join([
            "0 {}".format(random.randint(0, max))
            for i in range(m)
        ])
    ))
    fi.close()

暴力验证

只是没有斜率优化，其他一样。

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
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

const int MAX = 1e5 + 7;

long long a[MAX];
long long sum[MAX];

long long dp[100 + 7][MAX];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int m, p;
    cin >> m >> p;
    int tmp;
    for (int i = 1; i <= m; i++) {
        cin >> tmp >> a[i];
        a[i] -= tmp;
    }
    sort(a + 1, a + m + 1);
    // 前缀和
    for (int i = 1; i <= m; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    for (int j = 1; j <= m; j++) {
        dp[1][j] = a[j] * j - sum[j];
    }
    for (int i = 2; i <= p; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][1] + a[j] * (j - 1) - (sum[j] - sum[1]);
            for (int k = 1; k <= j; k++) {
                dp[i][j] = min(dp[i][j], dp[i - 1][k] + a[j] * (j - k) - (sum[j] - sum[k]));
            }
        }
    }
    cout << dp[p][m] << endl;
    return 0;
}

发表于 更新于 分类于 ， ，

题目

这次在每一轮游戏中，綾波需要使用鱼雷把一个区间[l,r]内的所有点的数值变为c，每改变一个点的数值需要消耗一枚特制鱼雷。

尽管如此，在知道了墙面上各点初始数值和每轮的任务后，綾波还是希望指挥官能帮她计算她各轮需要的鱼雷数量的说。呐，快来帮帮綾波吧。

题解

参照出题人题解PPT。

出题人告诉我们这题可以分块也可以用珂朵莉树。

分块实在太恶心了，所以我就试了下所谓的珂朵莉树，没有去看OI-WiKi，凭着感觉写的，没有用std::set而是用的std::map，当然他们内部也差不多，只是std::map可以很容易地带上一个载荷。

首先是初始化，把所有连续的部分都装进去。

对于每次查询，用二分查找到对对应的块，整块的就直接加到ans，其他的部分单独处理。

因为第一次写这种结构，还出了不少bug。

第一次查询和修改的复杂度都是$O(n)$，之后每次查询和修改的理想复杂度都是$O(\log_2n)$，因为总共$m$次查询，所以总的复杂度大概是$O(m\log_2n)$。

代码

有个宏定义DISPLAY_A用于在每次查询后打印完整的数组。

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
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

class Node {
public:
    int left, right;
    int val;

    Node(int left, int val, int right) : left(left), val(val), right(right) {}


    Node(int left, int val) : left(left), val(val), right(left) {}

    Node(int left) : left(left), val(0), right(left) {}

    Node() : left(0), val(0), right(1) {}

    bool operator<(Node node) const {
        return this->left < node.left;
    }
};

int arr[100000 + 7];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m;
    int l, r, c;
    map<int, Node> tree;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++) {
        int right = i;
        int i2 = i + 1;
        for (; i2 <= n; i2++) {
            if (arr[i2] != arr[i2 - 1]) {
                break;
            } else {
                right += 1;
            }
        }
        tree[i] = Node(i, arr[i], right);
        i = i2 - 1;
    }
    cin >> m;
    while (m--) {
        int ans = 0;
        cin >> l >> r >> c;
        auto it = tree.lower_bound(l);
        auto st = it;
        if (it->first != l) {
            st--;
            // 前面的区域
            if (st->second.val != c) {
                if (st->second.right > r) {
                    ans += r - l + 1;
                    tree[r + 1] = Node(r + 1, st->second.val, st->second.right);
                } else {
                    ans += st->second.right - l + 1;
                }
                st->second.right = l - 1;
            } else {
                l = st->first;
                if (r < st->second.right) {
                    r = st->second.right;
                }
            }
        }
        // 覆盖的部分
        for (; it->second.right <= r && it != tree.end();) {
            auto &node = it->second;
            if (node.val != c) {
                ans += node.right - node.left + 1;
            }
            it++;
            tree.erase(prev(it));
        }
        // 后面的区域
        auto et = it;
        if (et->first <= r && et != tree.end()) {
            if (et->second.val != c) {
                ans += r - et->first + 1;
                if (et->second.right - et->first > 0) {
                    // 长度大于1的时候才行，不然会错位
                    tree[r + 1] = Node(r + 1, et->second.val, et->second.right);
                }
                tree.erase(et);
            } else {
                r = et->second.right;
                tree.erase(et);
            }
        }
        tree[l] = Node(l, c, r);
#if DISPLAY_A
        for (auto itt:tree) {
            for (int i = itt.second.left; i <= itt.second.right; i++) {
                cout << itt.second.val << " ";
            }
        }
#endif
        cout << ans << endl;
    }
    return 0;
}

测试例生成（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def z(n, m, max=2 ** 31 - 1, filename='in'):
    n = int(n)
    m = int(m)
    fi = open(filename, 'w')
    fi.write("{}\r\n{}\r\n{}\r\n{}\r\n".format(
        n, " ".join([str(random.randint(-max, max)) for i in range(n)]),
        m,
        "\r\n".join([
            "{} {} {}".format(
                random.randint(1, n // 2),
                random.randint(n // 2, n),
                random.randint(-max, max),
            ) for i in range(m)
        ])
    ))
    fi.close()

暴力验证

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 1

using namespace std;
int arr[100000 + 7];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m;
    int l, r, c;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    cin >> m;
    while (m--) {
        cin >> l >> r >> c;
        int ans = 0;
        for (int i = l; i <= r; i++) {
            if (c != arr[i]) {
                ans += 1;
                arr[i] = c;
            }
        }
#if DISPLAY_A
        for (int i = 1; i <= n; i++) {
            cout << arr[i] << " ";
        }
#endif
        cout << ans << endl;
    }
    return 0;
}

发表于 更新于 分类于 ， ，

题目

在与拉菲、标枪等人相遇几次之后，綾波心里有些烦恼。一天，她独自在港区玩一个既有趣又能提升自己的能力的游戏，在这个游戏中，她面对一面长墙，墙上排列着 n个点（编号 1∼n），每个点都带有一个数值（可能为负数），同时，还有一个一定要记住的数值 k。

在每一轮游戏中，綾波需要使用鱼雷击中在一个区间（[l,r]）内的所有对 k取模（取非负最小剩余）后数值与 c对 k取模（同样取非负最小剩余）相等的点，每次击中每个点需要一枚鱼雷。

作为港区鱼雷能力最强的驱逐舰，綾波当然不可能因为没有命中而浪费鱼雷。

每轮游戏结束后，该轮目标区间内的所有点的值将增加 d（d 可能为负数）。

题解

参照出题人的PPT题解。

先做分块，把数组分成$\sqrt{n}$块，最后一块适当加长。

因为取模对加减符合交换律结合律分配律，所以为了不溢出，每次都取模就好了。

因为取模之后最大为$k$，直接用桶就行，对每个区块放一个长度$k$对桶，记录取模后各个数字的数量。

对于每次查询，如果$l$和$r$在一个区块内就直接暴力，否则对整块的部分直接加上，剩下的暴力。

修改的时候区块可以用一个偏移量来记录，暴力的部分直接加上就行。

每次查询和修改的时间复杂度都是$O(\sqrt n)$，共有$m$次查询，所以总的时间复杂度是$O(m\log_2n)$。

代码

放了个DISPLAY_A宏定义用来在调试的时候输出数组。

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
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;
const long long MAX = 1e5 + 7;
int k = 1;
int blockSize, numBlock;

int mod(int x) {
    int ans = x < 0 ? x % k + k : x % k;
    return ans >= k ? ans % k : ans;
}

int getBlock(int x) {
    int ans = (x - 1) / blockSize;
    if (ans == numBlock) {
        return ans - 1;
    }
    return ans;
}

struct Block {
    int left, right;
    int offset;
    int buck[MAX];
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    cin >> n >> k;
    int a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = mod(a[i]);
    }
    // 分块
    numBlock = sqrt(n);
    blockSize = n / numBlock;
    vector<Block> blocks(316);
    blocks[0].left = 1;
    blocks[0].right = blockSize;
    for (int i = 1; i < numBlock; i++) {
        blocks[i].left = blocks[i - 1].right + 1;
        if (i == numBlock - 1) {
            blocks[i].right = n;
        } else {
            blocks[i].right = blocks[i].left + blockSize - 1;
        }
    }
    // 预处理
    for (int i = 0; i < numBlock; i++) {
        for (int i2 = blocks[i].left; i2 <= blocks[i].right; i2++) {
            blocks[i].buck[a[i2]] += 1;
        }
    }
    // 查询
    int m, l, r, c, d;
    cin >> m;
    while (m--) {
        cin >> l >> r >> c >> d;
        int ans = 0;
        // 分块起点
        // s为l所在区块
        int s = getBlock(l);
        // 分块终点
        // e为r所在区块
        int e = getBlock(r);
        if (s == e) {
            // 在同一个区块，直接遍历吧
            int t = mod(mod(c) - blocks[s].offset);
            for (int i = l; i <= r; i++) {
                if (a[i] == t) {
                    ans += 1;
                }
                blocks[s].buck[a[i]] -= 1;
                a[i] = mod(a[i] + mod(d));
                blocks[s].buck[a[i]] += 1;
            }
#if DISPLAY_A
            for (int i = 1; i <= n; i++) {
                cout << mod(a[i] + blocks[getBlock(i)].offset) << " ";
            }
#endif
            cout << ans << endl;
            continue;
        }
        int t = 0;
        if (l != blocks[s].left) {
            // c % k == (a[i] + offset) % k
            t = mod(mod(c) - blocks[s].offset);
            for (int i = l; i <= blocks[s].right; i++) {
                // a[i] + offset == t
                if (a[i] == t) {
                    ans += 1;
                }
                blocks[s].buck[a[i]] -= 1;
                a[i] = mod(a[i] + mod(d));
                blocks[s].buck[a[i]] += 1;
            }
        } else {
            s -= 1;
        }
        if (r != blocks[e].right) {
            t = mod(mod(c) - blocks[e].offset);
            for (int i = blocks[e].left; i <= r; i++) {
                if (a[i] == t) {
                    ans += 1;
                }
                blocks[e].buck[a[i]] -= 1;
                a[i] = mod(a[i] + mod(d));
                blocks[e].buck[a[i]] += 1;
            }
        } else {
            e += 1;
        }
        // 分块查询
        for (int i = s + 1; i < e; i++) {
            ans += blocks[i].buck[mod(mod(c) - blocks[i].offset)];
            blocks[i].offset = mod(blocks[i].offset + mod(d));
        }
#if DISPLAY_A
        for (int i = 1; i <= n; i++) {
            cout << mod(a[i] + blocks[getBlock(i)].offset) << " ";
        }
#endif
        cout << ans << endl;
    }
    return 0;
}

测试例生成（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/bin/env python
import random


def h(n, m, k=random.randint(1, 1e5), max=2 ** 31 - 1, filename='in'):
    n = int(n)
    m = int(m)
    k = int(k)
    fi = open(filename, 'w')
    fi.write("{} {}\r\n{}\r\n{}\r\n{}\r\n".format(
        n, k, " ".join([str(random.randint(-max, max)) for i in range(n)]),
        m,
        "\r\n".join([
            "{} {} {} {}".format(
                random.randint(1, n // 2),
                random.randint(n // 2, n),
                random.randint(-max, max),
                random.randint(-max, max)
            ) for i in range(m)
        ])
    ))
    fi.close()

暴力验证

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
// @author: hzy
#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

int k;

int mod(int x) {
    int ans = x < 0 ? x % k + k : x % k;
    return ans >= k ? ans % k : ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m;
    cin >> n >> k;
    int a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = mod(a[i]);
    }
    cin >> m;
    int l, r, c, d;
    while (m--) {
        cin >> l >> r >> c >> d;
        c = mod(c);
        int ans = 0;
        for (int i = l; i <= r; i++) {
            if (a[i] == c) {
                ans += 1;
            }
            a[i] = mod(a[i] + mod(d));
        }
#if DISPLAY_A
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
#endif
        cout << ans << endl;
    }
    return 0;
}