文章目录
AtCoder Beginner Contest 208
A - Rolling Dice
题意：
题解：
代码：
#include <bits/stdc++.h>
#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;
int const MAXN = 2e5 + 10;
int n, m, T, a[MAXN];
int A, B;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> A >> B;
int low = A;
int up = A * 6;
if (low <= B && B <= up) puts("Yes");
else puts("No");
return 0;
}
B - Factorial Yen Coin
题意：
题解：
代码：
#include <bits/stdc++.h>
#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;
int const MAXN = 2e5 + 10;
int n, m, T, a[MAXN];
int get(int x) {
int res = 1;
for (int i = 1; i <= x; ++i) res *= i;
return res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
int cnt = 0;
for (int i = 10; i >= 1; --i) {
cnt += n / get(i);
n %= get(i);
}
cout << cnt;
return 0;
}
C - Fair Candy Distribution
题意：
题解：
代码：
#include <bits/stdc++.h>
#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;
int const MAXN = 2e5 + 10;
int n, m, T;
typedef pair<int, int> PII;
PII a[MAXN];
bool cmp(PII x, PII y) {
return x.second < y.second;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i].first;
a[i].second = i;
}
sort(a + 1, a + 1 + n);
int avg = m / n;
int remain = m % n;
for (int i = 1; i <= n; ++i) {
if (i <= remain) a[i].first = avg + 1;
else a[i].first = avg;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; ++i) cout << a[i].first << endl;
return 0;
}
D - Shortest Path Queries 2
题意： 有一张n个点m条边的有向图，定义 f ( s , t , k ) f(s,t,k) f(s,t,k) 为从s到t点，只在前1 ~ k个点之间流转的路径的最小长度。现在要你计算 ∑ s = 1 N ∑ t = 1 N ∑ k = 1 N f ( s , t , k ) \sum_{s=1}^N\sum_{t=1}^N\sum_{k=1}^Nf(s, t, k) ∑s=1N∑t=1N∑k=1Nf(s,t,k)。 数据范围 1 < = n < = 400 , 0 < = m < = n ∗ ( n − 1 ) 1<=n<=400,0<=m<=n*(n-1) 1<=n<=400,0<=m<=n∗(n−1)
题解： n是400，第一眼看过去应该就会想到Floyd。考虑floyd的过程，第一个循环for (int k = 1; k <= n; ++k)，这个循环决定了对于任意的i和j之间的转移，只经过当前的k来更新，因此当k从1 ~ n的过程，也就是使得i -> j之间的转移只通过1 ~ k的来流转的最短路，那么符合题目的定义。因此对于每一个k变化的时候，都更新下答案即可。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int const N = 410, INF = 0x3f3f3f3f3f3f3f3f;
int mp[N][N], n, m, k;
// floyd求最短路
int floyd() {
int res = 0 ;
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) // 枚举起点
for (int j = 1; j <= n; ++j) // 枚举终点
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]); // 更新i到j的距离
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (mp[i][j] < 1e9) res += mp[i][j];
}
return res;
}
signed main() {
cin >> n >> m; // 点、边、询问次数
// 初始化距离：初始化为正无穷
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
mp[i][j] = (i == j? 0: INF);
// 读入边
for (int i = 1, a, b, c; i <= m; ++i) {
scanf("%lld%lld%lld", &a, &b, &c);
mp[a][b] = min(mp[a][b], c);
}
// 求最短路
cout << floyd();
return 0;
}
E - Digit Products
题意： 计算[1, N]中有多少数字的数位乘积小于等于K。 1 < = N < = 1 e 18 , 1 < = K < = 1 e 9 1<=N<=1e18,1<=K<=1e9 1<=N<=1e18,1<=K<=1e9
题解： 本题需要考虑乘积，有18位，乘积的数字很大，但是状态数目不会很多，因此直接把状态离散化。同时，需要考虑前导0的影响。然后直接按照数位dp转移即可。
代码：
#include <bits/stdc++.h>
#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;
int const MAXN = 20;
int n, k, a[MAXN], dp[MAXN][1000000], len, idx;
unordered_map<int, int> H;
int mapping(int x) {
if (!H.count(x)) H[x] = ++idx;
return H[x];
}
int dfs(int pos, int lead, int sum, int limit) { // lead维护前导0，sum维护乘积
if (!pos) return sum <= k;
if (!limit && !lead && dp[pos][mapping(sum)] != -1) return dp[pos][mapping(sum)]; // 因为乘积总数少，所以离散化
int res = 0;
int up = limit? a[pos]: 9;
for (int i = 0; i <= up; ++i) {
if (lead) res += dfs(pos - 1, lead && !i, max((int)1, i), limit && i == up); // 需要考虑前导0带来的影响
else res += dfs(pos - 1, lead && !i, sum * i, limit && i == up);
}
if (!limit && !lead) dp[pos][mapping(sum)] = res;
return res;
}
int solve(int x) {
len = 0;
while(x) a[++len] = x % 10, x /= 10;
return dfs(len, 1, 1, 1);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
memset(dp, -1, sizeof dp);
cout << solve(n) - 1;
return 0;
}
F - Cumulative Sum
题意： 阴间拉格朗日插值，题解看了半天，还是不会，鸽了
题解：
代码：