[WC2022] 杂题选讲-钱易
新年的聚会
题目描述
点此看题
解法
其实用分治的思想很容易解决聚会个数的限制，我们可以枚举一个点对其他点做分治，那么询问次数是 \(O(m\log n)\)，但是这样做总人数不满足条件。
关键结论：对于一个边数为 \(m\) 的图可以划分出 \(\sqrt m\) 个独立集。对于度数 \(\geq\sqrt m\) 的点可以单独划分成独立集，对于度数 \(<\sqrt m\) 的点，考虑邻接点颜色的 \(\tt mex\) 必然小于 \(\sqrt m\)，所以可以根据 \(\tt mex\) 确定它的颜色（颜色就是指独立集标号）
划分独立集可以对于每一个点枚举它划分在哪个独立集中，然后用 \(\tt meeting\) 函数检验。然后我们对于枚举两个独立集，用分治的方法来确定他们的边，也就是把较大的那个集合拆成两半，然后递归下去即可，出口就是两个集合大小都为 \(1\)
复杂度显然是说不清楚的，但是上面是一个平衡复杂度的做法，如果不够放心可以在划分独立集的时候把所有点 \(\tt random\_shuffle\) 一遍。
总结
图论问题常用度数 \(\sqrt m\) 分类的方法来平衡复杂度。
#include
#include
#include
#include
#include
#include "meeting.h"
using namespace std;
#define pii pair
#define pb push_back
#define mp make_pair
const int M = 1005;
int cnt=0,p[M];
vector ans;vector s[M];
void cdq(int x,int y,int xl,int xr,int yl,int yr)
{
if(xr-xl>1;vector A,B;
for(int i=yl;i<=yr;i++)
A.pb(s[y][i]),B.pb(s[y][i]);
for(int i=xl;i<=xr;i++)
i<=mid?A.pb(s[x][i]):B.pb(s[x][i]);
if(!meeting(A)) cdq(x,y,xl,mid,yl,yr);
if(!meeting(B)) cdq(x,y,mid+1,xr,yl,yr);
}
vector solve(int n)
{
srand(time(0));
for(int i=0;i 赶路
题目描述
点此看题
解法
猜测结论：原问题一定有解，我们考虑用类似归纳法的方法找出做法。
考虑现在有一个固定起点和终点的集合 \(S\)，我们找到一个分界向量 \(\vec v\)，设起点和终点的向量是 \(\vec x\)，那么对于剩下的点，如果它和起点连成的向量和 \(\vec x\) 在 \(\vec v\) 的异侧，那么划分到 \(S_1\)；否则我们把这个点划分到 \(S_2\)
由于任意三点不共线，我们可以把原问题分成这样两个独立的子问题：起点和终点固定的 \(S_1\)；起点和终点都固定的 \(S_2\)，它们之间是绝对不会有边相交的，因为他们的凸包就不交。
那么分界向量怎么选取呢？我们可以在随机去集合中的一个点，这样每次都可以对半分，所以时间复杂度 \(O(n\log n)\)
总结
可以用分治实现所谓归纳法，关键是划分成之间没有限制的两个集合。
#include
const int M = 505;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,p[M],L[M],R[M];
struct node
{
int x,y;
node(int X=0,int Y=0) : x(X) , y(Y) {}
node operator - (node b) {return node(x-b.x,y-b.y);}
int operator * (node b) {return x*b.y-y*b.x;}
}a[M];
int cross(node a,node b,node z) {return (z-a)*(z-b)>0;}
void cdq(int l,int r)
{
if(l>=r-1) return ;
int s=p[l],v=p[l+1],j=0,k=0;
int f=cross(a[s],a[v],a[p[r]]);
for(int i=l+2;i Logistical Questions
题目描述
点此看题
解法
本题虽然是魔改的树上重心，但是仍然有一些比较好的性质。如果从一个点其子树方向调整，那么至多只有一个子树满足调整之后可能更优。
找出这个子树我们可以求导，只要套上一个点分治其他都可以暴力计算，时间复杂度 \(O(n\log n)\)
#include
#include
#include
using namespace std;
const int M = 200005;
#define db double
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,tot,rt,sz,id,f[M],siz[M],mx[M],vis[M];
db sd,sum,ans,d[M],w[M];
struct edge{int v,c,next;}e[M<<1];
void findrt(int u,int fa)
{
siz[u]=1;mx[u]=0;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa || vis[v]) continue;
findrt(v,u);
siz[u]+=siz[v];
mx[u]=max(mx[u],siz[v]);
}
mx[u]=max(mx[u],sz-siz[u]);
if(mx[u]=0) continue;
rt=0;sz=siz[v];
findrt(v,u);solve(rt);
}
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
w[i]=read();
for(int i=1;i