- 博客(405)
- 收藏
- 关注
RSS订阅原创 USACO FEB18,Platinum
slingshot 题意：给定n个单向传送门(a,b,c)和m次询问(x,y)，求至多用一次传送门的最短路径长度。 即求min(|x-y|,min{|a-x|+|b-y|+c})，考虑分类讨论后将绝对值打开，用主席树维护四个方向上对应的pa+qb+c(p,q为-1或1)的最小值即可。AC代码如下：#include<bits/stdc++.h>#define l...
2018-02-28 08:13:02
1423
1
原创 JOI-2016/17 春季合宿 切题记
17年的合宿好难啊。。。感觉是我做过的最难的一套题（没有之一）了。。。但是可能也是价值最高的？Day1： T1 Cultivation：给你一个H*W的网格，有N 考虑将上下和左右分开来考虑。对于一维的情况，求出A,B,C，分别表示最左边的点向左的距离，相邻两个点的最大距离，最右边的点向右的距离，则答案为max(A+C,B)。 现在考虑将向左
2017-12-28 20:47:26
2794
1
原创 USACO DEC17,Platinum
第一次打usaco，感觉题目还挺有趣的。（为啥感觉美国人的英语比日、俄的英语还要难读呢）Standinfg Out from the Herd. 题意：给n个字符串，对每个字符串求有多少本质不同的子串只在这个字符串中出现。 这题我直接求了一个广义后缀自动机，然后给每个点一个标记表示这个点对应的子串是否只在某个字符串中出现。然后随便统计一下就做完了。O(N...
2017-12-20 09:54:22
812
2
原创 atcoder CODE FESTIVAL 2017 qual A 手速（雾）赛
这个比赛看起来好像挺重要的，，（结果来了一众大佬谁都打不过qaq） A，B题不知道是干什么的 C题（其实也是不知道在干什么）就是给一个字母矩阵，重排列后问是否能使它水平轴对称+竖直轴对称。 可以发现一个矩阵最多由三部分组成：1.中心点，需要1个字母；2.中轴线，需要2个相同字母为1对填上去；3.其余部分，需要4个相同字母为1组填上去。显然能填3就能填
2017-09-25 07:58:52
1595
原创 NOI2017 游记
很幸运地搭上了前往绍一的末班车，抱着稳赚不亏的心态踏入了绍一 夕阳余晖洒下，高高的玻璃外墙上，泛起点点金光Day -1 报到日 到了绍一已经错过了饭店，在外吔饭又辗转不少，回到寝室有点头痛，，qaq。于是睡了一觉，不知道和我们同寝室的另外两位绍一大佬怎么样啊，， 然而事实是他们至始至终都没有出现过，， 晚上开了一道
2017-07-21 15:10:09
5067
4
原创 CTSC&APIO2017 后记
似乎这个时间写有点奇怪 果然是NOI结束无事可做的菜逼选手CTSCday 1 T1一眼50，本着ctsc100+就是胜利的原则，果断放。 T2感觉和ioi那题很像，感觉是加强版，那应该就是在直径上做吧。然而本着这是ctsc，必有高论的原则，并没有去写，，， T3不知道是什么东西，写个线段树维护矩阵怎么样啊，，
2017-07-21 15:09:35
1546
2
原创 ZJOI2017 酱油记
考挂了，自己菜，怪谁喽。 早上闹钟似乎并没有叫醒我们，，qaq，7点被老师门铃按醒了。 开场看了一遍题目，感觉T1的50分挺简单的，T2可能需要一点推倒，T3好大，果断10分。 推了T2发现是一个后缀和，然后要特判0的情况，于是就转化了为判断a[l-1]和a[r]是否相同，直接线段树维护一个*a+b的标记即可。 写完了发现过不了大样例
2017-03-23 20:51:49
2293
原创 uoj 279: [清华集训2016]温暖会指引我们前行
考前鏼一题保平安，，求明天rp++ 显然就是lct维护动态最大生成树，然后就没了。（写得最短好开心啊>. 另外有没有老司机告诉我findroot的时候不pushdown究竟会不会出问题啊，，在线等，挺急的。AC代码如下：#include#define N 400005#define isrt(x) (c[fa[x]][0]!=x && c[fa[x]][
2017-03-22 19:58:34
1535
4
原创 bzoj 3238: [Ahoi2013]差异 后缀树
学习了一下后缀自动机转后缀树的方法。虽然可能这道题目后缀数组也可以做。 考虑后缀自动机的parent，它对应的是比x的right集合略大一点的那个节点；对应到后缀树上，可以发现在缩边后对应的就是y的父亲。 但是后缀自动机求得实际上是所有前缀倒过来后的后缀树；因此把原串反过来跑sam，然后x连向fa[x]就是后缀树了；每个点的len实际上就是这个节点的深度。
2017-03-16 08:05:03
800
原创 bzoj 3528: [Zjoi2014]星系调查
这道题目，只要看懂题意，敢于展开，就是一道初中数学好题。 首先设直线为y=kx+b，那么可知答案为Σ(kxi+b-yi)/(k^2+1)，展开以后维护若干个东西就可以化简为(Ab^2+(Xk+Y)b+Uk^2+Vk+W)/(k^+1)的形式，其中A>0，那么以b为主元，最小值为(4ac-b^2)/4a，化简一下可以变成Ak^2+Bk+C/(k^2+1)的形式（A,B,C不同于之前的A
2017-03-15 08:05:41
1136
原创 Codechef 2017 March Challenge 简要题解
在比赛进行到一半的时候才参加，，导致challenge没法搞得很好 写一个简要题解吧，，challenge太差了就不放了Xenny and Alternating Tasks：直接按照题意模拟即可。Bear and Extra Number：首先处理重复；否则一定是极值。Bandwidth of a matrix：二分答案，然后贪心多放1，判断是否能合
2017-03-13 21:01:57
1427
2
原创 bzoj 3460: Jc的宿舍 莫队算法
一开始感觉是分块，但是好像不太兹瓷。于是觉得是莫队。 但是他有强制在线，，而且莫队还是N^1.5logN的，感觉很不兹瓷。 后来发现是假的在线。。。并且找到了一个题解发现就是N^1.5logN的，然后就做完了。 yy了一个做法就是每16个分成一块，然后O(16)修改，O(N/16)询问，配合莫队就是O(16N^1.5+N^2/16)，不知道能不能过（当然不
2017-02-19 14:06:00
4136
原创 THUWC2017 酱油记
从绍一滚到了学军，，持续滚粗之旅。day -1辗转到了绍一（1h的公交好累啊），已经19:00+了，然后进入学军报道，去了一趟寝室感觉好大啊，比某镇上的中学高到不知道哪里去了。当年ZJOI看宣传片的时候以为是ps的，现在发现居然是真的这么好。于是20:00左右噎了晚饭，可惜由于肚子不舒服不能噎很多。。。qaq晚上终于可以洗澡了，浑身舒爽。day 15:00被冻醒，被
2017-02-11 21:25:13
1730
原创 WC2017 酱油记
WC接THUWC，可以体验连续滚粗的快感。day -5 上了高铁发现居然和老师邻座，，， 15min的高铁也是劲啊。 晚上文艺表演，各种讲话，并没有什么兴趣。day -4 早上鏼鏼鏼讲字符串，大概还是能听懂一点的。 下午rzz将一个ulam猜数，感觉到了最后就是给一个估价函数？不是很懂有什么用。 myh讲ioi窝居然有
2017-02-08 20:14:10
2081
原创 bzoj 2555: SubString 后缀自动机+lct
WC前鏼一题求平安qaq，，，rp++ 首先求出后缀自动机，然后相当于统计一个点的right集合的大小；转化为一个树动态加点和增减边的lct问题，然后就码码码就好了。AC代码如下：#include#define N 1200005#define isrt(x) (c[fa[x]][0]!=x && c[fa[x]][1]!=x)using namespace std
2017-02-07 20:59:41
600
原创 uoj 279: 数据分块鸡 动态规划+可持久化线段树
一开始看到这道题目的时候以为是dp+线段树修改什么的来维护。 但是n=50000好奇怪啊。 看了题解才知道原来是决策单调性+暴力可持久化线段树求某一个区间的花费。 刚好没有怎么写过dp决策单调性的优化，就写一发吧。AC代码如下：#include#define ll long long#define N 100005#define M 2
2017-02-02 18:32:42
873
原创 Codeforces Round #393 (Div. 1) 螺杆记
这场比赛真是啊，，各种卡题意，好气啊。 英语太差没有人权啊TAT，就不能像上一场vk B题那样只有1行描述吗，，好难受啊。 A题好长啊，看了10min才看懂；然后又爆了3发oj（1发样例）才过，心态瞬间不好了。 B题更长了，看了20min都看不懂，心态爆炸了。因为有几个细节一个没注意到，导致题意理解一直有问题。最后终于看懂了，就是一个超级simple的dp
2017-01-23 11:43:02
553
原创 BestCoder Round #91 hack大战
好像写得晚了一点。 题目还是可以的（虽然说C代码量有些偏大），但是在某些方面，，，就不说了。 前两题都是sb题。不过第一题这么明显的可以放负数居然让过了pretest，，强行为了hack而hack啊。导致最后在C题全部fst的情况下大家靠hack拉排名啊。想我这种打完就去水uoj群的就没希望了啊。 C题这种题目没有spj真是差评啊。 D题其实
2017-01-23 11:22:03
1124
原创 bzoj 4727: [POI2017]Turysta 图论
在与Claris谈笑风生和自己的思考后终于学会了竞赛图的哈密顿回路。 讲道理我以前连竞赛图是啥都不知道。 首先求出强联通分量+dp是没有疑问的。那么考虑一个强联通分量，有一个结论是竞赛图一定存在哈密顿路径，然后存在哈密顿回路当且仅当强联通。下面给出构造方法。 首先求哈密顿路径（见代码或百度即可）；然后将路径变成环，考虑一个环+一条延伸出去的链，那么要
2017-01-20 19:50:39
1477
原创 uoj 279: [UTR #2]题目交流通道 动态规划
期末考炸飞了啊QAQ求安慰。 首先特判不合法的情况；然后考虑没有权值为0的边的时候，一条边(i,j)如果可有可无（也就是存在k使得d(i,k)+d(k,j)=d(i,j)），说明i->j可以不经过(i,j)，也就是这条边只要取>=当前权值且 有0边的时候，把用0边连的全部缩成一个团然后像上述类似地处理不同团的连边；0边连的就是一个dp就好了。AC代码如下：#in
2017-01-15 20:56:59
623
原创 bzoj 4730: Alice和Bob又在玩游戏 线段树合并&博弈论
n居然是10w左右你敢信。。。连爆10+发OJ才发现。 首先给每一个子树一个sg值；考虑当前点所在子树的sg，枚举第一次删哪一个点，那么剩下一些子树，这些子树的xor就是这个后继的值，然后求mex即可。 考虑用线段树合并来维护。用线段树维护某一个要被删除的点在当前点的后继的值，那么更新就相当于全部抑或一个值，打标记维护即可。 查询就贪心向左走即可。AC代码如
2016-12-31 19:16:33
1732
原创 uoj 198: [CTSC2016]时空旅行
一道比较套路的数据结构题。而且写起来也挺顺的。 首先可以发现y和z就是来卖萌的，无视即可。那么考虑一个点（星球）位置为x0，费用为c0，那么询问x到它的总花费为(x-x0)^2+c0=-2x0*x+(c0+x0^2) +x^2，那么我们可以将一个点看做一条直线y=-2x0*x+(c0+x0^2)，那么查询就相当于是求在当前空间中所有直线在x点的值的最小值。 直接斜率
2016-12-08 12:53:30
1552
原创 bzoj 4573: [Zjoi2016]大森林 lct
这道题目，黈力给我讲过一个splay维护括号序列的方法，讲道理是很兹瓷的。 但是在uoj上我看到了一个小哥写得超级短。（还跑得很快）。就学习了一下。 首先离线然后从左到右扫树。 给每一个生长节点新建一个点。这样的话，删掉这个生长节点相当于把新建的点连到它之前建的新建的点上；加入这个生长节点相当于把新建的点连到生长节点上。然后对于这颗树中的点，我们可以
2016-12-08 11:21:02
2931
原创 bzoj 3786: 星系探索 splay
bzoj真是坑爹，本地跑的差不多的程序，指针比数组快到不知道哪里去了。 然后我就开始了艰辛的卡常数，最终比很多指针快多辣~~~ 由于有子树移动，那么考虑维护括号序列。也就是dfs入栈为'('，出栈为')'，然后'('为正的权值。那么子树移动相当于平衡树的分裂和合并。用splay实现。 PS：求卡常数大神优化代码>.AC代码如下（目前最快的）：
2016-12-06 20:21:07
943
原创 bzoj 4725: [POI2017]Reprezentacje ró?nicowe 暴力
第一眼看到这道题目的我是懵逼的。 然而这道题目并不能经得起推敲>.AC代码如下：#include#define ll long long#define N 10005using namespace std;int n,cnt,ans1[N],ans2[N]; ll a[N],c[N];map mp;int calc(int x){ int l=1,r=cnt
2016-12-04 19:53:26
1198
原创 NOIP2016 简要题解
如此水的数据，由于太弱没有AK，真是太菜了。DAY1：T1：这道题我只记得mogician和mengbier了，其余都忘光辣~~~。T2：考场上写了lca后的O(NlogN)的做法，但还是A了。 首先将一个人的跑步拆成两条链，考虑向上走的那一条链（另一条链同理），深度+时间的值是一定的。那么，考虑令这个人出发点x的深度为t，那么x~lca上的深度+观察时间的询问的答案都
2016-12-04 15:25:22
1209
原创 bzoj 4712: 洪水 树链剖分
利用待修改树上两点间gcd的想法，大概YY出了树剖的方法。 然后点开Disscuss，发现了immortalCO（%%%）的做法，发现把自己YY的细节都补充完了，感觉很兹瓷。 然而他说这是经典问题，对此我对自己狭窄的知识面的可怜的鏼题量感到有点内疚。 不过带修的独立集做法还是很兹瓷的！AC代码如下：#include#define ll lo
2016-12-04 15:03:44
1528
原创 NOIP2016 酱油记
Day1： 赛前被连续毒奶，感觉要gg。 结果真的gg了，大家再见。。T2 lca后的O(N)怎么做啊，QAQ。Day2： 翻盘失败，OI再见。
2016-11-19 14:17:55
1446
5
原创 bzoj 1179: [Apio2009]Atm tarjan
NOIP前鏼一题神清气爽。 首先强联通分量里面的一定要么都取要么都不取，那么tarjan缩点之后，在DAG上面跑dp即可。 NOIP2016 rp++。AC代码如下：#include#include#include#define N 500005using namespace std;int n,m,cnt,tot,dfsclk,tp,fst[N],
2016-11-18 21:25:53
1002
原创 hdu 5398:GCD Tree lct
注意到如果(x,y)连边，且d=gcd(x,y)使得d 然后从小到大枚举然后lct维护最大生成树即可。（结果暴力可以怒草lct，QAQ）AC代码如下：#include#include#include#define inf 1000000000#define N 200005#define M 1100005#define isrt(x) (c[fa[x]][0]!
2016-11-13 20:53:30
988
原创 hdu 5981:Guess the number 动态规划
套路题，而且我觉得它题目描述有问题，决策的方案和样例对不上吧。 考虑dp。令f[i]为i个数最优情况的答案，则枚举第一个决策点f[i]=min{j-1,f[i-j]}。显然最优决策点单调，而且最优决策点是一个范围，暴力求出左右最优决策点即可。 时间复杂度：右端最优决策点显然单调；最短最优决策点不单调，但是离i的距离单调递增，所以为O(N)。 defi
2016-11-13 16:12:03
2233
3
原创 bzoj 4717: 改装 二分+set
md一开始被套路了浑身难受。 首先把所有装备扔进一个set（要用好的姿势处理重复）排序。询问的时候就扫一遍set然后把区间内的拿出来，这样就是有序的了。然后二分答案，每个船做一次二分查找，得到 由于set重复的缘故WA了好几发，浑身难受。AC代码如下：#include#include#include#include#define N 100005u
2016-11-12 08:15:27
1091
原创 pa2010 切题记
没有题解好虚啊。。。剩下的题要么不会，要么做起来太慢感觉没意义，弃了吧。Algorithmic Engagements 2010TasksRectangles(Round 0)(10/10)Orienteering [B](Round 1)(10/10)Mushrooms [B](Round 2)(10/10)
2016-11-01 18:04:47
1219
原创 bzoj 2534: Uva10829L-gap字符串 后缀数组+线段树合并
不是很懂那些很短的代码是什么方法，感觉好大啊。。 首先跑一个后缀数组，然后按照height数组从大到小合并，那么合并的两部分的lcp就是height的值，那么用经典的启发式合并求出答案就好了。 本来想用set的，发现set不兹瓷查询第k大，又不想写平衡树，最后冷静了一下写了个线段树合并。 tm它居然是字符串，我一直以为是小写字母串，爆了好几发oj，
2016-10-12 20:43:59
888
1
原创 bzoj 2844: albus就是要第一个出场
首先就是一个线性基。然后不能放进去的相当于0，然后枚举前多少位和m相同，那么后一位比m小的方案累加入答案即可。AC代码如下：#include#define mod 10086using namespace std;int n,m,cnt,bin[35],bs[35],s[35];bool ins(int x){ int i; for (i=29; i>=0; i--) if
2016-10-11 19:00:26
607
原创 hdu 5932: Backpack on Tree 贪心+dp
因为ypa的要求就开了这道题。据说这道题目只有一个人当场过，而且ypa还说是动态树合并导致我走上不归路
2016-10-11 18:05:10
718
原创 Codeforces Round #374 (Div. 2) 终场翻盘记
讲道理这场cf本来是不想打的，因为感觉时间有点晚（主要还是国庆作业爆表了）。。后来不知道为什么还是决定打了。 开场前发现注册人数又8000+，（为什么我一打比赛就8000+啊） 挂了个vpn冷静一下。 开场看A，直接看样例，大概就是统计B的段数和每段的长度吧，很快打完了。然而不知道在想些什么一直在强迫症改输出格式（就是行末空格）晚交了一些，A
2016-10-01 09:48:27
1153
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人