- 博客(60)
- 收藏
- 关注
RSS订阅原创 12345
割地求和题目背景相传，古时候有一片富饶的地方，叫比特兰。比特兰有两个国家，一个是河德国，一个是皮河德国（“皮”在比特语有“像pig一样愚蠢”的意思）。河德国认为皮河德国的国名在辱骂自己，于是挑起了战争。遗憾的是，河德国战败了。眼看皮河德的军队兵临城下，河德国王想到了一个缓兵之计：割地求和！国王发现河德国的国土呈条状，于是将国家割成n段，第iii段和第i+1i+1i+1段(1≤i&...
2019-11-24 09:04:22
491
1
原创 半平面交板子
O(n2):O(n^2):O(n2):#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define db
2019-01-08 00:24:41
233
原创 最假女选手
#include <stdio.h>#include <iostream>#include <algorithm>#include <cstring>using namespace std;#define Ls p->ls#define Rs p->rs#define mid ((l+r)>>1)#define...
2019-01-06 16:25:16
403
原创 多项式全套（待续）
#include &lt;stdio.h&gt;#include &lt;iostream&gt;#include &lt;algorithm&gt;using namespace std;const int P=333333,MOD=998244353;inline int add(int a,int b){a+=b;return a&gt;=MOD?a-MOD:a;}inline
2018-12-31 16:31:46
208
原创 锕——放一个(不)通用的二分栈优化决策单调性DP板子
返回值为在最优条件下使用最少点数int Gans(ll del,int n){ int hd=1,tl=0; st[0]=1; qu[++tl]=0; for(int i=1;i&amp;lt;=n;i++) { while(hd&amp;lt;tl&amp;amp;&amp;amp;st[qu[hd+1]]&amp;lt;=i)++hd; int now=qu[hd]; f[i]=G(i,now)+d
2018-12-25 08:42:01
327
原创 论抱大佬大腿的重要性——第九届大学生程序设计大赛
#define owo Newuser#define OB OBlackDay 0：碗了OB出的模拟赛，在没有主力队员（OB）的情况下挣扎了三个小时。。。居然没有垫底。。。Day 1：保证11小时的睡眠，下午头脑比较清醒。食堂饭菜真的不敢恭维 居然没有土豆，，但是有水果居然没有提前5分钟发题面。。。拿到尸体，先分尸，，一共八道题，先拿到G。。我一看，∑i=1n∑j=1mlc...
2018-12-08 19:39:02
315
1
原创 「ZJOI2016」大森林
题目描述小 Y 家里有一个大森林，里面有 nnn 棵树，编号从 111 到 nnn。一开始这些树都只是树苗，只有一个节点，标号为 111。这些树都有一个特殊的节点，我们称之为生长节点，这些节点有生长出子节点的能力。小 Y 掌握了一种魔法，能让第 lll 棵树到第 rrr 棵树的生长节点长出一个子节点。同时她还能修改第 lll 棵树到第 rrr 棵树的生长节点。她告诉了你她使用魔法的记录，你能不能...
2018-12-04 18:09:32
411
原创 「2017 山东二轮集训 Day3」第一题
题目描述体节贪心，每人每次分给的一定是所需代价最小的v[i]−1v[i]-1v[i]−1个，且分给他的只需要比上一个人多一个。代码#include <stdio.h>#include <iostream>#include <algorithm>#include <cstring>#define ll long longusing...
2018-11-18 11:14:02
2158
原创 NOIP2018 游记
Day 0 ：考了模拟赛，两道题爆零，完美的开端。。。Day 1 ：早饭很反常地吃饱了。。。拿到题，我一看，哇，T1好像以前见过啊。。。但是以前好像没做啊。。。。慌乱的想了一会儿，好像有思路了T2一眼就感觉是迭代加深。。。（逃T3没啥思路。。然后回去敲完T1，写对拍。。。又观察一下T2。。。感觉搜索没法写啊。。心态崩了，上个厕所~回来观察一下样例，突然感觉答案一定只选了给的集合...
2018-11-12 16:57:50
218
原创 Trajan
void dfs(int x){ inst[x]=1; st.push(x); dfn[x]=low[x]=++Time; for(int t=las[x];t;t=nn[t]) { int y=e[t]; if(!dfn[y])dfs(y),low[x]=min(low[x],low[y]); else if(inst[y])low[x]=min(low[x],dfn[y...
2018-10-25 22:12:09
229
原创 图的割点
好像快把割点怎么求忘了。。。复习一下#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int Q=111111;int ans=0;int e[Q<<1],nn[Q<<1],las[Q],inc=0;int d...
2018-10-24 23:29:22
153
原创 扩展Lucas板子
实在看不惯自己以前的代码风格，改了一下。。。#include <cstdio>#include <iostream>using namespace std;inline int add(int a,int b,int p){a+=b;return a>=p?a-p:a;}inline int ch(int a,int b,int p){return...
2018-09-08 18:54:53
224
原创 【巴蜀】士兵训练
题目描述待会儿补输入格式待会儿补输出格式待会儿补样例输入5 2 1 1 2 2 2 1 1 5 4 2 2 3 3 1 1 2样例输出13 3样例输入27 3 1 1 2 2 3 3 3 0 1 3 5 2 2 0 4 1 3 1 2 2 1 2 3样例输出25 3 4题解0817...
2018-08-17 16:10:02
457
原创 【NOIP2017】宝藏
题目描述题目描述见此处题解“所谓DP，不过是压缩了状态的暴力而已”——scαpescαpesc\alpha pe 看到数据范围，应该比较容易往状压的方向想。 我们观察哪些东西会影响答案的计算，需要作为状态。 题目让我们生成一棵树，每条边的贡献和父亲方的深度有关，所以需要深度。 既然规定了深度，那么就很容易想到需要记录当前深度的点有哪些。。 为了方便转移状态，还需要记录已经和根...
2018-08-13 00:35:40
1148
原创 8102正睿oi暑期集训营欢乐附加赛2——花样翻车夜
这场比赛打得简直精彩。。。三道题爆零，Rating-192。。。心态爆炸 还是简述比赛的心路历程吧。。。 睡过头，看题时比赛已经开始，逐渐慌张。。。 想到是“普及组”题，T1瞟一眼直接想到方法。。。看到排行榜上已经有人过了样例，飞速敲完代码，提交。。。 结果我被自己手构的样例卡住了。。。死活想不出正解，打完暴力溜掉。。 由于前一题的恐惧，第二题发现没有太多思路就打暴力走人。。 T3毫无...
2018-08-10 00:06:25
669
原创 【ZROI8102 D2T2】配对
题目描述给定一棵 n 个点的边有长度的无根树，小 A 的班里一共有 m 个男生和 m 个女生，他们各自会等概率出现在树上 n 个点中的某一个，(注意同一个点上可能会出现多个人)。然后小 A 会将他们配对成 m 对男女，设dis[i]dis[i]dis[i] 是第 i 对男女在树上的最短距离，小 A 会选择使得 ∑mi=1dis[i]∑i=1mdis[i]\sum^m_{i=1} dis[i...
2018-08-06 01:19:22
308
原创 Unknow
题目描述给定长度为n的序列｛a｝，求∑ni=1∑nj=iMax[i,j]∗Min[i,j]∑i=1n∑j=inMax[i,j]∗Min[i,j]\sum_{i=1}^{n}\sum_{j=i}^{n}Max[i,j]*Min[i,j] Max和Min为对应区间内的极值数据范围1≤≤\leqn≤≤\leq1e5，a[i]≤≤\leq1e9题解不要问为什么用分治，我也不知道 ...
2018-08-01 01:21:24
464
原创 GGG——六月月赛Round2
这场考试，可以说是暴露出了很多问题吧。。。 A题。。。还好，单调栈就能解决。。 B题。。。把数据范围看错了，一直在想整体二分。。并且低估了NKOJ的运行速度，冥思苦想如何优化。。。 C题。。一眼题，可惜手贱打错了数组大小。。。 D题。。。完全没往最短路方向想。。。DP敲G了。。。但是好像DP也做不了。。 rank倒数第二。。。 感觉以后看题要更仔细，考前还是要复习各个知识点（至少名字过...
2018-06-30 23:20:03
201
3
原创 二逼平衡树【树套树】
问题描述您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x，且最大的数) 5.查询k在区间内的后继(后继定义为大于x，且最小的数)输入格式第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数，表示...
2018-06-24 23:00:14
275
原创 【NKOJ3776】工资管理
问题描述何老板的公司有n名员工，编号1到n。一开始所有员工的工资都是0。根据何老板的心情好坏，可能出现下列两种针对员工工资的操作： 1.U x y 改工资操作：何老板将第x号员工的工资改成了y； 2.Z x y 减工资操作：何老板生气了，他想选出x个员工，并将他们的工资全都减去1。何老板想知道，他能否一口气进行y次这样的减工资操作。能输出TAK，否则输出NIE。注意，员工的工资不能为负。...
2018-06-24 22:06:13
235
原创 需要修改的后缀自动机模板
#include <cstdio>#include <algorithm>#include <iostream>#include <cmath>#include <cstring>using namespace std;int tot=0,e[500000][26],maxn[500000],par[500000];int ...
2018-05-21 19:26:36
110
原创 石乐志的CQU比赛
早上，怀着休闲的心情来到比赛楼，乱打一套模板，努力听完领导的长篇大论。。。 比赛开始。。。 A题非常water，直接输出答案即可，只是有坑点。但我们队坚持天真地认为题目不会那么坑，两发WA就出来了。。。于是A题愉快地带来了69分钟的罚时。。。 B题似乎是（PHD大佬的）语法基础。。。 C题似乎（在PHD大佬眼里）是KSM板子。。。 D题表面上是SPFA判环，但会T。。。。。我打了份DFS...
2018-05-20 15:00:18
168
原创 【作死】用Hash代替Manacher
Hash求最长回文串的方法，O（NlogNlogNlogN）的方法应该比较好想，枚举中点+二分答案即可。 至于O（n）算法。。。 假设我们已经知道了前i-1个数能构成的最长回文串长度lans，那么前i项的长度ans应该是lans、lans+1、lans+2中的一个。 然后枚举各情况即可。int Ex_Manacher(){ int ans=0; for(i=1;i&amp;lt...
2018-05-16 21:23:23
173
原创 APIO2018游记
Day 0:碗了一套APIO2015的题。由于OJ没有打包测试的能力，加上试题暴力分分高，居然在没有AC的情况下上了200。信心满满。 Day 1：到北京已经是中午。午饭异常拥挤，开始怀念南开食堂。下午去清华膜拜nodgd和Wo_Ai_Wang_Yuan，共进晚餐。 Day 2：开始讲课了。第一位老师讲的是计算机与哲学。啥都没听懂，只是知道了有一系列的折纸问题。第二位老师较为有趣，讲了图像处理...
2018-05-14 22:11:51
288
原创 过不了编译的树剖板子
没有查过错。。。 很可能有问题。。。const int Q=50000;int f[Q],id[Q],dep[Q],bs[Q],si[Q],toap[Q];int last[Q],e[Q],nn[Q];void Find_Best_Son(int x){ si[x]=1; int now=0; for(int t=last[x];t;t=nn[t]) ...
2018-05-11 22:17:35
124
原创 非常搞笑的LCT板子
const int Q=500000;int ls[Q],rs[Q],si[Q],v[Q],f[Q];bool lazy[Q];bool Isroot(int x){return ls[f[x]]!=x&&rs[f[x]]!=x;}void update(int x){si[x]=si[ls[x]]+si[rs[x]]+1;}void lx(int x){ ...
2018-05-11 21:46:39
235
原创 多项式开方板子
注意常数项要手动开方void My_Sqrt(int a[],int Sqrt[],int toap){ if(toap==1){Sqrt[0]=Get_Sqrt(a[0]);return;} My_Sqrt(a,Sqrt,toap>>1); fill(Sqrt+(toap>>1),Sqrt+(toap<<1),0); co...
2018-05-07 09:26:17
242
原创 【NKOJ 3699】送披萨
问题描述何老板开了一家披萨店，有一天突然收到了n个客户的订单。 何老板所在的城市只有一条笔直的大街，我们可以将它想象成数轴，其中位置0是何老板的披萨店，第i个客户所在的位置为Pi,每个客户的位置都不同。如果何老板给第i个客户送披萨，客户会支付Ei-Ti块钱，其中Ti是何老板到达他家的时刻。当然，如果到得太晚，会使得Ei-Ti<0,这时，何老板可以选择不给他送餐，免得他反过来找何老板...
2018-05-06 21:46:07
1625
7
原创 多项式除法板子
借鉴了OBlack大神的模版 见于NKOJ3215#include <cstdio>#include <algorithm>#include <iostream>using namespace std;const int Q=500000,MOD=998244353;inline int add(int a,int b){a+=b;return...
2018-05-05 17:27:36
329
原创 乱搞的随机数
可能时间消耗稍微多一点。。 但应该比较随机。。。#include &lt;cstdlib&gt; #include &lt;cstdio&gt; #include &lt;ctime&gt; using namespace std; bool a_rand() { int t=0; for(register int i=rand()%3;i&gt;=0;i--
2018-05-05 16:22:36
165
原创 多项式求逆板子
建议搭配NTT板子食用~ 并且注意，函数结束后有可能需要清空[toap，2*toap)的值，不清空可能会爆void GetInv(int a[],int ni[],int toap) { int i,now; ni[0]=ksm(a[0],MOD-2); for(now=2;now<=toap;now<<=1){ fill(...
2018-05-05 16:16:02
171
原创 应该正确的过不了编译的Hash表板子
膜数可改。。const int MOD=72227 or 66666 or 997,Q=???;int las[MOD],v[Q],nn[Q],be[Q],inc;void _init(){ memset(las,0,sizeof(las)); inc=0;}int _find(int k){ int x=k%MOD; for(int t=las...
2018-05-05 16:11:26
192
1
原创 NTT模版
emm 这好像是我第一次放模版。。 但是很懒，不想放头文件，反正函数部分对了就好吧。。。const int Q=500000,MOD=998244353;inline int add(int a,int b){a+=b;return a<MOD?a:a-MOD;}inline int sub(int a,int b){a-=b;return a<0?a+MOD:a;}...
2018-05-05 15:53:48
175
原创 【CodeForces】528D Fuzzy Search
题目描述Leonid works for a small and promising start-up that works on decoding the human genome. His duties include solving complex problems of finding certain patterns in long strings consisting of let...
2018-04-21 16:39:25
245
1
原创 [CodeChef] COUNTARI
问题描述给定一个长度为N的数组A[]，求有多少对i, j, k（1<=i输入格式第一行一个整数N（N<=10^5）。 接下来一行N个数A[i]（A[i]<=30000）。输出格式一行一个整数。样例输入10 3 5 3 6 3 4 10 4 5 2样例输出9题解PS：之后讲的“中间数”即为A[k]-A[j]=A[j...
2018-04-20 09:15:04
277
原创 关于差分约束的一点点点点思考
复习差分约束时，突然忘了为什么求最大解跑最短路，求最小解跑最长路。。。所以记下来，怕以后忘了。。。 何老板的证法是这样的： 证明最短路（NKOJ3459）： 或者这样： 这两张图片都可以从老板的啪啪T中找到然后。。我看不懂啊。。。 自己慢慢想，似乎找到一种较为易懂的方法（应该是对的吧。。。） 先说最短路吧。 显然，对于dis[y]，它最后一定是由某一条边更新而来，即dis...
2018-04-19 15:59:11
164
原创 清洁机器人
//何老板翻译问题描述何老板的公司生产了一种机器人，可以用于在运动会后清理运动场上的垃圾。在机器人开始工作前，给出了一张网格状的地图，每个包含垃圾的格子都被标记上了“G”。所有的机器人一开始都位于西北方的那一角，在工作结束时所有的机器人都会走到东南方的那一角。每个机器人只能往东和往南两个方向行走。一走到有垃圾的格子，机器人就会把垃圾清理掉。一旦机器人走到了东南方那一个角，它就会自动切断...
2018-04-14 21:01:55
1138
原创 【BJOI2014】大融合
问题描述输入格式第一行包含两个整数 N,Q，表示星球的数量和操作的数量。星球从 1 开始编号。 接下来的 Q 行，每行是如下两种格式之一： A x y 表示在 x和 y之间连一条边。保证之前 x 和 y 是不联通的。 Q x y 表示询问 (x,y)这条边上的负载。保证 x和 y之间有一条边。输出格式对每个查询操作，输出被查询的边的负载。样例输入18 6 ...
2018-04-06 13:44:13
150
原创 【WC2006】水管局长
问题描述SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。...
2018-04-06 03:31:13
328
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人