题意： 在狼人杀里，有三种类型的人，一种是狼人，一种是村民，还有一种是不确定身份的人。已知村民不会撒谎，狼人可能会撒谎。每个人都会说一句话，比如玩家x是狼人或者玩家x是村民，自己不会说自己。问狼人和村民各有几人。其中1≤T≤10,1≤N≤100000。 思路： 在比赛的时候思路在经过把本来的想法的叉掉的过程之后是对了，然而不会写… 因为无论说什么全部人都是狼的情况都肯定是成立的，所以不存在确定的村

题意： 写下一组数， 1.先写1,2,2。 2.第三个数字是2，所以在后面写两个3。 3.第四个数字是3，所以在后面三个4。 4.像这样可以得到1,2,2,3,3,4,4,4,5,5,5,6,6,6,6。 给出一个数字n，假设这个n的最后出现的位置为p，求p最后出现的位置。其中n≤10^9。 思路： 可以找出规律要求的F[n]=pre[pre[n]]，其中pre[n]为原数列的前缀和，可以写几项。

题意： 给出n,m，还有k个质数$p_1,…,p_k$，有$M=p1·p2···p3$，求$C_n^m\%M$的值。其中$T≤20,1≤m≤n≤10^{18},1≤k≤10,M≤10^{18},pi≤10^5$。 思路： 这题目有点套路啊？（模板一顿乱套系列…然而比赛的时候并没有想到…完全忘记了之前学的中国剩余定理啊… 用Lucas定理处理出每个$C_n^m\%p_i$的值，可以得到一堆模质数后的

题意： 有n个数初始都为0，有m次操作，每次操作对于[l,r]，如果v大于区间的数，就把这个数变为v，即对区间的每个数取当前值和v的最大值。求这m次操作后的⨁_{i=1}^n(i⋅a_i)，⨁表示异或和，其中1≤T≤100, 1≤n≤10^5, 1≤m≤5⋅10^6。 思路： 因为是区间更新刚开始想到是线段树剪枝啊…然而比赛的时候写gg了…然而想想这复杂度也不可能过啊 是$O(3m+mlogn)$

题意： 给出N*M的区域，每个格子(i,j)|(0≤i

题意： 给出N个点，求是否存在一条直线，至少经过N个点中的\lceil N*x\rceil个点。其中1≤ T ≤ 100，1≤N≤10^4，0 < x < 1且x为一位小数。 思路： 这道题是随机两个点形成一条直线，这条直线满足条件的概率为x*x，因为在满足条件的直线上的点至少有\lceil N*x\rceil个，所以某个点在这条直线上的概率为\frac{\lceil N*x\rceil}{N}≈

题意： 给出n个点，m条有向边，有q次询问，问从s到t至少经过k_i条路的最短路为多少。其中1≤T≤10,2≤n≤50,1≤q≤100000,1≤k_i≤10000。 思路： dp也可以分块啊 感觉开拓了我的思路啊(๑•̀ㅂ•́)و✧真有趣！ 这里有两份比较好的题解： https://blog.csdn.net/weixin_42068627/article/details/81299321 ht

题意： 定义图的匹配是一组任意两边都没有公共顶点的边集，有n个点，现在有两种类型的操作m个： + u\ v：在u和v之间加一条边， - u\ v：删去u和v之间的边， 问每次操作之后边集中有1,2,3,···,\frac{n}{2}条边的边集有几个。 其中1≤T≤10,2≤n≤10,n\ mod\ 2=0,1≤m≤30000。 思路： 由n的范围可以想到要状压， 考虑dp[i][j]：经过i次操作

题意： 给出长度为L的序列A，根据这个序列跑出一个矩阵，问左上角的点(x_0,y_0)和右下角的点(x_1,y_1)形成的矩阵的和。 思路： 打表可以打出规律，会发现有循环节。比赛的时候发现了，然而写法不好，就GG了。所以写之前一定要想出一个优雅一点的写法啊。 根据这张图可以看出，蓝色框子矩阵的和由那些小的矩阵组成，所以整张图中间的子矩阵可以用容斥原理表示成这些图的左上角的矩阵的运算之和。所以

题意： 给出n，m，求C_n^1+C_n^2+···+C_n^m，答案模10^9+7。 其中1≤T≤10^5，1≤m≤n≤10^5。 思路： 比赛的时候我是根据dp，想到这相当于是杨辉三角的前缀和，画出这个三角之后感觉是个莫队啊？然而觉得转移有点麻烦没细想而且队友打表打出的另一道题目有点东西就去转战其他题目了…赛后看题解感觉血亏啊？ m的转移相当于S(n,m)=S(n,m-1)+C_n^m，就是前