2021牛客寒假算法基础集训营1
A 串
dp, f[i][0~2] 表示长度为i, 状态为(没出现过(us, u), 出现过(u), 出现过(us)), 转移
f[i][0] = f[i - 1][0] * 25; //出去字母 u
f[i][1] = f[i - 1][1] * 25 + f[i - 1][0]; //除去字母s, 状态[0] 拼接字母 u
f[i][2] = f[i - 1][2] * 26 + f[i - 1][1]; //随便拼接, 状态[1]拼接s
B 括号
构造, 先放 50000 ')', 在最左边放 k / 50000 个 '(', 剩下的 k % 50000 的放一个 '(' 在 5000 个')'的确定位置
int main() {
int n; cin >> n;
for (int i = 0; i < n / 50000; ++i) cout << '(';
for (int i = 50000; i > n % 50000; --i) cout << ')';
cout << '(';
for (int i = n % 50000; i; --i) cout << ')';
return 0;
}
C 红和蓝
按题意写就行了, 叶子节点必须和唯一相连的父亲节点颜色相同,
按照dfs搜一遍, 发现没染色的孩子, 直接绑定这个孩子和当前节点,
最后再染色即可
vector<int> h[N];
int a[N], n;
bool col[N];
void dfs(int x, int fa) {
for (auto y : h[x]) if (y != fa) {
dfs(y, x);
if (!a[y] && !a[x]) a[x] = y, a[y] = x;
}
}
void dfs2(int x, int fa, bool c) {
col[x] = c;
for (auto y : h[x]) if (y != fa)
dfs2(y, x, c ^ (a[x] != y));
}
int main() {
cin >> n;
for (int i = 2; i <= n; ++i) {
int u, v; cin >> u >> v;
h[u].push_back(v); h[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; ++i) if (!a[i]) return cout << -1, 0;
dfs2(1, 0, 1);
for (int i = 1; i <= n; ++i) cout << (col[i] ? 'R' : 'B');
return 0;
}
D 点一成零
答案等于 每个连通块的大小相乘 和 连通块数量的全排列
每次变 1, 先把联通起来的块的贡献减去, 最后把通过新的 1 链接起来的连通块连起来即可
int n, f[N * N], sz[N * N], d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int mp[N][N], k;
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void unit(int x, int y) { x = find(x); y = find(y); if (x != y) f[y] = x, sz[x] += sz[y]; }
long long qpow(long long a, int b) {
long long ans = 1;
for (; b; b >>= 1, a = a * a % mod) if (b & 1) ans = ans * a % mod;
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
scanf("%1d", mp[i] + j); f[i * n + j] = i * n + j; sz[i * n + j] = 1;
if (mp[i][j] && i && mp[i - 1][j]) unit(i * n + j, (i - 1) * n + j);
if (mp[i][j] && j && mp[i][j - 1]) unit(i * n + j, i * n + j - 1);
}
long long ans = 1, cnt = 0;
for (int i = 0; i < n * n; ++i) if (f[i] == i && mp[i / n][i % n]) ans = ans * sz[i] % mod * ++cnt % mod;
for (cin >> k; k; --k) {
int x, y; cin >> x >> y;
if (mp[x][y]) { cout << (cnt ? ans : 0) << '
'; continue; }
int fx = find(x * n + y), fy;
mp[x][y] = 1; ans = ans * ++cnt % mod;
for (int i = 0; i < 4; ++i) {
int dx = x + d[i][0], dy = y + d[i][1];
if (min(dx, dy) < 0 || max(dx, dy) >= n || !mp[dx][dy]) continue;
fy = find(dx * n + dy);
if (fx == fy) continue;
ans = ans * qpow(sz[fy], mod - 2) % mod * qpow(cnt--, mod - 2) % mod;
unit(fx, fy);
}
ans = ans * sz[fx] % mod;
printf("%lld
", ans);
}
return 0;
}
E 三棱锥之刻
通过高中的计算机和, 确定在某个面的喷洒园, 在判断和正三角形的关系 (包含, 相切, 既不包含也不相切) 最后一中情况比较难算
求角度的cos算面积占比即可
double a, r, d;
int main() {
cin >> a >> r; d = a * sqrt(3) / 6;
r = sqrt(r * r - a * a / 24);
if (fabs(r) < eps) return cout << 0, 0;
if (d > r) return cout << precision(3) << 4 * r * r * PI, 0;
if (r > d * 2) return cout << precision(3) << sqrt(3) * a * a, 0;
double di = sqrt(r * r - a * a / 12), ans = di * d * 3, q = acos(d / r) * 3;
cout << precision(3) << 4 * (ans + (PI - q) * r * r);
return 0;
}
F 对答案一时爽
贪心
好玩的数字游戏
模拟, 写的有点丑, 就不放代码了, 按照提议模拟就行
H 幂塔个位数的计算
n == 1, 直接输出个位数 break
简单观察可得 a mod 10 = 0, 1, 5, 6, 9 时, 个位数不变(这不用证了吧....)
然后就是找 2, 3, 4, 7, 8 的乘方 mod 10的循环节
$2^1 mod 10=2,2^2 mod 10=4,2^3 mod 10=8,2^4 mod 10=6$ 循环节为 2,4,8,6
>同理 $3:3,9,7,1$;
$4:4,6;$
$7:7,9,3,1;$
$8:8,4,2,6;$
>先来看当 $a mod 10=2$的 $a^a$ 因为 $a mod 10=2$ 即 a为偶数, 则 $a mod 4 = 0(4 mod 4), 2$
故 $a^a mod 10=4,6$ 当 $a mod 4 == 0(4 mod 4) 为 6$; $a mod 4 == 2$时, 为4
对于 $a^{a^a}$ 呢? 因为 $a mod 10=2$, 所以a至少包含一个2, 则$a^a$至少包含两个2
故$a^a mod 4=0$ 故对于 $a^{a^a} mod 10=6$ 准确的说是 $a mod 10=2$, n==2 && $a mod 4 == 2$ 则 ans = 4 否则为 6
>$a mod 10 == 8$ 同理和 2 一样
>$a mod 10 == 4$, 对于4循环节是2, 直接当 n > 1, 则 ans = 6
>$a mod 10 == 3$, 因为a是奇数, 故 $a mod 4 = 1 or 3$
当 $a mod 4=1$, $a^a mod 10=3$; 当 $a mod 4=3$, $a^a mod 10=7$
对于$a^{a^a}$, 当 $a mod 4=1$, 则$a^a mod 4=a*a*a..*a mod 4=1$, 则$a^{a^a} mod 10=3$;
当 $a mod 4=3$, 则$a^a mod 4=(a*a mod 4)*(a*a mod 4)...*(a*a mod 4)*a mod 4=3$, 则$a^{a^a} mod 10=7$ 因为a是奇数啊, $a^a$是奇数个a在相乘
发现了吗指数%10在 3, 7之间交替!!
>$a mod 10 == 7$, 同 $a mod 10 == 3$ 指数在 7, 3之间交
替```c++
int main() {
cin >> a >> n;
if (n == "1") return cout << a.back(), 0;
int x = (a.back() ^ '0' + (a.size() - 1 ? (a[a.size() - 2] ^ '0') * 10 : 0 )) % 4;
switch (a.back() ^ '0') {
case 0 : case 1 : case 5 : case 6 : case 9 : cout << (a.back() ^ '0'); break;
case 2 : case 8 : cout << (n == "2" && x == 2 ? 4 : 6); break;
case 3 : cout << (x == 1 ? 3 : 7); break;
case 4 : cout << 6; break;
case 7 : cout << (x == 1 ? 7 : 3); break;
}
return 0;
}
## I 限制不互素对的排列
n/2 个偶数 最多再让6放到最右边和3相邻,
```c++
int ans[N], tot;
int v[N];
int main() {
cin >> n >> m;
if (n < 4 && m) return cout << -1, 0;
if (n < 6 && m > 1) return cout << -1, 0;
if (!m) for (int i = 1; i <= n; ++i) cout << i << ' ';
else if (m == n / 2){
cout << "2 4 ";
for (int i = 8; i <= n; i += 2) cout << i << ' ';
cout << "6 3 1 ";
for (int i = 5; i <= n; i += 2) cout << i << ' ';
} else {
for (int i = 2, j = 0; j <= m; ++j, i += 2) cout << i << ' ', v[i] = 1;
for (int i = 1; i <= n; ++i) if (!v[i]) cout << i << ' ';
}
return 0;
}
J 一群小青蛙呱蹦呱蹦呱
只有当某个质数pri[i] > 2, 且存在 2*pri[i] <= n, 才能对答案做贡献
对于 2, 存在 6才能做贡献, 直接晒质数就行 正好 1.6e8 / 2 = 7e7, 空间差不多
void init(int n) {
for (int i = 2; i <= n; ++i) {
if (!v[i]) pri[++tot] = i;
for (int j = 1; j <= tot && pri[j] <= n / i; ++j) {
v[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
int main() {
long long n; cin >> n; init(n >> 1);
if (n < 6) return cout << "empty", 0;
long long ans = 1;
while (ans * 2 <= n / 3) ans = ans * 2 % mod;
for (int i = 2; i <= tot; ++i) {
long long c = pri[i];
while (c * pri[i] <= n / 2) c *= pri[i];
ans = ans * c % mod;
}
cout << ans;
return 0;
}