链接：https://codeforces.com/gym/103389
A. 公交线路
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, x, y;
cin >> n >> x >> y;
x--, y--;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int m;
cin >> m;
vector<int> b(m);
i64 t = 0;
for (int i = 0; i < m; i++) {
cin >> b[i];
t *= 10;
t += b[i];
}
if (x > y) {
reverse(a.begin(), a.end());
x = n - 1 - x;
y = n - 1 - y;
}
i64 s1 = 0, s2 = 0;
for (int i = x + 1; i < x + 1 + m; i++) {
s1 *= 10;
s1 += a[i];
}
for (int i = x - 1; i >= max(0, x - m); i--) {
s2 *= 10;
s2 += a[i];
}
if (s1 == t) {
if (s2 == t) {
cout << "Unsure\n";
} else {
cout << "Right\n";
}
} else {
cout << "Wrong\n";
}
return 0;
}
D. 修建道路
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
i64 ans = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) {
ans += max(a[i], a[i - 1]);
}
cout << ans << '\n';
return 0;
}
F. 地图压缩
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int B = 114514;
constexpr i64 P = 1000000000039;
i64 *p;
void init(int N) {
p = new i64 [N + 1];
for (int i = 0; i <= N; i++) {
p[i] = 0;
}
p[0] = 1;
for (int i = 1; i <= N; i++) {
p[i] = p[i - 1] * B % P;
}
}
struct StringHash {
vector<i64> h;
StringHash() : h(1) {}
void push_back(char ch) {
h.push_back((h.back() * B + ch) % P);
}
i64 get(int l, int r) { // [l, r)
return (h[r] + __int128(h[l]) * (P - p[r - l])) % P;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init(2E3);
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<vector<StringHash>> hs(2, vector<StringHash>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
hs[0][i].push_back(a[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
hs[1][i].push_back(a[j][i]);
}
}
auto getcir = [&](const vector<i64> &s) {
int n = s.size();
vector<int> nex(n + 1);
int j = 0;
for (int i = 1; i < n; i++) {
while (j && s[i] != s[j]) {
j = nex[j];
}
if (s[i] == s[j]) {
j++;
}
nex[i + 1] = j;
}
return n - nex[n];
};
auto gets = [&](int d, int l, int r, int l1, int r1) {
vector<i64> s;
for (int i = l1; i < r1; i++) {
s.push_back(hs[d][i].get(l, r));
}
return s;
};
for (int i = 0; i < m; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--, y1--;
cout << getcir(gets(1, x1, x2, y1, y2)) * getcir(gets(0, y1, y2, x1, x2)) << '\n';
}
return 0;
}
G. 3G网络
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) {
auto &[x, y] = a[i];
cin >> x >> y;
}
cout << fixed << setprecision(12) << 1.0 / n << '\n';
return 0;
}
I. 驾驶卡丁车
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int sx = 0, sy = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == '*') {
sx = i;
sy = j;
break;
}
}
}
int v = 0;
int dx[] = {-1, -1, +0, +1, +1, +1, +0, -1};
int dy[] = {+0, +1, +1, +1, +0, -1, -1, -1};
int d = 0;
int q;
cin >> q;
string s;
cin >> s;
for (int i = 0; i < q; i++) {
if (s[i] == 'U') {
v = v + 1;
} else if (s[i] == 'L') {
d -= 1;
d += 8;
d %= 8;
} else if (s[i] == 'R') {
d += 1;
d %= 8;
} else {
v = max(v - 1, 0);
}
bool ok = 1;
for (int j = 0; j < v; j++) {
int tx = sx + dx[d];
int ty = sy + dy[d];
if (tx < 0 || ty < 0 || tx >= n || ty >= m || a[tx][ty] == '#') {
v = 0;
ok = 0;
cout << "Crash! " << sx + 1 << ' ' << sy + 1 << '\n';
break;
} else if (d % 2 == 1 && a[tx][sy] == '#' && a[sx][ty] == '#') {
v = 0;
ok = 0;
cout << "Crash! " << sx + 1 << ' ' << sy + 1 << '\n';
break;
} else {
sx = tx;
sy = ty;
}
}
if (ok) {
cout << sx + 1 << ' ' << sy + 1 << '\n';
}
}
return 0;
}
K. 音乐游戏
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
char ch;
int ans = 0;
while (cin >> ch) {
if (ch == '-') {
ans++;
}
}
cout << ans << '\n';
return 0;
}