A. Splitting into digits
Solved.
#include <bits/stdc++.h>
using namespace std; int n; void solve()
{
printf("%d\n", n);
for (int i = ; i <= n; ++i) printf("%d%c", , " \n"[i == n]);
} int main()
{
while (scanf("%d", &n) != EOF)
solve();
return ;
}
B. Game with string
Solved.
#include <bits/stdc++.h>
using namespace std; #define N 100010
char s[N]; int main()
{
while (scanf("%s", s + ) != EOF)
{
stack <char> sta;
int cnt = ;
for (int i = , len = strlen(s + ); i <= len; ++i)
{
if (!sta.empty() && sta.top() == s[i]) sta.pop(), ++cnt;
else sta.push(s[i]);
}
puts(cnt & ? "Yes" : "No");
}
return ;
}
C. Grid game
Solved.
#include <bits/stdc++.h>
using namespace std; #define N 1010
char s[N]; int main()
{
while (scanf("%s", s + ) != EOF)
{
int x = , y = ;
for (int i = , len = strlen(s + ); i <= len; ++i)
{
if (s[i] == '')
{
printf("%d %d\n", , x % ? : );
++x;
}
else
{
printf("%d %d\n", , y % + );
++y;
}
}
}
return ;
}
D. Game with modulo
Solved.
题意：
交互题
猜数，猜一个$a$
每次询问格式为$(x, y)$
返回结果有两种
$x \;if (x \; mod\; a) >= (y \;mod\; a)$
$y \;if (x \;mod\; a) < (y \;mod\; a) $
思路：
我们考虑 从小到大倍增，去找到$a的一个单调范围$
比如说$1, 2, 4, 8, 16, 32 如果某一次询问中返回了x$
那么说明$a在询问的(x, y)范围中 并且2 \cdot a 不在这个范围内$
因为是从小到大进行倍增
那么我们考虑某一次询问是$(x, 2\cdot x)$
$a在其中$
$如果 a > x, 那么必然有x >= 2 \cdot x - a$
$如果a = x 那么必然有 x \;mod\;a = 2 \cdot x \;mod\; a$
那么这个区间就具有一个单调性，可以进行二分
#include <bits/stdc++.h>
using namespace std; char op[]; bool check(int x, int y)
{
printf("? %d %d\n", x, y);
fflush(stdout);
scanf("%s", op);
return op[] == 'y';
} void solve(int l, int r)
{
int base = ;
for (int i = l; i <= r; i += base, base <<= )
{
printf("? %d %d\n", i, i + base);
fflush(stdout);
scanf("%s", op);
if (op[] == 'x')
{
int l = i + , r = i + base - , res = -;
while (r - l >= )
{
int mid = (l + r) >> ;
if (check(i, mid))
{
l = mid + ;
res = mid;
}
else
{
r = mid - ;
}
}
if (res == -) res = i;
printf("! %d\n", res + );
fflush(stdout);
return;
}
} } int main()
{
while (scanf("%s", op) && op[] != 'e')
solve(, );
return ;
}
E. Johnny Solving
Upsolved.
题意：
给出一个无向图，没有重边和自环，每个点的度数至少是3
要求找出一个长度至少为$\frac{n}{k}的简单路径$
或者找出$至少k个环，每个环的长度至少为3，并且环的长度不被3整除，并且环中有一个点只属于这个环$
思路：
首先跑一棵$DFS树，如果某个叶子结点的深度>= \frac{n}{k} 那么直接输出这条简单路径$
$否则叶子结点个数肯定大于 k 个$
证明
$我们假设每个叶子结点到根节点的距离为x_1, x_2, \cdots x_c$
那么$x_1 + x_2 + \cdots + x_c >= n$
$那么根据抽屉原理 max(x_1, x_2, \cdots x_c) >= \frac{n}{c}$
$又 \frac {n}{c} < \frac{n}{k} 所以 c > k$
再考虑对于一个叶子结点u来说，它度数至少为$3$
$考虑 它的两条返祖边连向x, y 我们令deep[x] < deep[y]$
$那么这个时候有三个环 dist(x,u) + 1, dist(y, u) + 1, dist(x, y) + 2$
$首先证明三个环的长度都>= 3$
$因为没有重边，所以dist(x, u) 和 dist(y, u) >= 2 = 3 - 1$
$又x和y是不同的两点 所以 dist(x, y) >= 1 = 3 - 2$
$再证明三个环的长度至少有一个不被3整除$
$我们假设三个环的长度都被3整除，那么有$
$(dist(x, u) + 1) \% 3 == 0$
$(dist(y, u) + 1) \% 3 == 0$
$(dist(x, y) + 1) \% 3 == 0$
$又 dist(x, u) = (dist(y, u) + dist(x, y))$
$所以 dist(x, y) \% 3 == 0$
那么$(dist(x, y) + 2) \% 3 != 0$
$与已知矛盾, 得证$
#include <bits/stdc++.h>
using namespace std; #define N 300010
int n, m ,k;
vector <int> G[N]; int fa[N], vis[N], deep[N], Max, pos;
void DFS(int u)
{
vis[u] = ;
if (deep[u] > Max)
{
Max = deep[u];
pos = u;
}
for (auto v : G[u]) if (!vis[v])
{
fa[v] = u;
deep[v] = deep[u] + ;
DFS(v);
}
} vector < vector <int> > res;
int isleaf[N];
void work(int u)
{
vis[u] = ;
if (!isleaf[u])
{
if (res.size() >= k) return;
int x = -, y = -;
for (auto v : G[u]) if (v != fa[u])
{
if (x == -) x = v;
else if (y == -) y = v;
else break;
}
if (deep[x] > deep[y]) swap(x, y);
vector <int> tmp; int it = -, top = -;
if ((deep[u] - deep[y] + ) % )
{
it = u; top = fa[y];
}
else if ((deep[u] - deep[x] + ) % )
{
it = u; top = fa[x];
}
else
{
tmp.push_back(u);
it = y; top = fa[x];
}
while (it != top) tmp.push_back(it), it = fa[it];
res.push_back(tmp);
}
else for (auto v : G[u]) if (!vis[v]) work(v);
} int main()
{
while (scanf("%d%d%d", &n, &m, &k) != EOF)
{
for (int i = ; i <= n; ++i) G[i].clear();
for (int i = , u, v; i <= m; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
deep[] = ; Max = ;
fa[] = ;
DFS();
if (Max > n / k)
{
puts("PATH");
vector <int> res;
int it = pos;
while (it)
{
res.push_back(it);
it = fa[it];
}
int len = res.size();
printf("%d\n", len);
for (int i = ; i < len; ++i) printf("%d%c", res[i], " \n"[i == len - ]);
}
else
{
puts("CYCLES");
memset(vis, , sizeof vis);
memset(isleaf, , sizeof isleaf);
for (int i = ; i <= n; ++i) isleaf[fa[i]] = ;
work();
for (int i = ; i < k; ++i)
{
auto it = res[i];
int len = it.size();
printf("%d\n", len);
for (int j = ; j < len; ++j) printf("%d%c", it[j], " \n"[j == len - ]);
}
}
}
return ;
}