NIM游戏的变形题：uva10561 需要理解NIM游戏的精髓，然后知道应该怎么建模，才能搞这个题 题意：从1到n总共有n个格子，初始状态有的格子中有棋子，有的没有；要求出现连续三个格子中都有棋子为胜利状态 问先手是否可胜，如果可胜，按照升序的顺序输出所有的可胜的第一步走法 如果是不可胜，输出LOSING 这个题为什么和NIM有关，就是可以将初始状态分解成多个子状态 如：。。。。。。。。。。 X  。。。。。。。。。 前面的状态与后面的状态无关的，所以前面的可以用sg函数算出来，后面也可以 然后把所有的都异或起来，就可以知道是不是先手可胜 所以，只需要处理先手第一步必...

又是多校的一道所谓签到题：但是感觉还是有难度的：HDOJ 5724 是一道典型的sg博弈打表的题 sg函数和NIM游戏已经解释得够多的了，现在就只分析这个题目 需要分阶段：一行一个阶段，然后把所有的sg值异或起来 然后呢，需要对每一行进行分析，因为最多20列，所以可以提前打表弄好，也可以用-1作为访问标记，来记忆化搜索 如何得到sg值？就需要对题意分析，如何得到后继状态？ 后继：把一个棋子移到右边的空格子，或者是一个棋子，跳过右边相邻的棋子，进入相邻的空格 所以就是检测一个有棋子的格子，和一个没有棋子的格子，然后与原理状态异或，则变成了新状态（也就是后继状态） 见...

题目链接：HDOJ5733 2016第一场多校的一个计算几何模板题 题意：给定四个点的坐标，如果是四面体的话，求出内切球的球心坐标和球径 kuangbin模板+百度公式 先说说如何判断是不是四面体 四点不共面+任意三点不共线：四个点构成四面体 公式：在代码里有 计算几何不需要解释太多，无非就是模板中的点乘叉乘搞几下，画个图就能够出来 #include<bits/stdc++.h> using namespace std; const double eps=1e-8; const int MAXN=550; int sgn(double x){ ...

HDOJ 3682 一个相当于暴力的好题：有点容斥原理的意思 题意：n*n*n的一个正方体，每次可以拿掉一个1*1*n的柱子，问拿掉m个这样的柱子后，总共取掉了多少个小方块 想法：首先是对输入的柱子所在平面进行记录 注意的是，这个题需要判重，即有可能输入的是已经拿走的柱子 我们先处理xz平面和yz平面上的小方块，并且对xy平面的柱子进行记录 在相同的z平面的高度上，每插入一个xz的柱子，如果有相同高度的yz柱子存在，那么说明有一个重复的 所以呢，我们需要记录在xz平面上，x=x0，z=z0这个柱子是否拿掉过 而且，需要记录在z=z0这个平面上，有多少条x的柱子存在 ...

HDOJ 5726 题意：给定区间【L，R】求出区间【L，R】内数组中的数的GCD，并且找出所有的数对L0，R0，1<=L0<R0<=n，使得区间【L0，R0】内的GCD等于前一个GCD值 看到这个题，跟codeforces 689 D似曾相识啊！所以把两个题都一起补了 题解统一写在这儿吧 首先说做法： ST表：用O（nlogn）的离线处理好任意区间的内的GCD值，然后做到O（1）的查询 ST表的搞法是典型的二分想法 拿最小值举例，我们要求某一段区间的最小值 可以把区间二分，先求左边区间的最小值，右边区间的最小值 那么整段区间的最小值就是上述两个值的较小...

codeforces689D 二分+ST表的经典搞法，和HDOJ 5726 GCD是一模一样的想法 贴个题解：HDOJ 5726 gcd 两次二分的问题 第一次二分，找到右端点的左值（如果有的话） 如果有，那么进行第二次二分，找到右端点的右值，那么对应该左端点，答案的增长是右端点的区间长度 如果没有，那么说明对应该左端点，没有符合条件的右端点 代码如下： #include<bits/stdc++.h> using namespace std; const int maxn=2e5+50; int ma[maxn][30],mi[maxn][30],n; ...

自己开了一个线段树和树状数组的专题还是有用的，自己第一次独立搞出来了这种类型的题 题意：n个人，每个人有一个排名，我们需要找到的是对于i<j<k的，ai<aj<ak或者ai>aj>ak的所有可能情况，n的范围到2e4 首先对排名，我有一个疑问是：题中的rank是1到n的一个排列吗？如果是，那么为什么rank的值会到1e5呢？ 不懂，所以按照POJ 1990 MooFest  的搞法，首先离散处理一发，那么先处理成了一个1到n的排列了 有了这个，就好搞了啊！ 因为，getsum（a【i】）就是第i个数左边的比a【i】小的数有多少个 然后...

题目是中文的，不多做解释 n*m的矩阵，最大都是8，所以可以随意暴力都不会超时！ 先说说网上所有的题解的方法：贪心的思想：对起点S和终点E进行封锁，也就是说用最多四个#就可以把S框住，或者把E框住，所以答案最多为4！（之后再说明，这样想应该是有问题的，感觉HDOJ的数据不对） 那么，我们从0枚举到4，枚举量为修改多少个点 如何检测这个枚举的值是否可行呢？用bfs 在T秒的时间之内，是否可以从S走到E，而且中途遇到过J（捡到过宝石） 这又涉及到一个判重的经典的问题：加一维变量：vis【x】【y】【num】：当前坐标为（x，y），从S走到这捡到了num个宝石，这个状态是否到达过 ...

题意：一个有向图，n个点，最大50，m条边，最大4000，现在要求删掉最少的点，使得不存在从1号点到n号点的长度<=k（k不超过1000）的路径 当然，不能直接删掉1号点或者n号点，输出为最少需要删掉的点数 删掉某个点时，会将与之相连的所有的边也删除 思路： 枚举所有删点的方案：与HDOJ 1983相同，迭代加深来搞 如果不删点，就满足题意，那么答案为0 如果删除1个点，就满足题意，那么答案为1 …… 删点如何删？用dfs！ 判断当前这个点是不是可以删？删了有没有意义？（会不会影响现在起点1到终点n的最短路径？） 所以，dfs需要在bfs的基础上来跑 bfs...

wa了三四天，查错都查到自己没信心了，结果：wa在了一个循环把m写成了n！！！ 这种错误你敢信！！！ 题意：n*m的地图，其中S是起点，Y是目标点，G是加油站 我们的目标是在S尽可能的少带油（油量定好了就是携带的量的最大值），走一格消耗一点油，每个加油站的油可以让我们补充到携带量的最大值，而且只能补充一次。需要求得最少的携带量，使得我们可以到所有的目标点（所有的Y必须到，所有的G可以去也可以不去） 题目中最重要的一句话：G和Y的数目不超过15！ 看到了15和20，这类很小的数据，就知道要用到：状态压缩dp 那么，怎么得到这些状态？ 我们需要把起点S，目标点Y，加油站G...

题意： 给出平面上的n个点，每个点有唯一的标号（label），这n个标号的集合记作S，点可能重合。求满足下列条件的S的子集T 的数目： 1. |T|≥2 2.T中的点共线 这个题的重点落在了： 一：如何处理重复的点？ 二：如何判断共线？ 判断重复，算是比较简单：把所有的点排序，先按x升序，再按y升序，就方便判断点的重合了 如何判断共线呢？ 采用斜率！斜率用（x，y）来表示，先化归成不可约 那么需要对相同的斜率的进行计算和排重 看了各位大神的题解之后，采用 map<pair<long long,long long>,int> v...

这个题，是我第一次试着自己理解模板，理解题意去做题 先说题意：提到了边上的费用，提到了运送物品的数目，最后问的是，要运送k个物品求的最小花费 这个没说的，肯定是用最小费用最大流的模板搞 问题一： 费用边怎么加？ 题目中说的：运送x的物品，那么付费是c*x*x，意思是跟物品的重量不成正比，而模板中是成正比的，怎么办？ 观察到一个细节：c不超过5！那么我们可以把本来容量为c的边拆成c条容量为1的边，让路上的付费权重不一样就好了 第一条边权重为1，第二条为3，第三条为5，第四条为7，第五条为9（最多5条边） 问题二： 这个题：不是求最大流啊！是流量到了K就已经够了！ ...

1<=L<=R<=1e18 求L & （L+1） &  （L+2）  & （L+3） ……  &  R 和L | （L+1） |  （L+2） | （L+3） …… |  R 这个题呢，让我自己做，肯定就是弃疗了，学习了一份二进制枚举的代码其实还是蛮简单的 拿第x位的二进制位置距离，要想在x上，&运算有值，那么就需要【L，R】的每一位二进制x都有值 就是说，【1，R】上二进制x位置上的个数 - 【1，L-1】 的x位置上的个数 = R-L+1 同理，|  运算，需要的是至少有一个，【1，R】上二进制x位置上的个数 - 【...

这个题呢，一开始是用DP想的，但是没有按照DP的思路走，因为题目意思描述得很简单，显然是可以打表找规律的 先附上打表的程序 #include<queue> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; int dp[10][10],n; int num[10]; bool vis[10]; void calc(){ //for(int i=1;i<=n;i++) // pri...