- 博客(123)
- 收藏
- 关注
RSS订阅原创 NOIP 2017 提高组 Day2 T1 奶酪 cheese.cpp
题目较为简单，将每个空洞看为一个点，N^2建图，BFS判断连通性即可。#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;const char Yes[5] = "Yes", No[5] = "No";int T, s, t,
2017-11-19 19:43:37
1079
原创 ～手机APP：Termux --模拟Linux终端
前几天在手机应用商店里发现的这个app，觉得很有意思就下载下来了。还记得很久很久之前找半天找不到什么合适我这种爱没事乱搞的软件能实现在手机上编程。然而这个软件是模拟Linux的shell。既然都模拟出来shell了，岂不是能做很多事情？其实类似的软件有很多，而且体积都很小，但是这一款稳定性很好，玩了这么几天了还没有崩过。其他有的刚打开就崩掉。与真实Linux终端极其相似，可以玩大部分命令，可以用ap
2016-05-15 13:47:26
20930
原创 Linux访问Windows FTP服务器中文乱码
在Linux下访问windows ftp服务器时可能会出现中文乱码的问题，这是由于中文编码不同的问题。Windows中文编码使用的是gbk，而linxu大多数版本默认的编码是utf8。一种解决方案是在终端使用lftp登录，手动设置中文编码方式，在终端中输入lftp <username>:<password>@<address>登录之后，输入set ftp:charset gbkset file:c
2016-04-17 12:22:08
7214
原创 BZOJ 4206 转换之后求LIS
CH链接：https://www.contesthunter.org/contest/CMC-Day4/B 在CH上也是有题解。对于每个点(xi,yi)，求出它与圆的两个切点，每个切点可以仅仅用一个数字表示，表示度数。所以每个点都转换成了两个度数(li,ri)。对于两个点i，j，它们的连线与圆没有交点当且仅当li < lj < ri < rj或lj < li < rj < ri。所以一个合法的答案
2016-04-17 09:06:42
661
1
原创 POJ 1149 PIGS 学会构图，最大流
这道题知道怎么构图之后就不难了，然而我一开始并没有想出来怎么构图，之后看了题解。大概理解了图是怎么建的，按照题解的套路写完A掉后也没有仔细去思考到底是怎样如此简洁地构图的。但是学会了一种思路，这个也是从那篇题解中看到的： 在面对网络流问题时，如果一时想不出很好的构图方法，不如先构造一个最直观，或者说最“硬来”的模型，然后再用合并节点和边的方法来简直化这个模型。经过简化以后，好的构图思路自然就会涌
2016-04-15 17:32:06
415
原创 POJ 2112 2391 floyd 二分 最大流
这两道题很像，基本可以粘代码，解法相同，唯一不同之处在于建图。2112题意：给出K+C个点，前K个点代表牛棚，之后的C个点代表牛，所有的牛都要转移到牛棚中去，然而每个牛棚最多能容纳M头牛，问最短多长时间可以将所有牛转移到牛棚中去（每条边不限制同一时间通过数量，牛可以同时移动）。输入数据第一行三个整数K C M，接下来一个邻接矩阵D，D[i][j]表示点i到点j的距离，D[i][i] = 0，当i!=
2016-04-12 10:13:20
338
原创 BZOJ 1492 货币兑换 cash 斜率优化DP
关于DP优化，可参考：《1D1D动态规划优化初步》这道动规题用斜率优化可以过，然而被cdq拿出来介绍了自己的分治算法，大家基本都用cdq分治写的这道题。确实cdq分治比splay维护凸壳的写法要好写，而且貌似更快一些。这道题的方程很好列，设f[i]表示第i天可以拥有的最多的资金，无论实际当天拥有的是金券还是金钱，肯定是总价值越高越好，又很容易想到，买入或卖出肯定是100%比率。所以方程列出来：f[i
2016-04-07 21:17:28
427
原创 POJ 3093 背包 （技巧优化）
参考：09年集训队论文《浅谈几类背包问题》 徐持衡题意：多组输入，每组给定物品数(<=30)和背包容量(<=1000)以及接下来每个物品的体积，问有多少种方案，使得装入一些物品后，无法装入剩下的任意一个物品。可以转化成0-1背包来做，首先按体积从小到大排序，枚举“剩下的物品”中体积最小的。剩下的物品中体积最小的为i时，前i-1个物品是必然被装入背包的，然后对第i+1到第n个物品做0-1背包问题，转移
2016-04-05 11:03:28
717
原创 POJ 1742 Coins 多重背包（单调队列优化）
题意：给定n，m，表示有n种硬币，接下来给定两个数组A[i]，C[i]分别表示第i种硬币的面值以及个数，问用这些硬币可以凑出多少[1,m]范围内的数额。输入以n，m都为0结束。首先可以转换为背包模型，f[i][j]表示前i种硬币是否可以凑出数额j，利用滚动数组可以优化第一维。对于一个多重背包的模型，可以很容易地写出来这道题的转移方程：f[j] = max(f[j-k*A[i]])，0<=k<=C[i
2016-04-03 17:29:24
446
原创 POJ 1509 后缀自动机+KMP
题意：给定n个字符串，求每个字符串最小表示法是从被给定的串的第几位开始求最小表示法可以直接在后缀自动机中跑n个字符，后缀自动机是根据原串复制成2倍长度建立的，所以在自动机中按照最小的边跑n个字符得到的就是被给定的字符串的最小表示法，然后再用KMP与2n长度的字符串匹配即可。【蒟蒻的无脑解法】#include <cstdio>#include <algorithm>#include <cstrin
2016-03-24 08:44:08
352
原创 BZOJ 1453 [WC] 双面棋盘 并查集+线段树暴搞
这道题大部分这么做的题解写的都很简洁，不过看代码就能看懂大概搞法。 线段树的一个节点维护的信息有：节点对应区间[l,r]为原图第l行到第r行这(r-l+1)×n的棋盘中的黑色连通块数和白色连通块数。然后我们保存第l行和第r行的连通的情况，这样就可以方便地合并两个相邻区间了。注意到同一行中不相邻的两个块可能是属于一个连通块的，所以用并查集来储存连通的信息比较合适。每次合并都是O(n)。合并区间时，连
2016-02-25 16:37:05
929
原创 无聊乱搞：用shell脚本实现windows下cena的评测功能
作为一个Linux渣渣，写出来这一个小脚本真是各种艰难，自己乱搞乱实验加网上各种查了解到了一些小语法以及一些命令的用法。最终还是实现了“截肢”版的cena。收获还是颇多的，主要是那一堆shell脚本的小语法细节。这个脚本的用法很简单，只要在当前文件夹里创建好data文件夹和src文件夹，直接运行即可，在result文件里查看结果。不过实现的仅仅是“截肢”版，而且会有评测误差，今后有时间会不断改进，并
2016-01-20 17:36:54
770
原创 BZOJ 1086 裸-树分块
分块好啊，进可巧计AC，退可暴力60。然而遇到树上的分块就不像一个序列那么简单了。这道题就是一道裸的树分块，分好块之后只需要输出块的个数，每个节点属于哪个块，以及一个奇奇怪怪的“省会”节点编号就好了。树分块也是按照大小来，我们设置一个值b。直接对树进行DFS遍历，每遍历到一个节点把它压入栈中，当我们发现栈中的节点超过b的时候，弹栈，弹出的元素即为一块。但是稍微想一下，直接这样做会出现“零零散散”的情
2016-01-17 22:55:14
1436
原创 BZOJ 1001 狼抓兔子 平面图上的最大流--跑最短路
首先应该能看出来这道题求的是最小割(最大流)。然后再看出来这道题的图是个平面图，然后就可以关于这个平面图建出它的对偶图，在这个对偶图上跑最短路就是答案了。直接跑网络流的Dinic应该是T的。然而，这需要知道什么是平面图，以及如何构建这个对偶图。边的交点都是顶点的图就是平面图。注意完全图K4也是平面图，详细可见百度百科：http://baike.baidu.com/view/143351.htm 或维
2016-01-12 16:08:30
587
原创 BZOJ 3261 最大异或和 可持久化Trie
前两天被带修改的可持久化线段树给搞毛了，弃疗了QaQ，数据结构搞累了准备换一换其它的。然而，还是遇到了数据结构。0.0 可持久化Trie——如果理解了主席树这个也就很好理解了，建树的方式是相同的，对于这道题来说也是logn的空间来新建一棵树。然而，为了减少不必要的空间浪费，选择了指针——很少用真正的指针，导致无限的调试。 感觉自己的代码还是臃肿，比起piupiuqqq神犇的代码。。简直没得比。对
2016-01-11 20:16:06
334
原创 BZOJ 1036 [ZJOI2008]树的统计Count 树链剖分练手题
写过的第一道树剖题。之前看过几个课件，也没写过，这次直接YY出来的竟然能A。维护区间信息时没用线段树，用的Splay，只为练练手，然而就导致代码无下限的长，可是心酸。还好这次写了之后1A(233，明明输出优化没加负号Wa一次的)，不然还真不敢调。#include <cstdio>#include <cstring>#include <algorithm>#include <vector>us
2016-01-07 15:16:43
354
原创 NOI 2005 BZOJ 1500 维护数列
这道算是一道合格的Splay基础题。距离上一次那道简单的Splay时间比较长，因为经历了元旦晚会和之后的一个小假期没写题。 这道题涵盖的Splay的操作还是比较多的，适合练手。写的时候思路一定要清晰，否则不好调。 推荐自顶向下写。我就是先写的最大的框架，判断输入，调用哪个函数。写出大框架之后就轮到挨个写函数了，这些函数也是有上下关系的，最靠上的当然就是最直接的对应每个操作的函数。我使用分裂和合并
2016-01-04 22:58:44
369
原创 BZOJ 1251 绳命中第一道SPLAY
不要问蒟蒻标题是怎么回事。蒟蒻就是蒟蒻，T^T到现在才会写SPLAY。感觉SPLAY也没啥好讲的，况且这道题还是很基础的SPLAY。第一次写，不过思路还是比较明朗。只不过最开始写这道题的时候傻乎乎的只给“加”的操作打标记，没给“翻转”打标记，T了一次。再加上自己这凌乱的代码、数不清的细节错误，调了老长时间。有这么一些值得我注意的细节：find()过程中要pushdownrotate()前要分别p
2015-12-25 16:23:40
290
原创 块状链表（附NOI 2003 Editor，POJ 2131 Key Insertion）
这两天学习了一下块状链表，也谈不上学习，可以说是练习。因为块状链表这种东西，猛一听起来好像很高端，但是拆开来说就是：分块+链表。根本上就是暴力，就是分块。只不过“分”的对象从数组变成了链表而已。知道了是什么，顺水推舟的就会写了——如果写过分块。块状链表==分块+链表==数组+链表。链表上的每一个节点都可以说是“一块”，这一个节点包含一个小数组，这个小数组内的一些信息可以预处理好，需要整块操作就很方便
2015-12-22 19:32:07
1273
原创 在Linux中卸载Refind
一直在用多系统，Linux系统安装后一般都会默认安装grub引导器。感觉grub界面比较low，就下载了refind。去sf上下载deb包，直接在软件中心就可以安装。 一开始用起来好好的，但是当我又装了一个系统之后，refind没有识别出来，也就是还是原来那两个系统，选择ubuntu之后，又进入到了原来的grub，还得自己选择。于是乎，想要卸载它。去网上没搜到教程（估计是自己搜索姿势比较low），
2015-12-11 16:21:57
8104
1
原创 Ubnutu使用su登陆认证失败的解决方法
转载自：http://studiogang.blog.51cto.com/505887/385223Ubuntu应该是出于安全性的考虑，刚刚安装之后，root用户默认是被锁定了的，不允许登录，不允许 su 到 root 。重新设置一下密码就可以了。
2015-12-05 21:38:40
707
原创 Linux下使用QQ：Chrome扩展程序ARC Welder
为什么我要装Android模拟器呢，因为想要在Linux下上QQ呀。 然而，花2GB内存代价开一个QQ感觉好不值的样子，于是发现了另一种可以上QQ的方法。 我是看了这个教程的：http://www.iplaysoft.com/arc-welder.html不过，在Chrome应用商店搜索到ARC Welder这个插件并不容易。 给出链接： https://chrome.google.com/
2015-11-19 11:27:44
3207
原创 Linux (Ubuntu) 下的Android模拟器：Genymotion
据说这是一款十分好用的Android模拟器，之前没玩过Android模拟器，这就是自己第一次使用。Downloads：https://www.genymotion.com/ 麻烦的是需要现注册才能下载。有收费版，也有免费版，点击buy genymotion，页面往下拉，就能发现这一行极小的字。【表示自己找了老半天】 我的是64位系统，所以最后下载下来的是genymotion-2.5.2_x64.
2015-11-19 09:54:53
66804
4
原创 BZOJ 1044 HAOI 2008 木棍分割 --二分 DP
这道题第一问很容易，二分答案，然后贪心判断即可。得出第一问答案maxl之后，解第二问可以DP。一个很容易想的状态就是f[i][j]表示前i根木棍，分成j段的方案数。转移是f[i][j] = sum {f[k][j-1]}，i’ <= k < i，i’满足它是最小的满足sum{a[i’] ~ a[i] <= maxl}的数。状态数O(nm)已经快要爆了，所以转移上必须O(1)做到。很容易知道，i’关于
2015-11-16 12:01:04
291
原创 BZOJ 1046 HAOI 2007 上升序列 -- DP 贪心
如果能想到贪心那么这道题就不难了。假设我们求出f[i]表示以i为第一个数的最长上升子序列长度，那么为了使字典序最小，我们可以采用这样的贪心策略：当前询问的长度为Q，我们枚举第一个i，使得f[i] >= Q && a[i] > last，找到i之后：Q–, last = a[i]，然后继续枚举。这个策略的正确性是很显然的。读入一个Q之后先判断是否有解，因为如果存在一个长度为L的上升序列，那么必定存在
2015-11-15 21:15:26
436
原创 Linux Mint + win10 双系统初体验
今天给自己的本装上了Linux Mint, 现在是和win10并存的状态. 在一位神犇的帮助下, 成功地搞好了.本来还想继续把ss搞好, 奈何自己对于Linux的操作一无所知, 最后只弄好了一, 还不能正常使用.我是刚刚才接触的Linux, 不过刚刚接触就感觉这个系统很好. 之前看到过NOI Linux, Ubuntu kylin, 自己着实感觉界面不大好, 所以也就没去更多接触。Linux Mi
2015-11-14 19:40:06
11637
原创 Treap 学习总结
Treap是一种BST，可以山寨set，另外还可以实现set实现不了的“名次树”。它可以说是一个满足堆性质的BST。“堆性质”是为了维护它的平衡，对于每个节点，都给它随机一个值，作为堆性质的关键字。所以，Treap的使用要看一点点人品，随机出的优先值在大多数情况下还是可以使BST趋于平衡的，各个操作的期望复杂度是O(logn)。写一个能实现名次树的Treap需要多开一个size数组，支持以下操作：
2015-11-12 10:02:27
259
原创 NOIP 2010 引水入城 （数据结构使人懒惰~.~）
发现这句话说的很对：数据结构使人懒惰。然而貌似大概可能，之后的考试中，不会再有裸数据结构题了TvT。这道题我的做法是：首先BFS/DFS【bitset黑科技大法好】求出对于每个临水的城市可以输水到那些沙漠城市。如果所有沙漠城市都可以得到水，那么问题就变成了选择最少的临水城市，使得沙漠城市都有水。这不就是赤裸裸的可重复覆盖问题嘛。于是写了DLX。#include <cstdio>#include <
2015-11-05 08:20:26
263
原创 N皇后问题 求解方案数
这是个很经典的练习回溯法的问题。目前还没有已知数学公式可以直接计算，所以只能交给CPU暴力搜索了。方案一： 直接搜索、回溯。对于每一行枚举皇后的位置，再开一个bool型数组记录哪一列、哪一条主对角线、哪一条副对角线已经放过皇后。速度上N <= 13还是能在1s之内跑出来的。 // 代码中id(x, y, 1)返回的是(x,y)所在行已经放过皇后的标号，实际没有任何卵用~.~#include <cs
2015-11-04 07:33:05
727
原创 模拟赛记录（3）：11.02 论想题思路
第 1 题 我们爱几何 (geometry) 【题目描述】 AngryBacon 和 ftiasch 是好朋友。ftiasch 酷爱几何，于是 AngryBacon 经常会为 ftiasch 出一些几何 题。这次，他又出了一道题目： 给出平面上的 N 个整点，AngryBacon 想选取这 N 个点中的 K 个点，连成一个正 K 边形。 正 K 边形的定义为边数为 K
2015-11-03 07:42:36
505
原创 模拟赛记录（2）：10.31 T1 double精度问题，T2 Trie树
这天真是考瞎自己了，三道水题，只拿了180分。真是值得注意~.~。T1：给定n，s和数列a，表示数列a有n个整数，每个数不超过s，求平均数，保留12位小数输出。并没有注意过double的精度误差有多大，于是也没想别的就直接用double储存，直接算。最后是A4个，W5个，T1个。精度误差导致W，而T的原因，应该是浮点数的运算比整形要慢，所以复杂度上自带常数。在自己的CPU上跑了一下，1亿次整形加/乘
2015-11-03 07:19:02
744
原创 POJ 2247 小DP？
题意：定义H***数为质因子仅有2、3、5、7的数以及1，将所有的H***数排序，输出序列中第n个H***数。说是DP。。也看不出来啥DP的特征，Openjudge是把这题分到DP一类里了。因为H***数仅由特定的质因子构成，所以每一个H***数都可以由已知的H***数乘2、3、5、7得来。我们预处理出数据范围n以内的所有H***数，O(1)查询。处理方式很简单，代码易懂。唯一比较恶心的就是这道题的
2015-10-29 20:06:01
510
原创 Dinic 算法求最大流（最小割） POJ 2536
题意：给定n, m, s, v, 意思是有n只兔子，m个洞，兔子的跑步速度是v，兔子有s的时间跑进洞里，给定兔子和洞的坐标，问最少有多少只兔子在s时间内无法跑进洞里。 这道题是在Openjudge上看到的。。。。网络流。。。说好的NOIP有两道题从里面抽，然而加了这道网络流。要跪、♥碎。 于是去复习了一下以前看过的Dinic，有一段时间没写了，都快忘记了。数组范围都给忘了，RE了好多次。 这道题要求
2015-10-29 18:56:07
906
原创 POJ 2676 锻炼码力：数独，精确覆盖的DLX
题意：先给定数据组数T，每组数据都是一个数独游戏，输出它任意一个解。自从学了DLX之后，还没写过精确覆盖，只用自己YY代码写过一次可重复覆盖。这次写一个精确覆盖。数独麻烦的就是构建M矩阵，想了有一段时间。对于构建数独的M矩阵，大都是这样的套路： 行表示的是在某个位置填某个数。 列表示的是：某个位置是否有数，某一行是否有某个数，某一列是否有某个数，某一个块是否有某个数。只要记录清楚行、列对应的是那
2015-10-27 11:10:04
370
原创 Miller Rabin 算法验证素数 USACO 1.5 回文质数
题意：给定a, b，从小到大输出区间[a, b]中所有的回文质数。当一个质数反过来之后与之前相同时为回文质数。其实这道题不必用MR算法，直接暴力sqrt(n)判断一个数是否为质数可过。先说这道题，为什么要用到判断一个数是否为质数。a, b的范围是1亿，所以先筛素数再判断每个素数是否回文数是行不通的。所以要先生成所有的回文数，判断它是否为素数。而且，生成回文数的过程还需要一点点优化： 1.回文数长度
2015-10-26 22:07:50
369
原创 模拟赛记录（1）：10.24 T3 有趣的有趣的家庭菜园 （线段树优化DP）
有趣的有趣的家庭菜园(C.c/cpp/pas/in/out) (Time Limit:1s Memory Limit:256MB) 【Description】 职业经营家庭菜园的JOI君每年在自家的田地中种植一种叫做IOI草的植物。IOI草的种子在冬天被播下，春天会发芽并生长至一个固定的高度。到了秋天，一些IOI草会结出美丽的果实，并被收获，其他的IOI草则会在冬天枯萎。
2015-10-26 07:21:54
264
转载 C++ string 用法概览
标准C++中的string类的用法总结相信使用过MFC编程的朋友对CString这个类的印象应该非常深刻吧？的确，MFC中的CString类使用起来真的非常的方便好用。但是如果离开了MFC框架，还有没有这样使用起来非常方便的类呢？答案是肯定的。也许有人会说，即使不用MFC框架，也可以想办法使用MFC中的API，具体的操作方法在本文最后给出操作方法。其实，可能很多人很可能会忽略掉标准C++中strin
2015-10-24 11:00:22
208
原创 BZOJ 3991 SDOI 2015 寻宝游戏（异象石） LCA + Set + DFS序
异象石 (stone.pas/c/cpp) 题目描述 Adera 是 Microsoft 应用商店中的一款解谜游戏。 异象石是进入 Adera 中异时空的引导物，在 Adera 的异时空中有一张地图。这张地图上 有 N 个点，有 N-1 条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的 M 个时刻中，每个时刻会发生以下三种类型的事件之一： 1.
2015-10-23 15:53:11
2737
3
原创 「Poetize9」礼物运送 Tyvj 2033 DP
看到这道题的第一眼，搜索搜索。觉得n只有18除了搜索也没谁了。于是很快写出了搜索方法：sec(a, b, ta, tb, ed)当第一个人在a，已经用时ta，第二个人在b，已经用时tb，两人一共经过了ed个点。floyd预处理出每两个点之间最短路，每次枚举下一个被访问的点，以及被谁访问。华丽丽的阶乘级搜索，数据范围小到18也是不行，自己还脑残的地以为，优化优化。最终还是放弃了挣扎，又突然想到了一个词
2015-10-22 21:51:25
408
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人