感觉这场题目的难题难度都差不多，不过都是窝做不出的好题就对了
G.智乃与模数
给定，求
这个集合中前
大的元素和。
赛时因为没时间了，痛失这道数论分块。其实分块数肯定不超过，每个块里面都是等差数列，双
二分就完事了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>
const int inf = 4e18;
const int N = 1e6 + 5;
int t = 1, k, n;
int tot;
int red[N], start[N]; // red记录该块的公差(的相反数)，start记录该块最大元素的值
int check(int mid)
{
int ret = 0;
for (int i = 1; i <= tot; i++)
{
if (start[i] < mid)
continue;
ret += 1 + (start[i] - mid) / red[i];
}
return ret;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k; // 最多分2\sqrt n块，双log二分
// 前\sqrt n个可以预处理，因为这些块必定都只有一个元素
int now = 1;
for (; now * now <= n; now++)
red[++tot] = n / now, start[tot] = n % now;
// 处理剩余最多\sqrt n个块
while (now <= n)
{
int L = now, R = n, cur = n / now; // 二分找这个块的最后一个位置
while (L <= R)
{
int mid = L + R >> 1;
if (n / mid != cur)
R = mid - 1;
else
L = mid + 1;
}
red[++tot] = cur, start[tot] = n % now;
now = R + 1;
}
// 开始二分答案（可以完全被接受的最大值）
int L = 1, R = n / 2;
while (L <= R)
{
int mid = L + R >> 1;
if (check(mid) > k)
L = mid + 1;
else
R = mid - 1;
}
int ans = 0, remain = k;
for (int i = 1; i <= tot; i++)
{
if (start[i] < L)
continue;
int add = 1 + (start[i] - L) / red[i]; // 这个块提供的贡献（数量）
remain -= add;
ans += start[i] * add - add * (add - 1) / 2 * red[i];
}
ans += (L - 1) * remain;
cout << ans;
return 0;
}
H.智乃与黑白树
个节点无根树，每个节点都是黑或白色，求将树中每一条边分别割断后，产生的两棵子树的黑白简单路径和（即从黑点出发到白点的所有的简单路径和）。
换根好题，虽然代码烦了一点点。合并两个子树的信息时，要注意需要维护好两种节点的个数和产生的贡献（贡献!=个数，这和上次第二场中的题目很类似）以及对应的子树答案。换根时先当前子树，再将父亲节点
过去即可。时间复杂度
。
注意删除操作和连接操作是完全反过来的，不仅是+变成-，在代码实现上也是倒的。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>
const int inf = 4e18;
const int N = 1e5 + 5;
int t = 1, n, u, v;
string s;
int tot[N][2], add[N][2]; // 分别记录提供的数量和贡献
int ans[N]; // 计算当前子树的答案
int fa[N];
bool type[N];
vector<PII> g[N];
PII ver[N];
PII res[N]; // 对应的答案
void dfs1(int pos)
{
tot[pos][type[pos]] = 1;
for (PII i : g[pos])
{
if (i[0] == fa[pos])
continue;
fa[i[0]] = pos;
dfs1(i[0]);
ans[pos] += ans[i[0]];
for (int j = 0; j < 2; j++)
ans[pos] += add[pos][j] * tot[i[0]][j ^ 1] + (add[i[0]][j] + tot[i[0]][j]) * tot[pos][j ^ 1];
for (int j = 0; j < 2; j++)
add[pos][j] += add[i[0]][j] + tot[i[0]][j];
for (int j = 0; j < 2; j++)
tot[pos][j] += tot[i[0]][j];
}
}
void dfs2(int pos)
{
for (PII i : g[pos])
{
if (i[0] == fa[pos])
continue;
// 删掉对应子树的贡献
for (int j = 0; j < 2; j++)
tot[pos][j] -= tot[i[0]][j];
for (int j = 0; j < 2; j++)
add[pos][j] -= add[i[0]][j] + tot[i[0]][j];
for (int j = 0; j < 2; j++)
ans[pos] -= add[pos][j] * tot[i[0]][j ^ 1] + (add[i[0]][j] + tot[i[0]][j]) * tot[pos][j ^ 1];
ans[pos] -= ans[i[0]];
int cnt = i[1];
res[cnt][0] = (ver[cnt][0] == pos ? ans[pos] : ans[i[0]]);
res[cnt][1] = (ver[cnt][1] == pos ? ans[pos] : ans[i[0]]);
// 将其他子树的贡献移动过去
swap(pos, i[0]);
ans[pos] += ans[i[0]];
for (int j = 0; j < 2; j++)
ans[pos] += add[pos][j] * tot[i[0]][j ^ 1] + (add[i[0]][j] + tot[i[0]][j]) * tot[pos][j ^ 1];
for (int j = 0; j < 2; j++)
add[pos][j] += add[i[0]][j] + tot[i[0]][j];
for (int j = 0; j < 2; j++)
tot[pos][j] += tot[i[0]][j];
swap(pos, i[0]);
dfs2(i[0]);
// 撤回其他子树的贡献
swap(pos, i[0]);
for (int j = 0; j < 2; j++)
tot[pos][j] -= tot[i[0]][j];
for (int j = 0; j < 2; j++)
add[pos][j] -= add[i[0]][j] + tot[i[0]][j];
for (int j = 0; j < 2; j++)
ans[pos] -= add[pos][j] * tot[i[0]][j ^ 1] + (add[i[0]][j] + tot[i[0]][j]) * tot[pos][j ^ 1];
ans[pos] -= ans[i[0]];
swap(pos, i[0]);
// 加回这棵子树的贡献
ans[pos] += ans[i[0]];
for (int j = 0; j < 2; j++)
ans[pos] += add[pos][j] * tot[i[0]][j ^ 1] + (add[i[0]][j] + tot[i[0]][j]) * tot[pos][j ^ 1];
for (int j = 0; j < 2; j++)
add[pos][j] += add[i[0]][j] + tot[i[0]][j];
for (int j = 0; j < 2; j++)
tot[pos][j] += tot[i[0]][j];
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> s;
s = ' ' + s;
for (int i = 1; i <= n; i++)
type[i] = s[i] == 'b';
for (int i = 1; i < n; i++)
{
cin >> u >> v;
g[u].push_back({v, i}), g[v].push_back({u, i});
ver[i] = {u, v};
}
dfs1(1);
dfs2(1);
for (int i = 1; i < n; i++)
cout << res[i][0] << ' ' << res[i][1] << '\n';
return 0;
}
I.智乃的兔子跳
找到一个公差不是的等差数列，使其覆盖给定数列中最多的点。公差
至少能覆盖
个点很容易想到，所以其他的必须超过这个值。
这里随机化还是有点难想到的，随机取两个不同的数，所得等差数列有
概率就是正确答案（如果正确答案公差不是
的话）。重复个
次，失败概率将无限趋近于
。
这题的代码实现也很玄，map竟然过不了QAQ
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>
const int inf = 4e18;
const int N = 1e6 + 5;
int t = 1, n;
int ans, a_1, D, gap;
int arr[N];
PII get_random;
int Rand()
{
return ((long long)rand() << 15ll | (long long)rand()) % n + 1;
}
void check(int p, int d)
{
int now = 0;
for (int i = 1; i <= n; i++)
if ((arr[i] - arr[p]) % d == 0)
now++;
if (now > ans)
ans = now, a_1 = arr[p] % d, D = d;
}
void Sep(int m, int p)
{
int now = m;
for (int i = 2; i * i <= now; i++)
{
if (now % i == 0)
{
while (now % i == 0)
now /= i;
check(p, i);
}
}
if (now != 1)
check(p, now);
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
srand(time(0));
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
if (n == 1)
{
cout << arr[1] << ' ' << 2;
return 0;
}
ans = 1, a_1 = arr[1], D = 2;
for (int test = 0; test < 100; test++)
{
do
{
get_random = {Rand(), Rand()};
gap = abs(arr[get_random[0]] - arr[get_random[1]]);
} while (!gap);
Sep(gap, get_random[0]);
}
cout << a_1 << ' ' << D;
return 0;
}
B.智乃的质数手串
给一个环形串，只有当相邻两个珠子数字和是质数才能取下左侧的那个；特别地，只剩一个的话可以直接取下。求是否可行+方案。
破环成链必然。可以发现：由于删除的是前面那个珠子，因此对后面的珠子是否会被删其实没有任何影响。于是想到用队列处理，又由于环的长度实际只有，因此使用单调队列，及时删掉超出范围的珠子即可。时间复杂度
。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>
const int inf = 4e18;
const int N = 2e5 + 5;
int t = 1, n;
int arr[N];
deque<int> deq;
vector<int> out;
// 素数筛板子
int prime[N], tot;
bool notprime[N];
bool remain[N];
void Prime(int range)
{
for (int i = 2; i <= range; i++)
{
if (!notprime[i])
prime[++tot] = i;
for (int j = 1; j <= tot && i * prime[j] <= range; j++)
{
notprime[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
}
void Add(int pos)
{
if (deq.size() && deq.front() <= pos - n)
deq.pop_front(); // 这个是用不到的
while (deq.size() && !notprime[arr[deq.back()] + arr[pos]]) // 让后面的把前面挤掉
{
out.push_back(deq.back());
deq.pop_back();
}
deq.push_back(pos);
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
Prime(2e5);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = n + 1; i <= 2 * n; i++)
arr[i] = arr[i - n];
for (int i = 1; i <= n - 1; i++)
Add(i);
for (int i = n; i <= 2 * n; i++)
{
Add(i);
if (deq.size() == 1)
{
cout << "Yes\n";
for (int j : out)
{
if (j <= i - n)
continue;
cout << (j - 1) % n << ' ';
remain[(j - 1) % n] = 1;
}
for (int j = 0; j < n; j++)
if (!remain[j])
{
cout << j << ' ';
break;
}
return 0;
}
}
cout << "No\n";
return 0;
}
J.智乃画二叉树
炒鸡大模拟，没啥好说的，不太想写._.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1 << 30;
const int MAXN = 200005;
const int MAXM = 5005;
int n, ch[MAXN][2], fx[MAXN], fy[MAXN], l2[MAXN], dch[MAXN][2], mp_tree[MAXN];
bool vis[MAXN], is_root[MAXN];
char s[MAXM][MAXM];
//Adapted from authorized solution
int lowbit(int x) {
return x & -x;
}
void dfs(int root1, int root2) {
assert(root1!=0&&root2!=0);
mp_tree[root1] = root2;
vis[root1] = true;
for (int i = 0; i <= 1; ++i) {
if (ch[root2][i] != -1) {
dfs(dch[root1][i], ch[root2][i]);
}
}
}
int cal_deep(int root) {
int ret = 0;
for (int i = 0; i <= 1; ++i) {
if (ch[root][i] != -1) {
ret = max(ret, cal_deep(ch[root][i]) + 1);
}
}
return ret;
}
void draw_node(int id, int x) {
sprintf(s[fx[l2[lowbit(id)]]] + fy[id], "%d", x);
if (x < 10) {
s[fx[l2[lowbit(id)]]][fy[id] + 1] = ' ';
}
s[fx[l2[lowbit(id)]] - 1][fy[id]] = '_';
s[fx[l2[lowbit(id)]] - 1][fy[id] + 1] = '_';
s[fx[l2[lowbit(id)]]][fy[id] - 1] = '/';
s[fx[l2[lowbit(id)]]][fy[id] + 2] = '\\';
s[fx[l2[lowbit(id)]] + 1][fy[id] - 1] = '\\';
s[fx[l2[lowbit(id)]] + 1][fy[id]] = '_';
s[fx[l2[lowbit(id)]] + 1][fy[id] + 1] = '_';
s[fx[l2[lowbit(id)]] + 1][fy[id] + 2] = '/';
}
void draw_left_line(int id) {
int x = fx[l2[lowbit(id)]] + 2;
int y = fy[id] - 1;
while (s[x][y] == '\0') {
s[x][y] = '/';
x++, y--;
}
}
void draw_right_line(int id) {
int x = fx[l2[lowbit(id)]] + 2;
int y = fy[id] + 2;
while (s[x][y] == '\0') {
s[x][y] = '\\';
x++, y++;
}
}
signed main() {
fx[1] = fy[1] = l2[1] = 1;
for (int i = 2; i <= 180; ++i) {
fx[i] = fx[i - 1] * 2 + 2;
fy[i] = fy[i - 1] + 3;
l2[i] = l2[i / 2] + 1;
}
for (int i = 1; i <= 180; ++i) {
fx[i] = 200 - fx[i];
if (lowbit(i) != 1) {
dch[i][0] = i - lowbit(i >> 1);
dch[i][1] = i + lowbit(i >> 1);
}
}
scanf("%lld %*lld", &n);
for (int i = 1; i <= n; ++i) {
is_root[i] = true;
}
for (int i = 1; i <= n; ++i) {
scanf("%lld %lld", &ch[i][0], &ch[i][1]);
is_root[ch[i][0]] = is_root[ch[i][1]] = false;
}
int root;
for (int i = 1; i <= n; ++i) {
if (is_root[i]) {
root = i;
}
}
int froot = 1 << cal_deep(root);
dfs(froot, root);
for (int i = 1; i < 180; ++i) {
if (vis[i]) {
draw_node(i, mp_tree[i]);
}
}
for (int i = 1; i < 180; ++i) {
if (vis[i] && ch[mp_tree[i]][0] != -1) {
draw_left_line(i);
}
if (vis[i] && ch[mp_tree[i]][1] != -1) {
draw_right_line(i);
}
}
int lx = INF, rx = -INF, ly = INF, ry = -INF;
for (int i = 0; i <= 200; ++i) {
for (int j = 0; j <= 2000; ++j) {
if (s[i][j]) {
lx = min(lx, i);
rx = max(rx, i);
ly = min(ly, j);
ry = max(ry, j);
}
}
}
for (int i = lx - 1; i <= rx + 1; ++i) {
for (int j = ly - 1; j <= ry + 1; ++j) {
if (i == lx - 1 || i == rx + 1 || j == ly - 1 || j == ry + 1) {
printf("*");
} else {
printf("%c", s[i][j] ? s[i][j] : ' ');
}
}
printf("\n");
}
return 0;
}
京公网安备 11010502036488号