- 博客(364)
- 收藏
- 关注
RSS订阅
原创 [挖坑]不想做&&不会的题
UPD:2016.1.23 先挖坑。。以后再填吧。。大多数是连要用的算法都没学过比如SAM,莫比乌斯反演，概率与期望什么的。。还有一些是太弱了连题解都看不懂的。。3308: 九月的咖啡店 1101: [POI2007]Zap 3998: [TJOI2015]弦论 4001: [TJOI2015]概率论 3926: [Zjoi20150]诸神眷顾的幻想乡 4008: [HNOI2015
2016-01-23 09:10:15
899
原创 [提醒]曾经犯的谜之错误
1.N,M输入反了。 2.LCT的access和cut操作后忘记pushup。 3.Splay的del操作后忘记pushup。
2016-01-13 10:39:10
779
原创 [挖坑]待学的算法
我太弱啦= =一大波东西没学，有很多东西还是有必要学一下的。可并堆 动态树分治 树套树 可持久化线段树 可持久化trie 可持久化平衡树 虚树 基环树 分块 莫队算法 块状链表 块状树 三分 后缀自动机 后缀树 整体二分 CDQ分治 K-D树 莫比乌斯反演 高斯消元 概率与期望DP 组合数学 set/map/rope/bitset/vector 计算几何
2016-01-12 22:43:39
883
3
原创 [挖坑]未解决的题
怎么也过不了的题QAQ3545: [ONTAK2010]Peaks 写的splay+启发式合并不知为何WA啊QAQ，然而网上都没这么写的。 3083: 遥远的国度 感觉是链剖sb题啊然而就是过不了，submit*20。
2016-01-08 21:37:00
869
1
原创 [颓废史]蒟蒻的刷题记录
QAQ蒟蒻一枚，其实我就是来提供水题库的。 以下记录从2016年开始。1.1 1227: [SDOI2009]虔诚的墓主人 树状数组+离散化 3132: 上帝造题的七分钟 树状数组 二维区间加减+查询 3038: 上帝造题的七分钟2 线段树+剪枝1.2 1047: [HAOI2007]理想的正方形 二维单调队列维护最值1.4 2095: [Poi2010]Bridges 二分+混合图欧拉
2016-01-05 19:23:00
3286
6
原创 NOI2016滚粗记
Day-1由于飞机是明天一早，所以今天就要先去济南了。下午2：00出发，与之前不同的是这次是商务车直达。路上老师检查了一下笔试，似乎没什么问题。傍晚就到了，老师们请客一起吃饭，然而在机场旁太偏了并没什么好吃的东西。 晚上没什么事情，玩了玩手机，跟yzy说了一些linux相关的东西。老师贴心的送来了明天早晨的早餐：2包好吃点（一脸不可吃）+1灌八宝粥+1包香肠。就早睡了。 6：15起床，我就喝了半
2016-07-29 22:32:42
5916
11
原创 PKUSC2016酱油记
无聊报上了pkusc结果居然过了初审，于是滚粗狗就又续命几天。 据说今年thusc比pkusc容易过然而我thusc没过pkusc过了是smgDay -?退役了报了D，虽然希望渺茫，但还是在机房里等着。期间跟随yzy大爷报了pkusc。然后yzy要去胜利一中参加省队集训，听说有不少退役选手也要去于是我也去旅游了。在胜利一中感觉生活不错，晚上偶尔浪浪，被叫去打狼人结果打完了还没搞懂游戏规则，和省实验
2016-06-05 22:44:15
3889
3
原创 3716: [PA2014]Muzeum 计算几何+贪心+set
刷空PA2014的CA凉果然劲啊。。这题好难。。 第一步是用计算几何的知识进行坐标变换，然后是一个最大权闭合图的模型。 由于图的特殊性可以贪心来解决。 具体参考CA的题解#include<iostream>#include<cstdio>#include<set>#include<algorithm>using namespace std;const int N=400005;int
2016-05-22 15:28:52
776
原创 3712: [PA2014]Fiolki LCA 思路题
非常神的一道题。。orzzzzz 做法： 我们用一个节点代表一个瓶子，合并的时候新建一个节点，代表合并出来的瓶子，并且向原来的两个点连边。可以发现，反应的话，其实就是两个瓶子代表节点的LCA。 然后按照LCA的深度以及时间戳排序，算答案就好了。#include<iostream>#include<cstdio>#include<algorithm>using namespace std;
2016-05-22 15:26:16
1183
原创 3718: [PA2014]Parking 树状数组
%CA凉 代码风格药丸#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=50005;int n,m;int tree[N],pos[N];inline int read(){ int a=0,f=1; char c=getcha
2016-05-22 15:22:16
696
原创 2626: JZPFAR K-D tree
裸题，用堆维护一下。#include<iostream>#include<cstdio>#include<algorithm>#include<queue>using namespace std;const int N=100005;const int INF=1000000007;int n,D,root;int ls[N],rs[N];struct node{ int d
2016-05-21 23:45:13
549
原创 4565: [Haoi2016]字符合并 区间DP
令fi,j,kf_{i,j,k}表示区间[i,j][i,j]合并成kk的最大收益，其中K=0/1K=0/1保证[i,j][i,j]可以合并成一个数。 转移的时候用gj,kg_{j,k}表示对于当前的ii,[i,j][i,j]合并成了kk，其中kk是一个二进制数。 然后转移一下就行了#include<iostream>#include<cstdio>#include<cstring>usin
2016-05-21 23:43:45
975
原创 4566: [Haoi2016]找相同字符 广义后缀自动机
建立广义后缀自动机，维护两个串的sizesize 那么答案等于∑(leni−lenfai)×size0×size1\sum (len_i-len_{fa_i})\times size_0 \times size_1#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=200005;
2016-05-21 23:40:55
703
原创 2893: 征服王 tarjan+最小流
首先tarjan缩点，然后裸的最小流。 好像是个挺麻烦的费用流。。然而我写的最小流居然跑到了rank1。。#include<iostream>#include<cstdio>#include<queue>#include<cstring>#include<vector>using namespace std;const int N=1100;const int M=50005;con
2016-05-21 23:35:12
626
原创 3180: [Coci2012]ograda 贪心
可以发现答案只与拐点有关，所以贪心就行了，最后把中间的点放进去。#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int N=300005;int n;int num[N],ss[N],ans[N];inline int read(){ int a=0,f=1; char
2016-05-21 23:29:25
635
原创 3463: [COCI2012] Inspector 分块+凸壳
可以发现答案一定在下凸壳上，我们考虑分块，然后如果有修改操作在块上打标记，查询的时候暴力重构。 由于TT是单调的，所以维护一个队列，弹出队头元素直到到了TT所在的直线就好了。#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int N=100005;c
2016-05-21 23:27:47
509
原创 3181: [Coci2012]BROJ 找规律
我们根据PP的大小来分类，当PP比较大的时候，10910^9范围内PP的倍数会比较少，暴力枚举就可以。 PP比较小的时候，我们来找循环节。 令C=∏pi<=PpiC=\prod_{p_i<=P}p_i，假设ii合法，则i+Ci+C也合法。 证明： 若C+iC+i不合法， 则存在质因子p<Pp<P且p∣C+ip\mid C+i，因为p∣Cp\mid C，所以p∣ip\mid i，矛盾。 所以
2016-05-21 23:24:37
621
原创 3176: [Coci 2012]Sort 树状数组
可以发现第一次reverse后，只会存在一些长度为2的递减序列，其实就是逆序对的数量了。#include<iostream>#include<cstdio>using namespace std;int n,a[100005],tree[100005];long long ans;inline int read(){ int a=0,f=1; char c=getchar();
2016-05-21 23:14:54
595
原创 2275: [Coci2010]HRPA 打表/齐肯多夫定理
博弈什么的真是弱啊。。虽然这题根本用不到博弈的知识。。但看着这类问题就懵逼。 记得sxb是打表找规律过的。。 题解是一个叫做齐肯多夫定理的东西。。可以百度一下qwq#include<iostream>#include<cstdio>using namespace std;long long n;int cnt;long long f[100];int main(){ scanf
2016-05-21 23:11:43
1221
原创 3881: [Coci2015]Divljak fail树+树链的并
我们对SS集建立AC自动机，用TT集中的串算答案。 可以发现在AC自动机上运行串时，所经过的节点和沿这个节点的fail指针向上经过的所有节点代表的串都在TT中出现过。所以要求的就是一些树链的并集。 我们把这些点拿出来按照fail树的dfs序排序，用树状数组维护dfs序的前缀和，把每个点处+1，把两两lca处-1，询问就变成询问子树了。#include<iostream>#include<cst
2016-05-21 23:07:17
808
原创 3188: [Coci 2011]Upit splay
splay，对于区间加等差数列的操作，我们可以发现等差数列的首项和公差是可以分开考虑并且可叠加的。那么就打标记就好了。#include<iostream>#include<cstdio>using namespace std;const int N=200005;int n,Q,t1,t2,tot,root;int fa[N],tree[N][2];long long size[N],su
2016-05-21 22:54:56
682
原创 3743: [Coci2015]Kamp BFS
首先我们可以搞出这KK个点的一棵生成树，记这棵生成树的边权和为sumsum。 假设每次都要返回出发点xx，那么这里分两种情况讨论： 如果xx是KK个点中的某个点，那么答案为2×sum2\times sum 否则，答案为2×sum+mindis(x,tree)2\times sum+mindis(x,tree) 那么如果不需要返回的话，答案在以上基础上上要减去maxdis(x,i)(i bel
2016-05-21 22:52:19
761
原创 3810: [Coci2015]Stanovi 记忆化搜索
首先观察性质：对于一个合法的方案，总能将矩形分成两部分。 否则总会有四面均不接触边界的矩形。 那么我们用fn,m,u,d,l,rf_{n,m,u,d,l,r}表示n×mn\times m的矩形，四个边界是否存在(0/1)(0/1)然后记忆化搜索#include<iostream>#include<cstdio>#include<cstring>using namespace std;con
2016-05-21 22:45:52
855
原创 4571: [Scoi2016]美味 主席树+贪心
建立主席树，然后从高位到低位贪心就好了。#include<iostream>#include<cstdio>using namespace std;const int MAXN=100000;const int N=200005;const int M=5000005;int n,m,size;int root[N];int ls[M],rs[M],sum[M];inline int
2016-05-21 22:41:44
937
原创 3727: PA2014 Final Zadanie 乱搞
很神的一道题。参考PoPoQQQ的题解： 首先转化为以11为根的有根树，sizeisize_i表示以ii为根的子树的aia_i的和。 那么有 b1=∑ai×disib_1=\sum a_i\times dis_i bi=bfai−sizei+(size1−sizei)b_i=b_{fa_i}-size_i+(size_1-size_i) 并且有ai=sizei−∑sizesonia_i=s
2016-05-21 22:36:32
2913
原创 SDOI2016 Round2 退役记
两年OI一场空，一场R2见祖宗。Day-？一轮回来后刷题效率并不高，与yts，sxb，DQS，Menci，wmy，yzy一起进行了几场胡策，场场垫底的我仰慕大爷们AK。 之后刷题乱做一气，做了做tsinsen，然后做了做各省省选，做了做COCI。 考前听说了悲伤的消息：教练有事班主任跟着去，压力++。Day0根据学校的坑爹安排只好10点就出发，也没堵车于是11点就到了火车站取了票，然后班主任请我
2016-05-14 18:05:54
2341
3
原创 SDOI2016 Round2 Bless All
NOIP完跪 WC完跪 HN集训一直被虐 SDOI2016 Round1完跪 CTSC&APIO因为奇♂怪的原因没去成 居然还没退役好好享受OI生涯的最后一场比赛吧。 Bless All。
2016-05-13 09:10:54
950
1
原创 4569: [Scoi2016]萌萌哒 倍增+并查集
好神的一道题，不会做。 %Claris#include<iostream>#include<cstdio>#include<cmath>using namespace std;const int N=100005;const int mod=1000000007;int n,m,ans;bool vis[N];int f[17][N];inline int read(){
2016-05-02 20:23:18
551
原创 4568: [Scoi2016]幸运数字 倍增+线性基
#include<iostream>#include<cstdio>#include<cmath>#include<vector>#include<cstring>using namespace std;const int N=20005;int n,Q,cnt;int deep[N],head[N],next[N<<1],list[N<<1];long long q[N<<1];
2016-05-02 20:21:18
1264
原创 4567: [Scoi2016]背单词 trie+贪心
代码能力太弱。。想了5分钟写了1小时。。 耐下心来读完题，然后发现最优解一定是不会出现第一种情况的，也就是说如果访问一个串之前一定要访问这个串的所有后缀。 那么我们把串反过来，转换成前缀，也就是沿着trie走的问题。然后就贪心一波，先走子树小的再走子树大的就行了。#include<iostream>#include<cstdio>#include<vector>#include<cstri
2016-05-02 20:09:44
1189
原创 3241: [Noi2013]书法家 DP
《根据数据范围猜做法系列》 首先感受一下题意，像一个DP。。。 然后观察一下数据范围，感觉应该是个三次方的DP。。 然后发现nn比mm小不少，应该是O(n2m)O(n^2m)的。。。 然后观察一下图形，发现了非常奇妙的性质。。 可以分成这11部分，然后用fif_i表示第ii块，枚举列进行转移。 大概有以下转移： empty→1,1→1,1→2,2→2,2→3,3→3,3→4,4→4
2016-04-29 21:16:30
1050
1
原创 4025: 二分图 分治+并查集
分治大法吼啊.. 好像动态图可以用LCT搞搞..不过没研究过 以后再说 分治的方法可以看popoqqq..感觉挺神的顺便了解了一下命名空间..#include<iostream>#include<cstdio>#include<vector>using namespace std;const int N=100005;int n,m,T,top;int stack[N<<2];str
2016-04-28 18:51:52
563
原创 4184: shallot 线段树+按时间分治+线性基
Oxer大爷安利的题 qwq。 了解了一下按时间分治。 由于每个数的出现区间一定是连续的一段，那么可以在线段树上对应节点插入这个数，也就是每个节点套一个vector。然后dfs一下把根到叶子路径上所有经过的点都插入线性基里，就可以求答案了。#include<iostream>#include<cstdio>#include<set>#include<vector>using namesp
2016-04-27 20:32:40
831
原创 3218: a + b Problem 最小割+主席树优化建图
妈的这题调了我一下午+半晚上= = 首先暴力最小割建图显然。 建边(S,i,bi),(i,T,wi)(S,i,b_i),(i,T,w_i)然后对于每个点ii新建一个点i′i'，建边(i,i′,pi)(i,i',p_i)，对于1≤j<i1\leq j<i且满足条件的jj，我们连边(i′,j,+∞)(i',j,+∞) 然后边数O(n2)O(n^2)，MLE。 我居然以为5000*5000=250
2016-04-26 20:08:53
613
原创 2878: [Noi2012]迷失游乐园 基环树+DP+概率与期望
不妨用downidown_i表示从点ii往下走的期望步数，upiup_i表示从点ii往上走的期望步数。 用sonison_i表示点ii的儿子个数，faifa_i表示点ii的父亲个数（基环树上的点有两个父亲） 那么答案显然等于ans=∑ni=1downi×soni+upi×faisoni+fainans=\frac{\sum_{i=1}^n\frac{down_i\times son_i+up_i
2016-04-26 08:10:32
528
1
原创 2651: 城市改建 树形DP
我太sb了。。一看输出方案就瞎jb记录了一坨信息。。最后发现根本没有用。。 结果写了6.7K。。。成功成为了BZOJ写的最长跑的最慢的选手2333。。题目即在一棵树上删一边加一边，使得新树的直径最小。 那么我们就要维护直径相关的信息。。于是大力DP。。 首先自底向上DP，设fif_i表示以节点ii为根的子树的直径，gig_i表示以节点ii为根的子树中离ii最远的点的距离。 假设j,kj,k为
2016-04-25 10:53:13
663
1
原创 A1330. 世博会(刘洪轩) 主席树
假设最后答案为x0,y0x_0,y_0。 然后ans=∑ni=1max{∣xi−x0∣+∣yi−y0∣}ans=\sum_{i=1}^n max\{ \mid x_i-x_0\mid + \mid y_i-y_0\mid\} 然后我们令Xi=xi+yi2,Yi=xi−yi2X_i=\frac{x_i+y_i}{2},Y_i=\frac{x_i-y_i}{2}，那么答案可以转化为ans=∑ni=1
2016-04-24 16:31:55
685
原创 A1251. 设计铁路(钱桥) DP+斜率优化
明明是一道裸题，我却做了这么久。感觉自己斜率优化真是弱啊，省选就没做出来，现在做还是这么费力。 我们用di,aid_i,a_i分别表示第ii个车站到终点的距离和人数。 首先按照did_i降序排序，然后我们用fif_i表示在第i个村庄出修建一个车站，且1 i1~i的所有人都开车到车站，此时的总花费。 然后我们维护两个前缀和si,pis_i,p_i。 si=∑j=i+1ndj∗ajs_i=\su
2016-04-23 19:30:47
592
原创 4542: [Hnoi2016]大数 莫队算法
555我好弱啊 都说今年的HNOI是无脑数据结构赛，都很好想只是码代码的问题，然而我还是不会做这道题。 要退役了啊啊啊。首先我们令sis_i表示以ii为开头的后缀形成的数字。 对于p≠2p\neq 2且p≠5p\neq5的时候，我们可以发现，若存在l,rl,r，满足sl≡sr+1(modp)s_l\equiv s_{r+1}\pmod{p}，则区间[l,r][l,r]组成的数字一定是pp的倍数
2016-04-23 08:07:14
436
原创 2959: 长跑 LCT+dfs
不错的一道题目，可惜tsinsen被卡常了，在BZOJ A掉了。 由于我们可以多次经过一个点，那么如果形成了一个简单环，那么环内的每个点都可以被经过，所以可以把这样的环缩成一个点，权值就是原来所有点的权值之和。 这样每次连边的时候如果发现有环就缩点，用并查集维护。 然后就是裸的LCT。#include<iostream>#include<cstdio>using namespace std
2016-04-20 21:15:53
502
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人