CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====比赛情况====

总题数:13 场上过题:7 至今过题:7

A:solved by wzy

大模拟，画氨基酸。

B:


C:


D:solved by qshr&wzy

题意：给定k，构造一个长度n的序列($n \leq 365,k \leq 1e8$)，这个序列恰好有k种方式分成一个不增序列和一个不降序列(不改变元素的相对顺序)

题解：考虑 $ \overbrace{1\ldots 1 }^{x1个1} \overbrace{2\ldots 2 }^{x2个2} \overbrace{3\ldots 3 }^{x3个3}\cdots $
有$(2^{x1}-1)+(2^{x2}-1)+(2^{x3}-1)+\cdots +1$种方案，那么把k二进制拆分一下并手玩出k是0，1的情况即可

E:solved by wyl

题意：给定一个长度和字符集大小均不超过2e5的字符串，有q组询问，每组询问为求出删掉包含[l,r]的连续串会得到多少种不同的字符串。

题解：删除一段数之后构成的区间，只有长度相等才可能一样，去除一定要删的那部分，你会发现等价于前边一段等于后边一段，这样的话前面和后面每有一对相等的数，就刚好会对应一对相等的区间，然后就需要求去掉这段数，前面的1的个数成后面1的个数，前面的2的个数成后面2的个数等等，离线下来莫队可做。

F:solved by qshr

题意：给一颗树，每个点有一个权值，求平均权值最大的路径（至少包含2个点）

题解：赛场上使用的是二分+树上dp。其实只需要考虑长度2和3的路径即可。

G:solved by wyl

题意：有n个球，每次有$P_i$的几率操作第i个球，将其放到第一个，代价为它前面有几个球，求操作无穷次后再操作一次的代价的期望

题解：算贡献，最终如果i在j前，那么如果选中j，i会对j造成1的贡献，那就只需要算出任意i，j  i在j前的概率就好了，就是pi/(pi+pj)再乘上选中j的概率pj 然后求个和就行了

H:



I:



J:



K:solved by wyl

题意：两个人打游戏，第一个人如果当前胜率小于等于a/b下一局就会赢，否则会输。求n局之后赢了几局

题解：答案一定是[n*a/b]或者[n/a*b]+1，如果上一局时答案是前者，那么这局会赢，否则会输。所以不管怎样，答案都是[(n-1)*a/b]+1

L:solved by qhsr

题意：平面上n盏相同的灯，每个灯向k个方向区间照明（$k\leq 10$，每盏灯方向相同），求每盏灯能被多少盏其它灯照亮

题解：每个方向区间独立，分别考虑，若i能照亮j，则i照亮区间与x轴交一定包含j的，求每个在x轴交的l,r,按l排序，加r,每次查询大于等于当前r的即为答案，浮点处理有些小细节。

M:

====比赛过程====

又是前期爆炸的一把

开场wyl说了B的想法，感觉很对，上去写，WA了。然后qshr说了F的想法，感觉很对，上去写，WA了。然后wzy说了D的想法，感觉很对，上去写，WA了。

一小时过去了。。这时候K过了很多人，wyl想了想，很快写出来AC了(87min) F又交了几次还是WA

wzy发现A是大模拟，就直接去写A，没过多久wyl会了G，直接开写，过了(115min)

qshr发现了D的bug，改了改，过了(129min)(花了好久构造1的情况，其实在样例里。。。)

wzy继续写A，过了一会qshr又发现F可能是精度问题，二分了一波eps，过了(147min)

wzy继续写A，写完了，交上去WA了，这时wyl想出了E题，直接冲，AC(192min)

qshr开写L，wyl和wzy一起调A和B，wyl突然发现wzy把A题意理解错了，改完后过了(217min)

qshr的L写完也过了(239min),三人一边debug B题，一边算c的积分，直到比赛结束。。

upd：B离散化寄了


dirt: A(-3) D(-4) F(-7)

====总结====

wyl带飞了。但没搞出B，C确实可惜，最后一小时一直在蹬WA了的B和想C的积分，我应该直接上去重构B的,且C完全可以离散解决。————quanshr

也许没状态/没思路就去写大模拟是个正确的选择。。。————wzy
CVBB ACM Team

用户工具

站点工具

页面工具
