这个 T1 的 \(n^{3}\) 的 SPJ 效率还是太慢了，膜拜 SPJ 大神学长，还会画画
A.Permutations & Primes
这题感觉挺水的但是感觉有不是那么水，主要还是因为我赛时没想出正解，在打的表里找了一组好看的规律，打上了然后就过了. 对偶数来说，我的规律正好是正解的特化，但是对奇数来说，我的规律就很奇怪了，我开头是 \(5\)，最中间是 \(1\)，结尾是 \(2\) 但是我完全卡不掉，如上图. 感觉是对的，不会证明其正确性.
学长写的 SPJ 挺神的，每次根据答案扩展，我的 \(n^{3}\) 写法比起来就太菜了
#include<bits/stdc++.h>
using namespace std;
int n,a[200001];
int main(){
int cases;scanf("%d",&cases);while(cases--){
scanf("%d",&n);
if(n&1){
a[(n+1)/2]=1;int tot=1;
int i1=1,j1=(n+1)/2-1,i2=(n+1)/2+1,j2=n;
while(i1<=j1 and i2<=j2){
a[j2]=++tot;j2--;
a[j1]=++tot;j1--;
if(i1<=j1 and i2<=j2){
a[i2]=++tot;i2++;
a[i1]=++tot;i1++;
}
}
for(int i=1;i<=n;++i){
printf("%d ",a[i]);
}
cout<<endl;
}
else{
int i1=1,j1=n/2,i2=n/2+1,j2=n;int tot=0;
while(i1<=j1 and i2<=j2){
a[i2]=++tot;i2++;
a[i1]=++tot;i1++;
if(i1<=j1 and i2<=j2){
a[j2]=++tot;j2--;
a[j1]=++tot;j1--;
}
}
for(int i=1;i<=n;++i){
printf("%d ",a[i]);
}
cout<<endl;
}
}
}
B.树上游戏
真有 \(50w\) 个吗，能不能送我一个
没想到答案居然有单调性，但是答案确实有单调性. 如果能选 \(k\) 种颜色就一定能选 \(\lt k\) 种颜色，因此可以用二分答案做.
现在问题就是 check() 怎么写，发现我们可以只考虑深度最大的节点往回搜，当搜到 \(mid\) 距离的时候就说明至少要在这里放一个点，否则就走不到了，因此我们据此来统计节点个数，然后跟 \(k\) 比较作为二分依据
#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
int a[200001],b[200001];
int num,len;
vector<int>e[200001];
void dfs(int now,int last){
int p=-1,q=0;
for(int i:e[now]){
if(i!=last){
dfs(i,now);
p=max(p,a[i]-1);
q=max(q,b[i]+1);
}
}
if(p>=q){
a[now]=p;
b[now]=-1;
return;
}
if(q<len){
a[now]=0;
b[now]=q;
return;
}
num++;
a[now]=len;
b[now]=-1;
}
bool check(int x){
memset(a,-1,sizeof a);
memset(b,-1,sizeof b);
len=x,num=0;
dfs(1,0);
if(b[1]!=-1){
num++;
}
if(num>k) return false;
return true;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n-1;++i){
int x,y;cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
int l=1,r=200000;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
cout<<ans<<endl;
}
C.Ball Collector
考虑对冲突的部分连边（还是记一下吧，挺套路的，上一个用这个套路的题还是二分图最大独立集）
连完以为是道不可做，结果能手玩一下出性质，性质就是树只能选出 \(x-1\) 个种类不同的数，其余情况均能选出 \(x\) 个
我在考场上大抵是没这么大胆猜这种结论.
维护是不是树，那么可以通过维护一个并查集，然后看它的 \(size\) 来决定，但是还需要写撤销操作，所以要用可撤销并查集，可撤销并查集思路还是挺巧的，用了按秩合并来维护平衡
D.满穗
