- 博客(330)
- 资源 (3)
- 收藏
- 关注
RSS订阅
原创 博客搬家辣！https://beiyuouo.github.io/
http://www.cnblogs.com/beiyuoi/ 传送门 求诸位神犇收藏，互加友链 CSDN的页面比较简洁但是限制太多，而且有广告让人很不舒服。 所以我选择弃坑。 部分博文我会搬到新博客，有些水题就不搬了。再次搬家QAQ 自己的博客搭起来好麻烦啊！还是用博客园好了~
2016-04-03 11:25:06
1857
原创 Blog
BeiYu 北屿联系方式QQ:729320011Tel:15666676912(上学怎么能拿手机呢！Note模板请直接翻，部分加了注释，如果感觉代码风格还好的话，请参考阅读Tip中有一些比赛优化什么的小技巧经验总结见名知意代码风格总结写函数完大括号不换行会有意或无意压行用逗号代替分号数据范围全部用宏定义常用STL，vector什么的每次循环变量重新申请读入优化最近不喜欢
2015-12-02 20:10:00
3562
原创 BZOJ_P1597 [Usaco2008 Mar]土地购买(斜率优化DP)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2884 Solved: 1062 [Submit][Status][Discuss] Description农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <=
2016-04-01 11:45:37
733
原创 BZOJ_P1934 [Shoi2007]Vote 善意的投票(最小割)
BZOJ传送门Time Limit: 1 Sec Memory Limit: 64 MB Submit: 1721 Solved: 1061 [Submit][Status][Discuss] Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可
2016-04-01 09:13:37
504
原创 BZOJ_P4196 [NOI2015]软件包管理器(树链剖分+dfs序)
BZOJ传送门Linux 用户和 OS X 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OS X 下可用的 homebrew
2016-04-01 07:53:41
627
原创 BZOJ_P4199 [NOI2015] 品酒大会(后缀数组+并查集)
BZOJ传送门一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。在大会的晚餐上，调酒师 Rainbow 调制了 nn 杯鸡尾酒。这 nn 杯鸡尾酒排成一行，其中第 ii 杯酒 （1≤i≤n1≤i≤n） 被贴上了一个标签 sisi，每个标签都是 2626 个小写英文字母之一。设 Str(l,r)Str
2016-03-31 19:08:37
635
原创 杂文_20160330
今天还有昨天完全不在状态……可能是有点感冒，什么都看不下去。什么goupi后缀数组(砸！想想去年、前年、大前年的今天对我还是一个特殊的日子，可是今年却只是平平淡淡过去了。去年的此时，我或许还在和初中的好友一起颓废(其实我还不知道这个名词)，现在都已物是人非。省选前我要立Flag吗……
2016-03-30 19:43:34
525
原创 POJ_P3415 Common Substring(后缀数组+单调栈)
POJ传送门Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 9232 Accepted: 3066 DescriptionA substring of a string T is defined as:T(i, k)=TiTi+1…Ti+k-1, 1≤i≤i+k-1≤|T|. Given two strin
2016-03-30 19:11:38
398
原创 POJ_P2774 Long Long Message/Codevs_P3160 最长公共子串(后缀数组)
Codevs传送门 POJ传送门最长公共子串 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 大师 Master题目描述 Description 给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。输入描述 Input Description 读入两个字符串输出描述 Output Description 输出最长公共子串的长度样例输入 Sample Input
2016-03-30 14:13:58
444
原创 模板_后缀数组
#define N 200005int t1[N],t2[N],c[N];int sa[N],rk[N],ht[N];int n,m=27,len;int s[N];void sort(int *x,int *y){ for(int i=0;i<m;i++) c[i]=0; for(int i=0;i<n;i++) c[x[y[i]]]++; for(int i=1;
2016-03-30 10:45:59
322
原创 Tyvj_P1860 后缀数组(后缀数组模板题)
Tyvj传送门时间: 1000ms / 空间: 131072KiB / Java类名: Main 描述 我们定义一个字符串的后缀suffix(i)表示从s[i]到s[length(s)]这段子串。 后缀数组（Suffix array）SA[i]中存放着一个排列，满足suffix(sa[i])< suffix(sa[i+1]) 按照字典序方式比较 定义height[i]表示suffix(sa[
2016-03-30 10:45:20
882
原创 Codevs_P1500 后缀排序(后缀数组+基数排序)
Codevs传送门时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master题目描述 Description 天凯是MIT的新生。Prof. HandsomeG给了他一个长度为n的由小写字母构成的字符串，要求他把该字符串的n个后缀(suffix)从小到大排序。何谓后缀？假设字符串是S=S1S2……Sn，定义Ti=SiSi+1……Sn。T1, T2, …, Tn就叫做S
2016-03-29 19:08:04
958
原创 BZOJ_P3048 [Usaco2013 Jan]Cow Lineup(二分答案+树状数组/单调队列)
BZOJ传送门Time Limit: 2 Sec Memory Limit: 128 MB Submit: 113 Solved: 82 [Submit][Status][Discuss] DescriptionFarmer John’s N cows (1 <= N <= 100,000) are lined up in a row. Each cow is identified by
2016-03-29 18:53:19
611
原创 BZOJ_P2330 [SCOI2011]糖果(差分约束+最长路)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 128 MB Submit: 3910 Solved: 1188 [Submit][Status][Discuss] Description幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比
2016-03-29 07:57:10
306
原创 BZOJ_P1467/POJ_P3243 Clever Y(扩展BSGS+哈希)
BZOJ-P1467 POJ-P3243Time Limit: 4 Sec Memory Limit: 64 MB Submit: 202 Solved: 106 [Submit][Status][Discuss] Description小Y发现，数学中有一个很有趣的式子： X^Y mod Z = K 给出X、Y、Z，我们都知道如何很快的计算K。但是如果给出X、Z、K，你是否知道如何快速
2016-03-28 21:43:23
675
原创 BZOJ_P2461 [BeiJing2011]符环(动态规划/记忆化搜索)
BZOJ传送门Time Limit: 20 Sec Memory Limit: 128 MB Submit: 113 Solved: 59 [Submit][Status][Discuss] Description在可以炼制魔力强大的法杖的同时，Magic Land 上的人们渐渐意识到，魔力 强大并不一定能给人们带来好处——反而，由此产生的破坏性的高魔力释放，给 整个大陆蒙上了恐怖的阴
2016-03-28 16:23:13
481
原创 BZOJ_P3262 陌上花开(CDQ分治+树状数组)
BZOJ传送门Time Limit: 20 Sec Memory Limit: 256 MB Submit: 1045 Solved: 475 [Submit][Status][Discuss] Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，
2016-03-28 14:59:19
481
原创 BZOJ_P1176 [Balkan2007]Mokia(CDQ分治+树状数组)
BZOJ传送门Time Limit: 30 Sec Memory Limit: 162 MB Submit: 1605 Solved: 697 [Submit][Status][Discuss] Description 维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.In
2016-03-27 18:53:39
313
原创 BZOJ_P1935 [Shoi2007]Tree 园丁的烦恼(离散化+树状数组+差分思想)
BZOJ传送门Time Limit: 15 Sec Memory Limit: 357 MB Submit: 808 Solved: 363 [Submit][Status][Discuss] Description很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里，若有所思，他问一个园丁道：
2016-03-27 15:47:22
618
原创 BZOJ_P1492 [NOI2007]货币兑换Cash(CDQ分治+斜率优化)
BZOJ传送门Time Limit: 5 Sec Memory Limit: 64 MB Submit: 3172 Solved: 1343 [Submit][Status][Discuss] Description Input第一行两个正整数N、S，分别表示小Y 能预知的天数以及初始时拥有的钱数。 接下来N 行，第K 行三个实数AK、BK、RateK，意义如题目中所述Output只有一
2016-03-27 13:39:03
349
原创 BZOJ_P1452 [JSOI2009]Count(二维树状数组)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1749 Solved: 1046 [Submit][Status][Discuss] DescriptionInputOutput Sample InputSample Output1 2HINTSourceSol: 二维树状数组裸题..如果你不介意树套树的话其实也可以…#i
2016-03-27 09:02:12
307
原创 BZOJ_P2763 [JLOI2011]飞行路线(分层图+最短路)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1725 Solved: 647 [Submit][Status][Discuss] DescriptionAlice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，
2016-03-27 07:55:42
717
原创 BZOJ_P3081 [Cerc2011]Strange Regulations(LCT)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 128 MB Submit: 28 Solved: 12 [Submit][Status][Discuss] Description在一个计算机网络中，连接两台计算机的电缆属于不同的公司。一项新的反垄断法规定，一家公司连接同一台计算机的电缆不能超过两条。为了避免资源浪费，另外一条法律规定，一家公司的电缆系统不能
2016-03-26 19:25:05
383
原创 BZOJ_P3651 网络通信(LinkCutTree)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 256 MB Submit: 71 Solved: 52 [Submit][Status][Discuss] Description 有一个由M 条电缆连接的 N 个站点组成的网络。为了防止垄断，由 C 个公司控制所有的电缆，规定任何公司不能控制连接同一个站点的两条以上的电缆（可以控制两条）。同时规定，
2016-03-26 16:01:47
361
原创 BZOJ_P3944 Sum(数论+杜教筛)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1108 Solved: 270 [Submit][Status][Discuss] DescriptionInput 一共T+1行 第1行为数据组数T(T<=10) 第2~T+1行每行一个正整数N，代表一组询问Output 一共T行，每行两个用空格分隔的数ans1,ans
2016-03-25 20:52:17
1002
原创 51Nod_P1239 欧拉函数之和(数论+杜教筛+欧拉函数+哈希+快速乘)
51Nod传送门基准时间限制：3 秒 空间限制：131072 KB 分值: 640 难度：8级算法题 对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler’s totient function、φ函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。 S(n) = Phi(1) + Phi(2) +
2016-03-25 17:05:13
847
原创 51Nod_P1244 莫比乌斯函数之和(数论+杜教筛+哈希)
51Nod传送门基准时间限制：3 秒 空间限制：131072 KB 分值: 640 难度：8级算法题莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。具体定义如下： 如果一个数包含平方因子，那么miu(n) = 0。例如：miu(4), miu(12), miu(18) = 0。 如果一个数不包含平方因子，并且有k个
2016-03-25 15:38:54
1529
原创 BZOJ_P2442 [Usaco2011 Open]修剪草坪(单调队列)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 128 MB Submit: 690 Solved: 338 [Submit][Status][Discuss] Description 在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。 然而，FJ的草坪非常脏乱，因此，FJ只能
2016-03-25 13:42:58
483
原创 BZOJ_P1666 [Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏(hhhhhh)
BZOJ传送门Time Limit: 5 Sec Memory Limit: 64 MB Submit: 651 Solved: 566 [Submit][Status][Discuss] Description奶牛们又在玩一种无聊的数字游戏。输得很郁闷的贝茜想请你写个程序来帮她在开局时预测结果。在游戏的开始，每头牛都会得到一个数N(1<=N<=1,000,000)。此时奶牛们的分数均为0
2016-03-25 13:39:20
546
原创 BZOJ_P1682 [Usaco2005 Mar]Out of Hay 干草危机(最小生成树)
BZOJ传送门Time Limit: 5 Sec Memory Limit: 64 MB Submit: 487 Solved: 329 [Submit][Status][Discuss] DescriptionThe cows have run out of hay, a horrible event that must be remedied immediately. Bessie i
2016-03-25 08:17:52
689
原创 BZOJ_P2118 墨墨的等式(最短路)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 259 MB Submit: 928 Solved: 356 [Submit][Status][Discuss]Description 墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在
2016-03-25 08:14:11
558
原创 BZOJ_P1529 [POI2005]ska Piggy banks(并查集)
BZOJ传送门Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1062 Solved: 494 [Submit][Status][Discuss] DescriptionByteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是
2016-03-24 21:27:56
476
原创 BZOJ_P2440 [中山市选2011]完全平方数(数论+莫比乌斯反演+容斥原理)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 128 MB Submit: 2225 Solved: 1070 [Submit][Status][Discuss] Description小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而 这丝毫不影响他对其他数的热
2016-03-24 20:48:42
458
原创 模板_zkw线段树
搞了一下午zkw线段树，思路有点混乱zkw线段树速度确实快！十分快！可是应用其实很有限(我太沙茶，貌似还能当Treap用？负数是硬伤RMQ问题，可惜解决不了负数int n,M,q;int d[N2];inline void Build(int n){ for(M=1;M1;M1);for(int i=M+1;iin(); for(int i=M-1;i;--i)
2016-03-24 20:01:50
535
原创 HDU_P1166 敌兵布阵(zkw线段树)
HDU传送门Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 68018 Accepted Submission(s): 28604Problem Description C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子D
2016-03-24 20:01:22
479
原创 BZOJ_P1303 [CQOI2009]中位数图(中位数)
BZOJ传送门Time Limit: 1 Sec Memory Limit: 162 MB Submit: 1974 Solved: 1268 [Submit][Status][Discuss] Description给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。Input 第一行为两个正整数n和b ，第二行
2016-03-24 20:00:56
496
原创 POJ_P1151/HDU_P1542 Atlantis(计算几何+扫描线+线段树)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 162 MB Submit: 810 Solved: 344 [Submit][Status][Discuss] Description Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。Input 输入n
2016-03-24 20:00:27
437
原创 POJ_P1144 Network(无向图割点)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 162 MB Submit: 810 Solved: 344 [Submit][Status][Discuss] Description Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。Input 输入n
2016-03-24 19:59:52
336
原创 BZOJ_P1123 [POI2008]BLO(无向图割点)
BZOJ传送门Time Limit: 10 Sec Memory Limit: 162 MB Submit: 810 Solved: 344 [Submit][Status][Discuss] Description Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。Input 输入n
2016-03-24 19:59:33
764
原创 HDU_P1269 迷宫城堡(有向图的强连通分量)
HDU传送门迷宫城堡 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 11289 Accepted Submission(s): 5060Problem Description 为了训练小希的方向感，Gardon建立了
2016-03-24 19:59:01
429
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人