- 博客(78)
- 收藏
- 关注
RSS订阅
原创 NOI主计划
主要是放一些自己不会||要考的东西SCOI考的果然狭窄一些啊，好多东西以前没管现在必须学了1.博弈论2.插头dp3.数位dp4.kd树5.懵逼钨丝繁衍(名字就是这么奇怪6.FFT7.动态凸包，可持久化凸包8.toptree，这个还在考虑，因为这个涉及到传说中的退役魔咒9.最小树形图10.各种完全分不清楚的分治算法11.仙人掌(鬼知道考不考啊12.
2016-04-13 11:20:21
1139
2
原创 方便OI/ACM竞赛的Notepad++配制方法
1.下载[神秘链接][https://notepad-plus.en.softonic.com/]2.安装安装简体中文版3.更改字体设置-语言格式设置-一个一个改，改成自己喜欢的4.括号匹配设置-首选项-自动完成 设置-首选项里面所有东西按照自己喜爱修改即可5.编译首先你电脑要有一个g++，这里我的电脑里面有devc++ 把devc++的Dev-Cp...
2018-05-26 17:23:40
528
原创 2018/2/17
鸽了一天。。不要在意（反正也没人看1.一个有趣的idea（不知道有没有题）给一张图，每个边有边权，现在要求log时间内求出： 给出x值和k点，去除大于x的所有边后k连通块的信息（sum啊max啊等等线段树干的事） 做法：首先跑最小生成树，我们建立一棵新树，如果最小生成树连接了u和v，建立新点p，连接p,fa[u]和p,fa[v]，并且把p作为新的连通块的父亲节点 这样就把连通块上...
2018-02-17 12:55:17
444
1
原创 2018/2/9
1.[Gym-101608H] [Problem H]题意：给出一个序列，每个位置为’.’或’+’，加号代表加油站，点代表空地。现在至多移动一个加油站，使得所有点到最近加油站的距离最大值最小。 做法：二分答案，问题变为求某个答案是否合法 如果有两个点区间大于2∗mid+12∗mid+12*mid+1不合法 如果有一个区间大于4∗mid+24∗mid+24*mid+2不合法 否则看能否调...
2018-02-09 16:05:45
520
原创 2018/2/2
1.暴力出奇迹题意：给出四个数求24点，交换两个数代价为2，加一个括号代价为1，求最小代价 做法：标准做法为建括号序列树 在训练中，我们发现一共只有10种合法的括号，于是。。暴力枚举这10种情况，每种情况求出后带上符号和括号扔进表达式求值的板子里面，就得出了正确结果 代码太长不扔了2.
2018-02-02 20:38:53
734
原创 Noip2016 Ac代码 by liuchenrui
noip2016AC代码 T1#include<cstdio>#include<string>#include<cstring>#include<cstdlib>#include<ctime>#include<iostream>#include<algorithm>void splay(int&v){ char s='x';v=0;int p=0; while(s<'
2016-12-01 18:05:29
722
原创 Noip 2016 蛋碎一地晚节不保
这次没怎么准备。直接被拉去考试了 day0 请了晚自习的假，住在uestc外面day1 早上一进校园遇见东辰大军，着实吓了一跳（mama吼多人 遇见zzq老司机，聊了一会，顺手奶了一口今天不考数学 拿到题，密码为什么一点也不文艺啊草，去年是“你那里今天下雪了吗”，今年为什么变成了乱码 T1 沙茶题，mogician好评 T2 我操怎么这么难 一眼看去，我想复杂了 再看一眼，我想
2016-12-01 18:00:56
654
原创 OI小结
本来这篇小结是准备7月28日写的，发生了一些奥妙重重的事就拖到了现在 27日晚上，zgs突然说28日开始补课，全天！ 喂我26日才从ns回来好不好！初中结束的暑假，本着可以浪2个月的心态然后被一场竞赛交流会打乱了。 我说我不想学数学了，初中弄了3年，伤 我妈说物理怎么样 还好，于是报了物理 我妈又说信息学听说前景还不错 好，报，反正休息不成了物理就是水过去的，一节课半天我看不到一点诚意
2016-08-08 11:02:40
2510
原创 树上（带修改）莫队算法-- bzoj4129 && bzoj3757
bzoj3757似乎因为版权挂了 首先，我们要熟悉序列莫队 然后考虑树上莫队 我们用(l,r)表示当前l到r这条链上的答案(不包括lca),现在考虑从(l,r)转移到(L,R)我们用(l,r)表示当前l到r这条链上的答案(不包括lca),现在考虑从(l,r)转移到(L,R) 我们发现,(l,r)=ans(root,l) xor ans(root,r)我们发现,(l,r)=ans(root,l
2016-07-10 12:52:15
1036
原创 bzoj 4632: 树的编码
首先根节点的长度为0 我们观察，如果当前子树根节点长度为xx，那么他的子树内节点长度不小于xx 如果只有一个儿子，那么这个儿子编码和父亲编码是一样的 如果有两个儿子，那么这两个儿子分别+1+1和+0+0 显然这是一个贪心问题，考虑对于xx节点如何贪心 我们把它所有的儿子扒出来，然后按照sizesize排序，对于这些sizesize构建哈夫曼树，这样某个节点在哈夫曼树上的deep−1deep
2016-07-08 16:36:44
737
原创 dp 杂练/专练 round2
上次题似乎有点水 大概到noi之前会进行一些针对自己薄弱点的专项训练吧 bzoj1419Redisgoodbzoj 1419 Red is good 额...dp[i][j]表示red剩i张，black剩j张的期望额...dp[i][j]表示red剩i张，black剩j张的期望 每次期望×概率转移就行每次期望×概率转移就行 注意如果期望在0以下就不取了注意如果期望在0以下就不取了 空间
2016-06-21 17:53:03
510
原创 bzoj2769 YY的快速排序
真是不想写这题题解。。为了后人不被坑还是写一个吧 首先，题意完全不清啊：每次选出一个数，会像快速排序那样交换前后的顺序，保证前面的数小于它，后面的数大于他，相对顺序不变其次，标程精度是挂的，开double才能过 再其次，它卡常数，而且很恶心 这TM就是我搞了一下午的三个理由 我们考察每对逆序对的贡献，都是2序列里面值在这两个数之间的个数我们考察每对逆序对的贡献，都是 \frac{2}{序
2016-06-17 20:31:23
709
2
原创 dp 杂练/专练
最近各种各样的事让我感受到了自己dp是多么弱，于是开始写dp bzoj1055bzoj1055 dp[i][j][k]表示i到j能否缩成kdp[i][j][k]表示i到j能否缩成k 没了//Copyright(c)2016 liuchenrui#include<bits/stdc++.h>#define N 255using namespace std;char p[]={'W','I
2016-06-17 15:38:59
623
原创 bzoj 4028 [HEOI2015]公约数数列
首先分块 我们预处理每一块的前缀gcdgcd和前缀xorxor 假设这一块开头为ll,结尾为rr 令g[i]=gcd(a[l],a[l+1],…a[i]),x[i]=xor(a[l],a[l+1],…a[i])g[i]=gcd(a[l],a[l+1],…a[i]), x[i]=xor(a[l],a[l+1],…a[i]) 然后把每一块按x[i]x[i]为第一关键字，下标为第二关键字排序
2016-06-13 20:15:10
607
1
原创 BSGS的一个拓展--模数为合数的做法
lsh留下来的遗产（虽然没看 求 ax==b(mod p)得 ax+k∗p==b设 g=gcd(a,p)，那么bg为整数得agax−1+kpg=bgagax−1==bg(mod pg)ax−1==bg(ag)−1(mod pg)ax′==b′(mod m′)其中x′=x−1b′=bg(ag)−1m′=pg a^x==b(mod\ p)\\ 得\ a^x+k*p==b\\ 设\ g=g
2016-06-13 13:22:09
753
原创 bzoj 4461: [Jsoi2013]美丽家园
千分矩阵乘法题 dp[i][j]表示第i行，j状态是否可行 矩乘就好,需要高精度#include<bits/stdc++.h>using namespace std;inline void splay(int&v){ v=0;char c=0;int p=1; while(c<'0'||c>'9'){if(c=='-')p=-1;c=getchar();} while
2016-05-31 10:40:05
936
原创 bzoj 4460 : [Jsoi2013]广告计划
脑残一下午首先，对于所有字符串建立后缀自动机这里可以是广义后缀自动机或者狭义后缀自动机，我会给出2份代码然后是匹配时间我们枚举答案，问题变成一个答案是否能够被成功匹配观察发现，如果当前答案为ans，那么1，1+ans，1+ans∗2……都会在一排一起出现同理2，2+ans，2+ans∗2……也会这样我们定义have[i][j]表示i，i+ans，i+ans∗2……是否在第j列出现这个可以在后缀自动机
2016-05-26 18:11:50
604
原创 中国剩余定理（CRT）
以前博客里面发过一篇，今天看了markdown语法，重写一次，复习&&练习markdown 内容：求 x1x_1 modmod p1p_1 = b1b_1 x2x_2 modmod p2p_2 = b2b_2 ........ xnx_n modmod pnp_n = bnb_n 考虑两个式子 x1x_1 modmod p1p_1 = b1b_1 x2x_2 modmod p2p
2016-05-23 17:02:58
964
原创 bzoj 4466 : [Jsoi2013]超立方体
这题有毒 首先，我们发现如果一张图合法，那么点数为2n2^{n}，边为2n−1∗n2^{n-1}*n 每个点度数为nn，并且图中没有奇数长度的环 我们可以假设00号点的新编号为0，并且把00点相连的边编号赋成1，2，4，8，16……1，2，4，8，16…… 然后bfs一遍，确定每个点编号 怎么bfs呢?我们注意到，两个点有边当且仅当两个点新编号二进制位差11 假设a−ba-b有边且a−c
2016-05-23 16:38:52
1088
原创 bzoj 4464 [Jsoi2013]旅行时的困惑
别信官方题解我们可以对每个节点维护有多少条 自己向儿子的边 和有多少条 儿子向自己的边对于一个节点，一条儿子向自己的边和自己向另外一个儿子的边可以直接合并成一条航线然后会有多余的，留到自己的祖先节点使用就好了感受一下，就是这个意思代码#include#define N 100010using namespace std;inline void read(int&a){
2016-05-22 20:25:22
898
翻译 bzoj3917 && apio2016练习赛T2 题解
CA那里有没有翻译的，本弱菜秉承着看不懂英文的原则翻译了一下（渣翻勿喷解决我们的这个任务，需要先解决一个更复杂的问题：我们对序列的第i个元素我们声明一个元素AiAi是第i位元素必须含有的数位对于我们最初的任务，Ai={di} (译者注：di是读进来的那个)让N=(X)y y是x%10(也就是N的最后一位)，X=N/10 (译者注：N=X*10+Y)当我们确定y的一个可能
2016-05-04 10:43:47
1518
2
原创 SCOI 2016 bzoj 4567~4572 题解
bzoj 4567 [Scoi2016]背单词首先，我们发现如果有S(a)是S(b)的后缀，那么S(a)一定先加入那么倒着建字典树，每次dfs自己所有的儿子，看哪棵子儿子结束节点最多，按照这个顺序贪心儿子结束节点：遍历当前节点子树能够到达并且不经过其他结束节点的节点什么意思呢，假设说我们有一个aabb 有一个abb，那么我计算abb的时候可以忽略aabb的贡献，这两个串对于 b 只
2016-04-28 22:24:28
2321
2
原创 bzoj 4494 题解
首先感谢某些大神帮我解决此题我们可以把所有的长度为前缀，后缀建字典树对于字典树深度为k的节点，可以合并在这个节点上的字符串那么相当于在一张图上跑最小点覆盖集此时我就不会了。。。跑去问，然后得到回复“这是一张二分图”为什么呢？我们可以把所有前缀放在一边，后缀放在另外一边，每一个字符串当做一条边，连接自己的前缀和后缀这样就变成二分图了，跑最大匹配（其实是最小点覆盖）就好了网
2016-04-27 11:33:55
709
原创 又是一个sb错误--附带 bzoj4530 大融合 题解
首先离线，把边建好然后再链剖线段树记录子树size和，然后记录哪些边链接了每次点亮一条边就把在下面的那个节点所在联通快的size在自己所有联通的祖先上加上线段树记录最后面是哪个节点没有点亮这样做是nlog^2的于是这题做完了，开始调第一个sb错：x=min(x,y);y=num[getfa(b[i])];写成了x=min(x,y);y=num[f[b[i]]];
2016-04-18 14:57:46
722
原创 bzoj1070--写下一个傻逼错误，警示自己
本来是一道正常的费用流可是我调了一早上为什么呢spfa里面有这么一句话#define inc(i) i++;if(i==1005)i=1;bool spfa(){ int head=0,tail=1; memset(dis,63,sizeof dis);dis[0]=0; while(head!=tail){ inc(head);int v=dl[head];exsit
2016-04-15 15:52:19
1035
原创 CQOI2016 day2 模拟赛总结
T1N=pqr=(p-1)(q-1)ed=1(mod r)c^d=n(mod N)第一步rho，第二步直接算第三步exgcd,第四步快速幂强行算就可以了exgcd忘开longlong 100->30T2蜜汁题意读懂过后发现建字典树然后随便维护个单调栈搞搞就OK了时间nlognT3每次考虑把最大的出堆，把次大的入堆hash去重这样是
2016-04-14 16:26:49
416
原创 FFT模板
四川省选不考我就一直没没管，现在要抓起来了抄黄学长的版，把他改快了不少，能凑活着用了这个板是做高精度乘法的//Copyright(c)2016 liuchenrui#include#define pi 3.1415926535897932384626using namespace std;inline void splay(int &v){ v=0;char c=0;int
2016-04-13 11:11:08
385
原创 CQOI2016 day1 总结
怎么发一次格式抽一次T1打表发现答案小于n考虑求出S,T的最小割，并且提取出在S这一边和在T这一边的点集考虑S'属于S这一边的点集，T'属于T这一边的点集，那么S'和T'的最小割可以用其他两个点代替借助bzoj2229黄学长的一句话：注意这样一个事实：如果(X,Y)是某个s1-t1最小割，(Z,W)是某个s2-t2最小割，那么X∩Z、X∩W、Y∩Z、Y∩W这四项不可能均非空
2016-04-12 18:36:41
815
原创 Scoi 2016 省选酱油记
Scoi2016 酱油记&&游记day-3：心态开始不稳，各种浮躁，调整day-2：一波模拟赛拉回状态，准备省选day0：看大家互相奶，说说笑笑，其实心里很难受，晚上去了神大，破天荒的10点过睡觉了day1：上考场辣T1：这画风不对啊。。省选不会这么简单。。写到一半，后面同学开始问题意，吓得我赶紧看了一波题。。好像并没有什么问题啊。。对拍挂后台不管了T2：树上问题+卡空间，
2016-04-11 15:22:49
1830
原创 关于如何减小线段树常数
以前写线段树常数巨大，因为懒所以一直没改，今天终于下定决心把线段树常数调小0.位运算，前置技能1.非递归是一定要有的，以前觉得非递归特别特别麻烦，今天写了一下发现比递归好写2.不要一直改变l，r，能在build时记录下来就不要每次更新了3.能从下往上修改就从下往上吧4.线段树不管什么地方，加一句话常数都会变大，如果是加个函数就更大了比如说我们会记录最大值mx[now]=
2016-03-07 13:22:43
2237
原创 整体二分&&bzoj 2738学习笔记
整体二分大概就是这么个东西：二分答案，对当前二份出来的答案有影响的元素扔进集合中，然后拿出当前当前答案有贡献的询问来更新感觉还是抽象了一点，那么来说道题吧给你一个N*N的矩阵，每次询问一个子矩形的第K小数。首先离线所有询问，将矩阵按大小排序二分答案，将小于答案的数扔到树状数组里面，询问当前询问矩阵中有多少合法的数如果多了把当前询问下沉，否则上浮所谓下
2016-03-02 14:05:19
850
原创 SCOI2015 day1
第二次做这套题了。。结果还是太naiveT1一个矩阵 n*m，选出n个数并且不在同一行同一列二份答案转换为判定问题，看看够不够k个如果在一行在一列有冲突怎么解决呢？网络流经典模型！如果一个符合要求，连接该点所在的行和列即可最大流满流的话就是合法的答案T2当年觉得需要离散化呢，现在写一下发现是想多了维护f[i][j]，表示i个人向前2^j传到达的人在环上？倍长
2016-02-03 10:45:56
705
原创 bzoj 4404 [Neerc2015]Binary vs Decimal题解
首先声明这题不打表可以过的。。只是我太笨了先说下做法 我们可以从一个合法的数XT，T是XT的后缀，那么T也是合法的我们得到一个合法的T，可以去试一下XT是否合法暴力枚举：//Copyright(c)2016 liuchenrui#include#include#include#include#includeusing namespace std;inline void
2016-01-24 10:24:43
3111
原创 Codeforces round 440 div2 总结&&题解
A答案显然，(A-1)/5+1B脑抽了最大答案为2^33,以为会爆longlong写了python写了就算了然后构造了数据去叉人。。。+1:-4Cnoip2010原题（导弹拦截）。，。。GTMDccf不卡特殊情况，，，粘板就WA啦D特判题。。注意T字形E莫队算法首先得到前缀xor和考虑[l,r]->[l,r+1],加入r+1，询问在r+1的前缀有
2016-01-24 09:54:36
575
原创 Educational Codeforces Round 6 题解&&代码
A设坐标(x1,y1)(x2,y2)答案max(abs(x1-x2),abs(y1-y2))B预处理出来每个数字要用多少。。暴力就好如果是10^12也不难（可以数位dp）C贪心就好，每次发现重复的就重新计数写T了一次。。自己的程序弱可以被卡到n^2，考完才发现D大概就是暴力？还没写E维护一颗线段树，树上有60个标记，压到一个longlong里面可以少个l
2016-01-22 09:31:29
644
原创 bzoj4391 [Usaco2015 dec]High Card Low Card题解
这道题算是见过奶牛题里面最难的。。是我见识太少了绕了一大圈，问了Q巨才明白这题怎么做下面是Q巨原话 先考虑前i张牌，并且是大的赢那么我们就用尽可能小的能赢对面的牌来打然后扫一遍就可以知道i=0,1,2,3,...,n时最多能赢多少同理倒着扫一遍小的赢的情况……然后枚举分割线 but……这样做的话可能会出现，一张牌被用了多次的情
2016-01-21 17:19:27
1538
原创 各种模板
LCTint c[N][2],st[N],size[N],fa[N],rev[N],next[N];bool isroot(int x){ return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}void pushup(int x){ size[x]=size[c[x][0]]+size[c[x][1]]+1;}void pushdown(int x){
2016-01-20 16:27:25
981
原创 WC2010 排序机
数据特点1.小数据 √2.随机 √3.随机 √4.链 √5.tarjan √6.菊花图 √7.菊花图 √8.满二叉树 √9.满二叉树 √10.完全二叉树 √一个一个点说1.手玩就好啦2.搜 手动迭代加深//Copyright(c)2016 liuchenrui#include#include#include#include#in
2016-01-19 14:33:12
782
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人