2020秦皇岛CCPC
我的情况
本人就读于一个不开设任何计算机课的专业（也就是和计算机一点关系都没有的专业）
凭借着摸鱼划水获得了学校一个参加这场比赛的资格
获得了之后继续摸鱼划水
也就是啥练习没做，裸奔上阵
但话说回来，你说我这跟计算机没啥关系的为啥要做题（雾
结果自然就是比赛的时候发现自己变得啥都不会，啥题都做不出来
凭借着队友的手速获得了Au
你说一个5h的比赛，我们怎么一个半小时就下班了？
为了提升一下以后还可能有的比赛的游戏体验，现在来补一下题
打算补的题
H. Holy Sequence
I. Interstellar Hunter
B. Bounding Wall
J. Jewel Splitting
I. Interstellar Hunter
就是问你在所拥有的向量中能否拼凑出某个向量
如果只有两个向量，显然可以随便搞出答案，大力讨论一下就可以了
那么有一个很常规的想法就是把若干个向量化为两个，考虑增量法
这里有一个误区是
a
,
b
a,b
a,b可以拼凑出
c
c
c，并不可以推出
a
,
c
a,c
a,c可以拼凑出
b
b
b，这也是本题难点之一
先说一个结论
(
x
1
,
y
1
)
(x_1,y_1)
(x1,y1)和
(
x
2
,
y
2
)
(x_2,y_2)
(x2,y2)必可以找到
(
x
3
,
y
3
)
(x_3,y_3)
(x3,y3),
(
0
,
d
)
(0,d)
(0,d)与之等价
辗转相除可轻易证明
(
x
1
,
y
1
)
(x_1,y_1)
(x1,y1)和
(
x
2
,
y
2
)
(x_2,y_2)
(x2,y2)必可以得到
(
x
1
%
x
2
,
y
′
)
(x_1\%x_2,y')
(x1%x2,y′),而
(
x
1
%
x
2
,
y
′
)
(x_1\%x_2,y')
(x1%x2,y′)和
(
x
2
,
y
2
)
(x_2,y_2)
(x2,y2)必可以得到
(
x
1
,
y
1
)
(x_1,y_1)
(x1,y1)，故得证
从证明我们也可以得到求出
(
x
3
,
y
3
)
(x_3,y_3)
(x3,y3)的方法
也就是在
e
x
g
c
d
exgcd
exgcd过程中的任意时刻的一组
(
x
1
,
y
1
)
(x_1,y_1)
(x1,y1)和
(
x
2
,
y
2
)
(x_2,y_2)
(x2,y2)都是和起点等价的
最后两组是
(
0
,
Y
1
)
(0,Y_1)
(0,Y1),
(
g
c
d
(
x
1
,
x
2
)
,
Y
2
)
(gcd(x_1,x_2),Y_2)
(gcd(x1,x2),Y2)
因此可以
x
3
=
g
c
d
(
x
1
,
x
2
)
x_3=gcd(x_1,x_2)
x3=gcd(x1,x2),用exgcd算出系数就可以得到
Y
2
Y_2
Y2了
至于
Y
1
Y_1
Y1，可以发现其实随便找一个凑得出来的就可以了
于是我们不妨假设当前的两个向量为
(
X
,
Y
)
(X,Y)
(X,Y),
(
0
,
d
)
(0,d)
(0,d)
假设现在又来了一个
(
a
,
b
)
(a,b)
(a,b)
显然找一组新的
(
x
3
,
y
3
)
(x_3,y_3)
(x3,y3),
(
0
,
d
′
)
(0,d')
(0,d′)和
(
X
,
Y
)
(X,Y)
(X,Y),
(
a
,
b
)
(a,b)
(a,b)等价，然后让(0,d’)和
(
0
,
d
)
(0,d)
(0,d)合并即可，显然就是
(
0
,
g
c
d
(
d
,
d
‘
)
)
(0,gcd(d,d‘))
(0,gcd(d,d‘))
于是我们就成功将三个向量合并成了两个，此题就做完了
H. Holy Sequence
首先，平方自然是要转化为数点对的
先说一个我在考场上的方法
首先暴力枚举
t
t
t
f
i
,
j
f_{i,j}
fi,j表示前
i
i
i个数最大为
j
j
j的方案数
g
i
,
j
g_{i,j}
gi,j表示前
i
i
i个数最大为
j
j
j的所有方案中
t
t
t出现的次数
h
i
,
j
h_{i,j}
hi,j表示前
i
i
i个数最大为
j
j
j的所有方案中
t
t
t出现的点对数
g
g
g可以由
f
f
f转移得到，
h
h
h可以由
g
g
g转移得到
此时是
O
(
n
3
)
O(n^3)
O(n3)，比赛的时候就僵在这里了
今天观察一下，如果把
t
t
t放入循环里面，对于同一个
j
j
j只会包含两种操作，前缀加或者单点修改
把
i
i
i滚掉，用线段树可以做到
O
(
n
2
l
o
g
n
)
O(n^2logn)
O(n2logn)的复杂度，但仍然过不去这个题
因为状态本来就是
O
(
n
3
)
O(n^3)
O(n3)的，因此暴力重构显然不现实，后面我就不会了
再说一个别的做法
可以发现，对于一个序列构造来说，每一个数，只有第一次出现是有用的
也就是判断一个序列合不合法，只需要判断每个数第一次的位置是否合法，剩下的删去队序列的合法性没有任何影响
因此，我们可以想到枚举每一个数第一次出现的位置
然后讨论点对的情况
显然只需要维护一个当前结尾同时也是最大的数时
i
i
i，往后填j
个
个
个数的方案
以及
f
i
,
j
f_{i,j}
fi,j表示前
i
i
i个数最大为
j
j
j的方案数
讨论合并一下就可以了
B. Bounding Wall
NMD，队友把题翻译成了Wall框住
(
x
,
y
)
(x,y)
(x,y)，而非包含，事后看了半天不知道别人在说什么浪费我时间
然后这题复杂度居然是
q
n
l
o
g
qnlog
qnlog的
居然还可以暴力枚举高度，看来我对ACM多组数据理解不深啊
综合以上两个条件，我比赛过程中怎么也不可能做出这个题
如果可以枚举的话计就很好做了
暴力讨论在哪一个边界
如果在下边界，暴力枚举上边界是哪一行i
那么问题就是找左右边界，先把上下边界可以走到的左右边界噶出来
每一个点维护一下向上走最多能走多远
在线段树上二分左端点，使得左端点可以一直扩展到
i
i
i就可以了
右端点同理
感觉是这几个里面最傻逼的题，虽然码量有点大
本文地址：https://blog.csdn.net/qq_36797743/article/details/109249587