从起点1到终点n，需要最短的时间是多少？ 看上去是一个很简单的题，意思也很容易懂：但是！图中暴力建边的情况太多了！ 题中说的是：每个集合中的点，互相之间的距离都是x 那么，我们可以在图中新建一个源点u，一个汇点v 连边（u，v），边权值为x 连边（i，u），边权值为0（这样就会有i到终点v的花费为x的边了） 连边（v，i），边权值为0（这样，集合中的任意两点i，j就是可达的） i-u-v-j，花费为x，j-u-v-i，花费为x：那么，在每个集合中添加了两个节点u和v之后，添加的边数减少了很多很多，成了O（E）的空间复杂度 所以，对于每个集合都是这样做 然后随便选取一个...

在【1，n】中，给定两个数x，y，保证在范围内，而且不相等 新数产生的规则是：a+b，或者，a-b：也必须在区间内 问：最后是先手胜利（后手无法产生新数）还是后手胜利（先手无法产生新数） 数论的简单题：需要知道的结论是：as+bt=gcd（a，b）是一定找到s，t使得成立的 那么，就是看n中有多少个gcd（a，b）：数量为n/gcd（a，b） 其实分不分类都无所谓，只是分类好想一点 当a和b互质的时候，可以产生【1，n】中所有的数：新产生的数目为n-2：只需要判断奇偶 当a和b不互质的时候，我们需要单独特判：新产生的数目是多少？ 然后，还是一样的判断奇偶就好了 #i...

给n(1≤n≤500)个字符串，求一个最大的i，使得存在一个Sj不是Si的子串。 这个题，用不用KMP其实意义不是太大，重点是如何把二维的循环减小到一维 跟二分答案的思路差不多： 维护两个指针l,r 那么有两种情况： 如果Sl是Sr的子串，那么l++。 如果 Sl不是是 Sr 的子串，那么将答案更新为 r ，然后 r++ 考虑Sr+1的时候为什么同样不考虑Sl之前的串了呢？ 因为 Sl 之前的串都是后面某个串的子串，所以如果他们中有不是 Sr+1 子串的串的话，那么一定有对应的那个串也不是 Sr+1 的子串。这样保证 r 一定能更新到 ans 如何去判断是不是匹配...

这个题就是个阅读理解！！！ 然后就是解一元二次方程：因为可以猜测得到在区间内的单调性，所以可以直接用二分法解方程来判断 贴两个写得好的博客吧：思路真的很直接 qscqesze snowy_smile 因为总共有5分（2-3-4-1四个点的分数）+打架的分数 所以，我如果打晕他之后，一定是需要马上跑的（不会浪费时间在等他） 所以，有v1，v2之后，相遇的打他的点必然是个固定的点（正好碰到是最好的情况） 打架一定会赢，所以我有如下几种可能的赢法： A：跑得和他一样，刚过2的时候，打赢他。他停了之后我就跑，能够赢 B：在（2，3）之间某点相遇，那么需要二分求得一个距离...

KMP匹配是模板题：这个题改了之后的模板题 问：每次需要间隔P个字符，求匹配数 间隔P个字符，那么我们可以分成多个子串去求咯？ 把大串分解成很多很多个小串，以P为间隔（也就是分成了P个） 然后查询P次 直接用BIN神模板，会出现一个很蠢的问题：next数组求了很多次！ 所以，这个题把求next数组的部分拿到外面来 然后分成以P为间隔，分成多个新的数组就好！！！ #include<bits/stdc++.h> using namespace std; const int maxn=1050000; void kmp_pre(int x[],int m...

题目中看到了Special Judge，看到了n和k是感觉无法暴力的数据大小，那么，我们就要试着去考虑一发公式了！ 当GCD的值取到最小的时候，说明相邻的两个数字全是互斥的 意思是：k=1时，数列为1，2，3，4，5，……是符合条件的 当k=2的时候，说明有一对不互斥，而且GCD只增加了1，那么我们可以构造出来一对偶数放到前面的情况，即：2，4，1，3，5，6，7，8，…… 当k=3的时候，说明有两对不互斥，而且GCD只增加了2，那么：2，4，6，1，3，5，7，8…… 所以，当k为几的时候，就是前几个偶数放在前面（k=1的时候，2，1，3，4，5，……也是可以的） 所以： ...

在【1，n】中，可以删去最多多少个数，可以使得剩下的数字构不成三角形的三条边 三角形：a+b<=c这样，才是构不成三角形的a，b，c三边 那么，极限条件是什么呢？！等于号 a+b=c 取a=1，b=2（前两个，肯定要尽量小）那么得到的FIB数列（讲道理的话，这个题的n设计的得太小了，如果搞大一点更容易知道是数学题） 1，2，3，5，8，13是可能取出的最多的三角形的边 所以，答案就是打表就好： #include<bits/stdc++.h> using namespace std; int ans[21] = {0,0,0,0,1,1,2,3,3,4...

这次比赛的数学题真心是有点多，所以确实成了一个手速场的比赛 5题可以从铁排到银确实还是有点恐怖 这个题的意思： 求一个连分数的值：写成循环或者递归或者迭代的方式是最省时间和精力的 （这个题的n实在太小了，考察不了什么。如果n大一点，就不会有去暴力推公式的了，考察度能强那么一点） #include<bits/stdc++.h> using namespace std; #define LL __int64 const int maxn=50; LL fenzi,fenmu,newfenzi,newfenmu; LL a[maxn],b[maxn]; int t...

题意比较好理解吧： 模拟一个双端的操作 PUSH就是插入值，其中值只可能是0或者1 POP就是弹出值 REVERSE是改变栈的开口（相当于如果一开始从底部插入的话，输入REVERSE之后，就从顶部插入了） QUERY：按照顺序计算栈中所有元素的与非值 这个题很明显是个数据结构的模拟题（竟然可以用线段树过的我也是佩服） 第一想法当然会是想到：deque这个双端队列 QUERY很明显不能一个一个的按照与非的定义去计算： 那么我们必须找到这样一个数学规律： A：0和任何数与非得到1（这个任何数不仅仅指0，1，也指任意一个01序列） B：奇数个1与非得到1，偶数个1与非得到0...

2015北京现场赛A题 2015北京现场赛题目 题意： 有一块R*R的土地，上面有n个矩形，告诉你左下角的坐标和长和宽，矩形不会超过土地的边界 现在要用一条竖直分割线，把土地分成两个部分，要求： A：左右两块土地，矩形面积和尽可能接近，而且左边的矩形面积不小于右边 B：在满足A的基础上，左边的土地面积尽可能的大 看到题目：很容易想到二分！ 那为什么这个题现场很多人过不了呢（我这种菜都不知道怎么二分） 第一遍二分： 求得面积相等的（如果有的话，最左边的点） 在二分的过程中，最后的结束必定是到了R+1==L的时候 所以，L点必定是当前矩形面积最接近的点 ...

提交链接：hiho1251 现场赛的时候这个题过题率特别特别低，原因是搞不懂这个题的正确姿势 现在想想，数据规模特别小的时候，暴力就是最好的姿势 题意：给两个只有1，2，3，4，5，6的数字串，操作A修改某一个字符，操作B为修改某一类字符，问最少多少次操作可以把第二个串变成第一个 题目的两种操作：我们可以知道，需要建立一个一一的对应关系： 1变成什么，2变成什么？这样会有123456对应到abcdef的情况 考虑到修改某一类字符，肯定是先刷一层，再去刷下一层，所以我们可以用状态压缩，然后暴力枚举出来所有情况 把123456变成012345，然后bfs，考虑出来所有的变化情...

《网络流建模汇总》最大流专题 对于每个顾客和每个猪圈的分析： 首先求最大，很明显是求最大的流量，那么需要添加源点s和汇点t 和汇点t相连的很明显：每个顾客的最大购买量buy【i】 那么猪圈这个应该怎么转移呢？ 题目中的意思是：如果我打开了1，2，3，4这几个猪圈，那么每个都可以互相转化（边的权值为INF） 因为现在网络流中的点是顾客 那么需要建立顾客与顾客的关系：那么只能以猪圈的打开和关闭来连边 如果我是当前打开某个猪圈的第一个顾客：我可以买完所有的~~~那就是看当前猪圈的容量，也就是建立边s-i，边权为猪圈的猪的数量 如果我是后面的第i个顾客： 我可以买完所有的（...

做过一个无向图欧拉回路的题 HDOJ 5883 但是这个题是个混合图（无向边和有向边都存在） 那么如何搞呢？ 首先判断点的度数 设D【i】=i点的入度 - i点的出度 把图中的所有边都任意定向，然后计算出所有的D【i】 如果存在某一个i，使得D【i】不为偶数，那么说明：不可能存在欧拉回路（反之不一定成立，即：都是偶数也可能没有欧拉回路） 也就是说，对于点i来说，D【i】个符号不对 我们需要改变D【i】/2条边的方向，就能保证D【i】=0，也就是出=入 现在的问题是：怎么做改变？ 细节在论文里~~~~~~ 谈谈自己的理解：用最大流来理解 在做改变的时候，我...

题意：一个无向图。点i处有Ai头牛，牛棚能够容纳Bi头牛，从i到j有个时间，求一个最短时间T，让所有的牛都能够进入牛棚 这个题呢，思路其实很简单：二分时间就能找到最小值，对于每个时间点T0，判断是不是可行就好 可行的意思：在给定的时间内，跑出来的最大流等于各个点的牛的数量之和 时间影响了什么？影响了从i点到j点能不能去。时间不够的话，就去不了 然后看看题目中的数据，n不超过200：所以用floyd算法得到任意两点之间的最短时间 这样建模就很清晰了： 拆点： 对于任意不同的两点i，j：如果time【i】【j】不超过当前二分的时间T0，说明第i个点的牛在时间内可以到第j个牛棚...