乘法逆元
小学奥数都还给老师了… 对于$a$，且$a,p$互质，称$a \times x \equiv 1 \pmod p$中的$x$为$a$的逆元，记为$a^{-1}$ 文中数字默认都是正整数
费马小定理
我们都知道，若$p$为素数，有$a^{p} \equiv a \pmod p$ 若$a$不是$p$的
0%
APIO/CTSC 2007数据备份
这两个题思路是一样的，都要用到优先队列和链表 [APIO/CTSC 2007]数据备份 种树 就以数据备份这个题为例： 首先我们可以知道，要取得最短配对方案，一定是相邻的楼相连，并且每对之间有空隙 可以把所有两个楼之间空隙放进数组中处理，即在数组中不能相邻取数 对于一个最小的空隙，在最优方案中它要么
HNOI2004宠物收养场
[HNOI2004]宠物收养场 一道可以用STLset解决的问题 这题貌似解法很多，但是蒟蒻只会用STL的set… 开两个set，每个分别插入INF与-INF作为边界 每次输入，如果另一个set中有可用元素，则取出进行判断 lower_bound(x)可以找出第一个大于等于x的值的位置，–x即第一个
金坷垃
Luogu P5035 金坷垃 数学题，给出k，求第k个用自身减去除本身的一个因数，重复过程可以得到1的数 我：打表可知，满足的数必为$2^x$（确信 众：数学论证，请 我： 若有$b a$，且$a - b = 1$，可知$a = 2, b = 1$ 进一步，若$b a$，且$a - b = 2$，
NOIP2018游记
Day -1
月考考完的周末就是初赛，期中考完的周末就是复赛…期中考炸了，郁闷了一天，晚上翘了一节晚自习去机房玩，做蚯蚓，没有思考的暴力打了85分…要是每道题都这么好骗分该多好
Day 0
上午摸鱼，下午去临汾了 火车上快乐聊天，还打了会osu! cwy无限循环新宝岛↓ 下午住进酒店了，旁边有个“
IOI1998 Polygon
Luogu P4342 [IOI1998]Polygon 又是区间dp耶qwq 根据题意，删掉一条边之后合并，其实类似合并果子一题 输入数据，首先任取一点破环称链，对于整个链dp之后，${f_max}[i][i+n-1]$即为答案 本题中，由于涉及乘法运算，可能有两很小的负数相乘，结果却很大，需要再
序列取数
Luogu P1430 序列取数 蒟蒻觉得很复杂的区间dp题… $A, B$两人从给定的长度为$N$的序列中轮流取数，都取自己最大结果，求A最终得分 当$A$取得数字和最大时，由于总和一定，$B$取得的数字和最小 让$dp[l, r]$表示取到$[l, r]$时，$A$的得分减去$B$的得分 若更新
SCOI2005骑士精神
Luogu P2324 [SCOI2005]骑士精神 把输入的棋子还原成题目要求的状态，求最小步数 第一次写IDA*，有点小激动www 如果考虑骑士（和马走法一样）的移动，情况过于复杂。发现只有一个空白位置，可以考虑移动空白位置 题目要求求出步数，而变换情况过多，难以直接搜索 这时候，迭代加深DFS
砝码称重
Luogu P1441 砝码称重 在N个数中去掉M个数，剩下的取任意个数相加，求最多能得到多少种和 看到题解里有用位运算的，不过本题dfs+dp即可解决 首先dfs出所有去掉M个数后的情况，暴力枚举即可
1
2
3
4
5
6
7
8
9
10
11
12
// s表示选中数字最大和
void