目录
Contest Info
[Practice Link](https://codeforc.es/gym/101981)
| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 7/13 | O | ! | - | O | O | - | O | ! | O | O | O | - | Ø |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. Adrien and Austin
题意：
有(n)个石头，标号为(1, cdots, n)，每一次可以移走连续的([1, k])个石头，问先手必胜还是后手必胜。
思路：
先手必输的状态为：
- (n = 0)
- (n \% 2 = 1, k = 1)
为什么其他情况先手必胜？
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
char *fi = "Adrien";
char *se = "Austin";
while (scanf("%d%d", &n, &k) != EOF) {
if (n == 0 || (n % 2 == 0 && k == 1)) {
puts(se);
} else {
puts(fi);
}
}
return 0;
}
D. Country Meow
题意：
三维里有(n)个点，找一个最小的球将所有点覆盖。
思路：
模拟退火求最小球覆盖。
代码：
#include <bits/stdc++.h>
using namespace std;
#define db double
#define N 110
const db eps = 1e-7;
int n;
struct node {
db x, y, z;
node() {
x = y = z = 0;
}
void scan() {
scanf("%lf%lf%lf", &x, &y, &z);
}
}a[N];
db dis(node a, node b) {
return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y) + 1.0 * (a.z - b.z) * (a.z - b.z));
}
db solve() {
db step = 10000, ans = 1e30, mt;
node c = node();
int s = 1;
while (step > eps) {
for (int i = 1; i <= n; ++i) {
if (dis(c, a[s]) < dis(c, a[i])) {
s = i;
}
}
mt = dis(c, a[s]);
ans = min(ans, mt);
c.x += (a[s].x - c.x) / mt * step;
c.y += (a[s].y - c.y) / mt * step;
c.z += (a[s].z - c.z) / mt * step;
step *= 0.98;
}
return ans;
}
int main() {
while (scanf("%d", &n) != EOF) {
for (int i = 1; i <= n; ++i) {
a[i].scan();
}
printf("%.16f
", solve());
}
return 0;
}
E.Eva and Euro coins
题意：
有两个01串(s、t)，问能够通过有限步的操作将(s)变成(t)。
操作为：
每次选择连续(k)个相同的字符，将其翻转，(0
ightarrow 1, 1
ightarrow 0)
思路：
我们考虑连续的(k)个相同字符，那么它可以任意移动。
比如说，(k = 4)的时候：
00001 -> 11111 -> 10000
这三步操作可以理解为把(1)从最后一位移动了第一位。
那么既然可以随便移动的话，我们可以认为直接把它们移出去了，而剩下的字符的相对位置是不会变的。
所以将所有连续的(k)个字符移走，判断剩下的字符组成的字符串是否相同，即表示(s)能否变到(t)
代码：
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
char s[N], t[N], sta[N];
int cnt[N], top;
int n, k;
void work(char *s) {
memset(cnt, 0, sizeof cnt);
top = 0;
for (int i = 1; i <= n; ++i) {
if (top == 0) {
sta[++top] = s[i];
cnt[top] = 1;
} else {
if (sta[top] == s[i]) {
cnt[top + 1] = cnt[top] + 1;
} else {
cnt[top + 1] = 1;
}
sta[++top] = s[i];
}
if (cnt[top] == k) {
top -= k;
}
}
for (int i = 1; i <= top; ++i) {
s[i] = sta[i];
}
s[top + 1] = 0;
}
int main() {
while (scanf("%d%d", &n, &k) != EOF) {
scanf("%s%s", s + 1, t + 1);
work(s); work(t);
puts(strcmp(s + 1, t + 1) == 0 ? "Yes" : "No");
}
return 0;
}
G.Pyramid
题意：
询问类似于这样的三角形中：
里面正三角形的个数是多少。
思路：
找了个规律，，答案是({n + 3 choose 4})
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll p = 1e9 + 7;
ll qmod(ll base, ll n) {
ll res = 1;
while (n) {
if (n & 1) {
res = res * base % p;
}
base = base * base % p;
n >>= 1;
}
return res;
}
int main() {
ll inv = qmod(24, p - 2);
int T; scanf("%d", &T);
while (T--) {
int n; scanf("%d", &n);
printf("%lld
", 1ll * n * (n + 1) % p * (n + 2) % p * (n + 3) % p * inv % p);
}
return 0;
}
I.Magic Potion
题意：
有(n)个士兵，(m)个怪兽，每个士兵初始的时候可以打一个怪兽，但是有(k)瓶药，每个士兵最多喝一瓶药，喝一瓶药可以多打一个怪兽。
士兵和怪兽之间有边，表示某个士兵可以打哪些怪兽，问最多打我的怪兽数量最多是多少？
思路：
网络流。
如果没有药，那么就是个简单的二分匹配。
但是这个和二分图-多重匹配有不一样。因为不知道把药给谁喝。
但是可以这么建图，跑网络流：
- (S)到所有士兵加一条流量为(1)的边。
- 所有士兵到它能打的怪兽加一条流量为(1)的边。
- 所有怪兽到(T)加一条流量为(1)的边。
- 再加一个点(C)，和(S)相连，流量为(k)。
- (C)到所有士兵加一条流量为(1)的边。
代码：
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 510
#define M 1000010
struct Edge {
int to, flow, nxt;
Edge() {}
Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
}edge[M << 2];
int head[N << 2], tot, dep[N << 2];
int S, T, n, m, k;
void init() {
memset(head, -1, sizeof head);
tot = 0 ;
}
void add(int u, int v, int w, int rw = 0) {
edge[tot] = Edge(v, head[u], w); head[u] = tot++;
edge[tot] = Edge(u, head[v], rw); head[v] = tot++;
}
bool BFS() {
memset(dep, -1, sizeof dep);
queue <int> q;
q.push(S);
dep[S] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = edge[i].nxt) {
if (edge[i].flow && dep[edge[i].to] == -1) {
dep[edge[i].to] = dep[u] + 1;
q.push(edge[i].to);
}
}
}
return dep[T] >= 0;
}
int DFS(int u, int f) {
if (u == T || f == 0) return f;
int w, used = 0;
for (int i = head[u]; ~i; i = edge[i].nxt) {
if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
w = DFS(edge[i].to, min(f - used, edge[i].flow));
edge[i].flow -= w;
edge[i ^ 1].flow += w;
used += w;
if (used == f) return f;
}
}
if (!used) dep[u] = -1;
return used;
}
int Dicnic() {
int ans = 0;
while (BFS()) {
ans += DFS(S, INF);
}
return ans;
}
int main() {
while (scanf("%d%d%d", &n, &m, &k) != EOF) {
init(); S = 0; T = n + m + 1; int C = n + m + 2;
add(S, C, k);
for (int i = 1; i <= n; ++i) {
add(S, i, 1);
add(C, i, 1);
}
for (int i = 1, sze, x; i <= n; ++i) {
scanf("%d", &sze);
while (sze--) {
scanf("%d", &x);
add(i, x + n, 1);
}
}
for (int i = 1; i <= m; ++i) add(i + n, T, 1);
printf("%d
", Dicnic());
}
return 0;
}
J.Prime Game
题意：
给出一个序列(a_1, cdots, a_n)。
定义：
[egin{eqnarray*}
mul(l, r) = prodlimits_{i = l}^r a_i
end{eqnarray*}
]
(fac(l, r))为(mul(l, r))中不同质因数的个数。
请计算：
[egin{eqnarray*}
sumlimits_{i = 1}^n sumlimits_{j = i}^n fac（l, r）
end{eqnarray*}
]
思路：
筛出(10^6)每个数的质因子，然后从右往左扫。
考虑在知道(fac(i, j))的答案，推出(fac(i - 1, j))的答案。
那么对于(a_{i - 1})中每个质因子，它产生贡献的区间是([i - 1, nx - 1])，(nx)表示这个质因子下一个出现的位置
那么倒着处理的时候顺带处理一下(nx)数组，再更新答案就好了。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000010
int n, a[N], nx[N];
int prime[N], tot, check[N];
vector <vector<int>> vec;
void init() {
memset(check, 0, sizeof check);
tot = 0;
for (int i = 2; i < N; ++i) {
if (!check[i]) {
prime[++tot] = i;
}
for (int j = 1; j <= tot; ++j) {
if (1ll * i * prime[j] >= N) break;
check[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
vec.clear(); vec.resize(N);
for (int i = 1; i <= tot; ++i) {
for (int j = prime[i]; j < N; j += prime[i]) {
vec[j].push_back(prime[i]);
}
}
}
int main() {
init();
while (scanf("%d", &n) != EOF) {
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
for (int i = 1; i <= 1000000; ++i) {
nx[i] = n + 1;
}
ll res = 0, base = 0;
for (int i = n; i >= 1; --i) {
for (auto it : vec[a[i]]) {
base += (nx[it] - i);
nx[it] = i;
}
res += base;
}
printf("%lld
", res);
}
return 0;
}
K.Kangaroo Puzzle
题意：
在一个(20 imes 20)的地图上，(1)表示有袋鼠，(0)表示有障碍物，边界外和障碍物上不能走。
要求给出一个(50000)步以内的操作，每一步操作为'L', 'R', 'U', 'D', 表示所有袋鼠一起动的方向，如果某个袋鼠下一个地方是不能走的，那么它那一步会忽略，使得所有袋鼠都聚集在一起。
思路：
随机输出(50000)个字符就好了，为什么呢？
代码：
#include <bits/stdc++.h>
using namespace std;
#define N 50
char G[N][N];
int n, m;
int main() {
srand(time(NULL));
char *s = "LRUD";
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 1; i <= n; ++i) {
scanf("%*s");
}
for (int i = 1; i <= 50000; ++i) {
putchar(s[rand() % 4]);
}
puts("");
}
return 0;
}
M.Mediocre String Problem
题意：
给出两个字符串(S)和(T)，问有多少个三元组((i, j, k))满足以下要求：
- (1 leq i leq j leq |s|)
- (1 leq k leq |t|)
- (j - i +1 > k)
- 将(s_i cdots s_j)和(t_1 cdots t_k)拼起来是一个回文串。
思路：
首先我们解析以下这四个条件：
- 相当于要从(s)串找一个子串，从(t)串中找一个前缀，并且(s)串中的子串长度要大于(t)串的子串长度
- 并且满足(s)串的子串的长度和(t)串子串长度相同的那段前缀刚好是(t)串子串的翻转
- 并且(s)串子串的剩余部分是个回文串
那么我们把(s)串翻转，求每个后缀(i)与(t)串的(LCP)，那么这部分再翻转回去，肯定存在一个(k)使得这两部分回文。
那么(LCP)的长度就是选择数量，那么左边还要再接一段回文串，用(Manacher)处理出每个端点结尾的回文串数量即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000010
char s[N], t[N];
struct ExKMP {
int Next[N];
int extend[N];
void get_Next(char *s) {
int lens = strlen(s + 1), p = 1, pos;
Next[1] = lens;
while (p + 1 <= lens && s[p] == s[p + 1]) ++p;
Next[pos = 2] = p - 1;
for (int i = 3; i <= lens; ++i) {
int len = Next[i - pos + 1];
if (len + i < p + 1) Next[i] = len;
else {
int j = max(p - i + 1, 0);
while (i + j <= lens && s[j + 1] == s[i + j]) ++j;
p = i + (Next[pos = i] = j) - 1;
}
}
}
void work(char *s, char *t) {
get_Next(t);
int lens = strlen(s + 1), lent = strlen(t + 1), p = 1, pos;
while (p <= lent && s[p] == t[p]) ++p;
p = extend[pos = 1] = p - 1;
for (int i = 2; i <= lens; ++i) {
int len = Next[i - pos + 1];
if (len + i < p + 1) extend[i] = len;
else {
int j = max(p - i + 1, 0);
while (i + j <= lens && j <= lent && t[j + 1] == s[i + j]) ++j;
p = i + (extend[pos = i] = j) - 1;
}
}
}
}exkmp;
struct Manacher {
char Ma[N << 1];
int Mp[N << 1];
int num[N << 1];
//字符串从0开始
void work(char *s) {
int l = 0, len = strlen(s);
Ma[l++] = '$';
Ma[l++] = '#';
for (int i = 0; i < len; ++i) {
Ma[l++] = s[i];
Ma[l++] = '#';
}
Ma[l] = 0;
int mx = 0, id = 0;
for (int i = 0; i < l; ++i) {
Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1;
while (Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++;
if (i + Mp[i] > mx) {
mx = i + Mp[i];
id = i;
}
}
for (int i = 0; i < l; ++i) num[i] = 0;
for (int i = 2; i < l; ++i) {
int r = i + Mp[i] - 1;
++num[i];
--num[r + 1];
}
for (int i = 2; i < l; ++i) num[i] += num[i - 1];
}
}man;
int main() {
while (scanf("%s%s", s + 1, t + 1) != EOF) {
int lens = strlen(s + 1);
reverse(s + 1, s + 1 + lens);
exkmp.work(s, t);
man.work(s + 1);
ll res = 0;
for (int i = 2; i <= lens; ++i) {
res += 1ll * (man.num[2 * (i - 1)]) * exkmp.extend[i];
}
printf("%lld
", res);
}
return 0;
}