题意： 三堆石子的数量分别为k，4k，5k，进行Nim博弈，问在k小于2^n的时候，有多少种情况先手一定会获得胜利。 思路： 这道题被我打表+OEIS水过了… 之后看了一下正解，是这样子的： 当k^4k^5k==0时，后手赢。 k^4k^5k=0可以化成k^4k=5k， 因为有k+4k=5k，而且4k是k的二进制形式左移两位， 两个数异或与相加的得数不同的情况只有1和1的时候。 所以k和k左移两位

题意： 给你一个序列，它是1～n的全排列，现在进行两种操作： 0 l r：把[l,r]从小到大排列； 1 l r：把[l,r]从大到小排列。 做完这些操作以后，请输出下标为k的数。 思路： 这道题挺巧妙的。 考虑到这只有一次查询操作，而且它是全排列的，所以可考虑二分，为什么可以二分呢？二分有什么用呢？我们后面来讲。 首先二分一个数mid（1～n），然后对于序列中小于它的数记为0，大于等于它的数记为

CodeForces906D题意： 给定一个数列w_1,w_2,...,w_n和模数p,每次询问一个区间[l,r],求{\,{w_l}^{\,{w_{l+1}\,}^{\,{w_{l+2}\,}^{...^{w_r}\,}\,}\,}\,}mod\ p的值。其中1\varphi(\varphi(m))，所以用新定义的Mod方式来进行快速幂运算，这样子每次在函数中调用快速幂的时候得到的就是c^d\

LOJ515题意： 一共有n个数，第i个数x_i​可以取[a_i,b_i]​中任意值。 设S=\sum{x_i^2}​，求S种类数。其中1≤n,a_i,b_i≤100​。 思路： 刚开始想到的是DP，但是100^4会爆炸，所以就用bitset来暴力一下。 每一位表示的是有没有该答案，这是一个集合，如果这个集合中的每个数要与一个数x相加怎么办呢？就是把这个集合左移x位然后再与集合或运算就可以了。 代

题意： 给你一个w*h的区域，给你n个不同的地毯，告诉你每个地毯的长宽，让你把区域铺满，地毯可以旋转，不能重叠，不能剪小。问你能不能铺满。其中1≤wi≤100;1≤hi≤100;1≤n≤7。 思路： 这属于小规模的平铺类搜索。 平铺：不允许重叠，将给出的一些方块（最容易处理的是长方形了）放置在一个目标区域内。 小规模：要放置的方块数量<10，放置的目标区域的边长<=100。 贪心策略是

旅行商问题就是每个点都要走到，一般用DP解决。 避免调太久存个模板。 点的编号为1～m。 memset(dp,INF,sizeof(dp)); for(int i=1;i<=m;i++) { dp[1<<(i-1)][i]=0; //printf("(%d,%d)\n",1<<(i-1),i); } for(int i=0;i<

题意： 有n个地点，有g个人要去医院疗伤，他们最开始在in，在T时间内要到m个医院的某一个，有m条x到y的有向边，每条边每个单位时间可以通过pi人，走到这里需要ti个单位时间。 人可以停留在任意一个点，求最多能有多少人到达医院。 思路： 可以看出是一道最大流。 那么如何建图呢？ 按时间拆点，比如n=4，t=5拆成： 超级源点向初始地点连边，容量为g，表示0时刻初始人数为g。 每个点的时刻向下个

题意： n个人做m道题目，给出n个人的答案，已知每个人对了几道，求正确答案有几种情况，如果只有一种，就输出那种方案。(1≤n≤12,1≤m≤30) 思路： 如果直接枚举的话有2^30种情况，这样肯定是不行的，如果m/2的话就可以，所以可以考虑折半搜索。 枚举前半段的正确答案，把每个人后半段正确的数量放在vector里存起来（总正确的-前半段正确的），然后把这种情况放在map里，因为可能要输出答案，

题意： 有n个人，给出n个人在三个项目中的排名，要选出一些候选人，要求不是候选人里面没有比候选人三项都好的人。 思路： 理解能力是硬伤啊QAQ 这题目的意思是比如3 9 7和5 10 8，其中3 9 7每一项都比5 10 8好，所以5 10 8肯定不是候选人。 就是如果存在三项都比它好的人，那么这个人就肯定不是候选人。 假设三个项目排名分别是x,y,z。 所以可以先把所有人根据x排序，那么就满足了

题意： 矩阵M包含R行C列。 请寻找一个子矩阵，使得这个子矩阵的和最大，且满足以下三个条件： 子矩阵的行数不能超过X行。 子矩阵的列数不能超过Y列。 子矩阵中0的个数不能超过Z个。 请输出满足以上条件的最大子矩阵和。 思路： 首先考虑一个问题：求一个序列的长度不超过m的最大连续子序列。 dp[i]:以i为结尾的长度不超过m的最大连续子序列。利用前缀和可知，dp[i]=pre[i]-pre[k],1