avatar

目录
2019 ICPC Asia Nanchang Regional

2019 ICPC Asia Nanchang Regional

solved:ACEGL 5/13

A. 9102

题意:

  让你搞一个可持久化并查集,而且资瓷删除。不要求强制在线。

解析:

  对于有时间戳要求但是不要求强制在线的,我们可以按照时间排序,依次处理。具体来说:我们对每一个操作建立由该操作导向下一个操作的时间戳标记,然后从开始处 dfs,处理完所有情况后回溯回初始情况即可。
  我们现在搞这个并查集,合并查找按照规矩来,但因为考虑到要回溯复原我们就放弃路径压缩但使用启发式合并(深度)。我们关注删除:很明显,我们不能直接通过替换父节点来满足删除,因为如果更改的节点不是叶子的话会对下面造成影响。
  这里感谢金巨(%%%)的思路:我们可以构造出该节点的影分身,原先点的具体情况及大小进行处理,仅起到占位的作用;新的节点代替原先的节点发挥作用,并按照规定挂到新的树上。在代码里,$id[i]$ 指的就是原先 $i$ 的点现在所在的位置。
  然后这道题就解决了。时间复杂度 $O(mlog\ n)$。

代码:

cpp
1
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long
#define il inline
il int read(){
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1; ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();
}
return x*f;
}
const int maxn=1000010;
int sz[maxn<<1],fa[maxn<<1],dep[maxn<<1];
int id[maxn];
struct operation{
int flag,x,y;
}opt[maxn];
int ans[maxn];
vector<int> G[maxn];
int n,m,read_k,tot;
int findfather(int x){
return (fa[x]==x)?x:findfather(fa[x]);
}
void work(int nowtime){
operation tmp=opt[nowtime];
int xx=tmp.x,yy=tmp.y;
if (tmp.flag==4){ //whether belongs to the same tree
if (id[xx]==-1||id[yy]==-1){
ans[nowtime]=0;
}else{
int fx=findfather(id[xx]),fy=findfather(id[yy]);
ans[nowtime]=(fx==fy);
}
}
if (tmp.flag==5){ //query sum
if (id[xx]==-1){
ans[nowtime]=0;
}else{
ans[nowtime]=sz[findfather(id[xx])];
}
}
for (int i=0;i<G[nowtime].size();++i){
operation nxt=opt[G[nowtime][i]];
int nx=nxt.x,ny=nxt.y;
if (nxt.flag==1){ //merge x's ancestor's whole tree to y's
if (id[nx]==-1||id[ny]==-1){
work(G[nowtime][i]); continue;
}
int fnx=findfather(id[nx]),fny=findfather(id[ny]);
if (fnx==fny){
work(G[nowtime][i]); continue;
}
if (dep[fnx]==dep[fny]){
fa[fny]=fnx; sz[fnx]+=sz[fny]; dep[fnx]++;
work(G[nowtime][i]);
fa[fny]=fny; sz[fnx]-=sz[fny]; dep[fnx]--;
}else{
if (dep[fnx]<dep[fny]) swap(fnx,fny);
fa[fny]=fnx; sz[fnx]+=sz[fny];
work(G[nowtime][i]);
fa[fny]=fny; sz[fnx]-=sz[fny];
}
continue;
}
if (nxt.flag==2){ //extermination
int res=id[nx];
if (id[nx]==-1){
work(G[nowtime][i]); continue;
}
int ff=findfather(id[nx]);
sz[ff]--; id[nx]=-1;
work(G[nowtime][i]);
id[nx]=res; sz[ff]++;
continue;
}
if (nxt.flag==3){ //transfer only one
if (id[nx]==-1||id[ny]==-1){
work(G[nowtime][i]); continue;
}
int ffx=findfather(id[nx]),ffy=findfather(id[ny]);
if (ffx==ffy){
work(G[nowtime][i]); continue;
}
int res=id[nx];
id[nx]=++tot; sz[id[nx]]=1; sz[ffx]--;
fa[id[nx]]=ffy; sz[ffy]++;
work(G[nowtime][i]);
sz[ffx]++; sz[ffy]--; id[nx]=res;
continue;
}
work(G[nowtime][i]);
}
}
int main(){
n=read(); m=read(); tot=n;
for (int i=1;i<=m;++i){
opt[i].flag=read();
read_k=read(); G[read_k].push_back(i);
opt[i].x=read();
if (opt[i].flag==1||opt[i].flag==3||opt[i].flag==4) opt[i].y=read();
}
for (int i=1;i<=n;++i){
fa[i]=i; sz[i]=1; id[i]=i;
}
work(0);
for (int i=1;i<=m;++i){
if (opt[i].flag==4){
if (ans[i]) printf("Yes\n");
else printf("No\n");
}
if (opt[i].flag==5){
printf("%d\n",ans[i]);
}
}
return 0;
}

B. A Funny Bipartite Graph

C. And and Pair

题意:

  给定二进制数 $n$,求有多少不大于 $n$ 的 $(i,j)$ 满足一下条件:

  • $0\le i\le j\le n$
  • $i$ & $n=i$
  • $i$ & $j=0$

解析:

  一开始想用数位dp搞一下,但觉得难以实现放弃。
  我们只考虑 $i,j$ 的关系,由第三条规则可以得知(仅看中一个位):

$$i=0\Rightarrow j=0,1$$

$$i=1\Rightarrow j=0$$

  当 $i=0$ 时 $j$ 有两种取值,否则就一种。我们不妨从枚举 $i$ 入手解决问题。从低位往高位枚举 $i$,因为 $i$ 不能有前导 $0$ 所以我们就处理最高位为 $1$ 的情况。注意到第二条条件,如果 $n$ 的所在位是 $0$,则 $i$ 必须是 $0$,但这样不符合 $i$ 最高位非 $0$ 的需求。所以我们只需在 $n$ 的二进制位为 $1$ 的时候进行相关统计。
  我们考虑统计 $i,j$ 的问题:假设我们确定好了 $i$ 的最高位,统计其低位情况。因为 $i$ 最高位为 $1$ 则 $j$ 的对应为肯定为 $0$,所以可以忽略第一条限制。考虑到第三条限制中 $i,j$ 的关系,我们设 $a,b$ 分别代表低位中 $0,1$ 的个数(当然是 $n$ 的)。由第二条限制得当 $n=0$ 时必定 $i=0$ ,从而 $j$ 有两种情况,这部分的分步贡献为 $2^a$ 。剩下的 $b$ 位 $i$ 可选 $0/1$ ,选 $0$ 则 $j=0/1$,否则 $j=0$。因而是个组合数求和。这部分的分步贡献是 $\sum\limits_{t=0}^{b}{C_{b}^{t}\times 2^t}$ 。
  这个式子看起来不舒服,考虑到二项式定理,上式可以化成 $(1+2)^b=3^b$。所以最后每一位的贡献就是 $2^a3^b$。
  最后考虑 $n$ 与 $i$ 的大小关系。$n$ 为 $0$ 的位置肯定 $i$ 为 $0$,而 $n=1$ 的时候 $i$ 为 $0/1$ ,满足小于关系。
  还有一个注意点:因为枚举的最高位锁定为 $1$ ,所以我们忽略了 $i=j=0$ 的时候。需要补上。复杂度 $O(T\times |S|)$。

代码:

cpp
1
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
#define il inline
const int maxn=100010;
const ll mod=1e9+7;
ll ans;
ll p2[maxn],p3[maxn];
int T,n;
char s[maxn];
int tot0,tot1;
int main(){
scanf("%d",&T);
p2[0]=p3[0]=1;
for (int i=1;i<=100000;++i){
p2[i]=(p2[i-1]*2)%mod;
p3[i]=(p3[i-1]*3)%mod;
}
while (T--){
scanf("%s",s+1); n=strlen(s+1);
ans=0; tot0=tot1=0;
for (int i=n;i>=1;--i){
if (s[i]=='1'){
ans=(ans+p2[tot0]*p3[tot1]%mod)%mod;
tot1++;
}else{
tot0++;
}
}
printf("%lld\n",(ans+1)%mod);
}
return 0;
}

D. Bitwise Tree

E. Bob’s Problem

题意:

  给定一个图,有带权值的白边黑边。白边的选择有数目限制,让你选择合适的边使得整个图联通且整体权值最大。

解析:

  对于黑边没有任何限制,既然权值非负则肯定将所有黑边连上是更优的。
  我们考虑白边:在保证联通的情况下要保证权值最大,同时有边数限制。由前两点可以想到最大生成树,因为黑边事先已经联通了一些点,可以考虑缩点。(当然,不用缩点处理也行。)
  我们对边进行排序后,首先照顾必须选取的边:即那些影响连通性的边。考虑完那些边后,如果有剩余我们再把剩下的那些边从大到小加入即可。

代码:

不知道为什么在计蒜客用C++11就CE了QAQ明明本地是好的C++14正常

cpp
1
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long
#define il inline
const int maxn=50010;
struct line{
int from,to,val;
bool operator < (const line &_a){
return val>_a.val;
}
};
vector<line> edge;
vector<int> rem;
ll ans;
int T;
int n,m,k;
int fa[maxn],tot;
int finda(int x){
return (x==fa[x])?x:fa[x]=finda(fa[x]);
}
bool cmp(int _a,int _b){
return _a>_b;
}
int ra,rb,rc,rd;
int main(){
scanf("%d",&T);
while (T--){
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;++i) fa[i]=i;
tot=0; ans=0; edge.clear(); rem.clear();
for (int i=1;i<=m;++i){
scanf("%d%d%d%d",&ra,&rb,&rc,&rd);
if (!rd){
int fx=finda(ra),fy=finda(rb);
if (fx!=fy){
++tot;
if (fx>fy) swap(fx,fy);
fa[fy]=fx;
}
ans+=rc;
}else{
edge.push_back((line){ra,rb,rc});
}
}
sort(edge.begin(),edge.end());
for (int i=0;i<edge.size();++i){
line e=edge[i];
int fx=finda(e.from),fy=finda(e.to);
if (fx==fy){
rem.push_back(e.val);
}else{
tot++; k--;
if (fx>fy) swap(fx,fy);
fa[fy]=fx; ans+=e.val;
}
if (k<=0) break;
}
if (tot<n-1){
printf("-1\n"); continue;
}
sort(rem.begin(),rem.end(),cmp);
for (int i=0;i<rem.size()&&k>=1;++i,--k){
ans+=rem[i];
}
printf("%lld\n",ans);
}
return 0;
}

F. Dynamic Suffix Array

G. Eating Plan

题意:

  给定一个 $n$ 的排列,每个位置的数的价值是它的阶乘 $mod\ 998857459$。$m$ 次询问连续区间和不少于询问值的最短区间长度。

解析:

  蒟蒻博主没看见排列卡了半天不会蒟蒻博主又把模数看成 998244353 然后卡了
  考虑到阶乘的因子非常多,便猜想当自身数很大时取余后为 $0$。我们打个表后发现 $2803$ 及其以后的阶乘 $mod\ 998857459$ 都为 $0$。
  因为是排列,所以所有 $n$ 个数中至多有 $2802$ 个数不为 $0$。我们考虑 $n^2$ 枚举左右端点得到值,更新对应答案。
  询问是离线的,我们可以按照值来排序。由于答案是单调的,我们可以二分答案处理,将每次得到的值赋给第一个不大于它的询问答案。防止有些询问没被扫到,最后从后往前更新一下答案即可。设筛选出的数有 $tot$ 个,复杂度 $O({tot}^2log\ m+mlog\ m)$。

代码:

cpp
1
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
#define il inline
const int maxn=100010;
const int jcmax=2803;
const ll mod=998857459;
ll jc[jcmax+10];
struct data{
ll val; int pos;
}a[jcmax+10]; int tot;
struct query{
ll val; int pos; int ans;
}q[maxn];
bool cmpv(const query &_a,const query &_b){
return (_a.val==_b.val)?_a.pos<_b.pos:_a.val<_b.val;
}
bool cmpp(const query &_a,const query &_b){
return _a.pos<_b.pos;
}
ll sum[jcmax+10];
int re;
int n,m;
int check(ll v){
int l=1,r=m,res=0;
while (l<=r){
int mid=(l+r)>>1;
if (q[mid].val<=v){
res=mid; l=mid+1;
}else{
r=mid-1;
}
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
jc[0]=1;
for (int i=1;i<=n&&i<jcmax;++i){
jc[i]=jc[i-1]*(ll)i%mod;
}
for (int i=1;i<=n;++i){
scanf("%d",&re);
if (re>=jcmax) continue;
a[++tot].val=jc[re]; a[tot].pos=i;
}
for (int i=1;i<=tot;++i){
sum[i]=(sum[i-1]+a[i].val)%mod;
}
for (int i=1;i<=m;++i){
scanf("%lld",&q[i].val);
q[i].pos=i; q[i].ans=2147483647;
}
sort(q+1,q+1+m,cmpv);
for (int i=1;i<=tot;++i){
for (int j=i;j<=tot;++j){
ll tmp=(sum[j]-sum[i-1]+mod)%mod;
int res=check(tmp);
q[res].ans=min(q[res].ans,a[j].pos-a[i].pos+1);
}
}
for (int i=m-1;i>=1;--i){
q[i].ans=min(q[i].ans,q[i+1].ans);
}
sort(q+1,q+1+m,cmpp);
for (int i=1;i<=m;++i){
if (q[i].ans==2147483647) printf("-1\n");
else printf("%d\n",q[i].ans);
}
return 0;
}

H. Powers of Two

  数太大了,咕咕咕。

I. Resistance

J. Summon

K. Tree

L. Who is the Champion

题意:

  给你一些队伍的互相比赛的情况。输出最高得分的人,如果最高得分相同则比较净进球数,否则输出平局。

解析:

  模拟题。按照条件统计后排序比较即可(或者不排序也行)。但要注意是净进球,即踢进的减去被进的。

代码:

cpp
1
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=110;
struct gp{
int sum,score,id;
}g[maxn];
int a[maxn][maxn];
int n,re;
bool operator < (const gp &_a,const gp &_b){
return (_a.score==_b.score)?_a.sum>_b.sum:_a.score>_b.score;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;++i) g[i].id=i;
for (int i=1;i<=n;++i){
for (int j=1;j<=n;++j){
scanf("%d",&a[i][j]);
g[i].sum+=a[i][j]; g[j].sum-=a[i][j];
}
}
for (int i=1;i<n;++i){
for (int j=i+1;j<=n;++j){
if (a[i][j]>a[j][i]){
g[i].score+=3;
}
if (a[i][j]==a[j][i]){
g[i].score++; g[j].score++;
}
if (a[i][j]<a[j][i]){
g[j].score+=3;
}
}
}
sort(g+1,g+1+n);
if (n!=1&&g[1].score==g[2].score&&g[1].sum==g[2].sum){
printf("play-offs");
}else{
printf("%d",g[1].id);
}
return 0;
}

M. XOR Sum

文章作者: lonlyn
文章链接: https://lonlyn.gitee.io/blog/2020/02/22/2019nanchang/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lonlyn's blog

评论