赛时 rank24，T1 20,T2 66,T3 0,T4 10
T1 *3100,T2逆天trick,T3 抽象题面，T4 也挺抽象
反正是暴力专场
T1、T3、T4太抽象了，不会，直接挂的官方题解
可能模拟赛难度为强紫+弱紫/强蓝+紫+紫？
调了一个最简单的T2，学习一下这个trick。
我树套树还没写玩呢
T1 法阵
原题3100，张口放T1
我会打暴力
点此查看代码
#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)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = infile("magic.in"),*OutFile = outfile("magic.out");
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2010,mod = 998244353;
int n,m;
vector<int> ok;
int last[N],ans = 0;
void dfs(int now){
if(now == n + 1){
for(int i = 1;i <= m; ++i){
bool flag = false,pd = false;
int tot = 0;
for(int j = 1;j <= n; ++j){
bool _ = (last[j]>>(i-1))&1;
if(!_ && pd && flag) return;
pd = _;
if(!_) flag = true;
if(_) tot++;
}
if(tot == n) return;
}
ans++;
return;
}
for(auto i : ok){
last[now] = i;
dfs(now+1);
}
}
inline void solve(){
cin>>n>>m;
auto OO = [](int x) -> bool{
bool flag = false,pd = false;
while(x){
bool _ = x&1;
if(_ && !pd && flag) return false;
pd = _;
if(_) flag = true;
x>>=1;
}
return true;
};
for(int i = 1;i < (1<<m); ++i){
if(OO(i)) ok.push_back(i);
}
dfs(1);
cout<<ans;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T2 连通块
弱化版 : [yLCPC2024] F. PANDORA PARADOXXX
强化版 : [USACO18FEB] New Barns P
trick + 经典结论
trick :
将询问离线，从后往前，将删边转变为加边
经典结论 :
两个连通块合并后最远点对一定是在两个连通块最远点对中出现的
证明 :
假设两个连通块是通过\((x,y)\)相连的,两个连通块内的最远点对分别为\((a,b),(c,d)\)
若合并后的连通块的最远点对不经过\((x,y)\)，则一定为\((a,b)\)或者\((c,d)\)
反之，我们有离\(x\)最远的一定为\(a,b\)中的一个，离\(y\)最远的一定有\(c,d\)中的一个，所以最远点对存在于\(\{a,b,c,d\}\)中
然后我们将所有操作离线下来。
对于询问，利用\(dis_{x\rightarrow y} = dis_{1\rightarrow x} + dis_{1\rightarrow y} - 2\times dis_{1\rightarrow LCA(x,y)}\)，我们可以求\(x\)到所在连通块点对的距离取\(\max\)
对于修改，利用上述结论，维护最远点对即可，时间复杂度为\(O(\log n)\)的。
点此查看代码
#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)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = infile("block.in"),*OutFile = outfile("block.out");
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e5 + 10;
int n,m,u[N],v[N];
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 dist[N],fa[N];
int get_fa(int x){return (x == fa[x]?x:fa[x] = get_fa(fa[x]));}
namespace TCS{
int fa[N],dep[N],siz[N],son[N],top[N];
void dfs1(int x){
siz[x] = 1;
dep[x] = dep[fa[x]] + 1;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(y == fa[x]) continue;
dist[y] = dist[x] + 1;
fa[y] = x;dfs1(y);
siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
void dfs2(int x,int t){
top[x] = t;
if(son[x]) dfs2(son[x],t);else return;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
if(y == fa[x] || y == son[x]) continue;
dfs2(y,y);
}
}
inline int LCA(int x,int y){
int fx = top[x],fy = top[y];
while(fx != fy){
if(dep[fx] < dep[fy]) swap(fx,fy),swap(x,y);
x = fa[fx];
fx = top[x];
}
if(dep[x] > dep[y]) swap(x,y);
return x;
}
}
using TCS::dfs1;using TCS::dfs2;using TCS::LCA;
int ver[N][3];
inline void Merge(int x,int y){
x = get_fa(x),y = get_fa(y);
vector<int> may;
for(int i = 1;i <= 2; ++i)
may.emplace_back(ver[x][i]),
may.emplace_back(ver[y][i]);
int res = 0,ver1,ver2;
for(int i = 0;i < 3; ++i){
for(int j = i + 1;j < 4; ++j){
int x = may[i],y = may[j];
int dis = dist[x] + dist[y] - dist[LCA(x,y)]*2;
if(res < dis){
res = dis;
ver1 = x,ver2 = y;
}
}
}
fa[x] = y,ver[y][1] = ver1,ver[y][2] = ver2;
}
inline int Get_ans(int x){
int fx = get_fa(x);
int res1 = dist[ver[fx][1]] + dist[x] - 2*dist[LCA(ver[fx][1],x)];
int res2 = dist[ver[fx][2]] + dist[x] - 2*dist[LCA(ver[fx][2],x)];
return max(res1,res2);
}
struct node{int op,x;}q[N];
vector<int> ans;
inline void solve(){
cin>>n>>m;
for(int i = 1;i < n; ++i) cin>>u[i]>>v[i],add(u[i],v[i]),add(v[i],u[i]);
for(int i = 1;i <= m; ++i) cin>>q[i].op>>q[i].x;
dfs1(1),dfs2(1,1);
for(int i = 1;i <= n; ++i) fa[i] = i,ver[i][1] = ver[i][2] = i;
bitset<N> ok;
for(int i = 1;i <= m; ++i) if(q[i].op == 1) ok[q[i].x] = true;
for(int i = 1;i < n; ++i) if(!ok[i]) Merge(u[i],v[i]);
for(int i = m;i >= 1; --i){
if(q[i].op == 1) Merge(u[q[i].x],v[q[i].x]);
else ans.emplace_back(Get_ans(q[i].x));
}
reverse(ans.begin(),ans.end());
for(auto i : ans) cout<<i<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T3 军队
T4 棋盘
出题人的碎碎念 :
