题目： 给n个人物m个装备，d是最大花费。每个人物和装备都有一个攻击力a和花费b。满足如下条件情况下选出一些人物和装备得到最大的攻击力：（1）人物数量>=装备数量（2）人物花费+装备花费<=d（3）人物数量<=5数据范围：0<n,m≤300，25≤d≤138，1000≤a1≤15488，500≤a2≤2500，3≤b1,b2≤12 做法： 01背包变形。这个数据范围即使没有第三个限制也能做。思路是这样的：dp1[j][k]表示选出≤j件装备花费≤k时，最大攻击力和。dp2[j][k]表示选出j个人物花费≤k时，最大攻击力和。如果我们得到上面信息。那么答案for一遍统计...

题目： 给一个树形城市网络。一开始住在s城，第一天游览距离s城≤1的城市，然后住进另一个未游览的城市，第二天重复游览步骤。问最多能游览多少天。 做法： 题意转化一下，让你选尽量多的城市，使城市之间两两不相邻。这就是树上的最大独立集问题。树形dp，dp[u][0/1]表示点u选/不选时，子树u下的最大独立集的点的数量。 u选了，儿子v就不能选。 u不选时，儿子v可选可不选。城市网络以s为根，答案是dp[s][1] 代码： #include <bits/stdc++.h> #define debug(a) cout << #a ": " << a <&...

题目： 给一个n*m的01矩阵。1代表可以安放士兵，0代表不能。士兵不能安放在相邻的位置（上下左右）。问有多少种安防士兵的方案。答案对1e8取模。n，m最大12 做法： 看n，m的数据范围，这是状压的数据范围。题目只问士兵的方案数，没有限制士兵的数量。所以我们直接对每一行的状态进行枚举，一行一行转移。对于第i行的状态sta，首先要与这行可放置士兵的状态无冲突。即sta中1的位，在给的01矩阵中都是1，即sta&b[i] == sta。然后这一行相邻位置不能同时有1。这样处理：sta&(sta<<1) == 0。经过这两个判断，这一行这种状态才合法。然后就是枚举上一...

题目： 你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。 做法： 二分套牌的数量，将问题转化成判定行问题。为什么可以这么做呢？因为若能组成x套牌，必定能组成x-1套牌，有一个临界点在里面。二分的check，我们可以算出mid套牌需要几张joker，若need...

题目： 花园里有n头牛，每头牛有ti和di。代表将它迁回家要花2*ti时间，而呆在花园里每单位时间消灭di朵花儿。问你按什么顺序牵牛使被消灭的花儿总数最小。输出最小总数。 做法： 相邻两头牛的顺序不影响除它们之外的所有牛的贡献，这是典型的贪心。若牛A排在前面比牛B排在前面优，可以列出如下式子： 移项化简：按这个式子排序。得到最优牵牛回家的方案。然后统计一下被牛消灭的花的数量即可。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) co...

题目： 给你n个数的正整数集合。让你挑选最少的数，使两个集合等价。集合等价，即两个集合能表示的数的集合相同。 做法： 由于给的都是正整数。题目就是让我们求给定的n个数中，哪些数是不必要的。所谓不必要，即某个数能被集合中的其他数表示。我们将集合a[]排序。若a[i]能被前i-1个数中的某个子集表示，则这个数就是不必要的。想到这，不难发现这就是个完全背包。做完全背包时，考虑到第i个数时，此时dp[]数组保存的恰是前i-1个数能表示的所有数。我们check一下此时dp[a[i]]的值。若为1说明a[i]容量的背包能被前i-1个数装满。即不必要。 代码： #include <bits/std...

题目： 有n个建筑待修理。修理第i个建筑用时，修理它的截止日期是。只有在截止日期前修好某个建筑才算修好。现在问最多能修好多少个建筑。 做法： 这题是个贪心。我们将截止日期排序。从前往后处理。当前修建筑的总用时时，选择修第i个建筑，而当时。我们就看需不需要用当前的建筑替换之前修过的建筑。很显然如果之前有一个建筑修理用时比当前建筑长，我们替换它后能在保证修理数量不减的情况下使当前修理总用时变小，这当然是更优的的做法。而替换掉之前修理用时最长的建筑，是最优解。这个贪心过程用优先队列维护一下就行了。 代码： #include <bits/stdc++.h> #define IOS io...

题目： 小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍历整个图。 做法： 两步走不难往二分图上想。如果一幅图是二分图，将图分成2个集合。从1出发只能走到1所在集合中的点。而只要该图不是二分图，必定有一条边连接同一个集合中的2个点，进而可以从一个集合走到另一个集合，也就能走完所有点。所以这题做法是：先求出所有联通块。联通块数量-1条边是必须加的。然后看一...

题目： 给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。对于 1100% 的数据中，满足n≤100000,1≤b≤n。 做法： 第一时间想着stl暴力搞搞，但写着写着发现没必要写这么麻烦。后来补了个简单写法。（但是时间居然差不多）b作为中位数，我们不关心其他的数的具体值。所以序列中的数我们这样处理：大于b的设为1，小于b的设为-1，b则设为0，然后做一个前缀和数组prefix[]。由于是排列所以只会出现一个b，设它的位置为pos。将序列的奇数位和偶数位分开考虑。从pos往后扫。当前位置是奇数位，则在前面的偶数位中找...

题目： 给一个nm的01矩阵。问有多少个kk的含1矩阵。（n最大1000） 做法： 二维前缀和。跟板子没啥区别。。利用二维前缀和可以快速得到某矩形区域中数字的和。那么枚举所有k*k矩阵的右下角位置，利用二维前缀和得到矩阵中1的数量，大于零则ans++即可。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl using namespace st...

题目： 你在打比赛，这场比赛总共有12个题。对于第i个题，你的队伍有a[i]的几率解决它。有b[i]的概率从左边那个队那里听会这个题的做法，有c[i]的概率从右边那个队那里听会这个题的做法。请问最终你们队伍解出0-12题的概率分别是多少？ 做法： 每道题做出来的概率可以直接算出来。然后只有12道题。那就二进制枚举暴力做题的所有状态，算概率，累加即可。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ...

题目： 一共有 n个数，第 i 个数是 xixi 可以取 [li , ri] 中任意的一个值。设 ，求 S 种类数。1 ≤ n , li , ri ≤ 100 做法： 建个1e6的bitset。从1到n枚举每个数的取值。用bitset左移k位表示前面能表示的所有数+k。就这样直接暴力就行了。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl ...

题目： 一个n*m的迷宫。问从起点走到终点最短用时。往上下左右走1格花费1s。用一次传送门花费3s。 做法： 简单题。从起点开始bfs搜到达所有点的最短用时就好了。从每个点转移到上下左右位置以及该点可以开启的传送门的位置。题目不难，细节比较多一点。可以看看我的写法，用优先队列优化bfs。 代码： #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(0) #define debug(a) cout << #a ": " << a << endl us...

题目： codeJan 非常喜欢旅行。现在有 n 个城市排在一条线上，并且 codeJan 的位置不和任何一个城市的位置重叠。codeJan 想要游览 m 个城市，同时因为时间是不断变化的，游览一个城市多次也是允许的，但是不能永远待在一个城市，否则那样太无聊了。给出这些城市的位置，codeJan 想要知道游览 m 个城市至少需要走多少米？ 做法： 这题数据太水了。写了发的A了。。不可思议。由于城市可以多次旅行。所以不难想到找2个相邻的城市疯狂摇摆即可。 的思路是，先从起点p出发找一个落脚点x。然后从x出发枚举走到相邻的2座城市摇摆。然而其实落脚点x是不需要枚举的，只需考虑距离起点p最近的2个...