UOJ NOI Round #6 寄()

Au \(15\) 个,Ag \(35\) 个,Cu \(50\) 个。

想拿个 Ag。

Day 0

笔试,晚上 \(7\) 点,在吃饭,忘了。

离 Ag 线:-100。

Day 1

开场先看 T1,一看这不是 ** 题,相当于所有人到一个点,直接对 \(k\) 个点跑个最短路,然后对于每个点判一下就好了。

\(30\) 分钟写完了,一测样例寄了,发现可以在边上相遇。

然后就相当于对每条边做,有 \(k\) 条折线,求个单点最大值的最小值。

斜率都一样,乱维护一下就好了,直接交了。\(75\) 分钟。

看榜,发现人均得分 \(100+0+75\),所以去 T3。

T3 是个典,相当于选一些点标为 \(1\),然后就相当于前缀满足一个东西,这个 \(O(n^2q)\) 的 dp 比较显然。

想了一会儿反悔贪心,不大会,然后感觉是不是直接贪心就行,写了一些过了所有样例,想了一下,发现是对的,复杂度 \(O(qn\log n)\),直接交了,\(127\) 分钟。

然后发现一车人过了 T2 所以去冲,感觉去重不会。

开始摆烂,写了个 \(10\) 分暴力先交了。

感觉肯定是 dp,考虑那些状态可以达到,从前向后 dp,但是有重复,不会。

想了半天,突然震惊,贪心匹配,如果不够直接回退即可,然后开写。

写了一下,过了前面两个样例,第三个寄了。

开始对拍,随便拍几个没有问题,由于本地没有 IDE,扔给 psz 帮我拍,结果随便拍了个 \(n=10,m=5\) 的数据。

调半天不会,然后又让他拍,随便拍了个 \(n=6,m=3\) 的数据。

还是调不出来,结果拍出个 \(n=4,m=2\) 的数据。。。

调了一万年,发现回退不一定退一格。

改了一下,直接过了。\(243\) 分钟,然后摆烂了。

下午看评测,寄动人心。

结果测了近 \(3h\)。。。

没 fst,这是好的,\(100+100+40=240\),进 Ag 线了,踩了 Au 线。

最后 rk 31。

T1 \(\color{green}\bigstar\)

题比较长,自己看吧。

题比较长,自己看吧。

小清新签到题。

考虑依次面基这个东西,由于所有人运动速度都相等,所以显然面基后就把两个人合并,这样就与顺序无关,所以相当于所有人到一个点。

如果这个点在一个点上很简单,对于每个人跑一遍 dij 即可。

如果在边上,考虑一个点到这个边上的点的距离的函数。

显然这个函数是一段斜率为 \(1\) 以及一段斜率为 \(-1\) 的。

维护这个东西,如果一个函数的最高点比另一个函数低,那么显然没有贡献,否则取出来按最高点横坐标排序,然后算交点的高度即可。

复杂度 \(O(kn\log n+nk^2)\)

code

T2 \(\color{blue}\bigstar\)

有一个长为 \(n\) 的 串,你需要计算 \(t\) 次操作后能得到多少不同的 串。
一次操作的定义为:在串中选两个位置插入一对 使得 在 前。
\(n,t\le 300\)。

有一个长为 \(n\) 的 串,你需要计算 \(t\) 次操作后能得到多少不同的 串。

01
01

一次操作的定义为:在串中选两个位置插入一对 使得 在 前。

01
0
1

\(n,t\le 300\)。

直接统计比较困难,因为会有重复。

考虑哪些最终情况是合法的,从左往右放 \(0,1\)。

那么就相当于去掉一个子序列满足等于给出的原串后,剩下的是一个满足卡特兰数的序列。

因此设 dp 状态 \(f_{i,j,k}\) 表示放了 \(i\) 个,匹配了 \(j\) 个位置,去掉匹配位置后的序列前缀和为 \(k\) 的方案数。

但会有一个问题,如果让匹配位置尽量多,比如原串为 ,枚举的最终状态时 ,如果贪心匹配就会匹配前面两个,这样后面就寄了,但是匹配后面两个就合法了,但如果不匹配位置尽量多也会寄掉。

00
001100

考虑如果匹配尽量多时,如果不合法,那么我可以把一些匹配的位置弹掉变成不匹配。

也就是对于一个位置 \(j\),找到最小的后缀满足 \(0\) 的个数比 \(1\) 多,找这个后缀可以直接 \(O(n^2)\) 预处理一下,然后直接 dp 即可,复杂度 \(O((n+m)^2n)\)。

code

————————

Au \(15\) 个,Ag \(35\) 个,Cu \(50\) 个。

想拿个 Ag。

Day 0

笔试,晚上 \(7\) 点,在吃饭,忘了。

离 Ag 线:-100。

Day 1

开场先看 T1,一看这不是 ** 题,相当于所有人到一个点,直接对 \(k\) 个点跑个最短路,然后对于每个点判一下就好了。

\(30\) 分钟写完了,一测样例寄了,发现可以在边上相遇。

然后就相当于对每条边做,有 \(k\) 条折线,求个单点最大值的最小值。

斜率都一样,乱维护一下就好了,直接交了。\(75\) 分钟。

看榜,发现人均得分 \(100+0+75\),所以去 T3。

T3 是个典,相当于选一些点标为 \(1\),然后就相当于前缀满足一个东西,这个 \(O(n^2q)\) 的 dp 比较显然。

想了一会儿反悔贪心,不大会,然后感觉是不是直接贪心就行,写了一些过了所有样例,想了一下,发现是对的,复杂度 \(O(qn\log n)\),直接交了,\(127\) 分钟。

然后发现一车人过了 T2 所以去冲,感觉去重不会。

开始摆烂,写了个 \(10\) 分暴力先交了。

感觉肯定是 dp,考虑那些状态可以达到,从前向后 dp,但是有重复,不会。

想了半天,突然震惊,贪心匹配,如果不够直接回退即可,然后开写。

写了一下,过了前面两个样例,第三个寄了。

开始对拍,随便拍几个没有问题,由于本地没有 IDE,扔给 psz 帮我拍,结果随便拍了个 \(n=10,m=5\) 的数据。

调半天不会,然后又让他拍,随便拍了个 \(n=6,m=3\) 的数据。

还是调不出来,结果拍出个 \(n=4,m=2\) 的数据。。。

调了一万年,发现回退不一定退一格。

改了一下,直接过了。\(243\) 分钟,然后摆烂了。

下午看评测,寄动人心。

结果测了近 \(3h\)。。。

没 fst,这是好的,\(100+100+40=240\),进 Ag 线了,踩了 Au 线。

最后 rk 31。

T1 \(\color{green}\bigstar\)

题比较长,自己看吧。

题比较长,自己看吧。

小清新签到题。

考虑依次面基这个东西,由于所有人运动速度都相等,所以显然面基后就把两个人合并,这样就与顺序无关,所以相当于所有人到一个点。

如果这个点在一个点上很简单,对于每个人跑一遍 dij 即可。

如果在边上,考虑一个点到这个边上的点的距离的函数。

显然这个函数是一段斜率为 \(1\) 以及一段斜率为 \(-1\) 的。

维护这个东西,如果一个函数的最高点比另一个函数低,那么显然没有贡献,否则取出来按最高点横坐标排序,然后算交点的高度即可。

复杂度 \(O(kn\log n+nk^2)\)

code

T2 \(\color{blue}\bigstar\)

有一个长为 \(n\) 的 串,你需要计算 \(t\) 次操作后能得到多少不同的 串。
一次操作的定义为:在串中选两个位置插入一对 使得 在 前。
\(n,t\le 300\)。

有一个长为 \(n\) 的 串,你需要计算 \(t\) 次操作后能得到多少不同的 串。

01
01

一次操作的定义为:在串中选两个位置插入一对 使得 在 前。

01
0
1

\(n,t\le 300\)。

直接统计比较困难,因为会有重复。

考虑哪些最终情况是合法的,从左往右放 \(0,1\)。

那么就相当于去掉一个子序列满足等于给出的原串后,剩下的是一个满足卡特兰数的序列。

因此设 dp 状态 \(f_{i,j,k}\) 表示放了 \(i\) 个,匹配了 \(j\) 个位置,去掉匹配位置后的序列前缀和为 \(k\) 的方案数。

但会有一个问题,如果让匹配位置尽量多,比如原串为 ,枚举的最终状态时 ,如果贪心匹配就会匹配前面两个,这样后面就寄了,但是匹配后面两个就合法了,但如果不匹配位置尽量多也会寄掉。

00
001100

考虑如果匹配尽量多时,如果不合法,那么我可以把一些匹配的位置弹掉变成不匹配。

也就是对于一个位置 \(j\),找到最小的后缀满足 \(0\) 的个数比 \(1\) 多,找这个后缀可以直接 \(O(n^2)\) 预处理一下,然后直接 dp 即可,复杂度 \(O((n+m)^2n)\)。

code