第 14 届 Python A 组（省赛）
T1 特殊日期 (5'/5')¶
题意：统计从 2000-1-1 到 2000000-1-1 有多少个日期满足年份是月份的倍数同时也是日的倍数。
思路：由于 Python 的 datetime.datetime 中年份范围为 \([1,9999]\)，因此没法用，老老实实枚举吧。注意最后一年只有一天，不要多枚举了。
最终答案为：\(35813063\)
Python
ans = 0
def get_days(y: int, m: int) -> int:
if m == 2:
return 28 + (y % 400 == 0 or (y % 4 == 0 and y % 100 != 0))
return 31 - (m in (4, 6, 9, 11))
for y in range(2000, 2000000):
for m in range(1, 13):
days = get_days(y, m)
for d in range(1, days + 1):
if y % m == 0 and y % d == 0:
ans += 1
print(ans + 1)
C++
#include <iostream>
using namespace std;
int get_days(int y, int m) {
if (m == 2) {
return 28 + (y % 400 == 0 or (y % 4 == 0 && y % 100 != 0));
}
return 31 - (m == 4 || m == 6 || m == 9 || m == 11);
}
int main() {
int ans = 0;
for (int y = 2000; y < 2000000; y++) {
for (int m = 1; m <= 12; m++) {
int days = get_days(y, m);
for (int d = 1; d <= days; d++) {
if (y % m == 0 and y % d == 0) {
ans++;
}
}
}
}
cout << ans + 1 << "\n";
return 0;
}
T2 分糖果 (5'/5')¶
题意：给定 \(9\) 个 \(A\) 类糖果，\(16\) 个 \(B\) 类糖果，现在要分给 \(7\) 个小朋友。问满足每个小朋友分得至少 \(2\) 个糖果至多 \(5\) 个糖果的分配方案数（同样的数量但糖果种类数不一样算不同的方案）。
思路：可以糖果选人，也可以人选糖果，考虑到糖果种类不止一种，我们采用「人选糖果」的策略。
- 记忆化搜索。我们定义 \(f_{i,a,b}\) 表示还剩 \(a\) 个 \(A\) 类糖果 \(b\) 个 \(B\) 类糖果的情况下给第 \(i\) 个人分配的方案数。考虑转移，根据每个人可能分到的糖果数，我们可以很容易的枚举出一个人所有可能的被分配情况，基于此，\(f_{i,a,b}\) 就可以通过 \(f_{i-1,a-x,b-y}\) 转移过来，其中 \(x\) 和 \(y\) 分别表示第 \(i\) 个人分到的 \(A\) 类糖果和 \(B\) 类糖果的数量。搜索终点就是 \(f_{0,\cdot,\cdot}\)；
- 递推。上述记忆化搜索的过程可以很容易转换为递推；
- 滚动数组优化。由于 \(f_{i,\cdot,\cdot}\) 只取决于 \(f_{i-1,\cdot,\cdot}\)，可以采用滚动数组优化空间复杂度。
假定小朋友数为 \(N\)，\(A\) 类糖果总数为 \(A\)，\(B\) 类糖果总数为 \(B\)，那么时间复杂度就是 \(O(NAB)\)。如果出成大题，基本就是最优解了。
最终答案为：\(5067671\)
Python
from functools import cache
@cache
def dfs(i: int, a: int, b: int) -> int:
# dfs(i, a, b) 表示给第 i 个人分配时还剩 a 个 A 类糖果和 b 个 B 类糖果
if i == 0:
return a == 0 and b == 0
ans = 0
for x in range(a + 1):
for y in range(b + 1):
if 2 <= x + y <= 5:
ans += dfs(i - 1, a - x, b - y)
return ans
print(dfs(7, 9, 16))
C++
#include <iostream>
using namespace std;
const int N = 7, A = 9, B = 16;
int f[N + 1][A + 1][B + 1];
bool vis[N + 1][A + 1][B + 1];
int dfs(int i, int a, int b) {
if (i == 0) {
return !a && !b;
}
if (vis[i][a][b]) {
return f[i][a][b];
}
vis[i][a][b] = true;
for (int x = 0; x <= a; x++) {
for (int y = 0; y <= b; y++) {
if (x + y >= 2 && x + y <= 5) {
f[i][a][b] += dfs(i - 1, a - x, b - y);
}
}
}
return f[i][a][b];
}
int main() {
cout << dfs(7, 9, 16) << "\n";
return 0;
}
Python
N, A, B = 7, 9, 16
f = [[[0] * (B + 1) for _ in range(A + 1)] for _ in range(N + 1)]
f[0][0][0] = 1
for i in range(1, N + 1):
for a in range(A + 1):
for b in range(B + 1):
# 枚举当前第 i 个小朋友还剩 a 个 A 类糖果
# 和 b 个 B 类糖果的情况下，可能分到的糖果数
for x in range(a + 1):
for y in range(b + 1):
if 2 <= x + y <= 5:
f[i][a][b] += f[i - 1][a - x][b - y]
print(f[N][A][B])
C++
#include <iostream>
using namespace std;
const int N = 7, A = 9, B = 16;
int f[N + 1][A + 1][B + 1];
int main() {
f[0][0][0] = 1;
for (int i = 1; i <= 7; i++) {
for (int a = 0; a <= A; a++) {
for (int b = 0; b <= B; b++) {
for (int x = 0; x <= a; x++) {
for (int y = 0; y <= b; y++) {
if (x + y >= 2 && x + y <= 5) {
f[i][a][b] += f[i - 1][a - x][b - y];
}
}
}
}
}
}
cout << f[N][A][B] << "\n";
return 0;
}
Python
N, A, B = 7, 9, 16
f = [[0] * (B + 1) for _ in range(A + 1)]
f[0][0] = 1
for i in range(1, N + 1):
d = [[0] * (B + 1) for _ in range(A + 1)]
for a in range(A + 1):
for b in range(B + 1):
for x in range(a + 1):
for y in range(b + 1):
if 2 <= x + y <= 5:
d[a][b] += f[a - x][b - y]
f = d
print(f[A][B])
C++
#include <iostream>
#include <vector>
using namespace std;
const int N = 7, A = 9, B = 16;
vector<vector<int>> f(A + 1, vector<int>(B + 1, 0));
int main() {
f[0][0] = 1;
for (int i = 1; i <= 7; i++) {
vector<vector<int>> d(A + 1, vector<int>(B + 1, 0));
for (int a = 0; a <= A; a++) {
for (int b = 0; b <= B; b++) {
for (int x = 0; x <= a; x++) {
for (int y = 0; y <= b; y++) {
if (x + y >= 2 && x + y <= 5) {
d[a][b] += f[a - x][b - y];
}
}
}
}
}
f = d;
}
cout << f[A][B] << "\n";
return 0;
}
T3 三国游戏 (10'/10')¶
题意：给定三个长度为 \(n\) 的数组 \(a,b,c\)。现在有三个累计值 \(x,y,z\)（初始均为 \(0\)）分别对应到数组 \(a,b,c\)。现在可以选择索引在 \([0,n-1]\) 中的任意个索引，使得初始值 \(x,y,z\) 加上对应数组索引所在的元素值。问使得三个累计值中的任意一个大于另外两个之和的情况下，最多可以选择多少个索引。返回最多可选择的索引数，如果不存在合法情况输出 \(-1\)。
思路：很显然的一个贪心。对于任意一个数组（假设为 \(a\)），统计所有的 \(a_i-(b_i+c_i)\) 的值，然后降序枚举即可。
时间复杂度：\(O(n\log n)\)
Python
n = int(input())
def f(a, b, c):
d = [0] * n
for i in range(n):
d[i] = a[i] - (b[i] + c[i])
d.sort(reverse=True)
s, cnt = 0, 0
for num in d:
if s + num > 0:
s += num
cnt += 1
return cnt if cnt else -1
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))
c = list(map(int, input().strip().split()))
print(max(f(a, b, c), f(b, a, c), f(c, a, b)))
C++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int f(vector<int>& a, vector<int>& b, vector<int>& c) {
vector<int> d;
for (int i = 0; i < a.size(); i++) {
d.push_back(a[i] - (b[i] + c[i]));
}
sort(d.rbegin(), d.rend());
int cnt = 0;
ll s = 0;
for (int num: d) {
if (s + num > 0) {
s += num;
cnt++;
}
}
return cnt ? cnt : -1;
}
int main() {
int n;
cin >> n;
vector<int> a(n), b(n), c(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
for (int i = 0; i < n; i++) {
cin >> c[i];
}
cout << max({f(a, b, c), f(b, a, c), f(c, a, b)}) << "\n";
return 0;
}
T4 平均 (10'/10')¶
题意：给定 \(n\) 个 \([0,9]\) 范围内的整数（\(n\) 是 \(10\) 的倍数）和修改每一个数的代价。现在为了让每一个数的数量都相等，即都为 \(n/10\) 个，问最小修改代价是多少。
思路：仍然是一个贪心，我们围绕「修改代价」这个变量进行贪心即可。具体地，为了让修改代价最小，我们每次修改时一定选择当前局面下「修改代价最小」且「对应数字数量超过 \(n/10\) 的数字」进行修改，至于修改成什么数字，无需考虑。
时间复杂度：\(O(n\log n)\)
C++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<pair<int, int>> a(n);
vector<int> d(10);
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
d[a[i].first]++;
}
sort(a.begin(), a.end(), [&](pair<int, int>& x, pair<int, int>& y){
return x.second < y.second;
});
ll ans = 0;
for (auto& [num, cost]: a) {
if (d[num] > n / 10) {
d[num]--;
ans += cost;
}
}
cout << ans << "\n";
return 0;
}
T5 翻转 (15'/15')¶
题意：给定两个等长字符串 \(t,s\ (1\le |t|,|s|\le10^6)\)，现在需要通过两种操作将 s 转换为 t，返回最小操作次数，如果无法转换返回 -1。两种操作如下：
- 选择 \(s\) 中的 \(010\) 子串并将其转换为 \(000\)；
- 选择 \(s\) 中的 \(101\) 子串并将其转换为 \(111\)。
思路：纯模拟。直接遍历 \(s\) 串的每一个字符并判定是否可以翻转即可。
时间复杂度：\(O(n)\)
Python
T = int(input().strip())
for _ in range(T):
t = list(map(int, input().strip()))
s = list(map(int, input().strip()))
n = len(s)
ans = 0
ok = True
for i in range(n):
if s[i] == t[i]:
continue
if i == 0 or i == n - 1 or s[i - 1] == s[i] or s[i + 1] == s[i]:
ok = False
break
else:
s[i] = t[i]
ans += 1
print(ans if ok else -1)
C++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
void solve() {
string t, s;
cin >> t >> s;
int n = s.size();
int ans = 0;
bool ok = true;
for (int i = 0; i < n; i++) {
if (s[i] == t[i]) {
continue;
}
if (i == 0 || i == n - 1 || s[i - 1] == s[i] || s[i + 1] == s[i]) {
ok = false;
break;
} else {
s[i] = t[i];
ans++;
}
}
cout << (ok ? ans : -1) << "\n";
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
T6 子矩阵 (15'/15')¶
题意：给定一个 \(n\times m\ (1\le n,m\le1000)\) 的矩阵，现在需要求出所有大小为 \(a\times b\ (1\le a\le n,1\le b \le m)\) 的子矩阵的价值和。一个子矩阵的价值定义为该子矩阵中最大值与最小值的成绩。输出与 \(998244353\) 取模后的结果。
思路：如果是一维的，那么就是单调队列的板子题，二维的只需要按行按列分开用单调队列维护即可。具体地，我们先按行维护每一个长度为 \(b\) 的数组的最值，然后再按列维护每一个长度为 \(a\) 的数组的最值，最后 \(O(1)\) 地取出最值相乘并求和即可。
时间复杂度：\(O(nm)\)，常数比较大。
Python
from collections import deque
class MonotonicQueue:
def __init__(self, is_min_queue: bool):
self.q = deque()
if is_min_queue:
self.compare = lambda a, b: a < b
else:
self.compare = lambda a, b: a > b
def push_back(self, x):
while self.q and self.compare(x, self.q[-1]):
self.q.pop()
self.q.append(x)
def pop_front(self, x):
if self.q and self.q[0] == x:
self.q.popleft()
def get_extreme_value(self):
return self.q[0]
mod = 998244353
n, m, a, b = map(int, input().strip().split())
g = [list(map(int, input().strip().split())) for _ in range(n)]
f = [[(None, None)] * m for _ in range(n)]
# 维护行最值
for i in range(n):
minq, maxq = MonotonicQueue(True), MonotonicQueue(False)
for j in range(m):
minq.push_back(g[i][j])
maxq.push_back(g[i][j])
if j >= b:
minq.pop_front(g[i][j - b])
maxq.pop_front(g[i][j - b])
f[i][j] = minq.get_extreme_value(), maxq.get_extreme_value()
# 计算列最值 & 求解答案
ans = 0
for j in range(m):
minq, maxq = MonotonicQueue(True), MonotonicQueue(False)
for i in range(n):
minq.push_back(f[i][j][0])
maxq.push_back(f[i][j][1])
if i >= a:
minq.pop_front(f[i - a][j][0])
maxq.pop_front(f[i - a][j][1])
if i >= a - 1 and j >= b - 1:
ans += minq.get_extreme_value() * maxq.get_extreme_value() % mod
print(ans)
C++
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <functional>
using namespace std;
using ll = long long;
template<class T>
struct MonotonicQueue {
std::deque<T> q;
std::function<bool(T, T)> compare;
MonotonicQueue(bool is_min_queue) {
if (is_min_queue) {
compare = [](T a, T b) { return a < b; };
} else {
compare = [](T a, T b) { return a > b; };
}
}
void pushBack(T x) {
while (q.size() && compare(x, q.back())) {
q.pop_back();
}
q.push_back(x);
}
void popFront(T x) {
if (q.size() && q.front() == x) {
q.pop_front();
}
}
T getExtremeValue() {
return q.front();
}
};
const int mod = 998244353;
const int N = 1010;
int n, m, a, b;
int g[N][N];
pair<int, int> f[N][N];
int main() {
cin >> n >> m >> a >> b;
// 维护行最值
for (int i = 0; i < n; i++) {
MonotonicQueue<int> minq(true);
MonotonicQueue<int> maxq(false);
for (int j = 0; j < m; j++) {
cin >> g[i][j];
minq.pushBack(g[i][j]);
maxq.pushBack(g[i][j]);
if (j >= b) {
minq.popFront(g[i][j - b]);
maxq.popFront(g[i][j - b]);
}
f[i][j].first = minq.getExtremeValue();
f[i][j].second = maxq.getExtremeValue();
}
}
// 计算列最值 & 求解答案
ll ans = 0;
for (int j = 0; j < m; j++) {
MonotonicQueue<int> minq(true);
MonotonicQueue<int> maxq(false);
for (int i = 0; i < n; i++) {
minq.pushBack(f[i][j].first);
maxq.pushBack(f[i][j].second);
if (i >= a) {
minq.popFront(f[i - a][j].first);
maxq.popFront(f[i - a][j].second);
}
if (i >= a - 1 && j >= b - 1) {
ans += 1ll * minq.getExtremeValue() * maxq.getExtremeValue() % mod;
}
}
}
cout << ans << "\n";
return 0;
}
T7 阶乘的和 (20'/20')¶
题意：给定一个含有 \(n\) 个数的数组 \(a\)，输出最大的 \(m\) 使得 \(\dfrac{\sum_{i=0}^{n-1}(a_i!)}{m!}\) 为整数。
思路：首先 \(m\) 取 \(a\) 中最小值上式一定为整数。为了让 \(m\) 更大，我们可以贪心地让 \(a\) 中小数的阶乘逐渐合并为更大数的阶乘。比如 \((x+1)\) 个 \(x!\) 就可以合并为 \(1\) 个 \((x+1)!\)。根据这样的贪心合并思路，我们将 a 中的元素排序后不断合并直到无法合并就是最终答案。
时间复杂度：排序为 \(O(n\log n)\)，合并不超过 \(O(\log n)\)。因此最终复杂度为 \(O(n\log n)\)。
C++
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
unordered_map<int, int> d;
for (int i = 0; i < n; i++) {
cin >> a[i];
d[a[i]]++;
}
sort(a.begin(), a.end());
int ans = a[0];
while (true) {
if (d[ans] % (ans + 1) == 0) {
d[ans + 1] += d[ans] / (ans + 1);
ans++;
} else {
cout << ans << "\n";
break;
}
}
return 0;
}
T8 奇怪的数 (5'/20')¶
题意：输出满足「长度为 \(n\ (5\le n \le 2\cdot 10^5)\) 且连续 \(5\) 位数位之和不超过 \(m\ (0\le m\le 50)\) 且奇数位为奇数、偶数位为偶数」的总数字个数，答案对 \(998244353\) 取模。最低位从 \(1\) 开始编号。
思路：
- 最优解 为数位 DP，不会；
- 爆搜加剪枝能过 5/20，第六个点的方案数已经超过 \(2\cdot10^9\) 了，再怎么剪枝也无力回天。不过也可以打表就是了。
Python
n, m = map(int, input().strip().split())
ans = 0
num = [0] * 13
idx = 0
def chk() -> bool:
pre = [0] * 13
pre[0] = num[0]
for i in range(n):
if (i + 1) & 1 != num[i] & 1:
return False
if i:
pre[i] = pre[i - 1] + num[i]
if pre[4] > m:
return False
for i in range(5, n):
if pre[i] - pre[i - 5] > m:
return False
return True
def dfs(u: int) -> None:
global idx, ans
if u == n:
ans = (ans + chk()) % 998244353
return
for x in range(10):
# 剪枝1：数位奇偶性
if (u + 1) & 1 != x & 1:
continue
# 剪枝2：数位之和
if idx >= 4 and sum(num[idx-4:idx]) + x > m:
continue
num[idx] = x
idx += 1
dfs(u + 1)
num[idx] = 0
idx -= 1
if n > 12:
ans = 114514
else:
dfs(0)
print(ans)
C++
#include <iostream>
#include <numeric>
using namespace std;
int ans;
int n, m;
int num[13], idx;
bool chk() {
int pre[13] {};
pre[0] = num[0];
for (int i = 0; i < n; i++) {
if (((i + 1) & 1) != (num[i] & 1)) {
return false;
}
if (i) {
pre[i] = pre[i - 1] + num[i];
}
}
if (pre[4] > m) {
return false;
}
for (int r = 5; r < n; r++) {
if (pre[r] - pre[r - 5] > m) {
return false;
}
}
return true;
}
void dfs(int u) {
if (u == n) {
ans = (ans + chk()) % 998244353;
return;
}
for (int x = 0; x <= 9; x++) {
// 剪枝1：数位奇偶性
if (((idx + 1) & 1) != (x & 1)) {
continue;
}
// 剪枝2：数位之和
if (idx >= 4 && accumulate(num + idx - 4, num + idx, x) > m) {
continue;
}
num[idx++] = x;
dfs(u + 1);
num[idx--] = 0;
}
}
int main() {
cin >> n >> m;
if (n > 12) {
cout << 114514 << "\n";
return 0;
}
dfs(0);
cout << ans << "\n";
return 0;
}
T9 子树的大小 (25'/25')¶
题意：给定 \(Q\ (1\le Q\le 10^5)\) 轮询问，每轮询问给定一棵含有 \(n\ (1\le n\le 10^9)\) 个结点的完全 \(m\ (2\le m\le 10^9)\) 叉树，输出第 \(k\ (1\le k\le n)\) 个结点对应子树的结点数。树中结点按照从上往下，从左往右的顺序从 \(1\) 开始编号。
思路：
- 直接模拟也行，就是麻烦了点，需要推导出在完全 \(m\) 叉树中，编号为 \(k\) 的结点所在的层数。同时，为了解决子树最后一层不满的情况，需要利用第 \(k\) 个结点左侧子树占用了最后一层的多少个结点，来倒推出第 \(k\) 个结点在最后一层可以分到的结点数；
- 更优雅的解法：https://www.lanqiao.cn/questions/573855/。
时间复杂度：\(O(Q\log n)\)
Python
import math
Q = int(input().strip())
OUTs = []
for _ in range(Q):
n, m, k = map(int, input().strip().split())
x = math.ceil(math.log(n * (m - 1) + 1, m)) - 1 # 最后一层层号（从0开始）
y = math.ceil(math.log(k * (m - 1) + 1, m)) - 1 # 当前结点层号（从0开始）
if x == y:
OUTs.append(1)
continue
ans = (1 - m ** (x - y)) // (1 - m)
# 当前结点所在层的结点数
now_level_cnt = m ** y
# 当前结点左侧结点的数量
left_node_cnt = k - ((1 - m ** y) // (1 - m)) - 1
# 满m叉数的情况下，左侧所有结点对应子树的最后一层的结点数量
left_sub_trees_nodes = left_node_cnt * m ** x // now_level_cnt
# 最后一层的实际数量
last = n - (1 - m ** x) // (1 - m)
if last - left_sub_trees_nodes > 0:
ans += min(m ** (x - y), last - left_sub_trees_nodes)
OUTs.append(ans)
print("\n".join(map(str, OUTs)))
T10 反异或 01 串 (15'/25')¶
题意：给定一个长度为 \(n\ (1\le n\le 10^6)\) 的 01 字符串 \(T\)，现在可以对一个空串 \(S\) 进行操作，要么在 \(S\) 的左右侧添加 \(0\)，要么在 \(S\) 的左右侧添加 \(1\)，可以任意次添加 \(0\)，给出最少添加 \(1\) 的次数使得 \(S\) 变成 \(T\)。期间最多可以使用一次新操作，即将 \(S\) 与 \(S\) 的翻转字符串按位异或。
思路：本题最少操作次数的突破口就在按位异或。显然的我们就是要找 \(T\) 串中含有 \(1\) 数量最多的回文子串，注意如果长度是奇数那么中间一个字符不能是 \(1\)。
- 暴力法。枚举每一个子串中心并统计最长回文子串对应的 \(1\) 的数量即可。时间复杂度为 \(O(n^2)\)，可以通过 \(60\%\) 的测试点；
- 最优解 涉及到字符串算法 Manacher。时间复杂度降至 \(O(n)\)。
Python
T = input().strip()
n = len(T)
ans = T.count('1')
# 统计最长回文串中 1 的数量
def calc(l: int, r: int) -> int:
cnt1 = 0
while l >= 0 and r < n and T[l] == T[r]:
if T[l] == '1':
cnt1 += 2
l -= 1
r += 1
return cnt1
max_cnt = 0
for i in range(n):
# 奇数长度的回文串
odd_cnt1 = calc(i - 1, i + 1)
if T[i] != '1':
max_cnt = max(max_cnt, odd_cnt1)
# 偶数长度的回文串
even_cnt1 = calc(i - 1, i)
max_cnt = max(max_cnt, even_cnt1)
print(ans - max_cnt // 2)
C++
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
string T;
cin >> T;
int n = T.size();
int ans = count(T.begin(), T.end(), '1');
int max_cnt = 0;
auto calc = [&](int l, int r) -> int {
int cnt1 = 0;
while (l >= 0 && r < n && T[l] == T[r]) {
cnt1 += T[l] == '1' ? 2 : 0;
l--, r++;
}
return cnt1;
};
for (int i = 0; i < n; i++) {
int odd_cnt1 = calc(i - 1, i + 1);
if (T[i] != '1') {
max_cnt = max(max_cnt, odd_cnt1);
}
int even_cnt1 = calc(i - 1, i);
max_cnt = max(max_cnt, even_cnt1);
}
cout << (ans - (max_cnt >> 1)) << "\n";
return 0;
}