算法很简单, 就是记录各个feature的累积和数组, 数组稍作处理, 只要能够比较 [让能够相减得出答案的两个数组] 的”形状”.
比如
111 111 000 110 221<= 110 111 332 110 010 342 120 001 342 120 100 443<= 110 010 453 120
中间一列的221和443的”形状”一样, 也就是相减能得到答案, 所以稍作处理都减去最右边的数即可, 方便比较.
问题是者离散化以后也有100000的数据怎么记录, 好吧我开始用的二叉树后来发现想错了..
无耻的Google以后发现对数组Hash的方法.. 很汗颜 太洋气了.. 跑2xxMS
代码:
Continue reading
第一道线段树.. 略难。 引用忘了哪看的一句话“10亿的的数据规模是任何数据结构都无能为力的，所以必须离散化”。因为略复杂我用class写的…yzhw牛说“线段树编程复杂度太高，一般用树狀数组或者STL set。不要class，class运行爆慢” 但是哥就是用class和链表过了，怎样！！ 1200ms.. 不过后来看了一下Google到用Pascal的蒟蒻牛的代码，发现树狀数组果然好用！
hw给了我篇论文，我发现现在的程度知道了一个数据结构的意思&&一些优化比如“lazy”，写出来的东西details上面大家都差不多的。比如这道题目的lazy我也是加了个-1作标签说明下面的节点需要递归确认，即这一块不是一大块一样的
优化有二：
1. compress() 每次插入完一个building以后沿着树往下看有没有标记为-1但是左右子树height（toLoad）相等的，如果有合并左右子树。实践证明这个优化对这题的数据用处不大，反而拖到了1800ms…
2. 这个厉害了，没它我算5000的数据都要跑半分钟，而还有两组40000的数据，加了这优化4w的秒出。也是刚刚那篇里提到的“观察发现，线段树的建树、统计操作已难以再优化，但插入操作却任可以优化。由于一开始房子的高度无序，所以每次插入如果全部包含不能直接赋值，还需要向下递归左右子树。其实我们可以先将房子的高度排序，然后再依次插入，这样一旦全部包含就可以直接赋值，程序的效率大大提高。这样这道题就可以AC了。”
代码：
简单DP + BFS
牌子之间两两组合出新牌子， 新产生的牌子只需与原始的号码两两组合即可，即，不用考虑两个新牌子组合的情况，因为两个新牌子组合的结果必然等价与一个新牌子和原始牌子组合的结果， 否则会超时。
很自然的就可以用类似BFS里的队列来做， 我由此引发的思考是， 这种新牌子和原始牌子组合到达新point， 和BFS的思想是十分一致的， 我可以把每一个原始牌子看作一个方向， 牌子号码的每一位是一维空间。 比如 01001 这个原始牌子， 对应了一个五维空间， 这个原始牌子的方向就是 ( 0, 1, 0, 0, 1 ) 。 题目就能抽象为， 给出一个B维的空间和可以走的E个方向， 问你能到达离某个点最近的维度。
Continue reading
状态转移很有新鲜感, 我没想到, 难道是我变弱了?
n>1时, dp[n][e][d]=min{ dp[n-1][e-p][d-p] }
n==1时, dp[1][e][d]=min{ dp[1][e-p^2][d-p] }
速度可以分段, 和路程的关系比较纠结, 列个方程算不出来 = =
代码:
Continue reading
DP就是每次在原序列右边加一个city的时候 (此时n个city) 只要看前一个状态 (n-1个city) 最右边的city的情况
也就是记录n个city时的三个状态 xxxV xxx> xxx<
xxxV 和 xxx< 的数量和就是要求的结果, xxx>是记录一下如果允许向右流水那么方案的数量
状态转移即为右图
然后dp[100]结果超过long long, 于是用BigInteger, 写这个报告的原因也是第一次用Java交OJ..
代码:
1 | import java.math.*; |
2 | import java.util.Scanner; |
3 |
4 | public class Main { |
5 | public static void main(String[] args) { |
6 | BigInteger dp[][]=new BigInteger[101][2]; |
7 | dp[1][0]=BigInteger.ONE; |
8 | dp[1][1]=BigInteger.ZERO; |
9 | for(int i=2;i<=100;i++) { |
10 | dp[i][0]=dp[i-1][0].add(dp[i-1][0]).add(dp[i-1][1]); |
11 | dp[i][1]=dp[i-1][0].add(dp[i-1][1]); |
12 | } |
13 | Scanner sc=new Scanner(System.in); |
14 | while(sc.hasNext()) { |
15 | int a=sc.nextInt(); |
16 | System.out.println(dp[a][0].add(dp[a][1])); |
17 | } |
18 | } |
19 | } |
我表示是跟着黄伟牛混的.. 他写的报告难以称作报告.. 题目一抄写两句话代码一贴万事, 自己琢磨了好久, 记录一下, 我记性不好喜欢写的详细一点以后自己可以查.. (拓展阅读: 刘未鹏牛的<为什么你应该（从现在开始就）写博客> )
快放假了, ACM + GRE 加油, 不拼命的下场只有一个, 平庸.. 哞
第一问 total number of symbols in BC(n,k,m) 比较容易, 简单DP
dp[n][k][m]=∑dp[n-i][k-1][m] , i∈[1,m]
第二问 yzhw口口声声“经典的逐位确定方法”..
也就是说, 我们来看 “1111010”(从0位到6位), 简单的讲从高位(0)到低位(6)每一位如果有1, 那么就看, 如果这一位是0, (继承前面的高位后) 低位能形成多少种组合, 把这个组合数加到rank中.
流程是 1[0xxxxx]能有多少组合 即求0xxxxx符合k-1和m的组合(直接用前面求出的dp数组即可, 虽然前面求的是1xxxxx, 但是和0xxxxx数量是一样的), 然后11[0xxxx]能有多少种, 遇到0跳过, 最后看11110[0x]
但是这样并不完全缜密, 我们考虑”10011000″的情况, 按上面的算法进行到第3位的时候, 100[0xxxx], 这个0xxxx是可能产生00011这种组合的, 而放入原文就变成了10000011, 0的长度就超过了. 所以我们想出来的办法是把 0-1 (不包括1到0) 交界处的那个1单独考虑, 看前面有多少位0然后详细说明. 比如100[0xxxx], xxxx只能是以1开头的, 10[0xxx], xxx只能是1xx或者01x, (11x到哪去了? 11x不是在这里的 [特殊情况] 内考虑的, 好好想一下.. 没法讲的太清楚)
代码如下, 写的时候很有自己的想法, 多推敲推敲最后的产品和yzhw的也八九不离十了.. 这个代码还是很精简很漂亮的
1 | #include <stdio.h> |
2 | #include <string.h> |
3 | #include <algorithm> |
4 |
5 | int main() { |
6 | int dp[34][34][34]; |
7 | memset(dp,0,sizeof(dp)); |
8 | //DP |
9 | for(int m=1;m<=33;m++) { |
10 | for(int i=1;i<=m;i++) |
11 | dp[i][1][m]=1; |
12 | for(int k=1;k<33;k++) |
13 | for(int n=k;n<33;n++) { |
14 | if(!dp[n][k][m]) |
15 | break; |
16 | for(int i=1;i<=m;i++) { |
17 | if(n+i>33) |
18 | break; |
19 | dp[n+i][k+1][m]+=dp[n][k][m]; |
20 | } |
21 | } |
22 | } |
23 |
24 | int n,k,m; |
25 | scanf("%d%d%d",&n,&k,&m); |
26 | printf("%d\n",dp[n][k][m]); |
27 |
28 | int N; |
29 | scanf("%d",&N); |
30 | while(N--) { |
31 | char a[34]; |
32 | scanf("%s",a); |
33 | char color='1'; |
34 | int rank=0; |
35 | int kRemain=k; |
36 | int head=0; |
37 | for(int p=0;a[p]!='\0';p++) { |
38 | if(color==a[p]) |
39 | continue; |
40 | if(color=='1') { |
41 | color='0'; |
42 | kRemain--; |
43 | for(int i=head+1;i<p;i++) |
44 | rank+=dp[n-i][kRemain][m]; |
45 | } |
46 | else { |
47 | color='1'; |
48 | kRemain--; |
49 | for(int i=std::min(n-1,head+m);i>p;i--) |
50 | rank+=dp[n-i][kRemain][m]; |
51 | } |
52 | head=p; |
53 | } |
54 | printf("%d\n",rank); |
55 | } |
56 |
57 | return 0; |
58 | } |
大飞同学问我这一题, 图论的东西我是一点都没看过, 直接看了discuss
做这题用了得有十个小时.. 我可是连二分图都不知道是什么..
然后什么是二分图匹配呢
而
最小覆盖数 == 节点数 – 最大匹配数
为什么呢, 数学归纳一下, 匹配数为0时显然 最小覆盖数 == 节点数, 然后有一个二分图匹配就能把两个覆盖路径合二为一, 很简单. 具体的在ufo008ahw这里有所说明
扩展阅读： Matrix67牛有一篇文章介绍了二分图最大匹配的König定理及其证明
求二分图最大匹配用匈牙利算法或者最大流(这个我还没看- -).
有向图转化成二分图很简单, 把每个节点变成两个节点(在二分图两边)一个负责入一个负责出即可
至此我们已经可以解决有向图的最小路径覆盖问题. 允许路径重叠的情况怎么办呢, 明显是要转化成不允许路径重叠的情况来依葫芦画瓢, 想要在求二分图最大匹配的过程中考虑允许重叠的情况我想过.. 没想出来, 难度吹牛逼一样.
怎样转化: 用Floyd求一下传递闭包即可, 这个我想了好久才明白, 我来说明一下
比如有向图G: 1->2->3 4->2->5
解释是: 对于任何的有重复节点的路径, 比如这里的2, 求了传递闭包以后的图就会包含1->3和4->5这两个路径, 实现”跳过去”的走法
Floyd没什么好说的, 关于匈牙利算法(初次接触)的一些细节:
1. 下面这个代码的我是看的这里, 这个数据结构和递归太牛了..做完我整个人都犀利了. 它是只记y指向x不记x指向y, 每次对x搜索可用的y, 而不是记录它们, 整个操作都简单了好多. 原文的注释写的很好
2. 代码中的visited[] 这个验证我列举了各种情况, 是正确的, 有点难度
3. 算法的原理我很清楚了. 但是代码里x和y双重循环, 为什么x和y各循环一遍就ok了我还是没有理解太透彻, 这也是匈牙利算法的精髓吧
代码点下面:
Continue reading
思路和yzhw牛一样
1. 每一个event它对应的可能的cause是这个event点下面的三角形区域(这个区域是无穷大的)
2. 问 “the latest time at which the earliest cause could have occurred” 就相当于用一条平行于x轴的直线 t=t0 把这些三角形区域拦腰切断(当然, 此线必须在所有event下面), 只准在腰以上的三角形里放cause. 然后用二分求到一个恰好不能再往上移了的直线, 就成了.
3. 可行性判断, 用贪心. 三角形们和直线相交的那个区间就可以代表这个三角形, 因为放在直线以上的cause都可以垂直投影到直线上, 效果更佳.
4. 在这些所有的区间中, 要找出最少的cause个数n, 使得每个区间内都能包含至少一个的cause. 如果这个n<=m, 那么这条直线ok, 否则不ok.
5. 怎么判断呢, 引用yzhw “以区间右端点为第一关键字，左端点为第二关键字进行排序，然后每次贪心的选择当前区间的右端点作为子区间，统计要导出全部区间需要子区间的个数num。” (其实第二关键字是不用排序的, 无所谓).
6. 对应5, 举个例子
1 | ---------(A) |
2 | ------ |
3 | ------- |
4 | -------- |
5 | ------- |
6 | ------------ |
7 | -----(B) |
8 | ..... ...... |
按照右边界升序排序, 123行显然要放一个点在他们区间里, 放哪呢, “不妨”(这个词表达能力太强了)放在最右边, 即点A处. 然后我们下面所有的左边界<=A的都可以ban掉了, 因为右边界是升序排序的. 这个操作后得到的问题是最优子结构的. 然后到了第7行, A不给力了, "不妨"取一个B. 这些操作整合一下就是维护一个变量rightEdge, 一旦rightEdge不给力就取一个当前区间最右边的点, 同时更新rightEdge至这个点. 之前的错误: 对应6的例子, 我以前是按左边界优先于右边界升序排序的, 那样虽然也对但是无法处理一个区间包含另一个区间的情况, 需要filter一下, filter的过程能写成O(n), 我比较愚钝写的n^2一个case要算2分钟 - -.. 总之这个贪心记住了, 求最小覆盖数 代码点下面: Continue reading
记录到当前位置combo数为k的尾巴的最小值, 比如 1 3 2 6, 则 dp[combo]=tail 罗列为 dp[1]=1, dp[2]=2 (1,2的尾巴比1,3等小), dp[3]=6, combo最大为6. 然后再多加一位就看能不能更新前面combo数对应的tail, 让tail更小; 当然还看combo数能不能+1. 比如1 3 2 6再加个5, dp[3]就=5 (1,2,5的tail比1,2,6的tail小), 不加5加7就多一个dp[4]=7. 因为dp[combo]值相对于combo数是递增的, 所以可以二分查找实现nlogn.
这两个是买一送一的题目.. 1887的二分写的有点蛋疼.. 2533要求不能相等, 就加了个标记每次对二分的两个指针p0,p1, 和中点(p0+p1)/2看一下, 重复就continue, 不重复一样做, 省得麻烦.. 想了一下还可以前面严格<, 后面可以>=, 这样更新tail的时候就不会重复产生影响.
代码点下面:
Continue reading
从左到右DP, 存储哪里有奶牛以后排序, 同一个x坐标的上下奶牛合并.. 0没有 1上 2下 3都有
随着奶牛的位置x从左到右DP, 需要记录的状态是dp[i][p][k], p是在x处的奶牛圈起来的方式, 我记的是 0没圈(这就初始状态可能) 1圈上 2圈下 3两个一起圈 4两个分开圈, 记录每个可能的k和对应的面积最小值
状态转移比较麻烦.. 我是又分两个状态之间的圈圈怎样互相结合来枚举, 0不结合 1上边延伸出去 2下边 3两边一起延伸 4两边分开延伸. 应该还有更巧妙的方法.. 不想再碰这题了
172ms 直接大数组20M内存..代码点下面
Continue reading
