比赛名称¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 49/? | 9 | 9 | 13 |
A¶
solved by YZW
题意¶
题解¶
B¶
**upsolved by **
题意¶
题解¶
C¶
solved by JLK
题意¶
签到，略
题解¶
D¶
solved by JLK
题意¶
\(n\)个单词，长度为\(f_i\)，屏幕的宽度为\(w\)。
要分成若干列显示，按顺序一列一列排下来，并且中间没有空位。每一列的宽度为单词长度max。
问每列的长度\(l\)最少是多少，使得宽度不会超过\(w\)。
题解¶
枚举\(l\)即可。预处理一下ST表，每次就是看\([1,l],[l+1,2l],\dots\)的最小值，暴力扫是\(O(n\log n)\)的。
E¶
solved by JLK
题意¶
\(n\)个数的排列，开始固定一些数，要满足每两个相邻数的差的绝对值大于等于两个数的min。求合法方案数。
\(1 \le n \le 27,n=2k+1\)
题解¶
有一些性质：
1、把大于等于\(\lceil \frac n2 \rceil\)的数看做大数，其他看做小数。则合法排列一定是大小交替，并且首尾都是大。
2、两个大数\(x，y\)中间的小数小于等于\(\lfloor \frac{\min\{x,y\}}2 \rfloor\)
考虑状压，从大到小确定大数。先假设没有固定的数。
状压已经放了数的位置，计算方案，每次枚举一个位置把现在要放的大数放进去。
每两个大数\(a+1,a\)放完之后必须在已经放了大数的某两个位置中间确定一个小数\(\lfloor \frac a2 \rfloor\)的位置。否则按照性质2，之后不可能再放这个数了。
这样全部放完之后，还有一些小数没有确定，这些数直接在剩下的空位全排即可。
现在考虑有固定的数的情况，那么就相当于枚举到对应的数的时候，位置只有1种或者0种可能，分类讨论一下即可。
\(O(2^{\frac n2}n^2)\)
F¶
solved by YZW
题意¶
题解¶
G¶
**upsolved by **
题意¶
题解¶
H¶
solved by JLK
题意¶
模拟，略
题解¶
I¶
solved by YZW
题意¶
题解¶
J¶
solved by TYB
题意¶
给出两个序列\(\{a_n\}\)和\(\{b_n\}\)和\(p,q\)，判断是否满足：
\(\bullet\) \(\forall S\subseteq\{1,2,\dots,n\},(\sum_{i\in S}a_i\ge p)\Leftrightarrow(\sum_{i\in S}b_i\ge q)\)
若不满足，给出一组反例。
\(n\le100, p,q\le10^6\)
题解¶
做两次背包：第一次以\(p-1\)作为背包容量，\(a_i\)作为物品体积，\(b_i\)为物体价值；第二次类似。
K¶
**upsolved by **
题意¶
题解¶
L¶
solved by YZW
题意¶
题解¶
M¶
**upsolved by **
题意¶
题解¶
记录¶
JLK过C(0:09)。
YZW写A，遇到了一点问题。
换JLK写D，WA3次后AC(0:34)。
YZW过L(0:39)，然后过A(1:02)。
JLK写H，WA了一次，换TYB写J(2:03)。
JLK改对了H(2:10)。
YZW I写了个暴力，发现是一个环，然后开始写正解。TLE两次后AC(3:09)。
期间一起看了一会F，没什么想法。
JLK写E，WA一次后开始对拍。此时YZW会F，开始写。
E拍出来了，然后改对了(4:02)。
YZW写F，WA一次后AC(4:13)。
最后JLK感觉M可做，又讨论了一会，没时间了。
总结¶
JLK：感觉中期卡在F上了，应该先看看M的。
Dirt¶
D(-3)
E(-1)
F(-1)
H(-1)
I(-2)