10.1
tyvj迎国庆新赛制模拟赛, 140min, 预计260
excel[模拟], 50min, 预计AC
直接模拟, 需要用康托展开. 可以打表判断位数(利用等比数列求和).
*注意考虑R C的顺序
stock[判断有向图连通性], 30min, 预计60/100, O(N^2*T)
给出N个点, T条边, 判断至多添加多少条边图仍是DAG.
对于每条边(u,v), 利用DFS染色+邻接表判断(v,u)是否可达.
maze1[双进程DP+输出方案], 60min, 预计AC, O(N^3)
[状态] f[x1][y1][x2][y2]表示从(1,1)两人走到(x1,y2)和(x2,y2)可以得到的最多的面包圈.
t[x1][y1][x2][y2]表示从(1,1)走到(x1, y1)某人可以得到的最多的面包圈(题目要求最小字典序)
G[x_][y_]表示(x_,y_)是否有面包圈
*注意到(x1,y1)和(x2,y2)地位平等, 故只考虑其中一个即可.
f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2], f[x1-1][y2][x2][y2-1], f[x1][y1-1][x2-1][y2], f[x1][y1-1][x2][y2-1]} + G[x1][y1] + G[x2][y2]
t[x1][y1][x2][y2] = max{t[x1-1][y1][x2-1][y2], t[x1-1][y2][x2][y2-1], t[x1][y1-1][x2-1][y2], t[x1][y1-1][x2][y2-1]} + G[x1][y1]
NOIp09 Hankson的趣味题[数论], 1.5h, O(50000N), AC
注意到最大公约数最小公倍数的性质就是
a = p1^a1*p2^a2…pn^an
a = p1^b1*p2^b2…pn^bn
gcd(a,b) = p1^min(a1,b1)*p2^min(a2,b2)…pn^min(an,bn)
lcm(a,b) = p1^max(a1,b1)*p2^max(a2,b2)…pn^max(an,bn)
这里去年就想到了, 然后去年实现无能. 下面对每个因子p进行讨论
(1)对于min{p_x, p_a0} = p_a1
i)若p_a0 = p_a1, 那么p_x ∈ [p_a1, ∞)
ii)若p_a0 > p_a1, 那么p_x = p_a1
(2)对于max{p_x, p_b0} = p_b1
i)若p_b0 = p_b1, 那么p_x ∈ [0, p_b1]
ii)若p_b0 < p_b1, 那么p_x = p_b1
利用筛法构造小于√(2e9)的素数表, 对a0, a1, b0, b1分解质因数, 然后分别讨论四种情况即可(乘法原理).
*需要注意存在大于√(2e9)的素因子的情况, 利用b0[0]和b1[0]记录即可, 需要注意b1|b0, ans*=2
*利用factor函数分解质因数时, 传递数组指针, 此时不能在函数内对数组赋初值, 原因不知.
-> size (int *) = 4, 即一个内存地址的大小, sizeof(char*) = 4. 因而只能利用循环赋值. by gXX
[另解]把b1分解质因数, 然后用质因数枚举b1的所有约数, 然后挨个求与a0的最大公约数和与b0的最小公倍数.
10.2
tyvj迎国庆新赛制模拟赛, 160min, 预计150 -> 60/110
60min时读题结束(大概开场25min才开始看题)
ship[杂题], 84min, 预计?
[题意]给定一个正n边形, 在每个顶点上放高度不同的柱子, 使得高度最高的柱子构成的多边形的重心落在多边形内.
1. 所有柱子同高显然符合条件
2. 高度最高的柱子构成正多边形同样符合条件, 即重心和正n边形重合
3. 重心不和正n边形重合且不在边界上, 判断无能
*需要注意的是2和3, 在看了coderspace的答疑之后才想到.
game[模拟_60/], 160min, 预计?
"他就要从自己从左边记下的数字和从右边记下的数字中分别选取一个数, 将大的减去小的并大声喊出来."
->O(N^2), 60
对于每个小朋友, 向左向右记录符合条件的最值. 如果两边同时记录了最值, 那么输出max{MaxL-MinR, MaxR-MinL}. 否则输出-1.
*这题读错很多次, 一开始的想法并不正确, 之后有认为是最长不下降子序列, 并复习了O(NlogN)做法. 但事实上符合条件的序列不是单调的. 需要在纸上抽象出条件.
maze2[二分+floodfill/], 120min, 预计AC
[题意]从(1,1)到(n,m)存在一条路, 使得途中的曼哈顿距离k最大.
对于每个k, 第一次floodfill表示c个面包圈附近所有曼哈顿距离d<=k的点. 然后从(1,1)进行第二次floodfill, 已标记的点不能通过, 若可以到的(m,n)则满足题意.
*需要注意可以从上下左右任意方向走, 只通过右下方向会忽略很多情况.(by coderspace)
*这题是gXX出的, gXX表示标准做法不是二分
tyvj迎国庆新赛制模拟赛[170/600] -> 各种问题亟待解决
10.17
[BYVoid Stage1] 3h + 2.5h, 位置值25%
写了2h, 前两题预计AC, 第三题满分算法需要递推式, 70%算法看不出来; 第四题类似OPEN11的第一题, 各种心理阴影. 第二题花了20min练习对拍.
[summary], 130 = 10 + 100 + 10 + 10;
P1: BFS染色看成DFS染色, 需要注意更新条件(G[kx][ky] > G[x][y]+1), 否则会超时 -> 涉及最短路径的问题显然是BFS, DFS会造成各种奇葩的问题
*事实上还是脑抽了, 标准做法O(MN), 将所有传染源加入队列, 直接BFS即可.
P2: 分组背包问题, 差点看成泛化物品. 数据很弱, 用来对拍的暴搜同样AC.
*O(ABN), 和标准做法一样, 而且利用了0/1背包的性质直接降维, 减少内存使用.
P3: 看了题解, 收获很多.
(1)从数学角度考虑, 70
不妨考虑题目的退化情况, 即不存在栈元素数量p的限制. 注意到1号元素比较特殊, 初始时1号元素必须先行进入b栈, 然后进入c栈. 故而可以划分为两个过程, 过程I在a元素进入c栈之前, 过程II在a元素进入c栈之后. 利用乘法原理f[n] = Σf[k]*f[n-k-1](0<=k<i). 当然这东西其实就是Catalan数.
*白书上给出了另一种推导方式, 利用凸多边形上的分割. 固定一三角形V1VkVn, 讨论其两侧的多边形的情况, 故而f[n] = Σf[k][n-k+1](k>=2), f[2]=f[3]=1. 也可以通过固定对角线的方式讨论, 注意到每条对角线被重复计算了2n-6次(凸n边形仅有n-3条对角线), f[n] = Σf[k]*f[n-k+2]*n/(2n-6). 与上式联立可知, f[n+1] = f[n]*(4n-6)/n.
*这里的推导方法和第二类stirling数的推导方式类似, 考虑一个特殊元素的动作, 然后划分问题(利用乘法原理).
加上栈元素数量的限制, f(i,j)表示i个元素在栈元素限制为j时的方法数, 可得f[n][p] = Σf[k][p-1]*f[n-k-1][p](0<=k<n), f[i][0] = 0(0<i<=n), f[0][j] = 1(0<=j<=n)
(2)从动态规划角度考虑, AC
考虑到题目中存在三个栈a\b\c, 设置状态为f(i,j,k)表示a栈中有i个元素, b栈中有j个元素, c栈中有k个元素的方法数, 注意到i+j+k=n, 故只用f(i,j)即可.
若a栈中有i个元素, b栈中有j个元素, 可能是a栈中的1个元素到b栈中, 亦可能是b栈中一个元素到c栈中, 故而方程为f[i][j] = f[i+1][j-1] + f[i][j+1], f[n][0] = 1, f(0,0)为所求. 这个方程应该同样适用于无栈元素限制的情况(即没有特别的限制).
*数学上的递推式的思考方式, 往往是固定或者讨论1个元素, 进而划分问题或者类似情况. 而DP的思考方式, 建立在状态的基础上, 注重状态间的转移, 进而找到方程.
*一个小技巧, a mod 2^p = a & (2^p-1); 直观上其实很容易理解, 转化为2进制看待, 取模即得到a二进制下得后p位, 和位运算与的目的是一样的.
P4: 需要抽象出最短路模型, SPFA即可.(注意此时的点数不超过p*p, 而不是p)
注意到题目中同种能量结界可以无损耗传送, 不妨将每个能量结界缩为一点, 于是可以得到一个新的图. 为了简化计算, 在第一行前增加起点, 在最后一行后增加终点. 求出从起点到终点的最小点权覆盖即为答案. 然后题解中给出了一种很神奇的构造, 将起点和终点外的点形成的边拆成两个边, 边权为边终点的点权, 起点和终点仅考虑单向. 利用邻接表实现, 可以利用一个bool型数组判重. 之后利用SPFA求最短路, h-d[p+1]即为答案, 小于0输出NO.
*关键在于1) 以能量结界为点抽象出图, 转化为最小点权覆盖.
2) 拆边赋权, 转化为最短路模型.
10.18
USACO Contest OPEN11 cornmaze(BFS), 2h
略复杂的BFS, 写了约30min, 调了1.5h. 主要卡在两个错误和STL的语法上.
按照题意, 从起点开始, 如果遇到装置直接跳, 遇到草地继续走, 遇到玉米就终止, 直接BFS即可. 注意到题目中的装置成对出现, 而且遇到装置必须走, 这和昨天的第四题不同. 可以利用map数组记录装置的对应关系.
*对于一对装置, 从A到B, 只需标记A已读, 无需标记B已读, 可能出现跳过来又跳回去更短的情况. 但是要使B入队, 并且更新B的距离, 而不是更新A的距离.
*利用x*n+y对坐标编码的时候, 充要条件是n>=m, 否则解码会出现错误. 因而可以利用x*(n*m)+y进行编码, 在不溢出int的情况下. 当时在白书上见到这种写法, n=m, 并且坐标从0开始.
10.19
Tyvj新赛制模拟赛 stock, unAC.
10.20
stock[传递闭包]
题意就是确保每条需要添加的边(x,y), (y,x)不连通, 且x!=y(即点上没有自环).
和wx神牛给出的做法一样, 维护一个N*N的矩阵表示连通性, 若加入边(x,y), 则更新x的前驱和与y的后继的集合(x,y分别在集合中)的边为连通.
*复习了对拍的写法, 昨天查错查了1h, 写了O(N^2*T)的写法:
(1)更改了已连通点的情况
(2)没有考虑x的前驱和y的后继直接连通的情况
(3)没有考虑点的自环(make中人为避免了这种情况, 审题不清.)
*参照题解写O(NT), 更新连通情况时G[A[i]][B[j]]打成G[A[i]][B[i]], 对拍后发现.
*当时的DFS写法的问题, 修正后50:
(1)没有考虑重边的情况, 因而对于每一条边都要重新加入, 数组必然会爆. 可以利用矩阵维护已添边, 这样的话复杂度应该为O(N^2*P).
(2)next[]数组范围开小
[BYVoid Stage2] 1.5h, 完全不会. -> 眼高手低
以下是对于题意的简单判断, 看起来和去年差不多, 眼高手低:
P1: 模拟, 但是概率无能
P2: DP, 没想出方程
P3: DP + 多重背包?
P4: 极大强连通分量, Tarjan忘了, 裸的做法不会(注意到范围很小)
-> 题解显示方向判断基本正确, 基本思路都正确, 但是实现都卡在某些地方
P1:分为两个部分, 求概率和期望, 有1个trick.
对于概率可以分四个部分讨论:
(1) 无事故 -> 按照题意, 乘以无事故概率分别计算即可
(2) 同时事故 -> 平局, 把四个独立事件(故障)乘起来
(3) 侏儒事故 -> 地精胜利, 地精无事故*侏儒事故概率 ->需要注意这里不需要考虑无事故获胜概率, 仔细读题
(4) 地精事故 -> 侏儒胜利, 类似上文
*需要注意利用pow(sum,1/n)开n次方的时候, 必须边读入边计算, N = 1e6. 可以利用e^((1/n)*ln(a)) = a^(1/n)来计算.
*没有在分类基础上结合题意继续讨论, 导致理解偏差, 于是没想出来.
P2:我想的方程的状态是f(i,j)表示疲劳度为i, 行走距离为j, f(i,j)表示所需最小时间.
所以方程 f(i,j) = min{f(i-1, j+1), f(i+2, j+5), f(i+5, j+10)} + 1 (i ≠ p)
f(p-10, j+10) + 10 (i = p)
以距离为阶段, 没有后效性, 看起来如果记忆化, f(0,0)是答案. 但min给初始化造成了一定的麻烦; 更重要的是, 这样的方程使用滚动数组较为麻烦, 会爆内存.
*事实上i == p的情况不会得到最优结果, 即干扰条件. 要避免疲劳度达到上限.
改进做法是这样, f(i,j)表示行走最大距离, i表示花费时间, j表示疲劳度, 可以得到方程:
f(i, j) = max{f(i-1, j+1)+1, f(i-1, j-2)+5, f(i-1, j-5)+10}
需要利用滚动数组降维, 即for(i = 1, k = 1; i <= S; i++, k = !k)
*需要指出方程不太严谨, 考虑S=1, P=1, 条件1的1+1>P, 所以需要特殊处理.
*太久没写DP了, 所以方程细节问题很多.
10.22
东方幻想乡Stage1, 2.5h, 215 -> 310, 位置值65%
*发现solution一个很好的用途, 比较命题人给出的题意, 锻炼从题目中抽取信息的能力.
P1: 模拟+分析, 20min, AC
(1) 计算整个序列的位移向量a
(2) T/len * a, T%len模拟
*个人觉得亦可正交分解, 统计不同方向向量个数(N S对称, W E对称), 做法同上.
P2: 二分高精除法, 1h, TLE原因不知
*[没有注意到范围] O(LlogANS), 题目中给的ANS<=2*1e9, 而我算的ANS是1e20000. 本来是20000*9, 范围错误后, 20000*20000, 显然TLE.
*按位除效率高于二分高精除 by qz神牛
*其实直接写单精度乘法即可
*题解中二分条件, left+1<right;left = mid;right = mid;
*INT_MAX的另一种写法, ~0U>>1, U表示无符号整数 by WJMZBMR
P3: DP+优化(单调队列\优先队列), 60
f[i]表示在i取得的最大冰冻指数值
f[i] = max{f[i-j] + A[i]}(L<=j<=R, 0<=i<=n+R)
利用prev[i]记录f[i]由f[i-j]推得, 递归即可记录方案.
*2个trick, 存在负数(初始化-INF), 可以越过终点(前驱必须在终点前) -> 注意数组大小为f[N+R], 否则溢出
P4: 强连通分量(Floyd传递闭包+并查集), 50
利用Floyd传递闭包, 对于每一点对(u,v), 若是双向连通则使用并查集合并集合{u},{v}. 统计元素数最多Max的集合, 从头开始扫面每个节点所属集合, 遇到所属集合元素数量为Max的点直接跳出. 扫描该集合即可输出方案.
10.23
toj 1169 广告印刷[单调队列]
NOI导刊(11.5)例题, 使得队列中元素大小和下标同时单调. TLE, 原因未知.
[东方幻想乡S1P2]iceroad, DP+单调队列, AC
维护区间[i-R, i-L]的最大值, 先检查队列中元素下标的合法性(即满足q[head]>=i-R), 然后插入元素f[i-L].
*越过终点的情况必须初始化A[], 否则会造成答案错误.
*按照std, 必须初始化为0, 否则最后两个点WA. -> 数组溢出, 必须初始化为-INF, 数据弱, wagner的std会挂
*对于大数据挂掉的情况, 很可能是由于数组溢出
[东方幻想乡S1P3]classroom, Floyd+并查集, 60
(1) 一个错误,如果存在边(v,u)会被删除.
G[v][u] = (type == 2) ? 1 : 0; -> 考虑之前存在边(u, v)
*缩略形式很可能是不等价的, 要考虑全面
(2) 记录集合元素个数的写法
path[y] = path[x];
tot[x] += tot[y];
可以这么解释, find(y)会指向x, 于是更新x的元素个数.
*想起了Tyvj9月月赛第二题
10.24
东方幻想乡Stage2, 2.5h, 200, 位置值82%
P1: 简化版最大子矩阵, AC.
给出了矩阵大小(R,C), 令s[i][j]表示Σs[1..i][1..j], 只需枚举[R,N, C,M]作为矩阵顶点计算大小即可.
s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + A[i][j]
矩阵大小S = s[i][j] - s[i][j-C] - s[i-R][j] + s[i-R][j-C]
P2: 进制转换+同余, AC.
(1) 得到1..L位分别对于M取余的余数pow[i]
(2) O(L), 判断当前数是否整除
余数rem = Σs[L-i-1]*(A[i]-'A'), 利用传递性取余.
(3) O(L^2), 枚举任意两个数对(i,j), 交换后计算余数, 若整除直接输出结果
题目要求字典序最小, 指字符串[1..L], 需要注意下标 -> 这里浪费了20min, 多次手工模拟错误
交换的写法:
rem += M - ((s[i]-'A') * pow[L-i-1]) % M;//利用补数, 分别减去i,j原来的位值
rem += ((s[j]-'A') * pow[L-i-1]) % M //加上i,j新的位值
*Win7一个奇葩的性质, patchouli因为有关键词patch, 会默认以管理员身份运行, 于是调试无能.
P3: 似乎是计算几何, 只想到了旋转坐标系. -> 预处理[排序]+DP
(1) 利用点斜式得到结论 d = y - kx, 以d为关键字对点进行排序
(2) f[i]表示1..i点可以取到的最大值
f[i] = max{f[j] + Σvalue[i]*Σmul[i]/(j-i) (这里Σ的范围是[j-i+1, i])} (0<j<i)
*对于α=90°的情况, 由于π的精度不够, 可以不讨论. -> 对x排序即可, 实现的话可以直接交换坐标
*对于多点d相同的情况, 按solution写法应该讨论, 但是参照标程特判会WA, 原因未知?
P4: 图论题, 有条件的最短路问题.
*分层图最短路
10.27
东方幻想乡Stage3, 2.5h, 110, 位置值64%
*心不在焉, 多次看错题.
*需要思考看完整套题的意义, 目的是什么, 需要得到什么样的信息.
P1: 二分+模拟, 95
(1) 记录被破坏点下一个被破坏点的位置next[]
(2) 以0为下界, [N/K]+1为上界, 二分答案L -> L=0即未被地震破坏, 考虑不周
(3) 利用next[]对数轴染色, 限制次数为K, 若染色后仍发现破坏点则无解
P2: 概率, 15, O(NT) -> 正解是DP
每个时刻更新每个点的概率, 利用邻接表(矩阵实现). 不更新的充要条件是vis[v][u][k-1]=1.
用P[i][k]表示第i个点在第k时刻的概率, 初始化P[1][0] = 100.
*思路非常混乱, 一开始不更新的充要条件找错. 错误原因不知.
*不明白O(NT)的做法为什么会错, 标程用类似树形DP.
P3: 最小生成树+并查集维护连通性+枚举 -> 不用并查集
利用Kruskal构造最小生成树, 并查集记录连通情况, 利用邻接矩阵维护, 枚举每个度大于2的点不断按照定义更新答案.
*考虑到多边权重相等的情况, 可能需要多次计算.
P4: LCS? -> 搜索+剪枝