5-16
P3934 [Ynoi2016] 炸脖龙 I
思路:
先不考虑带修 考虑化开式子 有 \(a^b=a^{b\mod\phi(p)+[b>=\phi(p)]\phi(p)}\pmod p\)
那么 \((l,r,p)\) 可以转移到 \((l+1,r,\phi(p))\)
p 为偶数时 \(\phi(p)<p/2\)
p 转移一次后必为偶数(或1)
那么 log 次后有 \((l,r,1)\) 显然为0
细节:
但是要比较 (l+1,r,phi(p)) 与 phi(p) 的大小关系
a[i]=1 后可以舍弃
当 a[l~r]>=2 且小于 : 区间长度一定很短 暴力判即可
代码:
看了一眼题解感觉写得最简单的是暴力判指数
以及我写错的点
1.求 phi 写错:if(i%p[j]==0){ phi[i*p[j]]=phi[i]*p[j]; break; }
2.多判了 a[i]=0 的情况
3. ask(i) 写成 ask(a[i])
隔壁 sxt 在做微积分?!!!
5-21
P4117 [Ynoi2018] 五彩斑斓的世界
非常好,使我五彩斑斓地发黑
37pts ,先弃了
思路:
经典题二创
考虑并查集维护数值的合并: fa[ ] 存并查集关系,val[ ] 存 rt 对应的颜色,rt[ ] 存颜色对应的 rt
发现有效区间大小只减不增,考虑每次做正好对应的区间长度的操作
为了保持正确的复杂度,有 trick : 线性分块
我的狗屎代码:
三目运算符忘加括号
无脑将地 rebuild 直接暴力 build ,本来最多 B 的值域硬拔到 V ,成功搞出 O(QV)
查询操作可以不用 rebuild 的
查询时可能爆数组
V=1e5+1,但我直接卡无意义的内存当 V=1e5 且开了 1e5+1 的数组
5-23
松鼠
思路:
首先 N Q 虽然大但不是很大
发现因为边权为 1/2 所以要跳的步数为 O(N/C) 级别
考虑按 /sqrt N 分两种情况:预处理和暴力跳
细节:
两边往上跳不过fa的点 然后算合并
把跳跃转化为覆盖,可证 上->下 与 下->上 无区别
我的shebi代码(不知道为什么但我好喜欢念傻逼为shebi):
1.lca
int lca(int u,int v){
if(fde[u]<fde[v]) swap(u,v);//lca比较的是点的深度不是带权深度!!!
dord(i,16,0) if(fde[fa[u][i]]>=fde[v]) u=fa[u][i];
if(u==v) return u;//记得加!!!
dord(i,16,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
2.倍增大小开小了
3.常数优化,去掉了不必要的vector
5-25
扭动的回文串:70
思路:
容易想到枚举中心点
对于一条扭动的串,容易想到:
它在当前行不会超过回文范围,而且对于多种下扭方案,在回文边界向下的一定更优
然后二分即可
细节:
一般的回文串可以通过加“#”一次性处理奇偶回文串
但这里由于有下扭,需要进行调整:
#A#B#C#D#E##
##D#E#B#A#C#
可证这样正确且不影响复杂度
写马拉车+二分(哈希判断),对于中心点所在的不同行做两遍
代码:
最开始加“#”写错了
二分时 l , r 判错了
为了防止哈希重复改成随机赋值但70pts依然没有变化
P3624 [APIO2008] DNA
这题不应该很水吗?
这么想的话都很水 或者都不水只有我水==
细节:
设 DP 状态的时候,直接设为恰有 k 次,方便转移
后面前缀和一下
代码( 1K 不到的代码 4 个错……):
f[N][11][4]//数组范围开错,为f[N][4][11]
m--;//我定义的状态和题意不一样……
c['A']=0,c['C']=1,c['G']=2,c['T']=3;//复制粘贴一半完忘改了,全部等于1
K-=f[i][m-(k<p)][k];//减去选v的数量(排名皆<K),但是忘了对应状态的m可能变化
5.31
月考浅炸一波
事已至此,先看番吧
P3625 [APIO2009] 采油区域
思路:
发现只有三个正方形,所以放置方案本质上不会太多
解析一下,再每种算一般取
细节:
发现所有方案都可以用一条直线分出一个方形
所以 3 -> 2+1
6.1
我真的只是站在外面吹了十分钟的风……我还穿了外套……
脆皮高中生石锤
PS : 六一快乐
6.2
打了校模拟赛
T1
n <= 1e6
a , b , x <= 1e9
思路:
发现转向那个条件对答案没有意义
因为问的是最后掉下来的蚂蚁的时间,容易想到它肯定是正好撞碎柱子的那一只
( 撞碎柱子后其他蚂蚁爬 < 2Len 的时间,它爬 2Len 才能掉下去)
可以想到二分
细节:
但其实有两种
一种是 a<<b , 这种情况下只可能全部从 a 掉下去
一种是 a , b 差不多大时,也可能从两端掉
但差不多,在 T_{ A | B } + 2Len 和 T_{ A & B } + Len 之间取个 min 即可
但我写挂了
代码:
1.longlong 转 double 会丢失精度
2.二分上边界写小了(调了超久)
另解:
对于一个边界,肯定是以 2Len 为周期的被撞
然后计算哪一个撞了最后一次,然后算
这样可 O ( N )
T2
解 a ^ x = b ( mod p )
思路:
可以想到枚举 a^0 , a^1 , a^2 , ... , a^phi(p)-2,但这样会炸
但这是可以压缩重复求逆的乘法运算
所以开块长 B ,暴力这一段
之后都可以分成 \(a^{kB+x'}=b\) 的形式
据说这个算法有个名字,叫BSGS
代码:
判无解的时候漏判了 a=0 (mod p)的情况
T3
n<=1e5 , m<=5
思路:
因为没想出来就先去看部分分了
-
m=5 ,n=1e5,数据随机
显然的最多2步就能到 -
m=2
转移肯定是不断从不同行的点之间跳跃
于是发现对于状态可以表示它的“价值”:c [ i ] [ j ] [ k ] 表示第 i , j 的点,一次转移到第 k 行可以覆盖的范围
而进行一次转移,就用 c 表示的区域内的 c' -> c
可以倍增: O ( N logN m3 )ord(k,1,16){ ord(j,0,m) ord(i,1,n) { f[j][i][k]=f[j][i][k-1]; ord(l,0,m) f[j][i][k].gin(f[l][f[j][i][k-1].c[l]][k-1]); } }
但是这个解法在 m=5 时会 TLE (因为我 T 了)
然后我不会了……
状态优化:
对于 a [ 1 ] [ x1 ] = a [ 2 ] [ x2 ] = ... = a [ m ] [ xm ] = v 这m个点来说,它们的“价值”是一样的
所以把 [ i ] [ j ] -> [ v ]
价值优化:
对应的把位置转化为最优位置的值
代码:
初代码的锅:
1.转移的时候直接,更新在用来确定更新范围的变量上了
tmp=S; ord(k,0,m) tmp.gt(f[k][S.c[k]][j]);
// tmp=S; ord(k,0,m) tmp.gt(f[k][tmp.c[k]][j]);
重写的代码:
1.边读入边转移完全没考虑过数据不全……
T4
网络流板子题,没什么好说的
6.3
P3626 [APIO2009] 会议中心
思路:
最开始想的是找到可行&当前最优块后删去因为其变的不优了的块
删除方案:
首先选择方案可以构成一张DAG
我们选的 x 在一条边上,与那条边并联的边都得删掉了
但是我下午困得要死想不下去了,然后跑去看题解了(我忏悔……
6.4
决策单调性
一类满足决策点单调的题目
判断方法:
1.凭感觉糊一下
2.\(w(l-1,r)+w(l,r+1)\) 优于 \(w(l,r)+w(l-1,r+1)\)
注意:
决策点单调并不代表对于 \(f_i\), 决策点越接近 \(k_i\) 越优
只是决策点覆盖的连续性(从 L 一直覆盖到 n )
P1912 [NOI2009] 诗人小G
思路:板子题
代码:
1.判断 x * y > M 时,用 x 和 M / y 比较,忘记判除数为 0
2.决策点的覆盖范围应不包含该点 l > x
3.对于两个决策点的比较,虽然其可能在某个位置双双过大,但再往前还是有用的,不能直接对 inf 赋定值(大小关系会判断错误),而是用 long double 比较
[ABC356FABC356F] Distance Component Size Query
思路:很显然
代码:
1.数组名称重复
2.set 写着很烦,建议模块化编程
3.函数内传 set 是复制一遍,手动加 &
扭动的回文串
思路:这题前面写过了只是没调出来
代码:
函数功能与调用目的有差错:用get(l,r)
取 [ l , r ] 的哈希值,但是函数内算的是 [ l , r )
P8352 [SDOI/SXOI2022] 小 N 的独立集
思路:
如果要做独立集,需要的状态为 \(f_{u,0/1}\)
显然有结论就是 \(f_{u1}<=f_{u0}+a[u]\),且 \(f_{u1}<=f_{u0}\) 时 \(f_{u1}\) 就用不上了
那么可以设状态 dp [ u ][ i ][ k ] ,最开始想的是表示 f [ u ][ 1 ] = i , f [ u ][ 0 ] = i - k 的方案数
但为了适应“\(f_{u1}<=f_{u0}\) 时 \(f_{u1}\) 就用不上了”这一条件
dp [ u ][ i ][ k ] 表示为 u 的父节点不选时(无限制)会取 i , 选了时会取 i - k 的方案数
背包即可
代码:
因为是01背包所以要加 tmp 数组存储,但是 dp[u] -> tmp 的位置写在内层循环了
函数类型写错,而且因为函数没有返回值RE了 ll uad(ll &x,ll y){ x=x+y<P?x+y:x+y-P; }
这种错本地跑不出来
6.7
学长们要高考了
P4027 [NOI2007] 货币兑换
思路:
首先有结论:每次买进操作使用完所有的人民币,每次卖出操作卖出所有的金券。严谨证明其实是很烦的,但是感性理解起来还是比较轻松
然后可以化出一个形如 ax+by( x,y 变量),问最值
这玩意是搞不出来的(没有凸包那样的几何性质),于是我逝了
但是再化:\(b(\frac{a}{b}x+y)\) ,可解
细节:
x , y 没有单调性,李超线段树维护
下标带浮点,值域过大容易超时,离散化
卡精度:long double,比较用 eps
6.15
虽然是补记录
最近whk/OI都提不起劲,死
你倒是卷啊啊啊啊啊啊
Ciel and Gondolas
思路:
显而易见的决策单调性
代码:
没加快读卡死
特别行动队
思路:
显而易见的凸包
细节:
其实李超线段树(Nlog2N)应该不会被卡,但是练一下斜率优化吧
维护线段和它的覆盖范围(根据 x 的变化取边界/弹出)
sl[h]=s[i]; while(h<t&&sl[h+1]<=s[i]) sl[++h]=s[i];//有用的覆盖范围到s[i]为止
while(h<=t&&sl[t]*sk[t]+sb[t]<sl[t]*k+b) t--;//整段弹出
t++,sb[t]=b,sk[t]=k;
sl[t]=t==h?s[i]:gt(sk[t],sb[t],sk[t-1],sb[t-1]);//求交点(覆盖范围),注意只有它这一段的可能
6/24
预祝YCE进清华
标签:tmp,phi,一下,代码,fa,思路,ord From: https://www.cnblogs.com/chaoyd/p/18291814