A - Water Station (abc305 a)
题目大意
给定一个数字\(x\)，输出一个数字，它是最接近\(x\)的 \(5\)的倍数。
解题思路
令\(y = x \% 5\)，如果 \(y \leq 2\)，那答案就是 \(x - y\)，否则就是 \(x + 5 - y\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int x;
cin >> x;
int mod = x % 5;
if (mod <= 2)
x -= mod;
else
x += 5 - mod;
cout << x << '\n';
return 0;
}
B - ABCDEFG (abc305 b)
题目大意
给定\(ABCDEFG\)的相邻距离，给定两个字母，问它们的距离。
解题思路
累加距离即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
array<int, 7> dis{3,1,4,1,5,9};
string a, b;
cin >> a >> b;
if (a > b)
swap(a, b);
int ans = accumulate(dis.begin() + a[0] - 'A', dis.begin() + b[0] - 'A', 0);
cout << ans << '\n';
return 0;
}
C - Snuke the Cookie Picker (abc305 c)
题目大意
二维平面，有一个矩形少了一块，问这一块的位置。
解题思路
找到矩形的左上和右下，然后遍历矩形的每一块看看是不是少了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int h, w;
cin >> h >> w;
vector<string> s(h);
for(auto &i : s)
cin >> i;
int sx = h, sy = w, ex = 0, ey = 0;
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j){
if (s[i][j] == '#'){
sx = min(sx, i);
sy = min(sy, j);
ex = max(ex, i);
ey = max(ey, j);
}
}
int ansx = 0, ansy = 0;
for(int i = sx; i <= ex; ++ i)
for(int j = sy; j <= ey; ++ j){
if (s[i][j] == '.'){
ansx = i;
ansy = j;
}
}
cout << ansx + 1 << ' ' << ansy + 1 << '\n';
return 0;
}
D - Sleep Log (abc305 d)
题目大意
给定一个睡觉日志\(a\)，从\(0\)开始（题目从\(1\)开始），奇数项表示醒来的分钟数，偶数项表示开睡的分钟数。
回答\(q\)组询问，每组询问 \(l, r\)，问从第 \(l\)分钟到第 \(r\)分钟，共睡了多久。
解题思路
因为分钟数高达\(10^9\)，因此不能每分钟的累加。
先对睡觉日志求一遍睡眠时间的前缀和。
对于询问 \(l, r\)，先找到第一个大于等于其的日志分钟数位置 \(posl, posr\)。
答案首先加上 \(a[posl] \to a[posr]\)的睡眠分钟数（前缀和得出），缺少了时间段 \(l \to a[posl]\)和额外的时间段 \(r \to a[posr]\)，判断其是否是睡眠的时间段，从而加回答案或减去即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<LL> a(n);
for(auto &i : a)
cin >> i;
vector<LL> presum(n);
for(int i = 2; i < n; i += 2){
presum[i] = presum[i - 1] + a[i] - a[i - 1];
if (i < n)
presum[i + 1] = presum[i];
}
int q;
cin >> q;
while(q --){
int l, r;
cin >> l >> r;
int posl = lower_bound(a.begin(), a.end(), l) - a.begin();
int posr = lower_bound(a.begin(), a.end(), r) - a.begin();
LL ans = presum[posr] - presum[posl];
if (~posl & 1)
ans += a[posl] - l;
if (~posr & 1)
ans -= a[posr] - r;
cout << ans << '\n';
}
return 0;
}
E - Art Gallery on Graph (abc305 e)
题目大意
给定一张\(n\)个点 \(m\)条边的无向图，边权为\(1\)。有\(k\)个关键点，每个关键点\(k_i\)可以监视距离不超过 \(h_i\)的点。
一个点若被至少一个关键点监视，则称该点被监视。
升序给出被监视点的标号。
解题思路
题意就是问每个点距离一堆特殊点的距离是否满足要求。初看没什么思路，因为\(k\)和\(n\)是同一个数量级，因此不能 \(k\)次 \(BFS\)。但忽然想到了GXOI/GZOI2019 旅行者，里面为了求一些点到一些点的最短距离，额外增加了个起点和终点，这样求一次最短路就可以了。
同样的道理，我们可以也增加一个起点\(st\)，该起点与 \(k\)个关键点都连边。至于边权，因为每个关键点的监视距离不一样，因此为了统一最后的判断（距离起点 \(st\)的距离），我们设关键点中最大的监视距离为 \(maxx\)，则 \(st \to k_i\)的边权为 \(maxx - h_i\)，这样最后从起点跑一遍最短路后，与起点距离不超过 \(maxx\)的点都被监视了。
注意这个起点\(st\)是我们额外加的，实际不存在，要防止关键点通过起点监视了其他点，因此要设 \(k_i \to st\)的距离为无穷大。
因为增加了额外点和额外边，边权不再是\(1\)了。因此不能跑 \(BFS\)，可以跑 \(Dijkstra\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<array<int, 2>>> edge(n + 1);
auto add = [&](int u, int v, int w = 1, int w2 = 1){
edge[u].push_back({v, w});
edge[v].push_back({u, w2});
};
for(int i = 0; i < m; ++ i){
int a, b;
cin >> a >> b;
-- a, -- b;
add(a, b);
}
int st = n;
int mstamina = 0;
vector<array<int, 2>> p(k);
for(auto &i : p){
cin >> i[0] >> i[1];
i[0] --;
mstamina = max(mstamina, i[1]);
}
for(auto &i : p){
add(st, i[0], mstamina - i[1], inf);
}
priority_queue<array<int, 2>> team;
vector<int> dis(n + 1, inf);
team.push({0, st});
dis[st] = 0;
while(!team.empty()){
auto [expect, u] = team.top();
team.pop();
if (dis[u] != -expect)
continue;
for(auto &[v, w] : edge[u]){
if (dis[u] + w < dis[v]){
dis[v] = dis[u] + w;
team.push({-dis[v], v});
}
}
}
vector<int> ans;
for(int i = 0; i < n; ++ i)
if (dis[i] <= mstamina && dis[i] != inf){
ans.push_back(i + 1);
}
cout << ans.size() << '\n';
for(auto &i : ans)
cout << i << ' ';
cout << '\n';
return 0;
}
F - Dungeon Explore (abc305 f)
题目大意
交互题。
一张无向图，但你不知道具体情况。从 \(1\)出发到 \(n\)。
一开始处于\(1\)号点。
当你处于 \(i\)号点，裁判会告诉你与 \(i\)号点相邻的点。
你需要决定下一个去的点的编号。
在移动不超过\(2n\)次走到点 \(n\)。
解题思路
其实就是一个\(DFS\)过程，\(DFS\)过程维护点的访问状态，每个点最多进栈一次出栈一次，因此在不超过 \(2n\)次就可以遍历所有的点，因此也能到达点 \(n\)。
注意回溯的时候也要读取回溯点的相邻点情况。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> visit(n + 1, 0);
function<void(int)> dfs = [&](int u){
if (u == n){
exit(0);
}
int k, _;
cin >> k;
vector<int> nxt(k);
for(auto &i : nxt)
cin >> i;
for(auto &i : nxt){
if (!visit[i]){
cout << i << endl;
visit[i] = 1;
dfs(i);
cout << u << endl;
for(int i = 0; i <= k; ++ i)
cin >> _;
}
}
};
visit[1] = 1;
dfs(1);
return 0;
}
G - Banned Substrings (abc305 g)
题目大意
给定\(m\)个 \(ab\)字符串。
问有多少种长度为 \(n\)的字符串，其子串不包括这 \(m\)个字符串。
\(n \leq 10^{18}\)
解题思路
一眼原，找到了两年前写的代码，直接复制粘贴（
对这\(m\)个字符串建立 \(AC\)自动机，然后问题就转换成有多少条长度为 \(n\)的路径，其不经过一些特殊点。
经典路径计数问题，\(dp[i][j]\)表示从起点出发，不经过特殊点，走了\(i\)个点，最终到达点 \(j\) 的方案数。转移就是从\(i-1\)中枚举 \(j\)的相邻点转移。
因为 \(n\)很大，且转移式子是线性的，\(dp\)转移可以写成矩阵的形式，快速幂一下就得到结果了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x) {
int s = 0, c = getchar();
x = 0;
while (isspace(c)) c = getchar();
if (c == 45) s = 1, c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s) x = -x;
}
template <typename T>
void write(T x, char c = ' ') {
int b[40], l = 0;
if (x < 0) putchar(45), x = -x;
while (x > 0) b[l++] = x % 10, x /= 10;
if (!l) putchar(48);
while (l) putchar(b[--l] | 48);
putchar(c);
}
class AC_automation{
#define N 300
#define M 2
int trans[N][M];
int fail[N];
int sign[N];
int tot;
public:
void insert(const char *s){
int cur = 0;
sign[cur] = 0;
for(int i = 0; s[i]; ++ i){
if (! trans[cur][s[i] - '0']){
trans[cur][s[i] - '0'] = ++ tot;
sign[tot] = 0;
}
cur = trans[cur][s[i] - '0'];
}
sign[cur] = 1;
}
void build(){
queue<int> team;
for(int i = 0; i < M; ++ i){
if (trans[0][i]) team.push(trans[0][i]);
}
int u = 0;
while(! team.empty()){
u = team.front();
team.pop();
for(int j = 0; j < M; ++ j){
if (trans[u][j]){
fail[trans[u][j]] = trans[fail[u]][j];
team.push(trans[u][j]);
}else{
trans[u][j] = trans[fail[u]][j];
}
sign[trans[u][j]] |= sign[fail[trans[u][j]]];
}
}
}
friend LL work(LL);
}AC;
const LL mo = 998244353;
class Matrix{
public:
LL a[300][300];
int n;
Matrix(int ss,int val = 0){
n=ss;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j){
a[i][j] = val;
}
}
Matrix(const Matrix & b){
n = b.n;
for(int i = 0; i < n; ++ i){
for(int j = 0; j < n; ++ j){
a[i][j] = b.a[i][j];
}
}
}
Matrix operator * (const Matrix & b){
Matrix tmp(this->n);
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
for(int k = 0; k < n; ++ k)
tmp.a[i][j] = (a[i][k] * b.a[k][j] % mo + tmp.a[i][j]) % mo;
return tmp;
}
void print(){
for(int i = 0; i < n ; ++ i){
for(int j = 0; j < n; ++ j){
printf("%lld%c",a[i][j],j==n-1?'\n':' ');
}
}
}
};
Matrix qpower(Matrix a, LL b){
Matrix tmp(a.n);
for(int i = 0; i < a.n; ++ i)
tmp.a[i][i] = 1;
while(b){
if (b&1) tmp = tmp * a;
a = a * a;
b >>= 1;
}
return tmp;
}
LL work(LL n){
int cnt = AC.tot;
Matrix ma(cnt+1);
for(int i = 0; i <= cnt; ++ i){
for(int j = 0; j < M; ++ j){
++ ma.a[i][AC.trans[i][j]];
}
}
int qaq = 0;
for(int i = 0; i <= cnt; ++ i){
if (! AC.sign[i]) ++ qaq;
}
Matrix tmp(qaq);
int x = -1, y = 0;
for(int i = 0; i <= cnt; ++ i){
if (AC.sign[i]) continue;
y = 0;
++ x;
for (int j = 0; j <= cnt; ++ j){
if (AC.sign[j]) continue;
tmp.a[x][y] = ma.a[i][j];
++ y;
}
}
// tmp.print();
Matrix qwq = qpower(tmp,n);
LL ans = 0;
for(int i = 0; i < qaq; ++ i)
ans = (ans + qwq.a[0][i]) % mo;
return ans;
}
char s[15];
int main(){
int m;
LL n;
read(n);
read(m);
while(m--){
scanf("%s",s);
for(size_t i = 0; s[i]; ++ i){
switch(s[i]){
case 'a' : s[i] = '0'; break;
case 'b' : s[i] = '1'; break;
}
}
AC.insert(s);
}
AC.build();
LL ans;
ans = work(n);
write(ans,'\n');
return 0;
}
不过本题的字符串只包含\(01\)，可以直接矩阵优化 \(dp\)转移。
Ex - Shojin (abc305 h)
题目大意
给定\(n\)个二元组 \((a,b)\)。
将二元组拆分成\(k\)段，让每段的代价的和不超过 \(x\)。
问最小的 \(k\)，以及对应的最小代价和。
每段的代价和定义如下：
首先可以对该段的二元组任意排序，然后初始代价 \(x\)，对每个二元组\((a,b)\)依次计算 \(x = ax + b\)。最后的 \(x\)就是该段的代价。
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 305beginner atcoder contest 305 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310