比赛体验表示极差，分类讨论相当崩溃，甚至前两个题 \(30min\) 才过。
A. Walking Master
题目分析：
慢慢分析一下，看看到底能不能走过去以及走到什么地方就好了。
一个前置知识，\(x \to y\)，如果只能 \(+1\) 或 \(-1\) 的最小操作步骤是 \(|x - y|\)
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;scanf("%d",&t);
while(t--){
int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
if(d < b){
printf("-1\n");
}
else if(d == b){
if(c <= a) printf("%d\n",a - c);
else printf("-1\n");
}
else{
if(c - a > d - b) printf("-1\n");
else printf("%d\n",d - b + abs(a - (c - (d - b))));
}
}
return 0;
}
B. Mex Master
题目分析：
答案显然不会很大，因为我们可以将序列变成 0 0 0 ... x y z 的形式，即将所有的 \(0\) 放到前面，这样答案就不可能大于 \(3\)。
而其实模拟一下答案等于 \(3\) 也一定存在一种方式可以让他变为小于 \(3\) 的数。
考虑如果可以将 0 0 全部分割开，答案显然就是 \(0\)。
否则肯定是尽可能不出现 1 0，按照上文的这种构造方式只要没有 \(1\) 或者存在一个数不是 \(1\) 放到 x 的位置，就可以避免 1 0 了。
否则答案就只能是 \(2\) 了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
int cnt0 = 0,cnt1 = 0,cnt2 = 0;
for(int i=1; i<=n; i++){
int a;
scanf("%d",&a);
if(a == 0) cnt0++;
if(a == 1) cnt1++;
if(a != 0) cnt2++;
}
if(cnt2 >= cnt0 - 1) printf("0\n");
else{
if((cnt2 - cnt1) || (!cnt1)) printf("1\n");
else printf("2\n");
}
}
return 0;
}
C.Sequence Master
题目分析：
可以显然地发现，题目这个限制非常强，会把绝大部分序列全都筛掉，至少我自己手模的都是错的。
那么就考虑打表，看看符合条件的 \(q\) 有什么特征。
这里贴上我的打表程序：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,tot = 0,a[1000];
bool flag[1000];
bool check(int now){
if(now == 0){
int sum = 0,pro = 1,cnt = 0;
for(int i=1; i<=n; i++){
if(flag[i]) ++cnt,pro = pro * a[i];
else sum = sum + a[i];
}
if(cnt == n / 2 && pro == sum) return true;
if(cnt != n / 2) return true;
return false;
}
bool tag = true;
if(tot < n / 2){
flag[now] = true;++tot;
tag = tag & check(now-1);
}
if(flag[now]) --tot;
flag[now] = false;
tag = tag & check(now-1);
return tag;
}
void dfs(int now){
if(now == 0){
if(check(n)){
for(int i=1; i<=n; i++) printf("%d ",a[i]);
printf("\n");
}
return;
}
for(int i=-4; i<=4; i++){
a[now] = i;
dfs(now-1);
}
}
int main(){
scanf("%d",&n);n *= 2;
dfs(n);
return 0;
}
建议手动试试，这样就可以得到这些规律：
- 若 \(n\) 为奇数，则只有全 \(0\) 合法。
- 若 \(n\) 为偶数，则除了全 \(0\)，还有就是 \(2\times n - 1\) 个 \(-1\) 和 \(1\) 个 \(n\) 的任意排列是合法的。
- 若 \(n = 1\)，则只要相等即合法
- 若 \(n = 2\)，多了
2 2 2 2这种合法情况。
然后对着规律直接写就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e6+5;
const int INF = 1e17+5;
int a[N];
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;scanf("%lld",&t);
while(t--){
int n;scanf("%lld",&n);
for(int i=1; i<=2*n; i++) scanf("%lld",&a[i]);
if(n == 1){
printf("%lld\n",abs(a[1] - a[2]));
}
else{
int ans = INF,tmp = 0;
for(int i=1; i<=2*n; i++) tmp = tmp + abs(a[i]);
ans = min(ans,tmp);
if(n % 2 == 0){
tmp = 0;
for(int i=1; i<=2*n; i++) tmp = tmp + abs(a[i] + 1);
int res = INF;
for(int i=1; i<=2*n; i++){
res = min(res,abs(a[i] - n) - abs(a[i]+1));
}
tmp += res;
ans = min(ans,tmp);
}
if(n == 2){
tmp = 0;
for(int i=1; i<=2*n; i++) tmp = tmp + abs(a[i] - 2);
ans = min(ans,tmp);
}
printf("%lld\n",ans);
}
}
return 0;
}
E.Tree Master
题目分析：
可以发现我们每次操作大概率都有很多重复算过的状态，所以其实可能访问到的状态不会很多。
假设我们每一次访问都不会经过重复状态，且每一次都是选择深度为 \(T\) 的点对，显然如果每次选择的深度不同对最劣情况下不怎么会影响。
那么我们的总状态数就是：\(T \times \min(q,(\frac{n}{T})^2)\)，因为 \(n,q\) 同阶，所以当 \(T = \sqrt{n}\) 时取得最大值即 \(n\sqrt{n}\)。
所以就直接暴力 map 记录一下，复杂度 \(O(n\sqrt{n}\log n)\)，个人感觉可以过，但是实际上就是差一丝丝。
但是这样我们本质上就是得到了一种查询比较优的做法，结合暴力做法不难想到使用根号分治。
设 \(s_i\) 表示深度为 \(i\) 的点的个数。
- 对于 \(s_i > \sqrt{n}\) 的层直接暴力跳，因为最多只有 \(\sqrt{n}\) 层满足暴力的条件，所以这部分的复杂度为 \(O(\sqrt{n})\)
- 对于 \(s_i < \sqrt{n}\) 的层按照记忆化的思想去做，总状态数不会超过 \(n\sqrt{n}\)，而且也显然不需要
map记录，直接离散化然后用数组记就好了。
因为 \(n,q\) 同阶所以总复杂度 \(O(n\sqrt{n})\)
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int a[N],p[N],dep[N],ans[N],pos[N],f[N][400],sz[N];
vector<int> G[N];
int get(int x,int y){
if(x == y) return ans[x];
if(x > y) swap(x,y);
if(!x || !y) return 0;
if(sz[dep[x]] < 320){
if(f[x][pos[y]]) return f[x][pos[y]];
return f[x][pos[y]] = get(p[x],p[y]) + a[x] * a[y];
}
return get(p[x],p[y]) + a[x] * a[y];
}
void dfs(int now,int fath){
dep[now] = dep[fath] + 1;sz[dep[now]]++;ans[now] = ans[fath] + a[now] * a[now];
pos[now] = sz[dep[now]];
for(int to : G[now]) dfs(to,now);
}
signed main(){
int n,q;scanf("%lld%lld",&n,&q);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=2; i<=n; i++) scanf("%lld",&p[i]),G[p[i]].push_back(i);
dfs(1,0);
for(int i=1; i<=q; i++){
int x,y;scanf("%lld%lld",&x,&y);
printf("%lld\n",get(x,y));
}
return 0;
}