#858 div2
A:
题目:
现在一个点在二维平面的 x1 y1, 要移动它到 x2 y2。 有两种操作。
1.x + 1, y + 1
2.x - 1, y
思路:
不难发现 y 只能加不能减。 所以先考虑 y 能不能到达。
其次到达 y 之后, x 只能减,不能加。 判断这两种情况即可
代码
void solved()
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >>y2;
if(y2 < y1 )
{
cout << "-1" << endl;
return;
}
int ans = 0;
ans += y2 - y1;
if(x1 + ans < x2)
{
cout << "-1" << endl;
return;
}
ans += x1 + ans - x2;
cout << ans << endl;
}
B
题目:
现在存在一个数组,把数组变为 a1 + a2, a2 + a3.., 问你 mex 的值最小是多少。可以任意改变数组 的顺序。
思路:
因为 a_i 都是整数,所以我们首先考虑 0,如果全是 0,那么就是 1。
如果不全是 0,就要考虑 0 的个数,如果 0 的个数占不到总数的一半,那么就可以避免相邻两个数都为 0,那么mex就为 0。
如果占了总数的一半,那么mex一定不为 0,考虑1。如果存在其他数字,那么就一定可以避免 0 和 1 相邻,从而 mex 为1。
否则只有0 和 1,那么就为 2.
代码
void solved()
{
cin >> n;
int sum0 = 0;
int sum1 = 0;
for(int i = 0; i < n; i++)
{
cin >> a[i];
if(!a[i]) sum0++;
if(a[i] == 1) sum1++;
}
if(sum0 == n)
{
cout << 1 << endl;
return;
}
if(sum0 <= (n + 1) / 2)
{
cout << 0 << endl;
return;
}
if(sum1 + sum0 == n)
{
cout << 2 << endl;
return;
}
cout << 1 << endl;
}
C:
题目:
现在给出一个长度为 2 * n 的数组 p,存在一个同样长度的 q, 并且 q 是好数组。
好数组:任意长度为 n 子序列的所有相乘等于其他没在子序列中的数字相加。
问你 p 和 q的距离的和最小是什么
距离: |q[i] - p[i]|
思路:
n 为 1时候,毫无疑问 q 数组两个最大数字是最优解。
n 为 2 时,题目给出的 2 2 2 2,要么是 0 0 0 0 或者是 -1 -1 -1 2
n 为 3是 只有 0 0 0 0 0 0
发现 n 为偶数时候,除了 0 0 0 0 ,还有 - 1 - 1 - 1 n
求 min 即可
代码
void solved()
{
cin >> n; for(int i = 1; i <= 2 * n; i++) cin >> a[i];
if(n == 1)
{
cout << max(a[1], a[2]) - min(a[1], a[2]) << endl;
return;
}
int sum = 0,ans = 1e18;
if(n == 2)
{
for(int i = 1; i <= 2 * n; i++) sum += abs(a[i] - 2);
ans = min(ans, sum); sum = 0;
}
for(int i = 1; i <= 2 * n; i++) sum += abs(a[i]);
ans = min(ans, sum), sum = 0;
if(n % 2 == 0)
{
sort(a + 1,a + 2 * n + 1);
for(int i = 1; i <= 2 * n; i++)
{
if(i == 2 * n) sum += abs(a[i] - n);
else sum += abs(a[i] + 1);
}
ans = min(ans, sum); sum = 0;
}
cout << ans << endl;
}
E
题目:
现在存在一个无向图。每个点都有一个值。每次询问 x 和 y。
x 和 y 的值为 a[x] * a[y], x = p[x], y = p[y] 直到其中一个到达根节点1。
思路:
不难发现有 记忆化 的性质,每一对 x 和 y 的值都可以记录下来再次使用。
所以用 map 记录一下,dfs 记忆化搜索即可。
但是因为卡常数导致 map 会 tle
所以用根号分治,只需要 [n] [sqrt((n)] 大小的数组即可。
对于当前深度的点的个数 > sqrt(N) 那么不管,否则我们就记忆化。
记忆化中不再用 map,我们用离散化。对同一层的节点进行离散化。
这样数组为 n sqrt n的大小,每次查询都是同一层内的。
代码
void dfs(int u, int fa)
{
dep[u] = dep[fa] + 1;
s[dep[u]]++;
id[u] = s[dep[u]];
for(auto x : g[u])
{
if(x == fa) continue;
dfs(x, u);
}
}
int dp(int x, int y)
{
if(x == 0 || y == 0) return 0;
if(s[dep[x]] < sqr && mp[x][id[y]])
{
return mp[x][id[y]];
}
int res = a[x] * a[y] + dp(p[x], p[y]);
if(s[dep[x]] < sqr)
{
mp[x][id[y]] = res;
}
return res;
}
void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 2; i <= n; i++) cin>> p[i], g[p[i]].push_back(i);
dfs(1, 0);
for(int i = 0; i < m; i++)
{
int x, y;
dfs(x, y);
}
for(int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
cout << dp(x, y) << endl;
}
}