【codeforces上紫】杂题/数据结构

E.

题意：每个人两个属性：高度和宽度。对于每个人，找另一个宽度和高度严格小于他（可以那个人的宽度和高度分别小于他的宽度和高度；也可以那个人的高度和宽度分别小于他的宽度和高度）的人的编号。数据范围2e5。

思路：一开始看到有两个属性，想起二维偏序问题，但是树状数组等二维偏序问题是用来解决计数问题的。此题需要给出一个答案，则无法使用。后来想到有非常简单的方法，先按一个属性排序，然后遍历数组，维护当前之前的第二个属性的最小值及其编号。然而问题有两个情况，即宽度和高度互换又可以。我不懂怎么交换高度和宽度重新遍历，写不出来。

题解是这样想的：按属性1排序，遍历一遍得到每个位置的答案（即前面最小的属性2的人的编号）。对每一个人，根据属性1二分他在序列中的位置，就得到答案。用这样二分的操作，就可以同时维护两个排序的序列，编码也非常结构化。下面贴一下题解代码：

#include
using namespace std;using pii = pair<int,int>;struct man {int h,w,id;
};bool operator<(const man &a,const man &b){return tie(a.h,a.w,a.id)<tie(b.h,b.w,b.id);
}struct my_min{pii mn1,mn2;
};vector<pair<int,my_min>> createPrefMins(const vector<man>& a){vector<pair<int,my_min>> prefMin;my_min curMin{pii(INT_MAX,-1),pii{INT_MAX,-1}};for (auto x: a) {if (x.w<curMin.mn1.first) {curMin.mn2 = curMin.mn1;curMin.mn1 = pii(x.w,x.id);} else {curMin.mn2 = min(curMin.mn2,pii(x.w,x.id));}prefMin.emplace_back(x.h,curMin);  // 这个高度位置的前缀最小和次小。}return prefMin;
}int findAny(const vector<pair<int,my_min>> &mins,int h,int w,int id){int l=-1,r=(int) mins.size();while(r-l>1){int m=(l+r)/2;if(mins[m].first<h) l=m;  // 可行的情况下越往后越好else r=m;}if(l==-1) return -1;auto mn1 = mins[l].second.mn1;auto mn2 = mins[l].second.mn2;if(mn1.second!=id) return mn1.first<w?mn1.second+1:-1;return mn2.first<w?mn2.second+1:-1;
}void solve() {int n;cin>>n;vector<man> hor,ver;vector<pii> a;for(int i=0;i<n;++i){int h,w;cin>>h>>w;hor.push_back({h,w,i});ver.push_back({w,h,i});a.emplace_back(h,w);}sort(hor.begin(),hor.end());sort(ver.begin(),ver.end());auto horMins = createPrefMins(hor);auto verMins = createPrefMins(ver);for(int i=0;i<n;++i){auto[h,w]=a[i];int id=findAny(horMins,h,w,i);if(id==-1) {id=findAny(verMins,h,w,i);}cout<<id<<" ";}cout<<endl;
}
int main(){int test;cin>>test;while(test--) solve();
}

说说思路二，就是大多数人的提交思路，编码比题解简单不少。由于宽度和高度可以互换，对应的编号不变。我们可以贪心地将每个人属性中较小的那个存为属性1。然后，遍历排好序的序列，维护当前之前的最小属性2及其对应人的编号。为了防止当前之前的对应人的属性1与当前人的属性1相等，我们将属性2取负存进去再排序。使得同一属性1的队列片段中，属性2越大的越靠前站，那么他们的答案就不会取到与自己同一属性1的人的编号。

#include
using namespace std;void solve(){int n;cin>>n;vector<int> ans(n,-1);vector<array<int,3>> a;for(int i=1;i<=n;++i){int h,w,id=i;scanf("%d%d",&w,&h);if(w>h) swap(w,h);a.push_back({w,-h,id});}sort(a.begin(),a.end());int mn=0x7f7f7f7f,mnid=-1;for(auto &i:a){int h,id;h=-i[1],id=i[2];if(h>mn) ans[id-1]=mnid;if(h<mn) mn=h,mnid=id;}for(int& i:ans) cout<<i<<" ";cout<<endl;
}int main(){int t;cin>>t;while(t--) solve();
}

F. New Year’s

题意：一个 2 × n 2\times n 2×n的网格，有一些网格被阻塞，要求用多米诺（ 2 × 1 2\times 1 2×1 or 1 × 2 1\times 2 1×2即横或竖）填满这网格未被阻塞的部分。输出能否填满。

思路：贪心地想。从第一列开始，如果当前这列完全被阻塞，则直接考虑第二列；如果完全没阻塞，则放一个竖着的多米诺；如果被部分阻塞，则只能放一个横着的影响到第二列的多米诺。此时第二列若完全被阻塞，输出no；若完全没阻塞，那么放一个横着的填满第一列空的格子，然后再放一个横着影响第三列的多米诺；若部分阻塞，若阻塞处与第一列一样，则输出no；否则刚好填补第一列，考虑第三列。综上所述，我们只用考虑有被堵住的列。下一列是否能补上上一列，取决于他们的距离和阻塞的位置。末尾放入一个最远的完全阻塞列，以完成关于最后一列的判断。

#include
using namespace std;void solve(){int n,m;cin>>n>>m;map<int,int>mp;for(int i=1;i<=m;++i){int r,c;scanf("%d%d",&r,&c);mp[c]|=1<<(r-1); // 完全填满：3，部分填满：2或1.}mp[1e9]=3;int ls=0,lspos=0;for(auto[a,b]:mp){int pos=(a+b)%2;if(ls){if(b==3||lspos==pos) {cout<<"no"<<endl;return;}else{ls=0;}}else{if(b!=3){ls=1;lspos=pos;}}}cout<<"yes"<<endl;
}int main(){int t;cin>>t;while(t--) solve();
}

D. Plays with a Tree

给一棵树，一种操作，增一条边同时删一条边。求使之成为竹子的最少操作次数。

考虑先拆边，再增边。考虑可以拆成竹林，然后将每两棵竹子首尾相接，便可得到竹子。

于是问题转化为：要把该树用最少的操作次数拆成竹林。

对于当前点v，设 c v c_v cv​是v的儿子的数量， p v p_v pv​是v的祖先。

我们已经处理完v的儿子（回溯中）。（儿子全是竹子）

最优贪心策略：

（1） c v ≤ 1 c_v\leq 1 cv​≤1 ，不管

（2） c v = 2 c_v=2 cv​=2，删v与其父亲的连边

（3） c v > 2 c_v>2 cv​>2，删v与其父亲的连边之外，再删任意 c v − 2 c_v-2 cv​−2个与儿子的连边。

为什么最优：

（1）对于当前点，删其与父亲的连边还是再删一个与儿子的连边，没有区别。

（2）然而，对于当前点的父亲，当前点删掉其与其父亲的连边，对其父亲来说，减轻了负担。

#include
using namespace std;vector<int> G[100005];
vector<vector<int>> ans;
int dfs(int u,int fa){ // 返回叶子节点int cnt=0,nxt=u; // 儿子个数 和 当前子树的叶子for(int& v:G[u]) if(v^fa){int leave = dfs(v,u); // 儿子子树的叶子节点if(leave < 0) continue; // 该儿子已经被切掉cnt++;if(cnt==1) nxt=leave; // 第一个儿子。我们把他的叶子当作现在子树的叶子else if(cnt==2) ans.push_back({fa,u,nxt,leave}),nxt=-1; // 切断与父亲的联系.记录的是上一个叶子节点和现在的叶子节点。else ans.push_back({u,v,v,leave});// 被切了，即顶和叶子}return nxt;
}int main(){int i,to,n;for(cin>>n;cin>>n;ans.clear()){for(int j=1,x,y;j<n;++j){cin>>x>>y;G[x].push_back(y);G[y].push_back(x);}for(i=1;;++i) if(G[i].size()==1) break; // 一个叶子节点to=dfs(i,-1); // 从该叶子节点出发.因为是叶子,所以tocout<<ans.size()<<endl;for(auto& x:ans) cout<<x[0]<<" "<<x[1]<<" "<<to<<" "<<x[2]<<endl,to=x[3];for(i=1;i<=n;++i) G[i].clear();}
}

C. Trees of

给两棵n个点的树，为S和K。构造一个新的n个点的图，u和v之间有边当且仅当两个条件同时满足：

（1）在S中，u是v的祖先或v是u的祖先；（2）在K中，u和v互不是祖先。

现求该新图中的最大团大小。

思路：

（1）S树上DFS（DFS的特性保证了当前遍历到的都是一条链上的），同时要用K中抽取到的信息判断两点是否在K中是先后辈关系

（2）K树抽信息：dfn。对于u和v，若st[u]>st[v]且ed[u] 两个点所属区间只有两种关系：一个嵌套在另一个中/两者没有交集。

（3）在S树上进行DFS，维护满足条件的集合S。

集合S的大小为最大团的个数。注意到，S上的链中两个点在K中是前后辈关系的话，S中保存那个后辈更优。（区间更小）

（3.1）对于当前遍历到的这个点，观察其在S中是否有K中的后辈。有的话不插入当前点。

（3.2）否则，插入当前点。

（3.3）且观察对于当前点，在S中是否有K中的前辈，有的话插入时同时删除前辈。

（3.4）离开当前点的时候要记得删掉当前点。且插入的时候要注意保存被删除的前辈的序号。离开当前点的时候还原前辈。

#includeusing namespace std;
#define int long long int
#define mp(a, b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i, n) for(i=0;i<n;i++)
#define rep(i, a, n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define Endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SECconst int maxn = 3e5+5;vector<int> s[maxn];
vector<int> k[maxn];
int st[maxn],ed[maxn];
set<pair<int,int> > se;
int ans,dfn;int add(int u){auto it = se.lower_bound({st[u],u});  // 第一个大于等于的if(it!=se.end() && ed[it->second] <= ed[u]) return -1; // 如果有后继if(it==se.begin()) return -2; // 没有前驱,直接插入--it; // 往前探一个int res = it->second; // 第一个小于等于的if(ed[it->second] < ed[u]) return -2;se.erase(it);return res;  // 返回前驱
}void s_dfs(int u){// 进入当前点int res = add(u);if(res!=-1) se.insert({st[u],u});  // 可插入ans = max(ans,(int)se.size());for(auto v:s[u]) s_dfs(v);// 退出当前点，删掉,记得要暂存历史版本if(res!=-1){// 如果被加入了se.erase({st[u],u});if(res!=-2) se.insert({st[res],res});}
}void k_dfs(int u){st[u] = ++dfn;for(auto v:k[u]) k_dfs(v);ed[u] = ++dfn;
}signed main() {fast;int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;++i) s[i].clear(),k[i].clear();se.clear();ans = 0;dfn = 0;for(int i=2,x;i<=n;++i){cin>>x;s[x].push_back(i); // 有向边}for(int i=2,x;i<=n;++i){cin>>x;k[x].push_back(i);}k_dfs(1);s_dfs(1);cout<<ans<<endl;}return 0;
}