我能在不做出任何观察的情况下进入省队吗？
sunrise1024 · · 生活·游记
Day1
诶我们开场先看 T1 ，这一大坨式子也太难分析了吧，能不能直接背包？
哇还真能背包，直接退背包复杂度是啥来着？是不是按照 LCA 处每对点贡献两次就能分析到
这真的对吗？考虑一下拆式子，那我数学不好拆不明白怎么办？是不是按照 LCA 处每对点贡献两次就能分析到
（30 min 后）
不管了，我猜是对的！
接下来看 T2 ，哇怎么是神秘小构造，我会建 kmp 自动机
诶不对我怎么好像就差一步神秘观察了，这也太困难了，拼暴力获得 30 分低保跑路！
接下来看 T3 ！哇怎么又是神秘小构造，我会把合并视为删除间隔，然后对间隔长度模 3 进行讨论，然后只要那些间隔建成图以后存在欧拉回路就能构造了！
诶不对我怎么好像就差一步神秘观察了，这也太困难了，爆搜判异或和获得 12 分低保跑路！
真是充实的一场比赛！差点总分就上 150 了！
Day 2
继续开场先看 T1 ，居然是一道交互题。我会先二分把 0 问出来！
然后呢？然后呢？然后呢？
（30 min 后）
不对这肯定错了，直接每次把两侧其中一边的有效位置问出来，然后向内做子问题直到问出来 0 ，知道 0 在哪以后在推回去不就行了！
T2 又是构造？我会根据
诶
那就先把
哇 T3 题面好长诶，这也太难分析了吧？是不是其实深度不同的子树一定是深度大的排名更靠前呢？
诶如果我模拟题意的话是不是其实把子节点排个序依次比较当作 cmp 函数就行了？
诶！我直接使用平衡树维护所有节点的排名，换根的时候删除两个节点更新完儿子集合以后再插回去就能做
:::warning[以下为考场代码，由于做法过于魔怔所以不建议仔细阅读]
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int cid;
int n,m;
vector<int> e[N];
class SOL1{
public:
int rt;
int grk(int x,int y){
if(x==y)return 1;
if(x==rt)return 2;
if(y==rt)return 2;
return 3;
}
void sol(){
rt=0;
for(int i=1;i<=n;++i){
if(e[i].size()==n-1){
rt=i;
break;
}
}
while(m--){
int s,t,opx,opy,rk;
cin>>s>>t>>opx>>opy>>rk;
vector<int> S,T;
if(s==t)opx=opy=0;
if(opx){
S.push_back(s);S.push_back(t);
if(s!=rt&&t!=rt)S.push_back(rt);
}
else S.push_back(s);
if(opy){
T.push_back(s);T.push_back(t);
if(s!=rt&&t!=rt)T.push_back(rt);
}
else T.push_back(t);
int cn=0;
for(int ns:S){
for(int nt:T){
cn+=grk(ns,nt)<=rk;
}
}
cout<<cn<<'\n';
}
}
}sol1;
class SOL2{
public:
int d[N];
int fa[N];
void dfs(int no,int ff){
fa[no]=ff;
d[no]=d[ff]+1;
for(int to:e[no]){
if(to==ff)continue;
dfs(to,no);
}
}
void sol(){
dfs(1,0);
while(m--){
int s,t,opx,opy,rk;
cin>>s>>t>>opx>>opy>>rk;
if(s==t){
cout<<"1\n";
continue;
}
if(!opx&&!opy){
cout<<"0\n";
continue;
}
if(!opx||!opy){
cout<<"1\n";
continue;
}
int len=0;
while(s!=t){
++len;
if(d[s]>d[t])s=fa[s];
else t=fa[t];
}
cout<<len+1<<'\n';
}
}
}sol2;
mt19937 mt(time(0));
int cmp(int x,int y);
vector<int> son[N];
class Treap{
public:
struct node{
int key;
int fa;
int cn;
int si;
int s[2];
}t[N];
int rt;
set<int> st[N];
int id[N];
vector<int> lj;
void init(){
rt=0;
lj.resize(n);
iota(lj.begin(),lj.end(),1);
}
void pushup(int x){t[x].si=t[t[x].s[0]].si+t[t[x].s[1]].si+t[x].cn;}
void split_by_val(int k,int x,int& idx,int& idy){
if(!k){
idx=idy=0;
return;
}
if(cmp(x,*st[k].begin())){
idy=k;t[k].fa=0;
split_by_val(t[k].s[0],x,idx,t[idy].s[0]);
t[t[idy].s[0]].fa=idy;
pushup(idy);
}
else{
idx=k;t[k].fa=0;
split_by_val(t[k].s[1],x,t[idx].s[1],idy);
t[t[idx].s[1]].fa=idx;
pushup(idx);
}
}
int merge(int x,int y){
if(!x||!y)return x|y;
if(t[x].key>t[y].key){
t[x].s[1]=merge(t[x].s[1],y);
t[t[x].s[1]].fa=x;
pushup(x);
return x;
}
t[y].s[0]=merge(x,t[y].s[0]);
t[t[y].s[0]].fa=y;
pushup(y);
return y;
}
int nw_node(){
int no=lj.back();lj.pop_back();
st[no].clear();
t[no].fa=t[no].cn=t[no].si=t[no].s[0]=t[no].s[1]=0;
t[no].key=mt();
return no;
}
void push_front(int x){
id[x]=nw_node();
int nd=id[x];
st[nd].insert(x);
t[nd].si=t[nd].cn=1;
rt=merge(nd,rt);
}
bool fd(int k,int x){
if(!k)return 0;
int op=cmp(x,*st[k].begin());
if(op==2){
t[k].cn++;t[k].si++;
id[x]=k;
st[k].insert(x);
return 1;
}
bool fl=0;
if(op)fl=fd(t[k].s[0],x);
else fl=fd(t[k].s[1],x);
if(fl)t[k].si++;
return fl;
}
void ins(int x){
if(fd(rt,x))return;
int rtx,rty;
split_by_val(rt,x,rtx,rty);
int ls=nw_node();
id[x]=ls;t[ls].si=t[ls].cn=1;
st[ls].insert(x);
rt=merge(rtx,merge(ls,rty));
}
void era(int x){
if(t[id[x]].cn>1){
t[id[x]].cn--;
st[id[x]].erase(x);
int no=id[x];
while(no){
t[no].si--;
no=t[no].fa;
}
return;
}
int no=id[x];lj.push_back(no);
int nf=t[no].fa;
t[t[no].s[0]].fa=t[t[no].s[1]].fa=0;
int ns=merge(t[no].s[0],t[no].s[1]);
if(!nf){
rt=ns;
return;
}
t[ns].fa=nf;
t[nf].s[t[nf].s[1]==no]=ns;
while(nf){
pushup(nf);
nf=t[nf].fa;
}
}
int query_rk(int x){
int s=t[t[x].s[0]].si;
while(x){
int y=t[x].fa;
if(t[y].s[0]==x)x=y;
else{
s+=t[t[y].s[0]].si+t[y].cn;
x=y;
}
}
return s+1;
}
int query_nd_rk(int x){
return query_rk(id[x]);
}
int cmp_nd(int x,int y){
if(id[x]==id[y])return 2;
return query_rk(id[x])<query_rk(id[y]);
}
void dfs(int k){
if(!k)return;
dfs(t[k].s[0]);
cout<<*st[k].begin()<<' ';
dfs(t[k].s[1]);
}
void ch(){dfs(rt);cout<<'\n';}
}treap;
int cmp(int x,int y){
const int mi=min(son[x].size(),son[y].size());
for(int i=0;i<mi;++i){
int idx=son[x][i],idy=son[y][i];
int op=treap.cmp_nd(idx,idy);
if(op==2)continue;
return op;
}
if(son[x].size()==son[y].size())return 2;
return son[x].size()>son[y].size();
}
void cg_son(int x){
vector<pair<int,int>> ve;
for(int to:son[x]){
ve.emplace_back(treap.query_nd_rk(to),to);
}
sort(ve.begin(),ve.end());
for(int i=0;i<ve.size();++i){
son[x][i]=ve[i].second;
}
}
void trans(int x,int y){
treap.era(x);treap.era(y);
{
vector<int> ns;
for(int no:son[x]){
if(no==y)continue;
ns.push_back(no);
}
swap(ns,son[x]);
}
son[y].push_back(x);
treap.ins(x);
cg_son(y);
treap.push_front(y);
}
int ans[N];
struct ques{
int t,rk;
int id;
ques(int t,int rk,int id):t(t),rk(rk),id(id){}
};
vector<ques> qus[N];
void dfs_init(int no,int fa){
son[no].clear();
for(int to:e[no]){
if(to==fa)continue;
dfs_init(to,no);
son[no].push_back(to);
}
cg_son(no);
treap.ins(no);
}
void dfs(int no,int fa){
for(auto [t,rk,id]:qus[no]){
int nrk=treap.query_nd_rk(t);
ans[id]=(treap.query_nd_rk(t)<=rk);
}
for(int to:e[no]){
if(to==fa)continue;
trans(no,to);
dfs(to,no);
trans(to,no);
}
}
int main(){
freopen("industry.in","r",stdin);
freopen("industry.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>cid;
cin>>n;
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
cin>>m;
if(cid==1){
sol1.sol();
return 0;
}
if(cid==2){
sol2.sol();
return 0;
}
for(int i=1;i<=m;++i){
int s,t,opx,opy,rk;
cin>>s>>t>>opx>>opy>>rk;
qus[s].emplace_back(t,rk,i);
}
treap.init();
dfs_init(1,0);
dfs(1,0);
for(int i=1;i<=m;++i){
cout<<ans[i]<<'\n';
}
return 0;
}
/*
g++ -o industry industry.cpp -O2 -std=gnu++14 && time ./industry
*/:::
真是紧张而又刺激的两天！我但凡有半点策略失误总分都上 300 了！
后记
对于不会打顺风局的表现是什么这个问题，小 sunrise 交出了一份完美的答卷！
他成功因为 NOIP 狗运大爆发而在省选中采取了两天低保的策略，为我们展示了按档拼暴力，先把所有模拟题意暴力都写完再考虑其他解法的策略在时间紧张的省选中是多么的失败。
让我们恭喜 sunrise1024 以参加了 4 年的省选中最高的水平打出了最差的发挥，以最搞笑的方式结束了自己的省选之旅 /hec