比赛链接：Here
A - Rolling Dice
水题
一个六面的骰子，请问摇动 (A) 次最后的点数和能否为 (B)
如果 (B in [a,6a]) 输出 YES
- C++
void solve() {
int a, b; cin >> a >> b;
if (a * 1 <= b && a * 6 >= b)cout << "Yes
"; else cout << "No
";
}
- Python
A,B = map(int,input().split())
if A <= B <= 6 * A:
print("Yes")
else:
print("No")
B - Factorial Yen Coin
找零问题 or 完全背包问题
- C++
void solve() {
ll n;
cin >> n;
int i = 2, cnt = 0;
while (n) {
cnt += n % i;
n /= i++;
}
cout << cnt << "
";
}
另一种写法
int fac(int i) {return i ? fac(i - 1) * i : 1;}
void solve() {
int n;
cin >> n;
int cnt = 0;
for (int i = 1; i <= 10; ++i) {
int div = fac(i + 1);
int res = n % div;
cnt += res / fac(i);
n -= res;
}
cout << cnt << "
";
}
- Python
from math import factorial
P = int(input())
answer = 0
for i in range(10, 0, -1):
while factorial(i) <= P:
answer += 1
P -= factorial(i)
print(answer)
C - Fair Candy Distribution
构造
一开始想错了，想模拟写。但在写样例时发现这个是对 k 平均分配，对于排序之后 (k \% n) 小的需要 + 1
- C++
void solve() {
int n; ll k; cin >> n >> k;
vector<ll>a(n), b(n);
for (int i = 0; i < n; ++i) cin >> a[i], b[i] = a[i];
sort(a.begin(), a.end());
for (int i = 0; i < n; ++i) {
if (b[i] < a[k % n])cout << k / n + 1 << "
";
else cout << k / n << "
";
}
}
- Python
n, k = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
print(*[k // n + (A[i] < B[k % n]) for i in range(n)])
D - Shortest Path Queries 2
最短路问题
跑 FLoyd 最短路即可
- C++
const int N = 410, mod = 1e9 + 7;
ll f[N][N];
void solve() {
memset(f, 0x3f, sizeof(f));
ll n, m; cin >> n >> m;
for (int i = 1; i <= n; ++i)f[i][i] = 0;
for (int i = 0, a, b, c; i < m; ++i) {
cin >> a >> b >> c;
f[a][b] = c;
}
ll cnt = 0;
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cnt += ((f[i][j] = min(f[i][j], f[i][k] + f[k][j])) != f[0][0]) ? f[i][j] : 0;
cout << cnt << "
";
}
- Python （TLE）
import sys
n, m = map(int, sys.stdin.buffer.readline().split())
ABC = map(int, sys.stdin.buffer.read().split())
d = [[1 << 60] * n for i in range(n)]
for i in range(n):
d[i][i] = 0
for a, b, c in zip(ABC, ABC, ABC):
d[a - 1][b - 1] = c
cnt = 0
for k in range(n):
nxt = [[0] * n for i in range(n)]
for i in range(n):
for j in range(n):
nxt[i][j] = min(d[i][j], d[i][k] + d[k][j])
if nxt[i][j] < (1 << 59):
cnt += nxt[i][j]
d = nxt
print(cnt)
E - Digit Products
数位 DP ，时间复杂度：(mathcal{O}(log n))
对于这道题来说，如果一个个去构造肯定是是 TLE ((n < 1e18))，所以我们利用数位 DP (一种著名的组合算法，用于快速计算受数字约束的、不超过 (n) 的整数）
- 构造一个 DP状态：即到目前为止确定的前 i 个数字是否严格小于 (n) 个数字
- 状态转移方程：(dp_{i,p}:=) 前 (i) 位（(0)除外）的组合数，其乘积为(p)
- 同样，设 (eq_i :=)（N的前 (i) 位的乘积）。
using ll = long long;
unordered_map<ll, ll>f[23];
ll n, k;
vector<int>a;
ll fun(ll x, ll y, ll z, ll t) {
if (!x)return y <= k;
if (!z and !t and f[x][y])return f[x][y];
ll ans = 0;
for (ll i = 0; i <= (z ? a[x - 1] : 9); ++i)
ans += fun(x - 1, y * (!i and t ? 1 : i), z and i == a[x - 1], t and !i);
if (!z and !t)f[x][y] = ans;
return ans;
}
void solve() {
cin >> n >> k;
while (n)a.push_back(n % 10), n /= 10;
cout << fun(a.size(), 1, 1, 1) - 1;
}