- 博客(152)
- 收藏
- 关注
RSS订阅
原创 CSP-S 2019凉凉记
noip取消了前途未卜day-14开始停课开始中午晚起，早退打球的悠闲生活好好学文化课不好吗？训练的还可以，题都好好改了但比赛状态真的一般day-1酒店好评叫了个宵夜结果10:15才送到。。day1早餐好评密码：认真思考T1，直接转化成二进制就很好做了呀n有可能为64？，要开ull不管了，写个高精度啥都不用担心T2左括号为1右括号为-1，找前缀和相同就好了哦还...
2019-11-18 22:39:28
397
原创 半平面交
head=tail=0; fo(j,1,tot){ if (j>1 && abs(b[j].z-b[j-1].z)<=e) continue; while (tail-head>1 && delet(b[j].x,b[pre[tail-2]].x,b[pre[tail-1]].x)) tail--; while (t...
2019-07-10 19:45:04
147
原创 km标号算法
bool diss(int x){ int i,t; visx[x]=true; fo(i,1,c[0]){ if (!visy[i] && map[x][i]){ t=wx[x]+wy[i]-dis[x][i]; if (t==0){ visy[i]=true; if (!linky[i] || diss(linky[i])){ ...
2019-07-10 19:42:02
295
原创 exkmp
void make(){ mx=1,a=2; while (s[1+mx]==s[mx] && mx<m) mx++; nex[1]=m,nex[2]=mx-1,a=2; fo(i,3,m){ if (nex[i-a+1]<mx-i+1) nex[i]=nex[i-a+1]; else{ j=max(0,mx-i+1); while (s[i...
2019-07-10 19:38:27
131
原创 GDSOI2019颓废记
day0GDGDGD怎么这么惨啊。。就几个初中生参加初三太颓了，几乎每2周训练一次，一点效果都没有了开心腐败不过进入酒店，打开窗发现居然是一面墙然后和古爷去探索，结果是采光通道还去吓了下别人没有衣服不良心啊吃了家餐馆很开心day1睡的还可以第一题一眼trie，然后是高维前缀和，然后就弃了第二题一眼tarjan，打了个dp第三题。。我还是暴力吧。。第四题，打完暴力发现可以...
2019-06-01 17:55:59
268
原创 PKUWC2019纪中游记
day-4晚上考完化学被告知要停课训练半喜半忧吧，可以为冬令营做准备，写不了寒假作业day-3早起训练，但估计在比赛时还是睡了至少1个小时，只会暴力只改出了一题，还有一道分治fft在拖day-2继续训练，考着IOI赛制蒙了点分中途回去上了一节特辑英语课，结果被xc发现了。。day-1范老师出的题题很难，就是题答题的拼图福利很好，知道就去刚了，图好评day0...
2019-01-21 22:21:19
590
1
原创 pion8012记闭自
day0：校运会，机房刷了几道题找手感，期中考试成绩还不错，那个四大竞赛着实尴尬，数理化生修电脑点了个寿司，正常睡觉今年居然不开会day1：早上：司机技术真好，到考场还剩5分钟开始T1这不是道原题吗，ccf自己抄自己。。T2这个好像找个尽量小的集合表示所有数就可以了，虽然不知道怎么证但反证反正它就是对的，排序+完全背包走人此时才9:30，上了个厕所，听见coldchair已经a...
2018-11-13 21:48:44
183
原创 P3203 [HNOI2010]弹飞绵羊（LCT）
题目描述某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmo...
2018-08-24 20:53:25
159
原创 5813. 【NOIP提高A组模拟2018.8.14】 计算 （结论+背包）
descripitionData Constraint想法这题一看很神仙，只会暴搜这题一看很神仙，只会暴搜 这题一看很神仙，只会暴搜假设现在的数组x满足i∀[1..2m],xi∈Z+,xi|n假设现在的数组x满足i∀[1..2m],xi∈Z+,xi|n假设现在的数组x满足i\forall [1..2m],x_i\in Z^+,x_i|n然后就是找结论，如果集合f(x)=∏...
2018-08-14 16:25:25
227
原创 JZOJ5796. 2018.08.10【2018提高组】模拟A组&省选 划分(二项式反演容斥+拓展GCD)
description有mmm个数a[1..m]a[1..m]a[1..m],对于a[i]a[i]a[i],我们可以知道∑k∗a[i]i=(k−1)∗a[i]+1x[i]（k∗a[i]<=n）∑i=(k−1)∗a[i]+1k∗a[i]x[i]（k∗a[i]<=n）\sum_{i=(k-1)*a[i]+1}^{k*a[i]} x[i]（k*a[i]x[i]x[i]x[i]...
2018-08-10 21:17:16
220
原创 4372. 【GDOI2016模拟】识别子串(SAM+线段树）
题目有一个字符串SSS,T=S[i..j]T=S[i..j]T=S[i..j]是kkk的的识别子串当且仅当1.i<=k<=ji<=k<=jiTTT在SSS中仅出现一次 求每个位置最短的识别子串想法想到用SAM搞定每个子串的出现次数，然后用线段树区间修改SAM上的状态i表示的是以某个位置xxx为右端点，以x−len[i]+1....x−mi[i]+...
2018-07-13 22:40:18
318
原创 jzoj3304. Theresa与数据结构(cdq分治+扫描线+带修主席树)
题目3个操作1:在当前空间加入一个权值为1，坐标为(x,y,z)(x,y,z)(x,y,z)的点2：同1，权值为-13：查询当前空间中，(x,y,z)(x,y,z)(x,y,z)~(x+r,y+r,z+r)(x+r,y+r,z+r)(x+r,y+r,z+r)正方体中的点想法：猥琐的数据结构~~先讲讲扫描线，即在二维平面中，已知某些点，查询某个矩形的权值和先将xxx坐...
2018-07-10 16:41:18
246
原创 JZOJ4202. Shopping（点分治+树形依赖+多重背包）
题意：一颗树，每个点代表一个物品，空间c[i]c[i]c[i],数量d[i]d[i]d[i],价值w[i]w[i]w[i],现有一个空间为mmm的背包，选树上相互连接的物品，求最大价值想法：一眼树形背包，时间复杂度上天f[i][j]f[i][j]f[i][j]表示i的子树内，i必选一个，空间为j的最大价值时间复杂度O（n2m2dn2m2dn^2m^2d）由于选互相连接的...
2018-07-07 22:25:34
295
原创 Codeforces469div2F curfew(贪心)
题意：有n间宿舍实施宵禁：1.一个舍监从1走向n，另一个舍监从n走向12每个宿舍有a[i]a[i]a[i]个学生，且∑ni=1a[i]=n∗b∑i=1na[i]=n∗b\sum_{i=1}^n a[i]=n*b3舍监走到某个宿舍前，未上锁宿舍的学生可以走到距离当前宿舍不超过d的宿舍4舍监查某个宿舍时，如果宿舍人数<b<bn/2+1n/2+1n/2+1个宿舍归第一个舍监查...
2018-07-07 22:03:41
246
原创 JZOJ4196. 二分图计数(容斥)
题意： 二分图，左边n个点，右边m个点 左边每个点都与右边某一点不相连 令S表示选择左边点的状态集合，g（S）表示选择里面的点，且里面的点与右边某一点连接，且右边的点最多只能跟一个左边点相连，总共的方案数 求∑2n−1s=1S∗G(S)∑s=12n−1S∗G(S)\sum _{s=1}^{2^n-1} S*G(S) 想法： 比赛看懂题意，想到容斥...
2018-07-06 17:24:45
312
原创 3952. Fair Photography
Description数轴上某些位置有一个种类a，选一个最大的区间使得里面每个种类a出现的次数都相等而且种类个数》=kn<=100000,2《=k<=8,种类数《8Idea其实关于区间问题，都是各种套路这里我们可以选定状态s，规定我们选哪几个种类，这样符合的位置就会得出一个又一个互不相交的区间设得出一个区间[l,r]我们顺着扫一遍，记录当前位置到l里各种牛的个数，...
2018-03-07 21:12:04
346
原创 jzoj3950. 【湖南省队集训2014】Clever Rabbit
Decriptionf（x）=x的十进制从小到大排序后的数g（x）=x的十进制从大到小排序后的数求n为下所有f（x）-g(x)=x的x的平方的和mod qIdea首先把f(x)与g(x)的每一位各自相减，在不考虑进位退位的情况，差的绝对值会构成一个回文串而且回文对应的2位互为相反数！那么我们可以先构造出差的前n/2位，后n/2位就得出然后高精度+求出实际上的差再判断差...
2018-03-07 20:00:23
260
原创 读入优化
void R(int &x){ char C=getchar();x=0; for(;C'0'||C>'9';C=getchar()); for (;C>='0'&&C'9';x=x*10+C-'0',C=getchar());}
2018-02-06 20:03:32
174
原创 bzoj2301[HAOI2011]Problem b
Description对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。Input第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、kOutput共n行，每行一个整数表示满足要求的数对(x,y)的个数Sample Input22 5 1 5 11 5
2018-02-06 19:46:35
165
原创 manacher
#include #include #include #define min(a,b)(((a)using namespace std;const int maxN=40010;char c,s[maxN],t[maxN];int tot,n,i,wz[maxN],id,mx,len[maxN],ans,ans1;int main(){ //freopen("a.in","
2018-02-03 21:20:14
291
原创 回文树
JZOJ3654. 【APIO2014】回文串(palindrome)Description考虑一个只包含小写拉丁字母的符串 s。我们定义 s的一个子串 t的“出现值”为 t在 s中的出现次数乘以t的长度。 请你求出s的所有 回文子串中的最大出现值。Input输入只有一行，为一个只包含小写字母 (a−z) 的非空字符串 s。Output输出 一个整数，为 所有 回文子串 的
2018-02-03 10:15:05
150
原创 拓展gcd
void gcd(int a,int b) { int x1,y1; if ((a==1)&&(b==0)) { x=1;y=0; return; } gcd(b,a%b); x1=x; y1=y; x=y1; y=x1-(a/b)*y1; }
2017-12-28 19:00:10
213
原创 网络流
#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxN=1010,maxM=1000010;int last[maxN],tov[maxM],next[maxM],len[maxM],n,m,tot,i,x,y,z,s,t,gap[maxN],cur[maxN],an
2017-12-22 21:12:30
158
原创 4216. 【NOIP2015模拟9.12】平方和
Description给出一个N个整数构成的序列，有M次操作，每次操作有一下三种： ①Insert Y X，在序列的第Y个数之前插入一个数X； ②Add L R X，对序列中第L个数到第R个数，每个数都加上X； ③Query L R，询问序列中第L个数到第R个数的平方和。Input第一行一个正整数N，表示初始序列长度。 第二行N个整数Ai，表示初始序列中的数。 第三
2017-12-20 20:26:48
196
原创 splay操作集合
下传标记void back(ll x,ll y){ a[x]+=y,ans[x]+=y,add[x]+=y;}更新当前点的答案void update(ll x){ ans[x]=max(a[x],max(ans[tr[x][0]],ans[tr[x][1]]));}把标记传给儿子void clear(ll x){ if (tr[x][0]) back(tr[x][0],a
2017-12-20 20:23:25
159
原创 C++bitset学习小记
刚刚打过这道题： https://jzoj.net/senior/#main/show/3486里面用到了一个叫做bitset的东西总而言之，一个bitset存的是一个状态，一个二进制状态，不过可以快速统计其中1的个数，也可以快速改变一个位置的0/1状态.比如说一个两千位的数，如何存储它的状态？嗯，用bitset.然而bitset也有其缺点，就是它只能进行位运算以及一些简单的赋值.定义：#inclu
2017-12-06 21:26:17
170
原创 3486. 【NOIP2013模拟联考10】道路改建(rebuild)（2017.12A组）（tarjan缩环+拓补排序+DP+bitset）
Description人称不死将军的林登·万，与他的兄弟林登·图两人的足迹踏遍了地球的每一寸土地。他们曾将战火燃遍了世界。即使是lifei888这样的强悍人物也从来没有将他彻底击败。这一次，林登·万在N个城市做好了暴动的策划。然而，在起事的前一天，将军得知计划已经泄漏，决定更改计划，集中力量掌握一部分城市。具体来说，有M条单向边连接着这N座城市。对于两座城市A,B，如果它们能够通过单向边直接或间接的
2017-12-06 21:22:46
406
原创 5483. 【清华集训2017模拟11.26】简单路径
Description一棵树有n个节点，编号为0到n-1。有一条叫Owaski的狗在树上面走，每一次它可以从一个顶点走到它的任何一个相邻顶点。每个顶点有个可正可负的快乐度，Owaski也有一个快乐度，这个值最开始是0。在他到达一个 顶点的时候，他的快乐度将会加上该顶点的快乐度。当然有时候Owaski的快乐度会是负数，这个时候他会很难受于是会宣泄情绪让快乐度重新变成0。Owaski是一条喜新厌旧的狗
2017-12-01 20:39:27
187
原创 3472. 【NOIP2013模拟联考8】匹配(match)
Description给定k个字符串以及长度为n的母串可选字母的集合，问母串要完整出现给定的k个字符串的方案数，答案模1000000007，字符仅包含小写字母。Input第一行两个整数n、k，表示字符串的长度和给定字符串的个数。接下来k行每行一个字符串。接下来一行1个整数m表示可选字母集合内元素个数。接下来一行给出一个长为m的字符串，表示字母的集合（可能有重复）。Output一个整数ans，表示方案
2017-12-01 20:37:01
364
原创 3467. 【NOIP2013模拟联考7】最长上升子序列(lis)
Description维护一个序列，使它可以进行下面两种操作：1.在末尾添加一个数字x2.将整个序列变成第x次操作后的样子在每次操作后，输出当前序列的最长上升子序列的长度序列初始时为空Input输入文件lis.in的第一行有一个正整数n，表示操作个数。接下来n行每行有两个整数op，x。如果op为0，则表示添加x这个数字；如果op为1，则表示回到第x次操作之后。Output对于每次操作，在输出文件li
2017-12-01 20:27:25
551
原创 【NOIP2017提高组正式赛】列队
Description Sylvia 是一个热爱学习的女孩子。 前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。 Sylvia所在的方阵中有n × m名学生，方阵的行数为 n，列数为 m。 为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中从 1 到 n × m 编上了号码（参见后面的样例）。即：初始时，第 i 行第 j 列的学生的编号是(
2017-11-22 20:43:01
1397
原创 【NOIP2017提高组正式赛】宝藏
Description 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋，也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。 小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助
2017-11-22 20:31:49
906
原创 【NOIP2017提高组正式赛】逛公园
Description 策策同学特别喜欢逛公园。公园可以看成一张��个点��条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，��号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从1号点进去，从��号点出来。 策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公
2017-11-22 20:25:23
1177
原创 noip2017提高组小结兼期中考试总结
学军山寨：100+100+0+100+40+30=370 洛谷：100+100+0+100+60+30=390
2017-11-17 20:16:43
248
原创 4890. 【NOIP2016提高A组集训第14场11.12】随机游走 (2017.10B组)
https://jzoj.net/senior/#main/show/4890 DescriptionYJC最近在学习图的有关知识。今天，他遇到了这么一个概念：随机游走。随机游走指每次从相邻的点中随机选一个走过去，重复这样的过程若干次。YJC很聪明，他很快就学会了怎么跑随机游走。为了检验自己是不是欧洲人，他决定选一棵树，每条边边权为1，选一对点s和t，从s开始随机游走，走到t就停下，看看要走多长时
2017-10-30 10:57:35
229
原创 4888. 【NOIP2016提高A组集训第14场11.12】最近公共祖先 （2017.10B组）
DescriptionYJC最近在学习树的有关知识。今天，他遇到了这么一个概念：最近公共祖先。对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。YJC很聪明，他很快就学会了如何求最近公共祖先。他现在想寻找最近公共祖先有什么性质，于是他提出了这样的一个问题：n层的满k叉树T，求对于每一对(i,j)(1≤i,j≤T的点数)，L
2017-10-28 21:58:14
189
原创 Tarjan求lca
一个优秀的求2点lca的离线算法 把所有询问用前向星储存 然后当dfs到x时，如果存在一个询问（x,y）使得两个点都被访问过，那么就将y的父亲跳上去，直到不能跳为止，这个点就是它们的lca （等dfs某个点后再规定他的父亲） 否则就标记 跳父亲可用并查集的路径压缩void dfs1(int x1){ int i,y; bz[x1]=false; for (i=la
2017-10-25 21:10:50
213
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人