在一个无向图（有重边无自环）中走，不能在经过连续经过某一条边2次。　　现在走t步，问有多少中从A到B的方案。　　答案mod45989　　点数<=20,边数<=60，t<=230　　一开始没看到不能来回走这一个条件，所以还以为是一道水题。　　发现这个之后，思考一下，发现还是一道水题。　　如果没有这个...

　　求一个区间范围内，近似幸运数字的个数。　　定义：　　幸运数字：仅由6或者8组成的数字。　　近似幸运数字：幸运数字的正整数倍。 　　我们发现幸运数字很少。　　然后，我们考虑容斥。　　我们发现原来的大整数除几次机会很小。所以记忆化dfs容斥，中途跳出。　　这样可以节省很多时间。　　然后居然过去了。 ...

　　给出多个凸包，求面积交。 　　首先我们考虑两个凸包相交的情况。　　例题：HDU1632　　我们可以证明，两个凸包相交，如果面积交为正，那么新构成的面积块一定也是一个凸包。　　具体证明可以分情况讨论，反正画几个图就明白了。也可以网上查一查。　　那么题目就简单了。　　变成了一道水水的码农题。　　两个凸包面积交...

　　平面上有n个点，现在把他们划分成k个部分，求不同部分之间最近距离的最大值。　　两个部分的距离就是两个部分中的最近的点对的距离。 　　n<=1000 　　我们把所有的点全部建边。　　然后我们要更新答案，就要尽量弄掉短的边。　　于是就按照kruscal那样从短的开始弄。　　当然要用并查集。　　...

　　在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.　　n,m<=100 　　其实就是不出现3炮共线就可以了。　　用dp[i][j][k]表示前i行，有j列还可以放1个跑，有k列还可以放2个跑的方案总数。　　然后...

　　给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。 　　点数<=20。　　我们发现，　　圆周上有矩形的充要条件是它的两条对角线一定是它的直径。　　如果不是，那就不会有直角了。　　所以搜素在同一直径上...

　　一个序列n个数，支持3种操作：　　1.询问区间和　　2.修改区间：每一个数加上一个数　　3.修改区间：每一个数乘上一个数　　n,m<=100000 　　线段树。　　懒标记维护两个，一个是加的数，一个是乘的倍数，我写的是先乘后加。　　下传的时候也是先乘后加。#include<cstring>...

　　有一棵节点为n个(n≤500000)的树。接下来m次询问(m≤500000)，每次给出3个点a,b,c，现在让你求一个点p，使得dis(p,a)+dis(p,b)+dis(p,c)最小。　　输出p和 dis(p,a)+dis(p,b)+dis(p,c)。 　　分别求3个LCA。　　学...

　　给出长度为n的数列，只会出现1~k这些正整数。现在有些数写成了-1，这些-1可以变成任何数。　　求把这些-1变成1~k中的正整数之后，最少的逆序对个数为多少。 　　我们可以判断，这些-1中写的数字一定是单调不降的。　　为什么？我们把答案序列的所有-1位抽出来，如果答案序列中有一组是逆序的，那么交换他们，一...

　　给出n个数，每一个数字<1000000，对于每一个数，让你求剩余的n-1个数中有多少是它的约数。 　　用桶计数，弄出每一个数字的出现次数。　　然后用类似筛法的方法，把每一个数字的倍数都加一下即可。 #include<cstring>#include<algorithm&g...

　　有N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换.如果FJ买一块3x5的地和...

　　给出数列，求 ∑F[i]，其中F[1]=a[1],F[i]=min(|a[i]-a[j]|) (j<i)　　只需要每次可以求那个东西就可以了。　　那么我们搞一个set，每次把数字放到set里面。　　查询就是lower_bound，这样就可以找到与这个数字差值可能最小的。　　然后只有...

　　给出两个n*n的数字矩阵，问最大公共正方形边长。　　先二分答案一个m，对于每一个m，哈希大矩阵中每一个位置上的边长为m的正方形，然后排序，lower_bound一下判定即可。　　鬼畜的是，我的代码在BZOJ上面过去了，but和hzwer大佬(Orz)的代码对拍没有过去，不知道怎么回事……...

　　两只青蛙，现在分别在x,y的位置，以m,n的速度在周长为L的环形跑道上面跑。　　问他们什么时候可以到同一个位置。（如果永远不能，则输出Impossible）　　扩展欧几里德模板题。　　设a=x-y,b=n-m,　　我们可以列出方程：ax ≡b(modL)   &n...

　　一个n*m的矩阵，现在有2种操作：修改某一个位置的值求一个子矩阵某值的出现次数　　n,m ≤300, 1≤ 元素的值 ≤100,操作次数 ≤200000　　100棵二维树状数组。维护每个值的二维前缀出现次数。　　好像该说的都说了&hellip...