有ai个重量为i的物品，i=1，2，3，4，5，6  问是否存在某种分配方案，把他们平均分？   其实这个题可以直接用多重背包搞：但是！对于每个题要仔细分析特点 举个例子，10000 10000 10000 10000 10000 10000这组数据 这么大的值有意义吗？其实并没有对吧。因为太大的值，我们可以提前平均分好 其实10000是等价于可以平均分的  但是，是偶数不能直接变成0。为什么？ 再举个例子：1 2 1 0 0 0 看到这组数据其实是可以平均分的，因为1+3==2+2 但是，如果把2删掉，剩下的1和3是不能平均分的，会导致wa  所以呢，我们把很大的值变小，而且不改变奇偶性：改...

Codeforces Round #377 (Div. 2) CF #377  这是原来的比赛：打CF打得多了之后，发现CF上分的秘诀有三个：  手速+暴力+模拟 DIV2场的AB基本送分题，C和D一般都是用简单的STL来维护几个数学值，然后用数学结论或者公式什么的搞一搞 然后E题呢，给足够的时间推推过程，其实是有可能做的  这场的6个题在补题之后写了5个   A. Buy a Shovel  这个题有个小小的坑点：注意多了一个单位价值为c的硬币：所以还有可能价值对10取余为c（当然这个坑点在样例中已经有了）  while(scanf("%d%d",&a,&...

先贴一个有数学公式的题解 题解  题意： n个人，其中每个人最少参加Ai次比赛。比赛是这样定义的：n个人之中出1个裁判，其中n-1个人参加 问：最少需要多少场比赛可以满足题目要求？  看到最少，然后  sum { A【i】}   是肯定可以的，0是肯定不行的。 想到了什么？二分答案。  如何判断某个x是否可行？ 如果x小于某个A【i】，是肯定不行的 否则，x-A【i】这么多场次，是第i个人可以用来作为裁判的比赛场次数目 所以，我们把x-A【i】这些值全部加起来，如果不小于x，说明每一场比赛都能够找到裁判 那么当前的x就可以 所以，该题又是把最优值问题转为了判定性问题，然后二分答案解决  #in...

这个题我一开始是当作树形dp搞的 题解：戳我  其实树上的dfs想成了树形dp，也是没走太多弯路的 但是为什么处理错了？  因为维护的方向和数值不对  维护的方向应该是从父亲的方向推到儿子的方向，但是基本树形dp都是从儿子维护到父亲  想想：如果当前节点u，有三个孩子，每个孩子有a1，a2，a3个孩子，那么如果我想要最小删除，那么当前节点u的总价值必须怎么计算？ 应该是lcm（a1，a2，a3）对吧，我算成了a1*a2*a3  所以整理完毕思路之后： 叶子节点是可以放着不用管的 对于每个非叶子节点，我们都需要求个lcm，然后维护一下 如果当前的值不够分，那么就需要把所有的值全部删除（这样每个子...

背包题还是太难太难，不是公式难，是理解公式运用公式太难  把n拆分成k个不同素数的和，有多少种方法。n不超过1120，k不超过14，一看就是个打表的题 首先把所有素数打表出来 然后，打表dp【i】【j】：把i拆分成j个不同的素数的和的方案数是多少  这个不同怎么来理解？ 用01背包来理解：每个素数去参与选择，只有1次选择机会（也就是说选或者不选，那么就是循环中的第一维） 由于是01背包，那么n这个值就是第二维，而且必须是降序 得到递推式子：  dp【i】【j】=sum{dp【i-prime【x】】【j-1】}，其中i-prime【x】>=0    代码如下：    //#include&...

暴力姿势永远学不会的姿势   先说题意：n点m条边，问图中有多少种情况是：有s个点两两相连（问子图的独立团，其中点数为s）  看到数据量其实并不大，n是100，m是1000，s最大为10 还有一句话：It is guaranteed that the maximum degree of the vertices is no larger than 20.  这句话其实是提示了最好的枚举方向的：从小到大来枚举，当前团中的最小编号 用mp【u】【v】来存储边，用O（1）的时间来确定u和v是否相连 用vec【i】来存储边，可以直接枚举与点i相邻的所有边  当然，这样交上去是TLE的 剪枝条件1：记录...

现场赛的铜牌题，没有搞出来挺遗憾的  题意：如果i%j==0，那么说（i，j）是可以匹配的 题目问：（s+1，s+2，……，s+n），（1，2，……，n）这两个数组能否找到某种对应方式，使得完全匹配（也就是说等于n）   一开始的思路是：素数是很特殊的数，当值很大的时候，（s+1，s+2，……，s+n）不能出现两个素数 但是这个判定条件其实很奇怪：因为不知道怎么定义值很大   那么：想着小数据打表：什么叫做小数据呢？ n很小：因为二分图匹配的算法是O（NM），所以不妨定在1000 这个范围内的直接跑算法   那么当n比较大的时候呢？直接输出no吗？ 思路接近了，但是有一种很极端的情况 n=10...

因为杭州B题是个强联通，而且90+队伍会，弱不会，所以来学一学这个专题 从最简单的模板题应用开始  n个人，m条边。（A，B）的边意味着A认为B是好人，这种关系具有传递性，即如果有（A，B）和（B，C）边在图中，那么A认为C是好人 给定n个人和m条边 问：图中有多少个人，他们被所有的人都认为是好人  看到这个题：第一想法好简单啊！暴力枚举啊，n方的算法 对于每个人，检查一遍就好！ 看到数据n最大10000，卡的就是这种思路  那么应该怎么做呢？想到的是昨天的沈阳暴力E题：如果出现了很多个点两两都可达，那么在这个问题中其实就是可以先处理成一个点集合（集合中只需要关注这个集合的数目了，还有这个集合...

全场90+个队伍过的图论模板题，自己太弱想当成网络流建图 来补完强连通的算法之后，发现：就是模板题   题意：题中有n个炸弹，其中每个炸弹有4个数据，坐标位置（x，y），引爆炸弹需要的费用c，引爆之后可以影响的范围半径r 问，我最少需要多少费用，才能把这些炸弹全部引爆！  这个题比POJ 2186难了那么一点点，因为加了个费用 从最开始：我们如何把它转化成一个图论的题：点已经有了，就是炸弹，那么边呢？？ 一定是建立有向图，因为炸弹x可能能够引爆y，但是y可能因为半径不够，无法引爆x  所以建图完毕之后（相当于POJ 2186只不过一个是给你图，一个是你自己来抽象建图）  要考虑费用最小：那么同...

做了几场CF的Div2级别的比赛，终于从这一场知道怎么上分了（因为自己很菜，还是1500+，所以上分很简单。。。） 先说说做题的心态： A题B题，看完样例，看完特判，直接求手速，一般不会卡太多太难的数据 只需要保证：如果题目中有Hint好好看看，题目中有无法达成目标，然后需要输出-1或者无解信息的需要认真去想边界情况  然后CDEF的策略： 如果C和D题同分，那么先花上10分钟左右选题，把题目和样例读懂（这种比赛一般会是2个半小时6题甚至7题，我们的目标是保证3题，冲刺4题） 如果只有一个题有思路，那么没得挑 如果两个题在大概思路上都是会写的，而且觉得思路比较靠谱：那么我推荐：先做数据结构维护...

题意：图中有n个点，m条有向边。保证不含有自环和重边 问：我们最多可以添加多少条边，使得原图不是强连通的  首先： 去掉不是强连通的条件：我们可以添加的总边数为：n*（n-1）-m 所以：如果原图已经是强连通了：那么答案为-1 需要特判吗？ 不需要！那么该题第一步就是用模板，缩点强连通 如果缩点后只有一个集合，那么输出-1（说明原图已经强连通）  然后，我们应该如何构造出最多的边？其实就是删掉最少的边。 考虑到点的总数为n，是个定值，要使得删掉的边最少，那么其实分成两个集合，每个集合中的边全部连完毕（是个完全图） 然后从A集合到B集合，要么全是出边，要么全是入边，并且使得A中点数和B中点数差别...

两边dfs还是好想好实现，就是不跟大众走，不用Tarjan   题意：有n个点，输入的时候比较奇怪，给的是第n个点与那些边相连，以0为结束符号，都是有向边 需要求两个值 第一个：我们要保证所有的点都能够得到消息，那么最少需要选取几个点来初始传送 第二个：我们想让任何一个点都能作为起点（那么就是说，该图已经成为了强连通图），最少需要添加几条边  最近刻意找的强连通的题来练习的，思路不用多分析 第一个：就是求原图中缩点后，有几个入度为0的点 第二个：我们要添加尽可能少的边，那么需要把图中的任何点都连起来 意味着：不能有入度为0的点，也不能有出度为0的点 所以，取其较大值就好  另外，我们需要加特判...

题意一句话：给你一个n*n的矩阵，求其中的最大子矩阵和  先考虑1*n的矩阵怎么求：就是一行的数怎么求： 从前往后dp对吧：对于当前第i个数，我们选，是因为加上前面的值仍然大于0，即（5，-3……）这种情况，-3是要选的，因为5-3=2>0 否则的话，把前面那一部分舍弃掉，只取当前的值，因为加起来小于0对求最大值没有意义 每选择一个数，就比较一次最大值就可以了  那么现在来考虑n*n的 我们可以枚举起始行i和起始行j，然后把从第i行的值到第j行的值压缩成一行，那么就是求1*n的矩阵的最大值了 枚举i，j，k是三重循环，在复杂度里面，那么应该怎么压缩呢？！  前缀和！提前把每一列的和存到s...

现场赛的时候，自己一个人乱搞了一发，其实题意是看懂了的，判断是对的。。。。 就是前期太SB，导致中期后期不自信，这是最大最大的问题  说下题意： n个点，m条边。x个好人，y个坏人，其中x+y<=n 好人相连的人一定是坏人，坏人相连的点一定是好人 问：我们是否可以给每个人定好坏的性质，使得既不矛盾，又不会出现某个人没有好坏身份的情况  样例： 5 5 0 0 5 1 1 2 2 3 3 4 4 5 会发现未知信息成了一个环形。 假如我们定义1号为好人，那么3号好人，2号和4号是坏人；但是现在，因为4号坏人，所以5号好人；又因为1号好人，所以5号坏人 所以出现了矛盾啊。说明这个图是NO的 ...