10.12
NOIp 2011 初赛, 84; 注意读题, 思维盲点;
10.13
NOIp 2012 初赛, 71.5.
(T_T 2.5分到哪里去了...)
10.19
「Clover IX」杯HE两校联赛(Day1)
只写了1.5h, 看了题就果断敲暴力了, 自己没出数据, 没对拍, 没手感......
40 + 10 + 0...明晚回来看题解, 果然NOIp裸考挂定了...
P1[简单数学]
注意到序列里的U和D只要合法就可以移动, 所以对字符串st计算高度的变化dH, 分类讨论:
1) |h[0]+dH-h[N]| < N-len, 奇偶性相同则有解, 反之无解
2) |h[0]+dH-h[N]| = N-len, 有解, 且需满足h[0]+dH >= 0 || h[N]-dH >= 0
3) |h[0]+dH-h[N]| > N-len, 无解
*要用草稿纸!!!注意考虑各种情况!!!
P2[字符串]
<暴力做法1>
用数组记录每个beautiful words的长度和起止字母, 然后用O(N^4*M)来暴力枚举.
<暴力做法2>
对于每个beautiful words, 从头扫一遍记录前缀长度, 从后面扫一遍记录前缀长度, 然后记录长度大于该beautiful words的字符串数量, 累加即可. 复杂度O(N^2*M).
<AC做法>
同暴力做法而, 不同的是由于使用了KMP所以复杂度变成O(NM)
P3[_____]
根据样例, 如果一对元素A_i, A_j需要操作的话, 必然满足A_i ^ A_j > max{A_i, A_j}. 于是当任何一对A_i, A_j都不能被操作时, \sum_{A_i}最大,
然后由于还有15min了, 我就果断敲回溯暴力了...
AC做法是高斯消元然后乱搞...看不懂
10.20
鉴于是恢复状态的训练, 而且AC做法全都没学过, 出于给生活以情趣的目的......看了题解就算了......
10.21
P1, Preda's queue, 模拟
注意到最多有N次弹出操作, 所以保留N个元素就好了, 然后模拟即可.
*居然爆零了...这不科学
P2, signal, 位运算+DP统计
[O(N^3)做法] 直接O(N^2)得到所有区间
[O(N^2)做法] 可以利用heap/线段树在O(NlogN)的时间里得到所有区间的操作结果, O(N^2)枚举. 特别地, xor满足区间减法, 可以直接O(N^2).
[O(NlogN)做法 by Juda]
(1) and
对于元素A_i, f[i][j]表示A_1...A_i的第j个二进制位中连续为1的个数, 累加即得.
(2) or
对于元素A_i, g[i][j]表示A_1...A_i的第j个二进制位中1第一次出现的位置, 累加即得.
*上述做法可以统一描述为, 自右向左扫描, and/or需要记录第i个元素前的元素中第j位第一次为0/1的位置, 2^j * (i - f[i][j] + 1)即为所求
(3) xor
[xor运算性质] 对于A_1 xor A_2 xor ... xor A_n, 考虑第j位, 若有奇数个1则为0, 反之亦然.
对于元素A_i, f[i][j]表示A_1...A_i, A_2...A_i, .. , A_i的中有奇数个1的序列个个数, g[i][j]表示序列中有偶数个1的序列个数, 不断交换, \sum 2^j * f[i][j]即为所求.
*还是爆零了不科学...
P3, catclimb, DFS-ID
一开始读题以为是DP, 条件反射想到training里的rocker和GDKOI 2012 Day1P1. 被P2虐了一通之后, 发现其实是搜索, 智商这个拙计啊....
标程给的做法是DFS-ID. 直接\sum{A_i}\N上取整可以得到理论下界, 然后qsort一下{A_i}先取大的再取小的填一下可以得到上界, 直接O(N!)暴力枚举. 如果达到下界或超过上界马上剪枝.
*只过了一个点...这不科学!!!!!!!!
P4, communicate, LCA
只会SPFA...但是这个范围!!!一看就不是NOIp题(
*明天晚上抽2h调一下吧...还要写PS...