在一个无向图（有重边无自环）中走，不能在经过连续经过某一条边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位抽出来，如果答案序列中有一组是逆序的，那么交换他们，一...

　　给出数列，求 ∑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)的代码对拍没有过去，不知道怎么回事……...

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

　　求所有数x，满足x<n且x2≡1（mod n）。　　n<=2000000000 　　对于所有的数x，如果 x2 ≡1（mod n），　　那么有 x2 modn-1=0　　可以化为 (x+1)(x-1)...

　　给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 　　我们找到b的位置，比如为pos。　　然后往左，逐位统计比b小的，比b大的，差记为a。　　对于左边所有的位置，bar[a]++，搞n×2个桶。然后右边一边扫过去，一...

　　有向图有N个节点，从节点0出发，他必须恰好在T时刻到达节点N-1。现在给出该有向图，问总共有多少种不同的路径吗？注意：不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。　　矩阵乘法。　　把一个点拆成9个，分别是time+0,time+1,time+2,...,time+8。　　然后根据输入转移，构建矩阵即可...