- 博客(37)
- 收藏
- 关注
RSS订阅
原创 <-这是目录-> SRM div1 hard solutions(52)
刚从百度空间搬过来。。百度空间没有置顶功能差评啊。。。从599向后，如果有做那场SRM，会写前两题的简单题解。（前提有做出来第三题233333，因为此帖本意是第三题练习记录做过哪些，tc你们懂得。。。）practice room练习的话不准备做前两题。599 598 597 596 595 594 593 592 591 5905
2013-12-19 03:45:38
2298
1
原创 SRM 622
easy：先floyd求出两两直接最短路，然后n^2枚举每条路，n^2判断他是不是某两点最短路可以路过的路径即可。medium：贪心。从某点开始dfs。如果孩子返回的分支长度大于maxdist，那把孩子单独分一块。剩下孩子返回的分支长度排序，最大+次大>maxdist，最大分支单独分一块，这样一直算知道最大+次大hard数位dp。Fibonacc
2014-05-29 11:43:08
1130
转载 C#调用Matlab生成的dll方法的详细说明
需要的工具：VS2005及以上版本，MATLAB2008B及以上版本，另外非常重要的需要安装一个MATLAB Compiler Runtime，这个文件（MCRInstall.exe）在安装完MATLAB之后就会在安装文件夹下存在，需要搜索一下（因为不同版本的MATLAB可能存放位置不同），把它安装一下就OK了。 接下来在MATLAB中写一个m文件，当然是一个函数啦。然后在matlab命
2014-05-13 07:28:01
1171
原创 SRM 619
easy： 如果每堆石头不全为1，那么每次我们总能取一堆石头分给另外两堆，堆数-1，并且新的局面肯定有一堆的个数大于1。于是，如果每堆石头数都为1 -> lose，否则的话判断堆数奇偶即可（堆数==1要特判）medium：树形dp，dp[i][j]，表示以i为根的子树分配完成，并且i节点会j技能的最小花费。转移：枚举i点在自己的department所用的技能(k)，然后
2014-05-06 04:39:28
1225
原创 SRM 617
easy: 注意consecutive这个词，给同一个人要连续的几段啊。。。。尼玛没有看到啊。。。。然后有了这个词，就可以直接暴力标记那些位置要切。
2014-04-24 13:08:56
1066
原创 SRM 613
因为博客被奇怪的封掉了两天，于是。。。现在才写easy：排序，然后枚举分界位置，分界左边向右走，分界右边向左走medium：因为The difference high - low will be less than or equal to 100,000.所以如果选了两个不同的，gcd肯定小于100000枚举1-100000，算出gcd是
2014-03-25 23:54:53
1610
2
原创 SRM 612
这道题是要算一个环形，把L都移动到一起的最小代价。枚举蓝色的分割点，那么它左侧右侧的L都向他靠拢（即箭头所示）可以得到一个最优的分割点（红色）那么蓝色分割点顺时针移动，红色也会顺时针移动（类似旋转卡壳对冲点）于是我们在O(n)的时间即可算出每一个蓝色分割点的最优解。#include #include #include #include
2014-03-19 01:32:23
956
原创 SRM 585
官网的图感觉很好，我就盗过来了。。。。（无视掉最后一张图首先求出来每个点它向前向后最远能连到哪里l[i],r[i]然后枚举a这个点，那么他向前最多能到达C这个点，那么对于他向后到达的b这个点，有很多情况，比如上图是三种情况对于每种情况，我们可以看得出所形成三角形个数是r[b]-b-(C-1-b),当然r[b]就是图中的f(b)因为b是连续的那么对于这个式子，我们可以对r
2014-03-02 20:26:01
922
原创 SRM 577
这题方法很多，我是用的最小割S -> i -> T然后S到i边为100，i到T边为100，割左边意思是这个格子的#属于竖着的，右边表示横着的（为什么选100。。。额，最后还要减去，为了S到i和i到T两条边只被割一条）如果选的竖着的（i到T的边没被割），那么如果这个格子上面一格不是#，那么要额外花费1的，选横着同理。如果i在j上面，那么如果i选横的（割右边
2014-02-19 16:25:45
1153
原创 SRM 578
先枚举割掉一个边，使得树分成两个树然后枚举两个树的根，来比较这两个树的最大同构子树大小。需要加个记忆化：dp[i][ifather][j][jfather]，即以ifather为父亲的i节点为根的子树和jfather为父亲j节点为根的子树的最大同构子树的大小看上去是个4维的，但其实[i][ifather]这两维合法的只有O(n)，即边的个数。同理，这个数组合法的其实只有n^2级
2014-02-19 09:45:34
1007
原创 SRM 586
dp[55][26][26]，三个下标分别表示dp到第i位，用了前k个字母，已经结束了j个字母（后面不会再用）。为什么这样的状态？首先我们前面用什么字母这个无所谓，然后到了这个位置，哪些字母结束也无所谓。。。所以只要记录当前在用的是几个字母：k-j，已经用过，不能再用的是几个字母：j，就够了然后枚举当前这个串用多少字母来操作：use、有多少字母在这个串结束：ed可以算出
2014-02-08 22:36:49
806
原创 SRM 608
看到300,600,900。。。做完300直接奔900了，结果900赛后半小时才搞过。。。。300还resubmit。。。。300： （1）从大到小枚举low，求和，当大于等于X的时候，更新答案 i （2）从小到大枚举high，求和，当小于等于C-X的时候更新答案 n-i结果初始值设成10000，枚举的时候又没枚举好，导致选n个的时候更新不到答案。。然后resubmit一发
2014-02-08 02:16:29
771
原创 SRM 589
分M大于17的情况和M小于17两种M大于17： 成段变化的一共只有N/MM小于等于17：dp[i][1#include #include #include #include #include #include #include #include #include #include #include #include #include #
2014-02-04 05:27:42
638
原创 SRM 574
先分联通块，左边或者右边，可以接起来如下图：XX...X..XX......XX...X..第5行可以接起来第3行，成为一个，这个可以用贪心搞定.....XXXXX.....XX....XXXX但是上面这种第二行就不知道哪边是头哪边是尾，所以用dp两种决策dp[i][j][k]，dp到第i行，左边可以有j个接上面的，右边有k个几个trick：....
2014-02-03 22:42:32
1010
原创 SRM 557
想了好久终于想清楚其中的正确性了思路是把这n个数看成n个k维向量，然后这是个向量基，答案也是个向量基，这两个基等价，就是可以互相表示，就满足。那么1、把向量基化成极小的向量，贪心方法，先把每个向量的最高位的位数变成不同的（类似解行列式），然后通过最高位比较低的向量，把最高位高的向量弄成极小。2、把第一个向量弄成极大的3、剩下所有向量都与第一个向量
2014-01-24 04:22:35
1126
原创 SRM 565
好多天没有进度了。。就因为这个。。这个丧心病狂的题。。丧心病狂的lyrically分四种情况1、三个相邻2、两个相邻，和第三个不相邻3、三个都不相邻并且成Y型4、三个都不相邻并且成一条直线然后每种情况是形成一个大的结构，讨论讨论，都能找到其他点在这个大的结构上或者从大的结构某个点伸出去，而且位置唯一确定。。。。剩下的就是码代码啊。。。。#include #includ
2014-01-24 01:11:24
787
原创 SRM 558
对网络流的建图又有了更深一步理解http://pan.baidu.com/share/link?shareid=1648064038&uk=1090822741看了这个以后。大概思路就是吧多元关系转化成两元关系，每个点多加两个收益点（一个表示放本位置收益，一个表示放周围收益），两个收益点分别连源点汇点（为了控制两个收益互斥）然后就是二元关系，剩下建图就很常规了，也用不到
2014-01-20 03:42:19
978
原创 SRM 399
水题，枚举+最大流，数据小连二分都不用果然前面场次水题多，还是老老实实做最近的那些吧- -#include #include #include #include #include #include #include #include #include #include #include #include #include #include #in
2014-01-20 01:22:17
657
原创 SRM 562
这题分两种情况考虑。1、2*k这种情况需要中间一段（n-2*k+2长度）是一条直线，直线两端分别接k-1个点，那么这k-1个点形成一个星型，只要保证叶子节点比内部节点编号小就满足情况（直线编号小的那端）。dp搞定。2、2*k>=n这个中间一坨需要联通，然后看成一个球，向外也是星形射出，外面星形的部分和上面一样，球的部分可以全排列。我代码具体做法：枚举一个点（假设是这个球
2014-01-19 23:12:13
819
原创 SRM 560
好神的思路- - 居然用图论转姿势化式子因为是很多两个变量的积加起来，那么转化成一张图，就是右边的两个点的值乘积，求个和。设想最后得到一个答案，如果某两个点不相邻，并且这两个点没有取到最值，点A周围点的权值和是suma，点B周围点的权值和是sumb。那么如果suma>sumb，那么可以增加A的值减少B的值使得答案更大，然后A，B中肯定一个会达到最值。所以，
2014-01-19 16:08:54
1045
原创 SRM 561
这题分两部分第一部分是k个点组成的树边的总长第二部分是每两*点的路径，做为了几个k集合的直径第一部分：就是求每个树边被几个集合用到，其实就是这个边去掉分成的两部分，*的个数分别是a，b，那么枚举 i = (1~ min(a,k)) 方案数是C(a,i)*C(b,k-i)第二部分：(感谢叉姐教我树直径性质)枚举两点，然后找到这条路径的中心。所有点到这个中心的距离，小于等于
2014-01-17 22:00:22
816
原创 SRM 573
见过几次坐标旋转的，还是没掌握到精髓啊，完全没往这边想。这题的转变很巧妙。旋转了45度，每步就变成(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)四种选择。这样每一步x和y都会变化，就可以独立分开考虑了。#include #include #include #include #include #include #include
2014-01-16 00:23:30
912
2
原创 SRM 554
矩阵连乘本以为很开心的一道题，矩阵构造太难写了。。 0. 1. 2. 2. 3. 3. 4. 4. 4. 4. 5. 6. ab ab ab aa ab ab ab ab aa ac aa aa cd ba ab bb ca bc ac cb cb bb aa ab这是我人肉的7中情况。。。然后。。。额。。。写了一下午。。。
2014-01-14 21:31:52
703
原创 SRM 552
哭瞎了。。想了这么几天原来是道暴搜题。。。之前思路就没错，广搜的时候不知道为什么爆掉了。。估计是内存没开下就以为很多。。。就是如果a[i]*a[i]>left的时候，二分最大界j使得a[j]#include #include #include #include #include #include #include #include #include #include #
2014-01-14 02:47:21
802
原创 SRM 551
这道题就是算出k个sweet的选择数，k个sweet生成树的个数，乘起来就是答案。选择数是个背包题，容量比较大，分成两段暴力。生成树个数是无向图生成树个数，矩阵来求的（不会的自行百度）然后会多算了0~k-1个sweet的情况，减去重复即可。#include #include #include #include #include #include #include #inc
2014-01-10 21:17:02
742
原创 SRM 384
暴力SG值#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include us
2014-01-08 01:01:29
667
原创 SRM 550
矩阵乘法状态表示为[i][j][k]表示这一个串中已经匹配好的有i个，差两步的有j个，差一步的有k个，显然i+j+k=len。len最多11，所以状态数最多不到80构造矩阵就是(i,j,k)->(i-1,j+1,k) ,有i个选择，要乘以i，另外两个转移也是一样的然后就是一共能走几步的问题，统计一下最少步数复原要走几步，花费cost。能走的步数就是 复原的步数+3*((最
2014-01-07 20:28:46
1014
原创 SRM 603
250取叶子节点最大值500可以看出A=s1+s2,B=s2+s1，满足这种的都能找到一个合适的C（s1,s2长度可以为0）所以对于任何一个A，循环移位得到的B都满足，但是循环移位有可能是重复，和循环节有关系，找出n的因子，每个因子的算出来，重复的减去即可。1000如果两个数组都没有重复的元素的话，直接FFT即可FFT是C[i+j] = sum{ A[i
2014-01-07 17:08:24
839
原创 SRM 601
唔。。。做悲剧了- - 250 一开始以为苹果的包和桔子的包不是同一个包。。。500 根本没思路。。950 看的晚了（早看了也写不完。。）250pt枚举从每包里那几个，然后找到能拿的最小的苹果数和最大的苹果树（中间那些情况都可以达到） ans += maxapple-minapple+1;500pt枚举哪一位开始不同（比如 r），然后dpdp[2005][3
2013-12-23 04:18:48
1641
3
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人