吃奶酪 题目传送门 解题思路 我们可以设一个f[i][j] i表示，当前在i点，j表示一个二进制，其中0表示没走过，1表示走过  f [ j ] [ i ] = m i n ( f [ j ] [ i ] , d o u b l e ( 1.0 ∗ f [ k ] [ i − ( 1 < < j − 1 ) ] ) + d o u b l e ( 1.0 ∗ d i s ( j , k ) ) ) ; / / 状 态 转 移 f[j][i]=min(f[j][i],double(1.0*f[k][i-(1<<j-1)])+double(1.0*dis(j,k)));//...

关灯问题II 题目传送门 解题思路 它的起点是一定的，终点也一定，求最小步数，满足边权都为1，很明显是一道状压BFS 将它的状态存到队列里，一开始全部为1 转移 我们设a[i][j]表示第i个开关可以改变第j个灯 当a[i][j]为1，并且当前状态的第j位为1时，则当前状态为当前状态异或2^j-1次方，即改变第j位上的值为0 当a[i][j]为-1，并且当前状态的第j位为0时，则当前状态为当前状态或2^j-1次方，即改变第j位上的值为1 AC代码 #include<iostream> #include<cstdio> using namespace std; int n...

小凯的疑惑 题目传送门  解题思路 这题就是一道数论 不妨设a<b 假设答案为 x 若  x ≡ m a ( m o d b ) ( 1 ≤ m ≤ b − 1 ) x≡ma (mod b)(1≤m≤b−1) x≡ma(modb)(1≤m≤b−1) 即  x = m a + n b ( 1 ≤ m ≤ b − 1 ) x=ma+nb(1≤m≤b−1) x=ma+nb(1≤m≤b−1) 显然当 n≥0 时 x 可以用 a,b 表示出来，不合题意。 因此当 n=−1 时 x 取得最大值，此时 x=ma−b。 显然当 m 取得最大值 b−1 时 x 最大，此时  x = ( b − 1 ) a...

过河 题目传送门  解题思路 这题就是状态压缩优化 你可以先去看看P3951 小凯的疑惑（数论） 从上题得知，a*b-a-b是最大不能得到的价值，后面的价值都能够得到 这题也大同小异，当奇数和偶数都可以被枚举到时，后面的数自然也可以被枚举到 最大能枚举到奇数和偶数的位置，就是T * (T-1)，这样就可以压缩空间和运算次数  for(int i=1; i<=m; i++) {  b[i]=min(a[i]-a[i-1],90);//最多是10*（10-1）=90 l+=b[i];//重新统计长度 sum[l]=1;//标记石头位置 }  DP 用一个 f[i] 表示当前第 i 个点走过了...

[USACO06NOV]Corn Fields G 题目传送门  解题思路 这题就用一个f[i][s[j]] 表示在当前第 i 行的状态为 s[i]  f [ i ] [ s [ j ] ] + = f [ i − 1 ] [ s [ w ] ] f[i][s[j]]+=f[i−1][s[w]] f[i][s[j]]+=f[i−1][s[w]] 注：要取模 AC代码 #include<iostream> #include<cstdio> using namespace std; long long n,m,x,t,answer,a[15],b[10005],f[15][...

人员分配 Description 设有M个工人x1, x2, …, xm，和N项工作y1, y2, …, yn，规定每个工人至多做一项工作，而每项工作至多分配一名工人去做。由于种种原因，每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。 Input 第一行两个整数m，n分别为工人数和工作数。 接下来一个整数s，为二分图的边数。 接下来s行，每行两个数ai,bi表示第ai个工人能胜任第bi份工作 Output 一个整数，表示最多能让多少个工人派到自己的胜任的工作上。 Sample Input 3 3 4 1 2 2 1 3 3 1...

Asteroids Description Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid. Fortunately, Bessie has a pow...

最小生成树 题目传送门  解题思路 这题就是最小生成树模板 因为kruskal是O(n3)会TLE 所以我放了个prim的代码 有道题目最优布线问题（最小生成树）和这题很像 AC代码 #include<iostream> #include<cstring> using namespace std; int n,n1,k,s,a[5005][5005],b[5005],m[5005]; int main() {  cin>>n>>n1;//输入 for(int i=1;i<=n1;i++) {  int x,y,z; cin>>x...

Knights Description We are given a chess-board of size n * n, from which some fields have been removed. The task is to determine the maximum number of knights that can be placed on the remaining fields of the board in such a way that none of them check each other.   一张大小为n*n的国际象棋棋盘，上面有一些格子被拿走了，棋盘规模n...

地鼠的困境 Description 地鼠家族面临着一个新的威胁——猎食者。   地鼠家族一共有N个地鼠和M个鼠洞，每个都位于不同的(x, y)坐标中。假如有地鼠在发觉危险以后s秒内都没有回到鼠洞里的话，就可能成为老鹰的食物。当然了，一个鼠洞只能拯救一只地鼠的命运，所有地鼠都以相等的速度v移动。地鼠家族需要设计一种策略，使得老鹰来时，易受攻击的地鼠数量最少。 Input 本题有多组数据。第1行为测试数据组数T(T<=50)。 对于每组数据，第一行4个整数n, m, s和v(n, m <= 100)。以后n行为地鼠的坐标，以后m行为鼠洞的坐标。距离的单位是m，时间的单位是s，速度的单位...

最小路径覆盖 Description 定义： 一个不含圈的有向图G中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束，且长度也为任意值，包括0。请你求任意一个不含圈的有向图G的最小路径覆盖数。 提示：最小路径覆盖数＝G的定点数－最小路径覆盖中的边数 最小路径覆盖数＝原图G的顶点数－二分图的最大匹配数 Input t 表示有t组数据；n 表示n个顶点（n<=120）；m 表示有m条边；    接下来m行，每行有两个数 i，j表示一条有向边。 Output 最小路径覆盖数 Sample Input 2 4 3 3 4 1...

拦截导弹 Description 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 Sample Input 300 250 275 252 200 138 245 Sample Output 5（最多能拦截的导弹数） 2...

最近公共祖先 题目传送门 解题思路 这题就是LCA（Least Common Ancestors）最近公共祖先 LCA LCA：基于有根树最近公共祖先问题 在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先，这个祖先节点即为lca。 同时lca一定是u、v路径上的点。 我们可以有这样一个思路，先让u、v中深度大的那个点先往上走，直到两点深度相同。然后一起往上走，知道两点相遇，这个点就是lca。 如果我们每次只走一步，显然单次查询lca复杂度为O(n)。那有没有在空间合适的条件下更好的算法呢？ 借助前面ST表的思路，如果我们设f[i][j]为以i为当前节点，往上走2^j步对应...

ST表 题目传送门 解题思路 这题就是ST表 我们设f[i][j]表示以i为左端点，长度为2^j的区间的最小值（最大值等）。 以最小值为例，显然可以有递推式  f [ i ] [ j ] = a [ i ] ( j = 0 ) f[i][j]=a[i] (j=0) f[i][j]=a[i](j=0)  f [ i ] [ j ] = m ( f [ i ] [ j − 1 ] , f [ i + 2 ( j − 1 ) ] [ j − 1 ] ) ( j > 0 ) f[i][j]=m(f[i][j-1],f[i+2^(j-1)][j-1]) (j>0) f[i][j]=m(f[i...