A – Consecutive Sum Riddle
思博题，没什么好讲的。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
ll n;
scanf("%lld", &n), printf("%lld %lld\n", -n + 1, n);
}
return 0;
}
B – Special Numbers
算乘方的题，没什么好讲的。直接二进制分解后类似快速幂做就行了。
// B.cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int fpow(int bas, int tim)
{
int ret = 1;
while (tim)
{
if (tim & 1)
ret = 1LL * ret * bas % mod;
bas = 1LL * bas * bas % mod;
tim >>= 1;
}
return ret;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n, k;
scanf("%d%d", &n, &k);
int ret = 0, bas = 1;
while (k)
{
ret = (0LL + ret + bas * (k & 1)) % mod;
bas = 1LL * bas * n % mod;
k >>= 1;
}
printf("%d\n", ret);
}
return 0;
}
C – Make Them Equal
显然答案只有三种。零的结果显而易见，就是全 c 的情况。我们现在来分辨 1 和 2 的情况。
首先我们可以注意到，操作 n 和 n – 1 就可以把整个序列整理完，所以最差情况就是 2。
如何判断 1？
我们可以用调和级数的时间来标记那些非 c 位置的倍数，然后找一个没被标记的即可。
// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 200;
int T, n;
char str[MAX_N], cmdlet[10], rc;
bool vis[MAX_N];
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%s%s", &n, cmdlet, str + 1), rc = cmdlet[0];
bool flag1 = true;
for (int i = 1; i <= n; i++)
flag1 &= (str[i] == rc);
if (flag1)
puts("0");
else
{
if (str[n] == rc)
printf("1\n%d\n", n);
else
{
for (int i = 1; i <= n; i++)
vis[i] = true;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j += i)
if (str[j] != rc)
{
vis[i] = false;
break;
}
int pos = -1;
for (int i = 1; i <= n; i++)
if (vis[i])
pos = i;
if (pos != -1)
printf("1\n%d\n", pos);
else
printf("2\n%d %d\n", n - 1, n);
}
}
}
return 0;
}
D – The Number of Imposters
用并查集随便搞下啦。
// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int T, n, m, ufs[MAX_N], siz[MAX_N];
char cmdlet[20];
int find(int x) { return ufs[x] == x ? x : ufs[x] = find(ufs[x]); }
void merge(int x, int y)
{
int fx = find(x), fy = find(y);
if (fx != fy)
ufs[fx] = fy, siz[fy] += siz[fx];
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= (n << 1); i++)
ufs[i] = i, siz[i] = (i <= n);
for (int i = 1, u, v; i <= m; i++)
{
scanf("%d%d%s", &u, &v, cmdlet + 1);
if (cmdlet[1] == 'i')
merge(u, v + n), merge(u + n, v);
else
merge(u, v), merge(u + n, v + n);
}
bool flag = true;
for (int i = 1; i <= n; i++)
flag &= (find(i) != find(i + n));
if (flag)
{
int ans = 0;
for (int i = 1; i <= n; i++)
if (find(i) == i)
ans += max(siz[find(i)], siz[find(i + n)]);
for (int i = n + 1; i <= (n << 1); i++)
if (find(i) == i)
ans += max(siz[find(i)], siz[find(i - n)]);
ans >>= 1;
printf("%d\n", ans);
}
else
puts("-1");
}
return 0;
}
E – Rubik’s Cube Coloring
两个版本放到一起讲。
首先，从 E1 可知，一个深度为 \(x\) 的子树的方案数为：
\[ 4^{2^x – 1} \]
那么对于 E2 而言，我们可以用类似 Trie 树的方式建出一个虚树，然后做一个 DP 就行了。范围很小，可以随便写。
实现起来有些细节，可以看代码。
// E2.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200, mod = 1e9 + 7, opp[6] = {1, 0, 3, 2, 5, 4};
typedef long long ll;
int k, n, nodes[MAX_N][2], ptot, dep[MAX_N], tag[MAX_N], dp[MAX_N][6];
char cmdlet[10];
int mapper(char c)
{
switch (c)
{
case 'w':
return 0;
case 'y':
return 1;
case 'g':
return 2;
case 'b':
return 3;
case 'r':
return 4;
case 'o':
return 5;
}
return -1;
}
int fpow(int bas, int tim, int modulo)
{
int ret = 1;
while (tim)
{
if (tim & 1)
ret = 1LL * ret * bas % modulo;
bas = 1LL * bas * bas % modulo;
tim >>= 1;
}
return ret;
}
void insert(ll x, int typ)
{
int p = 1;
vector<int> seq;
while (x)
seq.push_back(x & 1LL), x >>= 1;
seq.pop_back();
reverse(seq.begin(), seq.end());
for (int c : seq)
{
if (nodes[p][c] == 0)
nodes[p][c] = ++ptot, dep[ptot] = dep[p] + 1;
p = nodes[p][c];
}
tag[p] = typ;
}
void dfs(int u)
{
int udp[2][6], sum[2];
memset(udp, 0, sizeof(udp)), sum[0] = sum[1] = 0;
for (int dir = 0; dir < 2; dir++)
if (nodes[u][dir])
{
dfs(nodes[u][dir]);
for (int d = 0; d < 6; d++)
udp[dir][d] = dp[nodes[u][dir]][d];
}
for (int d = 0; d < 6; d++)
sum[0] = (0LL + sum[0] + udp[0][d]) % mod, sum[1] = (0LL + sum[1] + udp[1][d]) % mod;
for (int d = 0; d < 6; d++)
if (d == tag[u] || tag[u] == -1)
{
int ls, rs;
if (nodes[u][0] == 0)
ls = fpow(4, (0LL + fpow(2, k - dep[u], mod - 1) + mod - 2) % (mod - 1), mod);
else
ls = (0LL + sum[0] + (mod - udp[0][d]) % mod + (mod - udp[0][opp[d]]) % mod) % mod;
if (nodes[u][1] == 0)
rs = fpow(4, (0LL + fpow(2, k - dep[u], mod - 1) + mod - 2) % (mod - 1), mod);
else
rs = (0LL + sum[1] + (mod - udp[1][d]) % mod + (mod - udp[1][opp[d]]) % mod) % mod;
dp[u][d] = 1LL * ls * rs % mod;
}
}
int main()
{
memset(tag, -1, sizeof(tag)), dep[1] = ptot = 1;
scanf("%d%d", &k, &n);
for (ll i = 1, u; i <= n; i++)
scanf("%lld%s", &u, cmdlet + 1), insert(u, mapper(cmdlet[1]));
dfs(1);
int ans = 0;
for (int d = 0; d < 6; d++)
ans = (0LL + ans + dp[1][d]) % mod;
printf("%d\n", ans);
return 0;
}