比赛链接：
https://codeforces.com/gym/103389
A. 公交线路
题意：
已知 \(n\) 个公交站点的名字，现在从 \(x\) 站到 \(y\) 站，现在知道了在车上依次听到的站点的名字，问乘坐方向是否正确，或者不确定。
思路：
判断正反方向即可，若都相同，那么不确定。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n, x, y;
cin >> n >> x >> y;
vector <int> k(n);
for (int i = 0; i < n; i ++ )
cin >> k[i];
int m;
cin >> m;
vector <int> p(m);
for (int i = 0; i < m; i ++ )
cin >> p[i];
vector <int> a, b;
for (int i = x; i < x + m; i ++ )
a.push_back(k[i]);
for (int i = x - 2; i >= x - m - 1; i -- )
b.push_back(k[i]);
if (x > y) swap(a, b);
if (a == p && b == p) cout << "Unsure\n";
else if (a == p) cout << "Right\n";
else cout << "Wrong\n";
return 0;
}
B. 攻防演练
题意：
给定由前 \(m\) 个字母构成的长为 \(n\) 的字符串，进行 \(q\) 次询问，每次给定 \([l, r]\)，找到最短的一个由前 \(m\) 个字符构成的字符串，与 \(s[l, r]\) 没有公共子序列，输出这个字符串的长度。
思路：
考虑暴力找，从 \(l - 1\) 位开始，它的下一位可以是前 \(m\) 个字符中的一个，为了使字符串最短，应该选距离最远的那个字母。
显然暴力会超时，考虑通过倍增优化。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int m, n;
cin >> m >> n;
string s;
cin >> s;
s = '-' + s;
vector < vector <int> > nxt(n + 2, vector<int>(20));
for (int i = 0; i < 20; i ++ )
nxt[n + 1][i] = n + 1;
vector <int> pos(m, n + 1);
for (int i = n; i >= 0; i -- ){
for (int j = 0; j < m; j ++ )
nxt[i][0] = max(nxt[i][0], pos[j]);
if (i) pos[s[i] - 'a'] = i;
}
for (int i = n; i >= 0; i -- )
for (int j = 1; j < 20; j ++ )
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
int q;
cin >> q;
while(q -- ){
int l, r;
cin >> l >> r;
int ans = 0, now = l - 1;
for (int i = 19; i >= 0; i -- ){
if (nxt[now][i] <= r){
now = nxt[now][i];
ans += (1 << i);
}
}
cout << ans + 1 << "\n";
}
return 0;
}
C. 连锁商店
题意：
有 \(n\) 个景点，海拔高度从低到高的依次编号为 1 到 \(n\)，有 \(m\) 条缆车线路，可以将游客从低海拔的景点送到高海拔的景点。
第 \(i\) 个景点隶属于 \(c_i\) 公司，\(i\) 公司的优惠红包为 \(w_i\)，只有第一次来到这家公司的景点才能领这个红包，问从 1 号景点开始，到第 \(i\) 号景点的线路中，能获得的最大优惠红包之和为多少。
思路：
数据很小，考虑状压，总共状态数为 1 << 36，显然超了，对公司进行分类，第一次到这家公司才能领红包，后面不管来多少次都不领了，所以公司可以分成两类，那么对第二类公司进行状压，状态数为 1 << 18。
因为只能从编号小的到编号大的，定义 \(dp_{i, j}\) 为到达第 \(i\) 个景点，状态为 \(j\) 的最大红包收益。
先将第二类的公司预处理出来，然后在图上跑 \(dp\) 即可。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n, m;
cin >> n >> m;
vector <int> c(n + 1), cnt(n + 1);
for (int i = 1; i <= n; i ++ ){
cin >> c[i];
cnt[c[i]] ++ ;
}
vector <int> w(n + 1);
for (int i = 1; i <= n; i ++ )
cin >> w[i];
vector < vector <int> > G(n + 1);
for (int i = 1; i <= m; i ++ ){
int u, v;
cin >> u >> v;
G[u].push_back(v);
}
int sum = 0;
vector <int> idx(n + 1);
vector <bool> used(n + 1);
for (int i = 1; i <= n; i ++ ){
if (cnt[c[i]] > 1 && !used[c[i]]){
used[c[i]] = true;
idx[c[i]] = sum ++ ;
}
}
vector <int> state(n + 1);
for (int i = 1; i <= n; i ++ )
if (used[c[i]])
state[i] = 1 << idx[c[i]];
vector < vector <int> > dp(n + 1, vector<int>(1 << sum));
dp[1][state[1]] = w[c[1]];
int N = 1 << sum;
for (int i = 1; i <= n; i ++ ){
cout << *max_element(dp[i].begin(), dp[i].end()) << "\n";
for (int now = 0; now < N; now ++ )
if (dp[i][now])
for (auto j : G[i])
dp[j][now | state[j]] = max(dp[j][now | state[j]], dp[i][now] + (now & state[j] ? 0 : w[c[j]]));
}
return 0;
}
D. 修建道路
题意：
有 \(n\) 个村庄，在 \(i\) 和 \(j\) 村庄之间建立一条道路，花费 \(max_{i <= k <= j} a_k\) 的费用，问将所有村庄连接起来的最小花费。
思路：
因为花的是区间中的最大的费用，所以连接一个新的村庄，用当前最靠近目标村庄的村庄去连就行，答案就是 \(\sum_{i = 1}^{n - 1} max(a_i, a_{i + 1})\)。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n;
cin >> n;
vector <LL> a(n);
LL ans = 0;
for (int i = 0; i < n; i ++ ){
cin >> a[i];
if (i) ans += max(a[i - 1], a[i]);
}
cout << ans << "\n";
return 0;
}
G. 3G网络
题意：
有 \(n\) 个圆，圆心坐标告诉你，半径趋向于正无穷，问它们的交集和它们面积之和的比例。
思路：
半径正无穷，所以交集就是整个平面，有几个点分母就是一个平面，所以答案就是 \(\frac{1}{n}\)。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i ++ ){
int x, y;
cin >> x >> y;
}
cout << fixed << setprecision(12) << 1.0 / n << "\n";
return 0;
}
I. 驾驶卡丁车
题意：
一个 \(n * m\) 的地图，刚开始卡丁车在 '*' 的位置，'.' 表示空地，可以移动，'#' 表示障碍，不能过去，刚开始卡丁车向上走，速度为 0。
现在有 \(q\) 个指令，'L' 表示卡丁车左转 45°，'R' 表示卡丁车右转 45°，'U' 表示速度加 1，'D' 表示速度减 1，速度最低等于 0。
卡丁车碰到障碍后方向不变，速度变成 0。
问在每个指令发布后且卡丁车移动后的坐标及状态。若碰到障碍或者尝试移出地图，在坐标前输出 "Crash! "。
注意，卡丁车不能穿模，即当卡丁车斜着移动的时候，两边都是障碍，卡丁车是穿不过去的。
思路：
按题意模拟。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n, m, x, y;
cin >> n >> m;
vector < vector <char> > a(n + 1, vector<char>(m + 1));
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= m; j ++ ){
cin >> a[i][j];
if (a[i][j] == '*') x = i, y = j;
}
}
int q;
string s;
cin >> q >> s;
vector <int> dx = {-1, -1, -1, 0, 1, 1, 1, 0};
vector <int> dy = {-1, 0, 1, 1, 1, 0, -1, -1};
int d = 1, v = 0;
for (int i = 0; i < q; i ++ ){
if (s[i] == 'L') d = (d + 7) % 8;
else if (s[i] == 'R') d = (d + 1) % 8;
else if (s[i] == 'U') v ++ ;
else v = max(v - 1, 0);
bool ok = true;
for (int j = 1; j <= v; j ++ ){
int nx = x + dx[d], ny = y + dy[d];
if (nx < 1 || ny < 1 || nx > n || ny > m || a[nx][ny] == '#'){
ok = false;
break;
}
if (d % 2 == 0){
if (a[nx][y] == '#' && a[x][ny] == '#'){
ok = false;
break;
}
}
x = nx;
y = ny;
}
if (!ok){
cout << "Crash! ";
v = 0;
}
cout << x << " " << y << "\n";
}
return 0;
}
K. 音乐游戏
题意：
输出 '-' 的数量。
思路：
按题意模拟。
代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int ans = 0;
getchar();
for (int i = 0; i < n; i ++ ){
string s;
getline(cin, s);
for (auto c : s)
ans += (c == '-');
}
cout << ans << "\n";
return 0;
}