2017年10月22号第三届CCPC哈尔滨站，第二次代表学校出去比赛并且第二次打铁…… 即便是现在了，我依然是心如刀割…… 许颂嘉卡题卡了4个半小时，说句心里话，我无法完全掐灭她的失常发挥间接导致比赛打崩的想法。 但理性的我还是很清楚，这也并不能完全怪她 因为我对数学不是很敏感，没想到素因子，如果我能对了解一点数学就好了，尽管只是一点…… 因为我们的团队配合有问题，我一直在怼我的题，要是我能抽出点时间一直帮许颂嘉解决这个问题就好了…… 因为比赛前我并没有把许颂嘉的一些问题指出来，她写代码会写的很长很乱我在很早之前就知道了，但是当初都A了再加上她自己手速挺快我也没有说什么，现场赛让我帮她看代码就真的很致命…… 因为没有正确发挥陈雨情的作用，老实说，陈雨情虽然菜，特么的经常读错题让我白写，但是在考虑问题方面往往比我们两个都全面。这场也是的……打到一半才让她看…… 因为我太菜了，要是我能先比她出一个题，不仅可以鼓舞士气，说不定手速快点还能拿银牌……但是在后期我急了，应该说是很焦躁，导致最后一题很明显的随机化解法我都没有想到，只是给了它三分钟时间，就说了一句，“好难啊”就…
老实说，这题我在现场赛大概写不出来。 感觉还是比较需要脑洞。 题意： 一排不同重量的蚂蚁按重量排成一排玩饥饿游戏，每只蚂蚁最开始选择一个方向，左或者右，大蚂蚁吃小蚂蚁，并且使自己增加小蚂蚁的重量，如果重量相同，左吃右。 问 n 只蚂蚁，第 k 只活到最后的方案数。 思路： 直接切入正解。 首先第k只蚂蚁必须选择左边，不然只能被吃。( $n \neq k $ ) 如果想要第 k 只蚂蚁获胜，必须满足以下两个条件 1. $ weight[ max(p_1), k ] > weight[ 0, max(p_1) ) $ 2. $ weight[ 1, min(p_2) ] <= weight( min(p_2), n…
emmmmmmm不错的的最小割吧 唯一一个不是很好的点就是实在是太容易想到是最小割了，但是没想到具体的建图方法。 题意： 有n个点，m条边，要你分成两个集合，使得两个集合的导出子图各自权值和的和最大。 两个导出子图中，可选择其中一个，若导出子图中存在有两个点 (i,j) 相连，则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反，只有存在两个点没有边相连，才会增加权值。 思路： 题目的主要目的就是将点集分成两部分，这很容易想到二分图染色，但这是不现实的，因为这是一个最值问题，不存在必然关系。 而跟二分图相关的只有网络流了，将图分为两半是割的概念，当然只存在最小割，正面去想的话，就是总权值和-最小割。 然后……思路就断了，找不到有效的建图方法。 可以先这么想，我们假定与源点相连的点集为相连增加权值的集合，并称之为，与汇点相连的点集则相反，称之为汇点集。 那么我们先将每个点都与源点相连，其容量为将该点加入源点集所能增加的权值。 再将这个点与汇点相连，其容量为将该点加入汇点集所能增加的权值。 此时直接跑最小割是不对的，因为这些点并不是独立的。…
对Tarjan的算法理解有点要求的题，之前看了一下思路，敲了一下结果没过，照着博客改动了一下但并没有搞懂，今天补上。 题意： 给你一个有向图，若干询问，询问为从 s 到 t 的最小字典序路径中，第 k 个点是哪个点。 思路： 首先询问很多，有$4\times10^5$个询问，直接一个一个找肯定是不行的。 但是值得注意的是，点数比较少，只有$3000$个，假如我们固定起点，遍历全图来获得路径，在遍历的同时，对每一个点来记录答案。理想复杂度为$O(N^2)$，时间上满足条件。 一个问题是如何保证字典序最小，emmmm 用vector记录整张图，对于每个点的边进行排序，因为每个点访问一次，解决之。 这题还有一个合理的大坑，如果在遍历的时候，在之前已经出现了一个环，那么之后的所有点就都不会被访问。 当然你不能在找到一个环后，后面的点就不再遍历，…
今天因为薛昊买VPS了，赚点访问量简单写一下吧。 OwnCloud是开源私有云软件，功能强大，作为图床只是其一个小用法。 我的ACM模板和一些很重要的文件都在上面，在本地与云服务器中都有保存。 DigtalOcean的官方论坛上的关于安装OwnCloud的文章不错，是安装教程的不二选择。传送门 以下是标题相关正文，假设你已经搭建完成 1. 新建一个文件夹，并对其分享。这个文件夹作为我们的图床目录。 2. 在浏览器中打开分享目录。右击图片，点击复制下载链接。 2017-10-28 17:44:53 星期六 更新，mmp，owncloud改了？？？ 换一个方法，得到分享目录地址后,在后面加上download?path=%2F&files=image.png 即可。 files=后面的是图片文件名 该链接就是可以用markdown，html或者其他显示出来的链接。 就这么简单。 但是在不安装插件的情况下也只有这么一种操作选择。其他都无效。 当然这个方法是有缺点的： 显然其他人如果知道了你的服务器ip，那么你图床上的所有图片都会以一个目录的形式所…
今天老友跟女神走一路，赶着上课的时候老友喊了我一声。 我回头看了一眼，因为要迟到了就没回应。 老友后来跟我说，女神问她 “你刚刚喊的人是谁啊” 完。…
/doge薛昊老是偷我题做，最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有，这个区间DP的套路我还真没碰到过。 这是一个大区间推小区间的套路。 题意： 小明要在某层楼的各个老师那里交一大堆作业，但是小明来早了，老师还没上班，他站在这层楼的最左边，告诉你每个老师的上班时间，最后要在某个给定位置下楼，问最少时间。 思路： shit，完全是看博客，看代码敲的。 一个比较困难的点在于给定离开地点，算了，不装了，就算取消这个条件我也写不来…… 明确可以用dp求解，首先按照位置优先开门顺序次优的顺序排序，设三维数组 $dp[l][r][k]$。 当 $k=0$ 时，表示只有 $(l,r] $ 区间内的作业没有交。 而 $k=1$ 时，表示只有 $[l,r) $ 区间内的作业没有交。 而我们的其实状态$dp[1][n][0/1]…
自从把Linux强制全局代理很长时间了，已经不知道怎么改回去了…… 结果今天ShadowSocks-Qt5 崩溃就GG了，除了让终端unset意外，其他就没有上网办法了。 因为本人使用的 Arch ，各种软件包更新的快，要是等到作者来解决这个问题可能要等很长时间…… 终端错误提醒 ss-qt5: error while loading shared libraries: libbotan-2.so.2: cannot open shared object file: No such file or directory 找了一下的确没有。 sudo find / -name "*libbotan*" [sudo] password for key: find: ‘/run/user/1000/gvfs’: Permission denied /usr/lib/libbotan-2.so…