AtCoder Beginner Contest 319 全部题解
A Legendary Players
该题只需使用判断来写出所有的答案，注意不要复制错。
#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
cin >> s;
if(s == "tourist") cout << 3858 << endl;
if(s == "ksun48") cout << 3679 << endl;
if(s == "Benq") cout << 3658 << endl;
if(s == "Um_nik") cout << 3648 << endl;
if(s == "apiad") cout << 3638 << endl;
if(s == "Stonefeang") cout << 3630 << endl;
if(s == "ecnerwala") cout << 3613 << endl;
if(s == "mnbvmar") cout << 3555 << endl;
if(s == "newbiedmy") cout << 3516 << endl;
if(s == "semiexp") cout << 3481 << endl;
return 0;
}
B Measure
这道题只需要枚举每一个 \(i\) 并求答案即可
#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
cin >> n;
for(int i = 0; i <= n; i++){
if(n % 1 == 0 && (i % (n / 1) == 0)) cout << 1;
else if((n % 2 == 0) && i % (n / 2) == 0) cout << 2;
else if((n % 3 == 0) && i % (n / 3) == 0) cout << 3;
else if((n % 4 == 0) && i % (n / 4) == 0) cout << 4;
else if((n % 5 == 0) && i % (n / 5) == 0) cout << 5;
else if((n % 6 == 0) && i % (n / 6) == 0) cout << 6;
else if((n % 7 == 0) && i % (n / 7) == 0) cout << 7;
else if((n % 8 == 0) && i % (n / 8) == 0) cout << 8;
else if((n % 9 == 0) && i % (n / 9) == 0) cout << 9;
else cout << "-";
}
return 0;
}
C False Hope
这题难在题意。
题意：给定一个 \(3*3\) 的矩阵，每个数上都盖了贴纸，每次揭开一张，将某行、列、对角线中第一个翻看的数记为 \(i\)，第二个翻看的数记为 \(j\)，第三个翻看的数记为 \(k\)，满足：
\[i = j, j \ne k \]就会失望。求不失望的概率。
我们只需对每个格子的顺序进行排列，然后判断即可。
#include <bits/stdc++.h>
using namespace std;
int a[100], b[100], st, nd, rd;
double ans1, ans2;
bool used[100];
bool check2(int x, int y, int z){
if(b[x] < b[y] && b[x] < b[z]) st = x;
else if(b[y] < b[x] && b[y] < b[z]) st = y;
else st = z;
if(b[x] > b[y] && b[x] > b[z]) rd = x;
else if(b[y] > b[x] && b[y] > b[z]) rd = y;
else rd = z;
nd = x + y + z - st - rd;
if(a[st] == a[nd] && a[nd] != a[rd]) return false;
return true;
}
bool check(){
if(!check2(1, 2, 3)) return false;
if(!check2(4, 5, 6)) return false;
if(!check2(7, 8, 9)) return false;
if(!check2(1, 4, 7)) return false;
if(!check2(2, 5, 8)) return false;
if(!check2(3, 6, 9)) return false;
if(!check2(1, 5, 9)) return false;
if(!check2(3, 5, 7)) return false;
return true;
}
void dfs(int step){
if(step == 10){
if(check()) ans1++, ans2++;
else ans1++;
return ;
}
for(int i = 1; i <= 9; i++){
if(used[i]) continue;
used[i] = 1;
b[step] = i;
dfs(step + 1);
used[i] = 0;
}
return ;
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
for(int i = 1; i <= 9; i++) cin >> a[i];
dfs(1);
printf("%.10f", ans2 / ans1);
return 0;
}
D Minimum Width
这是一道很经典的二分题。
我在检查宽度是否合法时，定义了 res 和 now。
res表示当前要在哪一行now表示当前要在哪里插入位置（还没有字符）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7;
int n, m, a[N], sum, Max, mid, l, r, ans;
int check(int x){
int now = 0, res = 0;
for(int i = 1; i <= n; i++){
if(now == 0){
res++;
now += a[i];
}
else if(now + a[i] < x) now += a[i] + 1, now %= x;
else res++, now = a[i];
}
return res;
}
signed main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i] + 1;
Max = max(Max, a[i]);
}
l = Max, r = sum * 2;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid) <= m) ans = mid, r = mid - 1;
else l = mid + 1;
}
cout << ans << endl;
return 0;
}
E Bus Stops
在读题时，我们会看到一个很显眼的提示：\(1 \le P_i \le 8\)，而对于每一个车站，他所耗费的时间只和他的倍数有关。
那么我们就可以设一个数组表示当前时间 \(t \bmod (\gcd \limits_{i=1}^{8}i) = t \bmod 840\) 即可。具体的，首先用一个循环直接处理出对于所有 \(0 \le t < 840\) 中的解法，对每一个车站进行模拟，每次询问直接 \(O(1)\) 回答。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7;
int n, x, y, p[N], t[N], ans[N];
int q, op;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> x >> y;
for(int i = 1; i < n; i++)
cin >> p[i] >> t[i];
for(int i = 0; i < 840; i++){
ans[i] = i + x;
for(int j = 1; j < n; j++){
if(ans[i] % p[j] == 0)
ans[i] += t[j];
else
ans[i] += (p[j] - (ans[i] % p[j])) + t[j];
}
ans[i] += y;
}
cin >> q;
while(q--){
cin >> op;
cout << ans[op % 840] + op / 840 * 840 << "\n";
}
return 0;
}
F Fighter Takahashi
前置知识：状态压缩，树，优先队列
好题，非常好的题。
题目描述了一个游戏，你在一棵树上，初始位置为点 \(1\)，你目前的战斗值 \(f\) 也是 \(1\)，你每次可以在树上移动。这棵树上有一些药和怪，若你碰到了第 \(i\) 个怪，你需要 \(f \ge s_i\)，可以使你的体力增加 \(g_i\)，并将他打败，否则你会输掉游戏，并且你也不能绕过他。若你碰到了药水，你能也必须将它喝下，并将你的战斗值设为 \(f \times g_i\)。
求出你是否能够打败所有怪。
如果你经常看广告的话，你也会看到这种小游戏，叫什么梦想家园还是什么的。但广告中通常不会能么复杂，区别在于他不在树上，你可以任意选择打怪吃药的顺序。这本质上是一种贪心，先打怪一定优于先吃药，所以有怪就打，没怪吃药。
但这道题是在树上，一开始我们没什么思路，直到我们看到了这么一句话：
There are at most \(10\) vertices with a medicine.
翻译过来就是：
这里最多有 \(10\) 瓶药
一般的，提到范围为 \(10\) 的要么是和 \(O(n!)\) 有关的，要么是和 \(O(2^n)\) 有关的。显然这里时候一种，我们就能联想到状态压缩。
设拿了药的状态为 \(S\)，有 \(Med\) 瓶药我们最终求出 \(dp_{2 ^ {(Med - 1)}}\) 是否大于怪的最大防御力 \(Max\)。
显然，当 \(S=0\) 时，及没有药时，我们只用把所有到根节点的路径上没有药的怪全都放进一个优先队列，然后一个一个取出。
接下来我们考虑如何转移。若我们想要从状态 \(S\) 转移至 \(T\)，\(S\) 和 \(T\) 中一定会差一个二进制中的 \(1\)，所以我们要考虑哪些药可以继续吃。我们需要在算 \(S=0\) 和其他情况时记录下哪些节点的怪和药已经吃过了，注意：不是在搜索是被搜到，这很显然是因为被搜到的怪也不一定能走，这很容易错。
确定了 \(S\) 和 \(T\) 后，我们只需要搜索新加的药下面的怪，并放进原来 \(S\) 的优先队列中进行贪心即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000;
int n;
int cnt, head[N], nxt[N], e[N];
int f[N], t[N], s[N], g[N];
int med[N], medcnt;
int Max, Maxsum;
struct state{
int used[505];
priority_queue<pair<int, int> > q;
int num;
}dp[3005];
void addEdge(int x, int y){
e[++cnt] = y, nxt[cnt] = head[x], head[x] = cnt;
return ;
}
void init(int x, int y){
for(int i = head[y]; i; i = nxt[i])
if(t[e[i]] == 1)
dp[x].q.push(make_pair(-s[e[i]], e[i]));
while(!dp[x].q.empty()){
if(dp[x].num < -dp[x].q.top().first) break;
dp[x].num += g[dp[x].q.top().second];
dp[x].used[dp[x].q.top().second] = 1;
int op = dp[x].q.top().second;
dp[x].q.pop();
for(int i = head[op]; i; i = nxt[i])
if(t[e[i]] == 1)
dp[x].q.push(make_pair(-s[e[i]], e[i]));
}
return ;
}
void dfs(int u){
for(int i = 1; i <= medcnt; i++){
if(dp[u].used[med[i]] == 1 || dp[u].used[f[med[i]]] == 0) continue;
int v = u | (1 << (i - 1));
dp[3000] = dp[u];
dp[3000].num *= g[med[i]];
dp[3000].used[med[i]] = 1;
init(3000, med[i]);
if(dp[3000].num > dp[v].num) dp[v] = dp[3000], dfs(v);
}
return ;
}
signed main(){
cin >> n;
for(int i = 2; i <= n; i++){
cin >> f[i] >> t[i] >> s[i] >> g[i];
Maxsum = max(Maxsum, s[i]);
addEdge(f[i], i);
if(t[i] == 2) med[++medcnt] = i;
}
dp[0].num = 1;
dp[0].used[1] = 1;
init(0, 1);
dfs(0);
for(int i = 0; i < (1 << medcnt); i++){
Max = max(Max, dp[i].num);
}
if(Max >= Maxsum) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
G Counting Shortest Paths
也是一道很好的图论题。部分参考了其他一些题解。
若是在普通图中，我们很方便得出答案。先用 \(\text{BFS}\) 搜出第 \(i\) 个点的距离，以下用 \(dis_i\) 表示，然后再对其进行 \(\text{DP}\)，有
\[dp_u=\sum_{(v,u)∈E, dis_u=dis_v+1}dp[v] \]它的时间复杂度显然是 \(O(n^2)\) 的，这太大了。但是，我们可以由此获得一些提示：我们需要处理以下两个问题。
- 如何 \(\text{BFS}\)，及如何从一个点扩展至另一个
- 如何求出 \(dis\) 以及 \(dp\)。
如何 \(\text{BFS}\)：想要做到这一点，我们必须利用补图。首先，\(\text{BFS}\) 有一个特性，若当前点为 \(u\)，那么对于 \(u\)，我们扩展的点 \(v\) 满足 \(dis_v=dis_u+1\)，这是显然的。设原图的边集为 \(G\)，补图的边集为 \(G'\)，当 \((u,v)∈G'\) 时，一定满足 \(dis_v\ne dis_u+1\)，也就是不能搜 \(v\) 点。那么我们只需要将所有还未搜到的点放进一个集合，每次将不可能搜到的点排除即可。
如何求值：首先再 \(\text{BFS}\) 时，我们可以直接求出 \(dis_i\) 的值，所以只需考虑 \(dp\) 即可。我们会发现有：
\[dp_u=\sum_{(v,u)∈G, dis_u=dis_v+1}dp_v \]及：
\[\sum_{(v,u)∈G, dis_u=dis_v+1}dp_v=\sum_{1\le u,v \le n, dis_u=dis_v+1}dp_v-\sum_{(v,u)∈G', dis_u=dis_v+1}dp_v \]对于被减数，我们在计算 \(dp_u\) 时可以直接累加使 \(sum_{dis_u+1}=sum_{dis_u+1}+dp_u\)，对于减数，我们只需要先把所有点根据 \(dis\) 分类后直接相减即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7, Mod = 998244353;
set<int> notVis, Vis;
queue<int> q;
int cnt, e[N], nxt[N], head[N];
int num, val[N], NXT[N], HEAD[N];
int n, a[N], b[N], m, dis[N], dp[N], sum[N];
void addEdge(int x, int y){
e[++cnt] = y, nxt[cnt] = head[x], head[x] = cnt;
return ;
}
void add(int h, int x){
val[++num] = x, NXT[num] = HEAD[h], HEAD[h] = num;
return ;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) notVis.insert(i);
for(int i = 1; i <= m; i++){
cin >> a[i] >> b[i];
addEdge(a[i], b[i]); addEdge(b[i], a[i]);
}
notVis.erase(1); q.push(1); dis[1] = 0;
while(!q.empty()){
Vis = notVis;
int u = q.front(); q.pop();
add(dis[u], u);
for(int i = head[u]; i; i = nxt[i]) if(Vis.end() != Vis.find(e[i])) Vis.erase(e[i]);
for(int i : Vis) dis[i] = dis[u] + 1, q.push(i), notVis.erase(i);
}
if(dis[n] == 0){
cout << -1 << endl;
return 0;
}
dp[1] = 1, sum[0] = 1;
for(int i = 1; i <= dis[n]; i++){
for(int j = HEAD[i]; j; j = NXT[j]) dp[val[j]] = sum[i - 1] % Mod;
for(int j = HEAD[i - 1]; j; j = NXT[j])
for(int k = head[val[j]]; k; k = nxt[k])
if(dis[e[k]] == i)
dp[e[k]] = dp[e[k]] - dp[val[j]] + Mod, dp[e[k]] %= Mod;
for(int j = HEAD[i]; j; j = NXT[j]) sum[i] += dp[val[j]], sum[i] %= Mod;
}
cout << dp[n] % Mod << endl;
return 0;
}