| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 8/10 | O | Ø | O | Ø | . | Ø | . | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
属于是板子超级更新场了
A
题目描述
第一象限 $n\le 3e5$ 个点，开始有个 $(0,0)(1,1)$ 的小矩形，每次要扩展成一个更大的矩形使得其包含一些新的点，要让过程中的增量最小。
解题思路
贪心，每次加入增量最小的点。划成上、右上、右三个区域，分别用一些堆维护一下即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
typedef long long ll;
using namespace std;
struct P{
int x,y,i;
}p[N];
struct cmpx{bool operator()(const P&a,const P&b){return a.x>b.x;}};
struct cmpy{bool operator()(const P&a,const P&b){return a.y>b.y;}};
struct cmpxy{bool operator()(const P&a,const P&b){return a.x+a.y>b.x+b.y;}};
int vis[N];
priority_queue<P,vector<P>,cmpx>qx; // x <
priority_queue<P,vector<P>,cmpy>qy; // y <
priority_queue<P,vector<P>,cmpxy>qxy; // x+y <
priority_queue<P,vector<P>,cmpy>q1; // y <
priority_queue<P,vector<P>,cmpx>q2; // x <
int curx=1,cury=1;
int dis(int id){
return max(0,p[id].x-curx)+max(0,p[id].y-cury);
}
void update(int&id,P p){
if(!id)id=p.i;
else if(dis(id)>dis(p.i))id=p.i;
}
int main(){
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&p[i].x,&p[i].y);
p[i].i=i;
qx.push(p[i]);
qy.push(p[i]);
qxy.push(p[i]);
}
for(i=1;i<=n;i++){
int id=0;
if(!q1.empty())update(id,q1.top());
if(!q2.empty())update(id,q2.top());
while(!qxy.empty()){
auto x=qxy.top();
if(vis[x.i])qxy.pop();
else{
update(id,x);
break;
}
}
assert(id);
if(p[id].x<curx)q1.pop();
else if(p[id].y<cury)q2.pop();
else qxy.pop();
vis[id]=1;
curx=max(curx,p[id].x);
cury=max(cury,p[id].y);
while(!qy.empty()){
auto x=qy.top();
if(x.y>=cury)break;
qy.pop();
if(!vis[x.i])q2.push(x);
vis[x.i]=1;
}
while(!qx.empty()){
auto x=qx.top();
if(x.x>=curx)break;
qx.pop();
if(!vis[x.i])q1.push(x);
vis[x.i]=1;
}
printf("%d ",id);
}
return 0;
}
B
题目描述
有 $n\le 30$ 种物品，每一种物品 $1$ 或 $2$ 个。当第 $i$ 个物品有 $c_i$ 个时，选择 $i$ 的概率为 $\frac{c_iX_i}{\sum_j{c_jX_j}}$，告诉了玩 $m=100000$ 次游戏的选物品顺序，求概率数组 $X$。
解题思路
考虑从已有推未知。设 $be4_{i,j}$ 表示 $i$ 出现在 $j$ 前的次数，则与 $c_i$ 无关，我们可以大致地理解为 $\frac{X_i}{X_j}=\frac{be4_{i,j}}{be4_{j,i}}$。求出最大概率出现的元素，并设为 $X_i=1$。
增广时，使用已知且有有效信息的元素对新元素进行检查，计算出新元素 $X$ 的平均值。如果这个平均值过小，说明这个元素出现的次数与之前不是一个数量级，设置一个阶梯（实现中使用了当前最小值 $\times 1e-8$）即可；否则作为其 $X$ 更新答案。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
typedef long long ll;
using namespace std;
int a[N],be4[N][N];
double ans[N];
int eql(double a,double b){
return fabs(a-b)<1e-10;
}
int main(){
int m,n,tot=0,x,i,j,k;
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++){
ans[i]=-1;
scanf("%d",&x);
tot+=x;
}
for(i=1;i<=m;i++){
for(j=0;j<30;j++)scanf("%d",&a[j]);
for(j=0;j<30;j++)
for(k=0;k<j;k++)
be4[a[k]][a[j]]++;
}
int mx=1,cnt=0;
for(i=2;i<=n;i++)if(be4[mx][i]<be4[i][mx])mx=i;
ans[mx]=1;
vector<int>done;
while(++cnt<n){
vector<double>prob(n+1,-1);
for(i=1;i<=n;i++)if(ans[i]>=-0.5)done.pb(i);
sort(done.begin(),done.end(),[&](const int a,const int b){return ans[a]<ans[b];});
for(i=1;i<=n;i++){
if(ans[i]>=0)continue;
vector<int>temp=done;
while(temp.size()>=2){
if(be4[temp.back()][i]*1e-3>be4[i][temp.back()])temp.pop_back();
else break;
}
double avg=0;
for(auto x:temp)avg+=ans[x]*be4[i][x]/be4[x][i];
avg/=temp.size();
if(avg<1e-300){
double mn=1;
for(int i=1;i<=n;i++)if(ans[i]>=0)mn=min(ans[i],mn);
avg=mn*1e-8;
}
prob[i]=avg;
}
int id=-1;
for(i=1;i<=n;i++){
if(ans[i]>=0)continue;
if(id==-1||(prob[i]>prob[id]||(eql(prob[i],prob[id])&&be4[i][id]>be4[id][i])))id=i;
}
ans[id]=prob[id];
}
for(i=1;i<=n;i++){
if(ans[i]<1e-300)printf("%.300f\n",1e-290);
else printf("%.300f\n",min(ans[i],1.0));
}
return 0;
}
C
题目描述
$n\le 1000$ 个人唱歌，一共有 $s\le 1000$ 首歌。有 $k\le 10000$ 个待选唱歌节目，每个节目表示为 $(p,s,l)$ 表示某个人 $p$ 用 $l$ 语言唱 $s$ 歌。
安排一场演出，让每个人、每首歌都出现，而且同一个人不用同一种语言唱两次，同一首歌不被同一种语言唱两次。输出方案。
解题思路
S $\rightarrow$ 人 $\rightarrow$ (人 语言) $\rightarrow$ (语言 歌) $\rightarrow$ 歌 $\rightarrow$ T
上下界网络流。
有源汇上下界最大流：
$S\rightarrow…\rightarrow T$
- 预流每点 $low$，每条边变成 $upp-low$，每点记录净流出 $outflow$。新建超级源汇 $ns,nt$，净流出的连向超级汇，净流入的从超级源连向之，作为补偿流。
- 连接 $T\rightarrow S (inf)$ 形成无源汇网络
- $ns,nt$ 跑最大流，如果补偿流满流则是可行流
- $s,t$ 跑最大流，加上可行流即为答案
# 更新板子时刻 恰好缺这么个板子，于是封装了一下。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
typedef long long ll;
using namespace std;
namespace limit_networkflow{
struct Edge{
int e,n;
ll l;
}e[M<<1];
int hd[N],cur[N],cnt;
int max_node_cnt;
void add(int a,int b,ll l){e[++cnt].n=hd[a];e[cnt].e=b;e[cnt].l=l;hd[a]=cnt;}
void add2(int a,int b,ll l){add(a,b,l);add(b,a,0);}
ll outflow[N];
int dep[N];
ll dfs(int p,int s,int t,ll flow){
if(p==t)return flow;
int i;
for(i=cur[p];i;i=e[i].n){
int q=e[i].e;
cur[p]=i;
if(dep[q]==1+dep[p]&&e[i].l){
ll ans=dfs(q,s,t,min(flow,e[i].l));
if(ans>0){
e[i].l-=ans;
e[i^1].l+=ans;
return ans;
}
}
}
return 0;
}
int bfs(int s,int t){
static queue<int>Q;
int i;
memset(dep,0,sizeof(int)*(max_node_cnt+1));
Q.push(s);dep[s]=1;
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!dep[q]&&e[i].l)dep[q]=dep[p]+1,Q.push(q);
}
}
return dep[t];
}
ll dinic(int s,int t){
int i;
ll ans=0,d;
while(bfs(s,t)){
for(i=0;i<=max_node_cnt;i++)cur[i]=hd[i];
while((d=dfs(s,s,t,1e18)))
ans+=d;
}
return ans;
}
// n: point num
// edges: edge described as ((u,v), (low,upp))
ll calc(int n,vector<pair<pii,pll>>edges,int s,int t){
int i;
cnt=1;
memset(hd,0,sizeof(int)*(n+10));
memset(outflow,0,sizeof(ll)*(n+10));
ll sum_flow=0;
for(auto pr:edges){
int u=pr.fi.fi,v=pr.fi.se;
ll l=pr.se.fi,r=pr.se.se;
assert(r>=l&&l>=0);
outflow[u]+=l;
outflow[v]-=l;
add2(u,v,r-l);
sum_flow+=l;
}
int ns=n+1,nt=n+2; // super s/t
max_node_cnt=nt;
for(i=1;i<=n;i++){
if(outflow[i]>=0)add2(i,nt,outflow[i]);
else add2(ns,i,-outflow[i]);
}
add2(t,s,1e18); // inf
ll good_flow=dinic(ns,nt);
if(sum_flow>good_flow)return -1;
ll max_flow=dinic(s,t);
return max_flow;
}
}
map<int,pii>node;
int main(){
int i,j,n,m,k,cnt,s,t;
scanf("%d%d%d",&n,&m,&k);
cnt=n+m;
s=++cnt;
t=++cnt;
map<int,int>pl[1010];
map<int,int>sl[1010];
vector<pair<pii,pll>>edges;
map<pair<int,pii>,int>queries;
for(i=0;i<k;i++){
int p,s,l;
scanf("%d%d%d",&p,&s,&l);
queries[mp(l,mp(p,s))]=i+1;
if(!pl[p].count(l)){
pl[p][l]=++cnt;
edges.pb(mp(mp(p,cnt),mp(0,1)));
}
if(!sl[s].count(l)){
sl[s][l]=++cnt;
node[cnt]=mp(s,l);
edges.pb(mp(mp(cnt,s+n),mp(0,1)));
}
edges.pb(mp(mp(pl[p][l],sl[s][l]),mp(0,1)));
}
for(i=1;i<=n;i++)edges.pb(mp(mp(s,i),mp(1,1e9)));
for(i=n+1;i<=n+m;i++)edges.pb(mp(mp(i,t),mp(1,1e9)));
ll ans=limit_networkflow::calc(cnt,edges,s,t);
if(ans==-1)printf("-1\n");
else{
printf("%lld\n",ans);
vector<int>res;
for(i=1;i<=n;i++){
for(auto pr:pl[i]){
int lang=pr.fi;
int p=pr.se;
for(j=limit_networkflow::hd[p];j;j=limit_networkflow::e[j].n){
auto edge=limit_networkflow::e[j];
int q=edge.e;
ll l=edge.l;
if(l==0&&node.count(q)){ // not edges with people
assert(node.count(q));
auto pr=node[q];
assert(pr.se==lang);
res.pb(queries[mp(lang,mp(i,pr.fi))]);
}
}
}
}
for(auto x:res)printf("%d ",x);
}
return 0;
}
D
题目描述
有一些集合，每个集合有若干堆石子，每个人从一些集合中各恰选一堆出来。选完之后，Alice 挑选一个子集玩 Nim 游戏。已知 Alice 选了哪些，问 Bob 能不能先手必胜。
解题思路
题意也就是说，有一些二元组 (集合号,石子数)，两个拟阵（选出的所有元素构成线性基，每个集合至多选出一个元素），于是就是拟阵交的板子了。
拟阵是一种模拟线性无关组的抽象，类似线性无关地定义基（最大的线性无关的独立集）。要求拟阵有继承性（每个子集都线性无关），有交换性（如果有线性无关集合 $AB$ 满足 $|B|>|A|$，则必有 $x\in B-A$，使得 $A+\{x\}$ 线性无关）。
求一个集合中同时满足两个拟阵的过程，称为求拟阵交。
求拟阵交的过程就是暴力扩展。设两拟阵分别为 $M_1,M_2$，维护这个结果集合 $I$，初始时为空（或者为满足两拟阵的一个初始集合）。每次尝试加入一些元素使得两个拟阵仍然满足。设 $X_1$ 为 $I$ 外直接暴力加入 $x$ 仍保证 $M_1$ 的 $x$ 集合，$X_2$ 为 $I$ 外直接暴力加入 $x$ 仍保证 $M_2$ 的 $x$ 集合。如果能够加入 $X_1$ 中的某元素，删掉其对于 $M_2$ 的影响，再加上删掉元素能要回来的元素，…，一直加回来某个能保证 $M_2$ 的元素，那么恰好净增加了一个元素，一次扩展结束。考虑如何维护这个过程。
设二分图 $D_{M_1,M_2}(I)$ 的左部为 $I$，右部为 $\complement_SI$ ，左部 $y$ 指向右部 $x$ 当且仅当 $I-\{y\}+\{x\}$ 满足 $M_1$，右部 $x$ 指向左部 $y$ 当且仅当 $I-\{y\}+\{x\}$ 满足 $M_2$，则二分图上最短的从 $X_1$ 到 $X_2$ 的路径即为所求。$\complement_S I$ 表示补集 $S-I$。
原论文链接，P154，下截图摘录，可以与上述描述结合理解。
这里如果没有权值，具体求解的过程可以 BFS。对 $M_1,M_2$ 和每个 $y$ 维护一个 $I-y$ 的集合并检查 $x$ 加入是否合法即可。
本题的非模板具体实现（比较偏向原理，容易理解一些）：
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
typedef long long ll;
using namespace std;
struct linear_base{
ll b[60];
void init(){memset(b,0,sizeof(b));}
linear_base(){init();}
int insert(ll x,int flag){
int i;
for(i=59;i>=0;i--){
if(!(x>>i&1))continue;
if(b[i])x^=b[i];
else{
if(flag)b[i]=x;
return 1;
}
}
return 0;
}
int check(ll x){
return insert(x,0);
}
}lb;
int vis[N];
vector<pair<ll,int>>v;
set<int>I,_I; // _I is C_{S} I
linear_base lbI;
vector<linear_base>I_minus; // I-y
vector<int>G[N];
set<int>X1,X2;
int dfsvis[N],pre[N];
int dfs(int p,vector<int>&path){
path.pb(p);
dfsvis[p]=1;
if(X2.count(p))return 1;
for(auto q:G[p])
if(!dfsvis[q]&&dfs(q,path))return 1;
path.erase(--path.end());
return 0;
}
int augment(){
memset(vis,0,sizeof(vis));
memset(dfsvis,0,sizeof(dfsvis));
lbI.init();
for(auto idx:I)G[idx].clear(),I_minus[idx].init();
for(auto idx:_I)G[idx].clear();
X1.clear();X2.clear();
for(auto idx:I){
vis[v[idx].se]=1;
assert(lbI.insert(v[idx].fi,1));
for(auto idy:I)
if(idx!=idy)
I_minus[idx].insert(v[idy].fi,1);
}
for(auto idx:_I){
if(lbI.check(v[idx].fi)){
// X1 ^ X2 != empty
if(!vis[v[idx].se]){
I.insert(idx);
_I.erase(idx);
return 1;
}
else X1.insert(idx);
}else if(!vis[v[idx].se])X2.insert(idx);
}
for(auto idy:I){
for(auto idx:_I){
if(I_minus[idy].check(v[idx].fi))G[idy].pb(idx);
if(v[idx].se==v[idy].se||!vis[v[idx].se])G[idx].pb(idy);
}
}
queue<int>Q;
memset(pre,-1,sizeof(pre));
for(auto idy:X1){
Q.push(idy);
pre[idy]=-2;
}
while(!Q.empty()){
int p=Q.front();Q.pop();
for(auto q:G[p]){
if(pre[q]!=-1)continue;
pre[q]=p;
if(X2.count(q)){
int x=q;
while(x>=0){
if(I.count(x))I.erase(x),_I.insert(x);
else I.insert(x),_I.erase(x);
x=pre[x];
}
return 1;
}
Q.push(q);
}
}
return 0;
}
int main(){
int i,j,n,m,num,k;
ll x;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%lld",&x);
v.pb(mp(x,i));
}
scanf("%d",&m);
for(i=n+1;i<=n+m;i++){
scanf("%d",&num);
for(k=0;k<num;k++){
scanf("%lld",&x);
v.pb(mp(x,i));
}
}
I_minus.resize(N);
for(i=0;i<v.size();i++)_I.insert(i);
for(i=0;i<n+m;i++)
if(!augment())return printf("-1"),0;
for(auto idx:I)if(v[idx].se>n)printf("%lld\n",v[idx].fi);
return 0;
}
根据上述做法，下面给出一个模板，其中为简化而进行的细节比较多（如将 $I$ 记录为特殊的 $\complement_Sn$ 并进行拓展等）。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
typedef long long ll;
using namespace std;
struct LBMatroid{
vector<ll>b;
LBMatroid(int n):b(n,0){}
int insert(pli pr,int flag=1){
int i;
ll x=pr.fi;
for(i=61;i>=0;i--){
if(!(x>>i&1))continue;
if(b[i])x^=b[i];
else{
if(flag)b[i]=x;
return 1;
}
}
assert(!flag);
return 0;
}
int independent_with(pli pr){return insert(pr,0);}
void clear(){fill(begin(b),end(b),0);}
};
// every element at most appear once
struct AtmostMatroid{
vector<int>vis;
AtmostMatroid(int n):vis(n){}
int insert(pli pr){
int id=pr.se;
assert(!vis[id]);
vis[id]=1;
}
int independent_with(pli pr){return !vis[pr.se];}
void clear(){fill(begin(vis),end(vis),0);}
};
template<class M1,class M2,class T>struct MatroidIntersect{
int n; // [0,n)
vector<T>ground;
vector<char>inI;
vector<M1>m1;
vector<M2>m2;
MatroidIntersect(M1 _m1,M2 _m2,vector<T>_ground):n(_ground.size()),ground(_ground),m1(n+1,_m1),m2(n+1,_m2),inI(n+1){}
vector<T>solve(){
int i;
inI[n]=1; // n stands for the all set
for(i=0;i<n;i++){
// make sure X1 and X2 have no intersection
if(test(m1,i,n)&&test(m2,i,n)){
inI[i]=1;
m1[n].insert(ground[i]);
m2[n].insert(ground[i]);
}
}
while(augment());
vector<T>res;
for(i=0;i<n;i++)if(inI[i])res.pb(ground[i]);
return res;
}
template <class M>int test(vector<M>&m,int x,int y){
// when y isnt n, add x into S\y, still satisfy m matroid?
// when y is n, add x into I, still satisfy m matroid?
return !inI[x]&&inI[y]&&m[y].independent_with(ground[x]);
}
int augment(){
int i,j;
// update S\i
for(i=0;i<=n;i++){
if(inI[i]){
m1[i].clear();m2[i].clear();
for(j=0;j<n;j++)if(i!=j&&inI[j])
m1[i].insert(ground[j]),m2[i].insert(ground[j]);
}
}
queue<int>Q({n});
vector<int>pre(n+1,-1);
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=0;i<=n;i++){
if(pre[i]==-1&&(inI[i]?test(m2,p,i):test(m1,i,p))){
if(i==n){
while(p!=n)inI[p]^=1,p=pre[p];
return 1;
}
pre[i]=p;
Q.push(i);
}
}
}
return 0;
}
};
int main(){
int i,j,n,m,num,k;
ll x;
vector<pli>v;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%lld",&x);
v.pb(mp(x,i));
}
scanf("%d",&m);
for(i=n+1;i<=n+m;i++){
scanf("%d",&num);
for(k=0;k<num;k++){
scanf("%lld",&x);
v.pb(mp(x,i));
}
}
vector<pli>ans=MatroidIntersect<LBMatroid,AtmostMatroid,pli>(
LBMatroid(60),AtmostMatroid(v.size()),v
).solve();
if(ans.size()<n+m)printf("-1\n");
else for(auto pr:ans)if(pr.se>n)printf("%lld\n",pr.fi);
return 0;
}
E
题目描述
解题思路
AC代码
2
F
题目描述
给一张 $n\le 200,m\le 1000$ 的图，给出平面上每个点的坐标，保证边两两不相交于一个内部点（这个定义就非常神秘，数据不满足它是一个平面图）。
让你将点分成两个集合，割边为不同集合间点的连边，求最大割。
解题思路
暂且不管它的神秘定义，求平面图最大割。
按照割的定义，我们考虑被割掉的边，它们构成一张二分图。也就是我们需要将图删掉尽量小权重的边后，让整张图变成二分图。
由于原图是平面图，而平面图是二分图 $\Leftrightarrow $ 每个围成的区域都由偶数条边组成，故考虑将奇区域两两合并成偶区域。由于边都是正权边，这个合并所删除的边必定能由不相交的一堆边进行表示。
如下左图，有四个奇区域，需要两两合并为数个偶区域。也可能与无限域进行合并，如下右图。
因此，将每个区域当成一个点，构建对偶图，奇区域变成了奇数度数的点。在对偶图上两两奇点都可以进行匹配，求完多源最短路再求一个一般图最小权匹配即可。
板子大合集：先将原图根据坐标转化为对偶图（$O(n\log n)$），再求两两点之间的最短路（$O(n^2\log n)$），再设置一下奇点间边权跑一般图最大权匹配（$O(n^3)$）。所以码量还挺大的。
平面图转对偶图是头一次写，下面简述一下思路。
对于每一个区域，它包含了一圈边，考虑求出每个区域对应了哪些边，并且要快速知道每个边连接了哪两个区域。将无向图拆成两条单向边，互相记录对面在哪里（或者利用 $i$ 和 $i\oplus 1$ 的存图法），这样一个区域就是由一些有向边连起来的部分了。
下左图为原图，右边的三张图均为逆时针包起来的区域（第二张图是无限域，有向面积为负，故显示为顺时针）。因此对于每个点，按照极角序排一下各个边，就可以逐顶点二分查了。一个无向边的两个有向边分别位于两个区域，于是问题得解。平面图 $E\le 3V-6$，故这部分的复杂度是可以做到 $O((n+m)\log n)=O(n\log n)$ 的。
好题，就是数据太傻逼了。说是平面图整了一堆有重合的平行边。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
typedef long long ll;
using namespace std;
using T=ll;
namespace blossom_tree{
const T INF=0x3f3f3f3f3f3f3f3f;
struct edge{
int u,v;T w;
edge(){}
edge(int u,int v,T w):u(u),v(v),w(w){}
};
// Graph
int n,n_x; // [1, n]: point; [n+1, n_x]: flower
edge g[N][N]; // adjacent matrix
// flower
vector<int>flower[N]; // nodes in flower i (outer flower)
int root[N]; // flower root, root<=n root=i: normal nodes
int flower_from[N][N]; // flower_from[b][x]: outermost flower in b that contains x
// slack
T label[N]; // node label, [1, n] point label, [n+1, n_x] flower label
int col[N]; // color saved at flower root
int slv[N]; // slack node of NON LEAF NODES, slv[y]=x z(x,y) min_x
// match
int mat[N]; // match, mat[x]=y (x,y)\in E
int fa[N]; // fa in cross tree
int vis[N]; // if in path
queue<int>Q; // bfs queue
// calculate slv
inline T calc_slv(edge e){return label[e.u]+label[e.v]-e.w;}
inline void update_slv(int u,int v){if(!slv[v]||calc_slv(g[u][v])<calc_slv(g[slv[v]][v]))slv[v]=u;}
inline void recalc_slv(int u){
slv[u]=0;
for(int i=1;i<=n;i++)if(g[i][u].w>0&&root[i]!=u&&col[root[i]]==1)update_slv(i,u);
}
// only push nodes, not flowers
void q_push(int x){
if(x<=n)Q.push(x);
else for(auto p:flower[x])q_push(p);
}
// set root of all nodes in x to r
void set_root(int x,int r){
root[x]=r;
if(x>n)for(auto p:flower[x])set_root(p,r);
}
// return a (+-)^k path in flower b from root[b] to x
int get_even_path_in_flower(int b,int x){
int pr=find(flower[b].begin(),flower[b].end(),x)-flower[b].begin();
assert(b>n&&b<=n_x&&pr<flower[b].size()); // b is flower, x in b
if(pr%2==0)return pr;
reverse(flower[b].begin()+1,flower[b].end());
return flower[b].size()-pr;
}
// set (u,v) match, can be flower
void set_match(int u,int v){
mat[u]=g[u][v].v;
if(u>n){
edge e=g[u][v];
int xr=flower_from[u][e.u];
int pr=get_even_path_in_flower(u,xr);
for(int i=0;i<pr;i++)set_match(flower[u][i],flower[u][i^1]);
set_match(xr,v);
rotate(flower[u].begin(),flower[u].begin()+pr,flower[u].end()); // change receptacle
}
}
// link 2 S points
void side_augment(int u,int v){
int nv=root[mat[u]],nu=root[fa[nv]];
while(1){
set_match(u,v);
u=nu,v=nv;
if(!nv)break;
set_match(nv,nu);
nv=root[mat[u]],nu=root[fa[nv]];
}
}
void linkSS(int u,int v){
side_augment(u,v);
side_augment(v,u);
}
int get_lca(int u,int v){
static int t=0;
++t; // to avoid clearing vis
while(u||v){
if(vis[u]==t)return u;
vis[u]=t;
u=root[mat[u]];
if(u)u=root[fa[u]];
if(!u)swap(u,v);
}
return 0;
}
void add_blossom(int u,int v,int r){
int i,b=n+1;
while(b<=n_x&&root[b])b++;
if(b>n_x)++n_x;
// clear
col[b]=1;label[b]=0;mat[b]=mat[r];flower[b].clear();
for(i=1;i<=n_x;i++)g[i][b].w=g[b][i].w=0;
for(i=1;i<=n;i++)flower_from[b][i]=0;
// construct flower
while(u!=r){
flower[b].pb(u);u=root[mat[u]];q_push(u);
flower[b].pb(u);u=root[fa[u]];
}
flower[b].pb(r);
reverse(flower[b].begin(),flower[b].end());
while(v!=r){
flower[b].pb(v);v=root[mat[v]];q_push(v);
flower[b].pb(v);v=root[fa[v]];
}
// set as outermost flower
set_root(b,b);
// calculate slack
for(auto p:flower[b]){
for(i=1;i<=n_x;i++){
// set to min slave
if(!g[b][i].w||calc_slv(g[p][i])<calc_slv(g[b][i])){
g[b][i]=g[p][i];
g[i][b]=g[i][p];
}
}
for(i=1;i<=n;i++)if(flower_from[p][i])flower_from[b][i]=p;
}
recalc_slv(b);
}
// only expand outermost blossom b, b is T(white) blossom
void expand_blossom(int b){
int i,x;
for(auto p:flower[b])set_root(p,p);
x=flower_from[b][g[b][fa[b]].u];
// [0,pr]: (+-)^k, insert into tree, add black to queue
int pr=get_even_path_in_flower(b,x);
col[x]=2;fa[x]=fa[b];
for(i=0;i<pr;i+=2){
// from bottom to upper layer in tree
int white=flower[b][i];
int black=flower[b][i+1];
col[black]=1;col[white]=2;
fa[white]=g[black][white].u;
slv[black]=slv[white]=0;
q_push(black);
}
// others: color=0
for(i=pr+1;i<flower[b].size();i++){
col[flower[b][i]]=0;
recalc_slv(flower[b][i]);
}
// delete b
root[b]=0;
flower[b].clear();
}
// found_edge
int augment_path(edge e){
int u=root[e.u],v=root[e.v];
if(!col[v]){
assert(mat[v]);
fa[v]=e.u;
col[v]=2;
int nu=root[mat[v]];
slv[nu]=slv[v]=0;
col[nu]=1;
q_push(nu);
}else if(col[v]==1){
int r=get_lca(u,v);
if(r)add_blossom(u,v,r);
else return linkSS(u,v),1;
}
return 0;
}
int augment(){
int i;
memset(col,0,sizeof(int)*(n_x+1));
memset(slv,0,sizeof(int)*(n_x+1));
memset(fa,0,sizeof(int)*(n_x+1));
Q=queue<int>();
for(i=1;i<=n_x;i++)
if(root[i]==i&&!mat[i]){
// add all unmatched points
col[i]=1;
q_push(i);
}
if(Q.empty())return 0;
while(1){
while(!Q.empty()){
int p=Q.front();Q.pop();
assert(col[root[p]]==1);
for(i=1;i<=n;i++){
if(g[p][i].w==0||root[i]==root[p])continue;
// not in same flower
T d=calc_slv(g[p][i]);
if(!d){if(augment_path(g[p][i]))return 1;}
else if(col[root[i]]!=2)update_slv(p,root[i]);
}
}
T delta=INF;
// calc delta
for(i=1;i<=n;i++)if(col[root[i]]==1)delta=min(delta,label[i]);
for(i=n+1;i<=n_x;i++)if(root[i]==i&&col[i]==2)delta=min(delta,label[i]/2);
for(i=1;i<=n_x;i++){
if(root[i]!=i||!slv[i])continue;
if(!col[i])delta=min(delta,calc_slv(g[slv[i]][i]));
else if(col[i]==1)delta=min(delta,calc_slv(g[slv[i]][i])/2);
}
// update label
for(i=1;i<=n;i++){
if(col[root[i]]==1)label[i]-=delta;
else if(col[root[i]]==2)label[i]+=delta;
}
for(i=n+1;i<=n_x;i++){
if(root[i]!=i)continue;
if(col[i]==1)label[i]+=2*delta;
else if(col[i]==2)label[i]-=2*delta;
}
for(i=1;i<=n;i++)if(label[i]<=0)return 0;
for(i=1;i<=n_x;i++){
if(root[i]!=i||!slv[i]||root[slv[i]]==i)continue;
if(calc_slv(g[slv[i]][i])==0&&augment_path(g[slv[i]][i]))return 1;
}
// expand
for(i=n+1;i<=n_x;i++)
if(root[i]==i&&col[i]==2&&label[i]==0)
expand_blossom(i);
}
return 0;
}
void init(int _n,vector<pair<T,pii>>edges){
int i,j;
n=n_x=_n;
memset(mat,0,sizeof(mat));
for(i=0;i<=n;i++){
root[i]=i;
flower[i].clear();
for(j=0;j<=n;j++){
flower_from[i][j]=(i==j)?i:0;
g[i][j]=edge(i,j,0);
}
}
T w_max=0;
for(auto pr:edges){
int u=pr.se.fi,v=pr.se.se;
T w=pr.fi;
g[u][v]=edge(u,v,w*2);
g[v][u]=edge(v,u,w*2);
w_max=max(w_max,w);
}
for(i=1;i<=n;i++)label[i]=w_max;
}
pair<int,T>calc(){
int i,cnt=0;T s=0;
while(augment())++cnt;
for(i=1;i<=n;i++)if(mat[i]>i)s+=g[i][mat[i]].w/2;
return mp(cnt,s);
}
}
namespace planar_to_dual{
const double eps=1e-12;
int dcmp(double a,double b){return fabs(a-b)<eps?-1:a<b;}
typedef struct Point{
int x,y;
Point(){}
Point(int x,int y):x(x),y(y){}
ll operator^(Point b){return 1LL*x*b.y-1LL*y*b.x;}
double r()const{return atan2(y,x);}
}P;
ll cross(P a,P b){return a^b;}
P operator-(P a,P b){return Point(a.x-b.x,a.y-b.y);}
vector<P>p;
struct Edge{
int u,v,ind;
int origin;
T l;
double r;
bool operator<(const Edge&b)const{
int res=dcmp(r,b.r);
if(res==-1)res=0;
return res;
};
}e[M];
int cnt,n,nxt[M]; // nxt: counterclockwise nxt edge
vector<Edge>G[N];
void add(int a,int b,T l,int origin){
e[++cnt].v=b;e[cnt].u=a;
e[cnt].l=l;e[cnt].ind=cnt;
e[cnt].origin=origin;
e[cnt].r=(p[b]-p[a]).r();
G[a].pb(e[cnt]);
}
// pos: counterclockwise area of i
int curface,pos[M],outer,indeg[M];
ll s[M]; // square
pair<int,vector<pair<pair<T,int>,pii>>> calc(){
int i,j;
for(i=1;i<=n;i++)sort(G[i].begin(),G[i].end());
for(i=2;i<=cnt;i++){
auto u=e[i].u,v=e[i].v;
int it=lower_bound(G[v].begin(),G[v].end(),e[i^1])-G[v].begin();
nxt[i]=G[v][(it+1)%G[v].size()].ind;
pos[i]=0;
}
for(i=2;i<=cnt;i++){
if(pos[i])continue;
pos[i]=++curface;s[curface]=0;
for(j=nxt[i];!pos[j];j=nxt[j]){
int u=e[j].u,v=e[j].v,rt=e[i].u;
pos[j]=curface;
}
}
vector<pair<pair<T,int>,pii>>edges;
for(i=2;i<=cnt;i+=2)edges.pb(mp(mp(e[i].l,e[i].origin),mp(pos[i],pos[i^1])));
return mp(curface,edges);
}
void init(int _n,vector<P>pos,vector<pair<T,pii>>edges){
int i;
cnt=1;n=_n;curface=0;
assert(n==pos.size()-1&&n>=0);
for(i=1;i<=n;i++)G[i].clear();
p=pos;
int t=0;
for(auto pr:edges){
int u=pr.se.fi,v=pr.se.se;
T w=pr.fi;
int origin=t;
add(u,v,w,origin);
add(v,u,w,origin);
t++;
}
}
}
int ind[N],vis[N],del[N];
ll dis[N][N];pii pre[N][N];
int main(){
int i,j,n,m,init_n;
ll ans=0;
scanf("%d%d",&init_n,&m);
// planar graph to dual graph
vector<pair<T,pii>>init_edges;
vector<planar_to_dual::P>pos(init_n+1);
for(i=1;i<=init_n;i++)scanf("%d%d",&pos[i].x,&pos[i].y);
for(i=0;i<m;i++){
int u,v;T l;
scanf("%d%d%lld",&u,&v,&l);
init_edges.pb(mp(l,mp(u,v)));
}
planar_to_dual::init(init_n,pos,init_edges);
auto pr=planar_to_dual::calc();
// shortest path
n=pr.fi;
vector<pair<pair<T,int>,pii>> edges=pr.se;
vector<pair<pil,int>>G[N];
map<pii,T>edge_mp;
for(auto pr:edges){
int u=pr.se.fi,v=pr.se.se;
T l=pr.fi.fi;
int origin=pr.fi.se;
ind[u]++;
ind[v]++;
G[u].pb(mp(mp(v,l),origin));
G[v].pb(mp(mp(u,l),origin));
}
for(i=1;i<=n;i++){
memset(vis,0,sizeof(int)*(n+1));
memset(dis[i],0x3f,sizeof(ll)*(n+1));
memset(pre[i],0,sizeof(pii)*(n+1));
dis[i][i]=0;
priority_queue<pli>Q;
Q.push(mp(0,i));
while(!Q.empty()){
int p=Q.top().se;Q.pop();
if(vis[p])continue;vis[p]=1;
for(auto pr:G[p]){
int q=pr.fi.fi;
if(dis[i][q]>dis[i][p]+pr.fi.se){
dis[i][q]=dis[i][p]+pr.fi.se;
pre[i][q]=mp(p,pr.se);
Q.push(mp(-dis[i][q],q));
}
}
}
}
vector<pair<T,pii>>blossom_edges;
for(i=1;i<=n;i++)if(ind[i]%2==1)
for(j=1;j<i;j++)if(ind[j]%2==1)
blossom_edges.pb(mp(2e11-dis[i][j],mp(i,j)));
// general maximum weight match
blossom_tree::init(n,blossom_edges);
blossom_tree::calc();
vector<int>graph[N];
static int col[N];
for(i=1;i<=n;i++){
int j=blossom_tree::mat[i];
if(j>i){
while(i!=j){
int tj=pre[i][j].fi;
del[pre[i][j].se]=1;
j=tj;
}
}
}
for(i=0;i<m;i++)
if(!del[i]){
ans+=init_edges[i].fi;
int u=init_edges[i].se.fi,v=init_edges[i].se.se;
graph[u].pb(v);graph[v].pb(u);
}
function<void(int)> dfs=[&](int p){
for(auto q:graph[p])
if(!col[q])
col[q]=col[p]^1,dfs(q);
};
for(i=1;i<=init_n;i++)if(!col[i])col[i]=2,dfs(i);
printf("%lld\n",ans);
for(i=1;i<=init_n;i++)printf("%d ",col[i]%2);
return 0;
}
G
题目描述
解题思路
AC代码
2
H
题目描述
签到题。
解题思路
略。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
typedef long long ll;
using namespace std;
int main(){
int i,j,n,ans=0,a;
scanf("%d",&n);
for(i=1;i<=n;i++){
int mn=1e9;
for(j=1;j<=n;j++){
scanf("%d",&a);
mn=min(mn,a);
}
ans=max(ans,mn);
}
printf("%d",ans);
return 0;
}
I
题目描述
有一个 $n\times m$ 的矩阵，每一个方格内有一个拖鞋（左脚或者右脚）。可以做任意次操作，每次可以选两个相邻拖鞋，一个顺时针转 $90$ 度，一个逆时针转 $90$ 度。问最后最多有多少对拖鞋可以左右配对。
解题思路
一次操作没有改变的是总的方向，因此考虑旋转程度对 $4$ 的模数。因此先左右配对，求一个二分图最大匹配。如果不是所有格子都在匹配中，那么通过非匹配格子一定能把它们转到互相匹配；否则检查一下对于这个匹配，旋转程度的模数是否合法。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
typedef long long ll;
using namespace std;
char s[M][M][10];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int n,m;
int in(int x,int y){
return x>=0&&y>=0&&x<n&&y<m;
}
int id(int x,int y){return x*m+y;}
pii pos(int x){return mp(x/m,x%m);}
vector<int>G[N];
void add(int a,int b){G[a].pb(b);}
int vis[N],mt[N];
int dfs(int p,int t){
for(auto q:G[p]){
if(t!=vis[q]){
vis[q]=t;
if(mt[q]==-1||dfs(mt[q],t)){
mt[q]=p;
return 1;
}
}
}
return 0;
}
int maxflow(){
int i,ans=0;
memset(vis,-1,sizeof(vis));
memset(mt,-1,sizeof(mt));
for(i=0;i<=id(n-1,m-1);i++)
if(dfs(i,i))ans++;
return ans;
}
int dir[M][M];
int main(){
int i,j,k;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++){
scanf("%s",s[i][j]);
switch(s[i][j][1]){
case '^':{
dir[i][j]=0;
break;
}
case '>':{
dir[i][j]=1;
break;
}
case 'v':{
dir[i][j]=2;
break;
}
default:{
dir[i][j]=3;
break;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(s[i][j][0]=='L'){
for(k=0;k<4;k++){
int tx=i+dx[k],ty=j+dy[k];
if(!in(tx,ty)||s[tx][ty][0]=='L')continue;
add(id(i,j),id(tx,ty));
}
}
}
}
int ans=maxflow();
if(ans*2==n*m){
int r=0;
for(i=0;i<n*m;i++){
if(mt[i]!=-1){
auto pr=pos(i);
auto pl=pos(mt[i]);
assert(s[pl.fi][pl.se][0]=='L');
assert(s[pr.fi][pr.se][0]=='R');
for(k=0;k<4;k++){
int tx=pl.fi+dx[k];
int ty=pl.se+dy[k];
if(mp(tx,ty)==pr){
r+=dir[pl.fi][pl.se]+dir[pr.fi][pr.se]-2*(k-1);
}
}
}
}
if(r%4)ans--;
}
printf("%d",ans);
return 0;
}
J
题目描述
有三种人，你需要在一定指令数（$30m$）内辨别他是哪种人。$m\in[1,1000]$，也不告诉你。
第一种人初始在 $m$ ，让他往右走的时候会往右走两步，让他往左走的时候往左走一步。
第二种人初始在 $-m$ ，让他往右走的时候会往左走两步，让他往左走的时候往右走一步。
第一种人初始在 $m$ 或者 $-m$，有两种情况：让他往右走的时候会往右走一步，让他往左走的时候往左走一步；或者让他往右走的时候会往左走一步，让他往左走的时候往右走一步。
解题思路
考虑左右摆动，先往右走一步，再往左走一些步数，再往右走一些步数，使得中间每个元素都会被覆盖到。取公比为 $3$ 可过。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
typedef long long ll;
using namespace std;
void u(){
printf("! ugly\n");
fflush(stdout);
}
void g(){
printf("! good\n");
fflush(stdout);
}
void b(){
printf("! bad\n");
fflush(stdout);
}
int query(char* s){
printf("%s\n",s);
fflush(stdout);
int x;
scanf("%d",&x);
return x;
}
int query(int x){
if(x==1)return query("+");
else return query("-");
}
int main(){
int i,flag=0,x=1,bas=3,cur=0;
while(1){
cur^=1;
for(i=0;i<x;i++){
int r=query(cur);
if(r){
query(1);
r=query(0);
if(r)u();
else if(query(0))g();
else b();
return 0;
}
}
x*=bas;
}
return 0;
}