Codeforces Round 1284 简要题解

A. New Year and Naming

略

B. New Year and Ascent Sequence

略

C. New Year and Permutation

略

D. New Year and Conference

容易证明要判定是否存在venue-sensitive的非空子集，只需判定所有大小为$2$的子集。也即判定是否存在区间$x?=y$，使得$[[s{a}_x,e{a}_x]\cap [s{a}_y,e{a}_y]=?]?=[[s{b}_x,s{b}_x]\cap [s{b}_y,e{b}_y]=?]$。
比较简单的做法是考虑异或哈希，对每个区间附上一个随机权值，分别求出每个区间在$a$和$b$中与它不相交的区间集合的哈希值，判定是否相等。注意到对于一个区间$[l_1,r_1]$，区间$[l_2,r_2]$与它不相交当且仅当$l_1>r_2$或$r_1<l_2$。那么可以分别对区间按端点排序后做几次two pointer求出哈希值。
时间复杂度为$\mathcal{O}(n\log n)$。

#include <bits/stdc++.h>
#include <random>
#define FR first
#define SE second
#define y1 yyusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pr;mt19937 rnd(time(0));ull randull() {
    ull s=0;for(int i=0;i<4;i++)s=(s<<16)|((int)abs((int)rnd())%(1LL<<16));return s;
}ull s1[100005],s2[100005],num[100005];
pr a[100005],b[100005],c[100005],d[100005];int main() {
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) {
    int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);a[i]=pr(x1,i);b[i]=pr(y1,i);c[i]=pr(x2,i);d[i]=pr(y2,i);num[i]=randull();}sort(a+1,a+n+1);sort(b+1,b+n+1);sort(c+1,c+n+1);sort(d+1,d+n+1);int r=0;ull s=0;for(int i=1;i<=n;i++) {
    while (r<n&&b[r+1].FR<a[i].FR) {
    r++;s^=num[b[r].SE];}s1[a[i].SE]^=s;}int l=n+1;s=0;for(int i=n;i>0;i--) {
    while (l>1&&a[l-1].FR>b[i].FR) {
    l--;s^=num[a[l].SE];}s1[b[i].SE]^=s;}r=0;s=0;for(int i=1;i<=n;i++) {
    while (r<n&&d[r+1].FR<c[i].FR) {
    r++;s^=num[d[r].SE];}s2[c[i].SE]^=s;}l=n+1;s=0;for(int i=n;i>0;i--) {
    while (l>1&&c[l-1].FR>d[i].FR) {
    l--;s^=num[c[l].SE];}s2[d[i].SE]^=s;}for(int i=1;i<=n;i++)if (s1[i]!=s2[i]) {
    puts("NO");return 0;}puts("YES");return 0;
}

E. New Year and Castle Construction

考虑点$p$可以在另$4$个点$a,b,c,d$所构成的某个多边形中的条件，可以发现这当且仅当$p$在$a,b,c,d$的凸包内成立。这里必要性显然，充分性只讨论$a,b,c,d$的凸包大小为$3$的情况，不妨设$d$在三角形$abc$内，由于没有重点和三点共线，对该三角形以$d$为中心作三角剖分，则$p$必然落在其中某个三角形内，显然能构造出一个包含它的四边形。
直接对每个点计数它在多少个大小为$4$的点集的凸包内有点困难，考虑计算反面，即它不在多少个大小为$4$的点集的凸包内。这是比较容易的，枚举一个点$p$，以$p$为原点，对其他点按极角排序，枚举排序后选的第一个点$q$，则要求剩余的$3$个点极角序在$q$后且与$q$极角差$<\pi$，这可以简单two pointer求解。
时间复杂度为$\mathcal{O}(n^2\log n)$。

#include <bits/stdc++.h>
#include <random>
#define FR first
#define SE second
#define y1 yyusing namespace std;typedef __int128 lll;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pr;struct Point {
    ll x,y;int quad; Point() {
    }Point(ll a,ll b):x(a),y(b) {
    if (x>=0&&y>0) quad=1;else if (x<=0&&y>0) quad=2;else if (x<0&&y<=0) quad=3;else quad=4;}Point operator - (Point b) {
    return Point(x-b.x,y-b.y);}
};inline lll cross(Point x,Point y) {
    return (lll)x.x*y.y-(lll)x.y*y.x;
}bool cmp(Point x,Point y) {
    if (x.quad!=y.quad) return x.quad<y.quad;else return cross(x,y)>0;
}Point p[3005],q[6005];int main() {
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) {
    int x,y;scanf("%d%d",&x,&y);p[i]=Point(x,y);}ll ans=(lll)n*(n-1)*(n-2)*(n-3)/24*(n-4);for(int i=1;i<=n;i++) {
    int sz=0;for(int j=1;j<=n;j++)if (j!=i) q[++sz]=p[j]-p[i];sort(q+1,q+sz+1,cmp);for(int j=1;j<=sz;j++) q[sz+j]=q[j];int r=1;for(int j=1;j<=sz;j++) {
    if (r<j) r=j;while (r<2*sz&&cross(q[j],q[r+1])>0) r++;int len=r-j;if (len>=3) ans-=(ll)len*(len-1)*(len-2)/6;}}printf("%lld\n",ans);return 0;
}

F. New Year and Social Network

显然一条$T1$中的边$(u_1,v_1)$能被一条$T2$中的边$(u_2,v_2)$替换，当且仅当$T1$中$u_2$到$v_2$的简单路径包含边$(u_1,v_1)$。
事实上，一定存在一个$T1$中边与$T2$中边的完美匹配。证明可以考虑Hall定理，对于一个$T1$中边大小为$k$的子集，删去这些边后会将$T1$分成$k+1$个连通块，考虑每个连通块的点集$S_1,S_2,...,S_{k+1}$，在$T2$上显然必须至少有$k$条两个端点在不同点集中的边，这些边一定能替换$T1$中选的大小为$k$的边子集中至少一条边。
考虑如何构造出一组解。我们每次从$T2$找一条边$(u,v)$，使得$u$为$T2$叶子，尝试在$T1$中找一条边$(u^{\prime },v^{\prime })$与它匹配。事实上，我们只需选择$T1$中$u$到$v$的简单路径上第一条边$(u,w)$即可。随后我们不再会用到点$u$了，那么可以在$T2$上删除这个叶子，并且在$T1$上合并点$u$和点$w$（这样显然不会影响之后的匹配），归纳构造即可。
事实上显然没有必要每次在$T1$上缩点，只需标记每条边是否已经被用过了，每次在初始的$T1$上找到简单路径上第一条没用过的边即可。这可以简单地用LCT维护，不过我选择了一个比较好写的做法：用并查集维护所有的合并，每次倍增找到应该合并的边。
时间复杂度为$\mathcal{O}(n\log n)$或$\mathcal{O}(n\log n\alpha (n))$。

#include <bits/stdc++.h>
#include <random>
#define FR first
#define SE second
#define y1 yyusing namespace std;typedef __int128 lll;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pr;namespace SETS {
    int fa[300005];void init(int n) {
    for(int i=1;i<=n;i++) fa[i]=i;
}int find_father(int x) {
    return (fa[x]==x)?x:fa[x]=find_father(fa[x]);
}bool check(int x,int y) {
    x=find_father(x);y=find_father(y);return x!=y;
}void merge(int x,int y) {
    x=find_father(x);y=find_father(y);if (x==y) return;fa[x]=y;
}}vector <int> e1[300005],e2[300005];
int id[300005],fa1[300005],dfs_cnt;int fa2[300005][20],dep[300005];void dfs1(int x) {
    id[++dfs_cnt]=x;for(int i=0;i<e1[x].size();i++)if (e1[x][i]!=fa1[x]) {
    int u=e1[x][i];fa1[u]=x;dfs1(u);}
}void dfs2(int x) {
    for(int i=0;i<e2[x].size();i++)if (e2[x][i]!=fa2[x][0]) {
    int u=e2[x][i];dep[u]=dep[x]+1;fa2[u][0]=x;for(int j=1;j<20;j++) fa2[u][j]=fa2[fa2[u][j-1]][j-1];dfs2(u);}
}int lca(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);int d=dep[x]-dep[y];for(int i=0;i<20;i++)if ((d>>i)&1) x=fa2[x][i];if (x==y) return x;for(int i=19;i>=0;i--)if (fa2[x][i]!=fa2[y][i]) {
    x=fa2[x][i];y=fa2[y][i];}return fa2[x][0];
}int jump(int x,int v,int d) {
    for(int i=19;i>=0;i--)if (fa2[x][i]&&dep[fa2[x][i]]>=d&&SETS::find_father(fa2[x][i])!=v) x=fa2[x][i];return x; 
}int main() {
    int n;scanf("%d",&n);for(int i=1;i<n;i++) {
    int x,y;scanf("%d%d",&x,&y);e2[x].push_back(y);e2[y].push_back(x);}dfs2(1);for(int i=1;i<n;i++) {
    int x,y;scanf("%d%d",&x,&y);e1[x].push_back(y);e1[y].push_back(x);}dfs1(1);printf("%d\n",n-1);SETS::init(n);for(int i=n;i>1;i--) {
    int x=id[i],y=fa1[x];int p=lca(x,y);if (SETS::check(x,p)) {
    int u=SETS::find_father(x);SETS::merge(u,fa2[u][0]);printf("%d %d %d %d\n",u,fa2[u][0],x,y);}else {
    int u=jump(y,SETS::find_father(x),dep[p]);SETS::merge(u,fa2[u][0]);printf("%d %d %d %d\n",u,fa2[u][0],x,y);}}return 0;
}

G. Seollal

一个挺神仙的题，范围比较有迷惑性。
问题可以描述为给定一个连通网格图，对图黑白染色（$(1,1)$为黑点），要求找出一棵生成树使得所有非$(1,1)$的黑点都度数$>1$，或判定无解。事实上，标准算法可以扩展到一般无向图，且给定限制的点形成独立集的情况。
令给定限制的点集为$S$。可以发现有解当且仅当能选出一个无环的边集，使得$S$中每个点的度数恰为$2$。这里必要性由于$S$为独立集，可以在真实的生成树上保留一部分边得到；充分性考虑将选出的边集扩展为一棵生成树即可。
这个充要条件还是不好直接考虑。我们考虑理解为选出一个大小最大的无环边集，使得每条边有一个端点在$S$中，且$S$中每个点的度数不超过$2$，问该最大大小是否为$2|S|$。限制选出的边集满足$S$中每个点的度数不超过$2$，这要求了选出的边集集合是一个度数限制拟阵的独立集（事实上无向图中选择一个边集，要求选出集合满足某个点独立集中每个点有度数上限都成立），这里的遗传性和交换性都很显然。那么问题可以理解为只考虑有一个端点在$|S|$中的边集，求图拟阵与度数限制拟阵的交的最大独立集。这是一个不超过$2nm$条边的拟阵交问题，直接套用拟阵交算法即可。
单组数据视实现时间复杂度为$\mathcal{O}(n^3{m}^3)$或$\mathcal{O}(n^3{m}^3\alpha (n))$。

#include <bits/stdc++.h>
#define FR first
#define SE secondusing namespace std;typedef pair<int,int> pr;namespace SETS {
    int fa[405];void init(int n) {
    for(int i=1;i<=n;i++) fa[i]=i;
}int find_father(int x) {
    return (fa[x]==x)?x:fa[x]=find_father(fa[x]);
}bool check(int x,int y) {
    x=find_father(x);y=find_father(y);return x!=y;
}void merge(int x,int y) {
    x=find_father(x);y=find_father(y);if (x==y) return;fa[x]=y;
}}char str[25][25];
int id[25][25];
bool kind[405];int d[1005];
pr ee[1005];
bool in[1005];vector <int> e[1005];
bool spos[1005],tpos[1005];void build(int n,int m) {
    memset(d,0,sizeof(d));memset(spos,0,sizeof(spos));memset(tpos,0,sizeof(tpos));for(int i=1;i<=m;i++) vector<int>().swap(e[i]);for(int i=1;i<=m;i++)if (in[i]) {
    if (kind[ee[i].FR]) d[ee[i].FR]++;if (kind[ee[i].SE]) d[ee[i].SE]++;}for(int i=1;i<=m;i++)if (in[i]) {
    SETS::init(n);for(int j=1;j<=m;j++)if (in[j]&&j!=i) SETS::merge(ee[j].FR,ee[j].SE);if (kind[ee[i].FR]) d[ee[i].FR]--;if (kind[ee[i].SE]) d[ee[i].SE]--;for(int j=1;j<=m;j++)if (!in[j]) {
    int u=ee[j].FR,v=ee[j].SE;if (!kind[u]&&!kind[v]) continue;if (SETS::check(u,v)) e[i].push_back(j);if ((!kind[u]||d[u]<2)&&(!kind[v]||d[v]<2)) e[j].push_back(i);} if (kind[ee[i].FR]) d[ee[i].FR]++;if (kind[ee[i].SE]) d[ee[i].SE]++;}SETS::init(n);for(int i=1;i<=m;i++)if (in[i]) SETS::merge(ee[i].FR,ee[i].SE);for(int i=1;i<=m;i++)if (!in[i]) {
    int u=ee[i].FR,v=ee[i].SE;if (!kind[u]&&!kind[v]) continue;if (SETS::check(u,v)) spos[i]=1;if ((!kind[u]||d[u]<2)&&(!kind[v]||d[v]<2)) tpos[i]=1;}
}bool vis[1005];
int p[1005];
queue <int> q;bool bfs(int n) {
    while (!q.empty()) q.pop();memset(vis,0,sizeof(vis));memset(p,0,sizeof(p));for(int i=1;i<=n;i++)if (spos[i]) {
    vis[i]=1;q.push(i);}while (!q.empty()) {
    int x=q.front();q.pop();if (tpos[x]) {
    for(int i=x;i;i=p[i]) in[i]^=1;return 1;}for(int i=0;i<e[x].size();i++)if (!vis[e[x][i]]) {
    int u=e[x][i];vis[u]=1;p[u]=x;q.push(u);}}return 0;
}char ans[45][45];
pr pos[405];int main() {
    int cases;scanf("%d",&cases);for(;cases;cases--) {
    memset(id,0,sizeof(id));memset(kind,0,sizeof(kind));int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%s",str[i]+1);int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if (str[i][j]=='O') {
    id[i][j]=++cnt;kind[cnt]=((i!=1||j!=1)&&(!((i+j)&1)));pos[cnt]=pr(i,j);}int sz=0,s=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if (str[i][j]=='O') {
    s+=kind[id[i][j]];if (j<m&&str[i][j+1]=='O') ee[++sz]=pr(id[i][j],id[i][j+1]);if (i<n&&str[i+1][j]=='O') ee[++sz]=pr(id[i][j],id[i+1][j]);}memset(in,0,sizeof(in));bool ok=1;for(int i=1;i<=2*s;i++) {
    build(cnt,sz);if (!bfs(sz)) {
    ok=0;break;}}if (!ok) {
    puts("NO");continue;}puts("YES");SETS::init(cnt);for(int i=1;i<=sz;i++)if (in[i]) SETS::merge(ee[i].FR,ee[i].SE);for(int i=1;i<=sz;i++)if (!in[i]&&SETS::check(ee[i].FR,ee[i].SE)) {
    in[i]=1;SETS::merge(ee[i].FR,ee[i].SE);}memset(ans,0,sizeof(ans));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) ans[2*i-1][2*j-1]=str[i][j];for(int i=1;i<=sz;i++)if (in[i]) {
    int u=ee[i].FR,v=ee[i].SE;if (pos[u].FR==pos[v].FR) ans[2*pos[u].FR-1][2*pos[u].SE]='O';elseans[2*pos[u].FR][2*pos[u].SE-1]='O';}for(int i=1;i<=2*n-1;i++) {
    for(int j=1;j<=2*m-1;j++) putchar((ans[i][j])?ans[i][j]:' ');putchar('\n');}}return 0;
}