赛时 rank 42,T1 80，T2 13，T3 0,T4 20
在T4挂死了，赛时胡了一个挺没有前途的\(O(n\log_2^3n)\)的做法，结果赛后发现假了，没有时间打T2，T3的暴力了。
糖
T1 Permutations & Primes
赛时有一个特判\(n=3\)错了，挂了20pts
结论非常显然，1放中间，2、3各放一边，剩下的随便放。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;using db = double;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const int N = 2e5 + 10;
int n,a[N],ans[N];
vector<int> prime;
bitset<N> vis;
inline void Prime(int n){
for(int i = 2;i <= n; ++i){
if(!vis[i]) prime.push_back(i);
for(auto j : prime){
if(i*j > n) break;
if(i % j == 0)break;
vis[i*j] = true;
}
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
Prime(N-10);
int T;
cin>>T;
while(T--){
cin>>n;
if(n == 1){cout<<1<<'\n';continue;}
if(n == 2){cout<<"1 2\n";continue;}
if(n == 3){cout<<"2 1 3\n";continue;}
int tot = 1,l = 1,r = n;
vis.reset();
for(auto i:prime){
if(i > n) break;
vis[i] = true;
if(tot & 1) a[l++] = i,tot++;
else a[r--] = i,tot++;
}
a[n/2+1] = 1;
for(int i = 2;i <= n; ++i){
if(vis[i]) continue;
if(tot & 1) a[l++] = i,tot++;
else a[r--] = i,tot++;
}
for(int i = 1;i <= n; ++i) cout<<a[i]<<' ';
cout<<'\n';
}
}
T2 树上游戏
[ARC116E] Spread of Information
一眼看上去像是个dp，但是好像不太行。
使最大值最小，考虑一下二分答案＋贪心。
二分答案，贪心构造，看是否可以用k个点使得最大值\(\le mid\)
我们可以发现，对于深度最深的叶子节点，选择它的mid级祖先一定不劣。
所以可以贪心构造
设\(a_x\)表示\(x\)到以\(x\)为根的子树内最远的未被覆盖的点的距离。
\(b_x\)表示\(x\)到以\(x\)为根的子树内最远的被选的点的距离
\[a_x = \max{a_y+1}\quad b_x = \min{b_y+1}\quad y\in son_x \]如果\(a_x=mid\)说明该点必选，那么\(a_x = -\infty,b_x = 0\)，计数器加一
如果\(b_x>mid\)，那么以\(x\)为根的子树所选的点无法覆盖自己，需要祖先覆盖。
如果\(a_x+b\_x\le mid\)时，那么以\(x\)为根的子树所选的点可以覆盖自己，\(a_x=-\infty\)
注意特判根节点。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;using db = double;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const int N = 2e5 + 10;
struct EDGE{int to,next;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){edge[++cnt] = {v,head[u]};head[u] = cnt;}
int n,k,a[N],b[N],len,num;
void dfs(int x,int fa){
a[x] = -0x3f3f3f3f;
b[x] = 0x3f3f3f3f;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(y == fa)continue;
dfs(y,x);
a[x] = max(a[x],a[y]+1);
b[x] = min(b[x],b[y]+1);
}
if(b[x] > len) a[x] = max(a[x],0);
if(a[x] + b[x] <= len) a[x] = -0x3f3f3f3f;
if(a[x] == len) a[x] = -0x3f3f3f3f,b[x] = 0,num++;
}
inline bool check(int mid){
len = mid,num = 0;
dfs(1,0);
num += a[1] >= 0;
return (num <= k);
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>k;
for(int i = 1,u,v;i < n; ++i) cin>>u>>v,add(u,v),add(v,u);
int l = 1,r = n,ans = 0;
while(l <= r){
int mid = (l+r)>>1;
if(check(mid)) ans = mid,r = mid - 1;
else l = mid + 1;
}
cout<<ans<<'\n';
}
T3 Ball Collector
考虑套路，将\(a_i\)与\(b_i\)连边。
我们发现，如果答案是点数减去连通块为树的个数。
可撤销并查集维护
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;using db = double;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const int N = 2e5 + 10;
struct EDGE{int to,next;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){edge[++cnt] = {v,head[u]};head[u] = cnt;}
int n,a[N],b[N],num[N];
int dis[N],fa[N],siz[N],ans[N],res = 0;
#define mk make_pair
pair<int,int> sta[N];
int top,tag[N];
int get_fa(int x){return (fa[x] == x?x:get_fa(fa[x]));}
inline void merge(int x,int y){
x = get_fa(x),y = get_fa(y),top++;
if(x == y){
if(num[x] == siz[x]-1) res++,tag[top] = 1;
num[x]++,sta[top] = mk(-1,x);
}
else{
if(siz[x] > siz[y]) swap(x,y);
if(num[x] == siz[x] - 1 || num[y] == siz[y] - 1) res++,tag[top] = 1;
siz[y] += siz[x],fa[x] = y,sta[top] = mk(x,y);
num[y] += num[x] + 1;
}
}
inline void undo(int rest){
while(top > rest){
if(sta[top].first == -1) num[sta[top].second]--;
else{
int x = sta[top].first,y = sta[top].second;
fa[x] = x,siz[y] -= siz[x],num[y] -= num[x]+1;
}
if(tag[top]) res--;
tag[top] = 0;sta[top] = mk(0,0);
top--;
}
}
void dfs(int x,int f){
int now = top;
merge(a[x],b[x]);
ans[x] = res;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(y == f) continue;
dfs(y,x);
}
undo(now);
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n;
for(int i = 1;i <= n; ++i) cin>>a[i]>>b[i];
for(int i = 1,u,v;i < n; ++i) cin>>u>>v,add(u,v),add(v,u);
for(int i = 1;i <= n; ++i) fa[i] = i,siz[i] = 1;
dfs(1,0);
for(int i = 2;i <= n; ++i) cout<<ans[i]<<' ';
}
T4 满穗
难题，用分块维护凸壳，不会打，跳了
赛时太糖了，没有磕T2T3反而磕了T4。
学会了可撤销并查集，算是一个不错的东西。