CEOI 2019

发表于

链接

A B C D E F
$\color{red}{\texttt{-}}$ $\color{green}{\texttt{+}}$ $\color{green}{\texttt{+}}$ $\color{green}{\texttt{+}}$ $\color{green}{\texttt{+}}$ $\color{red}{\texttt{+6}}$

A. Building Skyscrapers

可以构造一个矩形变成一个等面积的正方形的方案，以此可以将任意两个等面积矩形互相转化。而一个三角形也可以变成一个等面积的矩形，所以可以将第一个多边形任意三角剖分，将得到的若干三角形拼成一个大正方形，然后再倒回去变成第二个多边形。

B. Dynamic Diameter

可以证明两个点集的直径对应端点一定在两个点集分别直径的端点中，所以可以合并两个点集。

考虑按 dfs 序建线段树，可以发现一次修改会影响一段区间 $[l,r]$ 的深度，会影响包含 $l$ 和 $r$ 的区间。区间个数为 $O(\log n)$，暴力更新这些区间即可。

复杂度 $O(n\log^2 n)$。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#define clz(x) (64-__builtin_clzll(x))
using namespace std;
typedef long long ll;
const int N=200010,M=60;
int ch[N*M*2][2],t[N*M*2],tt=1;
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        ll x,y;int v;scanf("%lld%lld%d",&x,&y,&v);
        int lx=clz(x),ly=clz(y),u=1;
        for(int i=0;i<lx-1;u=ch[u][x>>i&1],i++) if(!ch[u][x>>i&1]) ch[u][x>>i&1]=++tt;
        if(!t[u]) t[u]=++tt;u=t[u];
        for(int i=0;i<ly-1;u=ch[u][y>>i&1],i++) if(!ch[u][y>>i&1]) ch[u][y>>i&1]=++tt;
        t[u]+=v;
    }
    for(int i=1;i<=m;i++)
    {
        ll x,y;scanf("%lld%lld",&x,&y);
        int lx=clz(x),ly=clz(y),res=0;
        for(int j=0,u=1;u && j<lx;u=ch[u][x>>j&1],j++)
            for(int k=0,v=t[u];v && k<ly;v=ch[v][y>>k&1],k++) res+=t[v];
        printf("%d\n",res);
    }
    return 0;
}

C. Cubeword

考虑枚举立方体八个顶点中任意四个互不相邻的顶点，这样剩下的四个顶点也互不相邻。再预处理一端公共顶点，另一端分别为 $x,y,z$ 的立方体填词方案数，就可以 $O(1)$ 计算答案。

复杂度 $O(n\log n+|\sigma|^3)$。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 100010
#define mod 998244353
using namespace std;
vector<string>a[12];string str;
int id(char x){return x>='a'?x-'a':(x>='A'?x-'A'+26:x-'0'+52);}
string rev(string a){return string(a.rbegin(),a.rend());}
int mp[110][110],f[62][62][62];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>str,a[str.size()].push_back(str),a[str.size()].push_back(rev(str));
    int ans=0;
    for(int i=3;i<=10;i++) if(a[i].size())
    {
        memset(mp,0,sizeof(mp)),memset(f,0,sizeof(f));
        sort(a[i].begin(),a[i].end());
        a[i].erase(unique(a[i].begin(),a[i].end()),a[i].end());
        for(auto &str:a[i]) mp[id(str.front())][id(str.back())]++;
        for(int w=0;w<62;w++) for(int x=0;x<62;x++) if(mp[x][w])
        for(int y=0;y<62;y++) if(mp[y][w]) for(int z=0;z<62;z++) if(mp[z][w]) f[x][y][z]=(f[x][y][z]+1ll*mp[x][w]*mp[y][w]*mp[z][w])%mod;
        for(int x=0;x<62;x++) for(int y=0;y<62;y++)
        for(int z=0;z<62;z++) if(f[x][y][z]) for(int w=0;w<62;w++) ans=(ans+1ll*f[x][y][z]*f[x][y][w]%mod*f[x][z][w]%mod*f[y][z][w])%mod;
    }
    printf("%d\n",ans);
    return 0;
}

D. Amusement Park

显然一张合法的图的所有边反向之后也是合法的。所以答案等于将所有边定向后的合法方案数 $\times \frac m2$。

考虑 dp 分层图，每层图之间不能有边。当每层只有一个点时就是拓扑图，但是此时会计重，用子集容斥即可。

复杂度 $O(3^n)$。可以用子集 dp 做到 $O(n^22^n)$。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=18,mod=998244353,iv2=(mod+1)/2;
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int g[N],_2[1<<N],f[1<<N];bool hv[1<<N];
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=0;i<1<<n;i++) hv[i]=true;
    for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),--u,--v,hv[(1<<u)^(1<<v)]=false;
    for(int i=1;i<1<<n;i++) _2[i]=_2[i>>1]+(i&1);
    for(int i=0;i<n;i++) for(int s=0;s<1<<n;s++) if(!(s>>i&1)) hv[s^(1<<i)]&=hv[s];
    f[0]=1;
    for(int s=1;s<1<<n;s++)
        for(int t=s;t;t=(t-1)&s) if(hv[t])
            add(f[s],_2[t]&1?f[s^t]:mod-f[s^t]);
    printf("%lld\n",1ll*m*iv2%mod*f[(1<<n)-1]%mod);
    return 0;
}

E. Magic Tree

用 $f_{i,j}$ 表示 $i$ 子树中在 $j$ 时刻的最大果汁数。

显然可以线段树合并，用后缀 max，单点查的线段树维护。复杂度 $O(n\log n)$。

其实还可以用 map 启发式合并。考虑将答案数组差分，容易发现一次插入最多只会插入一个位置，合并的时候可以直接将差分数组合并，这样复杂度就是正确的。注意插入之后要把推平的位置删掉。复杂度 $O(n\log^2 n)$。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define N 100010
#define fi first
#define se second
#define ll long long
using namespace std;
int fa[N],n,m,k,val[N],ti[N];vector<int>g[N];
map<int,ll>f[N];
void merge(map<int,ll>&a,map<int,ll>&b)
{
    if(a.size()<b.size()) a.swap(b);
    for(auto p:b) a[p.fi]+=p.se;
}
void dfs(int u)
{
    for(int v:g[u]) dfs(v),merge(f[u],f[v]);
    if(!ti[u]) return;
    f[u][ti[u]]+=val[u];int v=val[u];
    for(auto t=f[u].upper_bound(ti[u]);t!=f[u].end();f[u].erase(t),t=f[u].upper_bound(ti[u]))
        if(t->se<=v) v-=t->se;
        else{t->se-=v;break;}
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=2;i<=n;i++) scanf("%d",&fa[i]),g[fa[i]].push_back(i);
    for(int i=1,u;i<=m;i++) scanf("%d",&u),scanf("%d%d",&ti[u],&val[u]);
    dfs(1);
    ll ans=0;for(auto p:f[1]) ans+=p.se;
    printf("%lld\n",ans);
    return 0;
}

F. Building Skyscrapers

不妨假设有大厦的地方是黑点，其余是白点。直接将所有读入点周围九宫格点拿出来，显然只有这些点会影响答案。

既然要求倒序字典序最大，不妨直接将序列倒过来操作，这样相当于每次拆一座大厦，即将一个黑点染成白点，要求每次操作后黑点是一个八连通块，且操作的黑点周围存在白点与无穷远处白点四连通。

后面的条件很好处理，重点在于前面的条件。考虑一个经典的结论，对于两个不交的平面图：

1
2
3
  1-----o
3-x-4   |
  2-----o

若 $1$ 和 $2$ 连通，$3$ 和 $4$ 通过 $\times$ 连通，那么将 $\times$ 删去后 $3$ 和 $4$ 一定不连通。

所以我们考虑根据与删除点 $x$ 周围白点的连通性来判断 $x$ 删去后是否会导致黑点不连通。手模一下可以发现只有两种情况：

1
2
3
4
5
6
7
8
9
AoB
oxB
BBB

或

AoB
AxB
AoB

当两个 $\circ$ 处为同一连通块白点，$A$ 和 $B$ 的位置上分别至少有一个黑点时，$\times$ 删去后会导致黑点不连通。

由于 $\times$ 删去的前提是与周围存在白点与无穷远处白点四连通，所以删去后 $\circ$ 一定与无穷远处白点连通。暴力将每个白点 check 周围九宫格的黑点即可。

复杂度 $O(n\log n)$。

代码 
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<cstring>
#include<vector>
#include<map>
#include<set>
#define N 2000010
#define fi first
#define se second
using namespace std;
struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
    bool operator <(const node a)const{return x==a.x?y<a.y:x<a.x;}
}p[N];
node operator +(const node &a,const node &b){return node(a.x+b.x,a.y+b.y);}
node P[]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int n,f[N],col[N],deg[N],tt,rt;
map<node,int>mp;
int id(const node &a){if(mp.count(a)) return mp[a];return 0;}
int find(int x){return x==f[x]?f[x]:(f[x]=find(f[x]));}
set<int>su;
bool check(int u)
{
    if(deg[u]<=1) return true;
    bool hv=false;
    for(int i=0;i<4;i++) if(find(id(p[u]+P[i]))==rt){hv=true;break;}
    if(!hv) return false;
    static int Id[3][3];
    int x=p[u].x,y=p[u].y;
    for(int i=0;i<=2;i++) for(int j=0;j<=2;j++) Id[i][j]=id({x+i-1,y+j-1});
    auto id=[&](int x0,int y0){return Id[x0-x+1][y0-y+1];};
    for(int i=-1;i<=1;i+=2)
        for(int j=-1;j<=1;j+=2) if(col[id(x+i,y+j)]==1)
        {
            int vx=id(x+i,y),vy=id(x,y+j);
            if(vx && vy && find(vx)==find(vy)) return false;
        }
    if(col[id(x+1,y)]==2 && col[id(x-1,y)]==2 && find(id(x+1,y))==find(id(x-1,y)))
    {
        int hv=0;
        for(int i=-1;i<=1;i++) if(col[id(x+i,y-1)]==1){hv++;break;}
        for(int i=-1;i<=1;i++) if(col[id(x+i,y+1)]==1){hv++;break;}
        if(hv==2) return false;
    }
    if(col[id(x,y+1)]==2 && col[id(x,y-1)]==2 && find(id(x,y+1))==find(id(x,y-1)))
    {
        int hv=0;
        for(int i=-1;i<=1;i++) if(col[id(x-1,y+i)]==1){hv++;break;}
        for(int i=-1;i<=1;i++) if(col[id(x+1,y+i)]==1){hv++;break;}
        if(hv==2) return false;
    }
    return true;
}
bool vis[N];
void dfs(int u)
{
    vis[u]=true;
    for(int j=0;j<4;j++)
    {
        int y=id(p[u]+P[j]);
        if(col[y]==1){if(check(y)) su.insert(y);else su.erase(y);}
        if(col[y]==2 && !vis[y]) dfs(y);
    }
}
void del(int u)
{
    col[u]=2,vis[u]=true;f[u]=rt;
    for(int i=0;i<8;i++)
    {
        int v=id(p[u]+P[i]);
        if(col[v]==1)
        {
            deg[v]--;
            if(check(v)) su.insert(v);
            else su.erase(v);
        }
    }
    for(int i=0;i<4;i++)
    {
        int x=id(p[u]+P[i]);if(col[x]!=2) continue;
        x=find(x);
        if(x!=rt) f[x]=rt,dfs(x);
    }
}
int ans[N],at;
int main()
{
    scanf("%d%*d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
    for(int i=1;i<=n;i++) mp[{p[i].x,p[i].y}]=++tt;
    for(int i=1;i<=n;i++)
        for(int j=0;j<8;j++) if(!mp.count(p[i]+P[j])) mp[p[i]+P[j]]=++tt,p[tt]=p[i]+P[j];
    for(int i=1;i<=tt;i++) col[i]=i<=n?1:2;
    for(int i=1;i<=tt;i++) f[i]=i;
    for(int i=1;i<=n;i++)
        for(int j=0;j<8;j++)
        {
            int u=id(p[i]+P[j]);
            if(col[u]==1) f[find(u)]=find(i);
        }
    for(int i=1;i<n;i++) if(find(i)!=find(i+1)){puts("NO");return 0;}
    for(int i=1;i<=tt;i++) f[i]=i;
    for(int i=n+1;i<=tt;i++)
        for(int j=0;j<4;j++)
        {
            int u=id(p[i]+P[j]);if(col[u]!=2) continue;
            f[find(i)]=find(u);
        }
    rt=find(mp.begin()->second);
    for(int i=1;i<=n;i++)
        for(int j=0;j<8;j++) if(col[id(p[i]+P[j])]==1) deg[i]++;
    for(int i=n+1;i<=tt;i++) if(find(i)==rt) vis[i]=true;
    for(int i=1;i<=n;i++)
        for(int j=0;j<4;j++)
        {
            int u=id(p[i]+P[j]);
            if(col[u]==2 && find(u)==rt && check(i)){su.insert(i);break;}
        }
    while(!su.empty()){int u=*su.rbegin();su.erase(u),ans[++at]=u,del(u);}
    puts("YES");
    for(int i=at;i;i--) printf("%d\n",ans[i]);
    return 0;
}