直接模拟，每找到一个相交就拿构成环的长度去更新答案
P[j]..........
| |
| |
P[i]---O-----P[i-1]
|
|
P[j-1]
302.无聊模拟题
304.容量为P(P<=106)的背包，N个物品，每个物品属于一个类别，如果在第i类里取了至少一个物品，则必须花费额外Bi的容量。问取到的物品数最多是多少。
DP:用f(i,j)表示只取前i类物品取了j个的情况 O(N^2)
f(i-1,j)-->f(i,j+k)
305.N(N<=100)个等差数列Ai,Bi (X=Ai+Bi*k k为自然数) 用1~M(M<=10^9)中的N个数给等差数列标号，使得拥有在自己序列中的标号的等差数列总数最大 虽然M很大，但是一个等差数列最多用到前N个数，待选标号的集合不超过N^2, 然后最大匹配 ~_~ 309.给N个整点(N<=20000)求最小的长度D使得三个边长为D的正方形能覆盖点集（允许Overlap). 首先要二分答案，然后 我一开始想肯定要覆盖最左/右/上/下的一条边，但是确定了一个左边。。另一个坐标无法确定?后来经过提示发现：放正方形的时候，最小覆盖当前点集的矩形的四个角其中一个一定要被正方形盖到。但是我想了好久也不知道究竟应该放哪个角。。后来发现枚举每次应该盖哪个角就行了 =.= 310.长度为N的01串，每个长度为M的子串都有至少K个1，问有多少种方案。
简单的状态压缩Dp...
311.有两种操作：1.运来价格为P(P<=10^6..整数!)的Ice-Cream K个(K<=10^6) 2.一个人用T(T<=10^12)的钱买最便宜的n个Ice-Cream,如果当前有>=n个Ice-Creams而且最便宜的n个价格不超过T。。就输出"HAPPY"否则输出"UNHAPPY"
关于价格的线段树，flag记当前区间是否被整体删除，sum cost分别表示在当前价格区间[a,b]内共有的冰激凌数量和总价值
316.无聊模拟题
317.一条数轴上的路，信使要从0移动到T，但是他必须骑马移动。路上有N(N<=5000)个马厩，每个马厩有若干匹马，每匹马有两个属性：速度和能跑的距离，问到达终点所用的最短时间。马的总数<=10^5 f[i]=f[j]+cost[j][i] 顺推，把从每个点出发的马按速度排序，每次递推找出当前速度最快的马，如果跑当前这个点路程不够就抛弃（后面的点更不行了@_@） 用堆维护即可
如果两个资源的需求情况(需要的人的集合）是一样的，这两个资源就是等价的，显然等价具有传递性。。DisjointSet..方法很多..
320. n*m的方格上写了0~9的数字，同数字的相邻格看作属于同一个势力。如果一个势力的格子数达到或超过k，则称其为一个大势力。如果一个格子属于大势力，或被某个大势力完全包围（切断了它到整个地图边缘的所有途径），则称其为危险的。问有多少危险的格子。
这题在集训队论文里有一个神奇的方法：将小势力块每个方格拆开看成大势力，从边界沿着不同大势力之间的隔离墙往里面灌水，如果每个格子四个角都能被灌到，那么它是能被访问到的。
注意这里的隔离墙不仅指边还指这种情况
AC
BA 两个A有顶点相连，这里我们把这个顶点看作隔离墙的门=.=...水是不能往门里流的，B或C边的水只能拐弯而不能穿过门
用朴素的方法+一定的优化 或者构图求割点也可以
321.简单的树贪心
322.给出两个生成树，每次可以在第一棵生成树上减去一条边同时加上一条边，要最少的操作次数变为第二棵生成树，在每次操作结束后都要求图依然是生成树。
每次找一条在第二棵不在第一棵的边，连上它，形成的环里面肯定有二不包含的边(否则还是生成树?)，删去
323.有一张无向图，每条边有一个权值和一个颜色。修改某条边的颜色的费用是这条边的权值。求最小的花费使得产生某种颜色的生成树
就是Kruskal..先把所有边排序，然后枚举生成树需要的颜色，判断一下就行了，而且剪枝很方便
324.无聊模拟题 减号随便分配
325.to do...
326.给定了一些队已经比赛的成绩，以及他们之间剩余的比赛场次，问第一个队友没有取胜希望（胜利数达到所有队中最大）
先让第一个队把剩下的比赛赢掉，其他队把跟外部队的比赛全部输掉，然后内部分配比赛的“胜利果实”。显然每个队不能超过S1-Si..网络流分配一下这些比赛结果
327.给一些串，找到一个最短的包含他们全部的回文串。 不会做 :( 貌似是Dp :(
328.找规律的SG函数题
329.把一个边长是N(N<=5)的三角形划分成X2个小三角形,用4种图案给它染色，要求每条边两侧的颜色相同，给了4种图案的个数，问有多少种方案。
记忆化搜索+状态压缩..我的常数控制得不好..只能去const :(
330.给两个数A和B，问每次给A加上A的一个大于1小于A的约数，能否得到B。并输出一个方案。
显然观察偶数的二进制数********0 每次加上 10...0(一共是原数右端连续的0的个数，前提是不要超界) 这样总可以得到比它大的任何偶数
把A B分别搞成两个偶数A' B' A<=A' B<=B' A'<=B',用上面的方法就行了 334.把一个9个格子组成的连通图形切成尽量少的几份，然后拼成一个3*3的正方形。
加深搜索，每层搜索一种“零件”的形状，同时枚举在原图形的位置(细节有小技巧，略）
336.不会做 :(
337.简单的枚举 O(N^2)
340.无聊模拟题 again..
342.高精度对小数取余 + 简单的Dp
F[i]表示当前位付钱(显然跟前面一位就没关系了。)
G[i]表示当前位找钱(前一位得多付一个来填这一位的洞)
344.BFS
346.不无聊的模拟题 @_@
347.排列N个串使得合成的串字典序最小
排序: 两个串Sa Sb,若Sa+Sb
0 评论:
发表评论