5 lych_cys

尚未进行身份认证

我要认证

这是一只沙茶

等级
TA的排名 6k+

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

WC2018 游记

       辣鸡出题人,毁我青春。作业题出出,交互库数据不是临时生成不声明。辣鸡游戏,退役保平安。

2018-02-24 18:59:52

JOI-2016/17 春季合宿 切题记

17年的合宿好难啊。。。感觉是我做过的最难的一套题(没有之一)了。。。但是可能也是价值最高的?Day1:        T1 Cultivation:给你一个H*W的网格,有N        考虑将上下和左右分开来考虑。对于一维的情况,求出A,B,C,分别表示最左边的点向左的距离,相邻两个点的最大距离,最右边的点向右的距离,则答案为max(A+C,B)。       现在考虑将向左

2017-12-28 20:47:26

USACO DEC17,Platinum

        第一次打usaco,感觉题目还挺有趣的。(为啥感觉美国人的英语比日、俄的英语还要难读呢)Standinfg Out from the Herd.        题意:给n个字符串,对每个字符串求有多少本质不同的子串只在这个字符串中出现。        这题我直接求了一个广义后缀自动机,然后给每个点一个标记表示这个点对应的子串是否只在某个字符串中出现。然后随便统计一下就做完了。O(N...

2017-12-20 09:54:22

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

NOI2017 游记

很幸运地搭上了前往绍一的末班车,抱着稳赚不亏的心态踏入了绍一       夕阳余晖洒下,高高的玻璃外墙上,泛起点点金光Day -1       报到日       到了绍一已经错过了饭店,在外吔饭又辗转不少,回到寝室有点头痛,,qaq。于是睡了一觉,不知道和我们同寝室的另外两位绍一大佬怎么样啊,,       然而事实是他们至始至终都没有出现过,,       晚上开了一道

2017-07-21 15:10:09

CTSC&APIO2017 后记

似乎这个时间写有点奇怪       果然是NOI结束无事可做的菜逼选手CTSCday 1       T1一眼50,本着ctsc100+就是胜利的原则,果断放。       T2感觉和ioi那题很像,感觉是加强版,那应该就是在直径上做吧。然而本着这是ctsc,必有高论的原则,并没有去写,,,       T3不知道是什么东西,写个线段树维护矩阵怎么样啊,,

2017-07-21 15:09:35

ZJOI2017 酱油记

考挂了,自己菜,怪谁喽。       早上闹钟似乎并没有叫醒我们,,qaq,7点被老师门铃按醒了。       开场看了一遍题目,感觉T1的50分挺简单的,T2可能需要一点推倒,T3好大,果断10分。       推了T2发现是一个后缀和,然后要特判0的情况,于是就转化了为判断a[l-1]和a[r]是否相同,直接线段树维护一个*a+b的标记即可。       写完了发现过不了大样例

2017-03-23 20:51:49

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

bzoj 3238: [Ahoi2013]差异 后缀树

学习了一下后缀自动机转后缀树的方法。虽然可能这道题目后缀数组也可以做。       考虑后缀自动机的parent,它对应的是比x的right集合略大一点的那个节点;对应到后缀树上,可以发现在缩边后对应的就是y的父亲。       但是后缀自动机求得实际上是所有前缀倒过来后的后缀树;因此把原串反过来跑sam,然后x连向fa[x]就是后缀树了;每个点的len实际上就是这个节点的深度。   

2017-03-16 08:05:03

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

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

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

THUWC2017 酱油记

从绍一滚到了学军,,持续滚粗之旅。day -1辗转到了绍一(1h的公交好累啊),已经19:00+了,然后进入学军报道,去了一趟寝室感觉好大啊,比某镇上的中学高到不知道哪里去了。当年ZJOI看宣传片的时候以为是ps的,现在发现居然是真的这么好。于是20:00左右噎了晚饭,可惜由于肚子不舒服不能噎很多。。。qaq晚上终于可以洗澡了,浑身舒爽。day 15:00被冻醒,被

2017-02-11 21:25:13

WC2017 酱油记

WC接THUWC,可以体验连续滚粗的快感。day -5     上了高铁发现居然和老师邻座,,,     15min的高铁也是劲啊。     晚上文艺表演,各种讲话,并没有什么兴趣。day -4     早上鏼鏼鏼讲字符串,大概还是能听懂一点的。     下午rzz将一个ulam猜数,感觉到了最后就是给一个估价函数?不是很懂有什么用。     myh讲ioi窝居然有

2017-02-08 20:14:10

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

uoj 279: 数据分块鸡 动态规划+可持久化线段树

一开始看到这道题目的时候以为是dp+线段树修改什么的来维护。       但是n=50000好奇怪啊。       看了题解才知道原来是决策单调性+暴力可持久化线段树求某一个区间的花费。       刚好没有怎么写过dp决策单调性的优化,就写一发吧。AC代码如下:#include#define ll long long#define N 100005#define M 2

2017-02-02 18:32:42

Codeforces Round #393 (Div. 1) 螺杆记

这场比赛真是啊,,各种卡题意,好气啊。      英语太差没有人权啊TAT,就不能像上一场vk B题那样只有1行描述吗,,好难受啊。      A题好长啊,看了10min才看懂;然后又爆了3发oj(1发样例)才过,心态瞬间不好了。      B题更长了,看了20min都看不懂,心态爆炸了。因为有几个细节一个没注意到,导致题意理解一直有问题。最后终于看懂了,就是一个超级simple的dp

2017-01-23 11:43:02

BestCoder Round #91 hack大战

好像写得晚了一点。      题目还是可以的(虽然说C代码量有些偏大),但是在某些方面,,,就不说了。      前两题都是sb题。不过第一题这么明显的可以放负数居然让过了pretest,,强行为了hack而hack啊。导致最后在C题全部fst的情况下大家靠hack拉排名啊。想我这种打完就去水uoj群的就没希望了啊。      C题这种题目没有spj真是差评啊。      D题其实

2017-01-23 11:22:03

bzoj 4727: [POI2017]Turysta 图论

在与Claris谈笑风生和自己的思考后终于学会了竞赛图的哈密顿回路。       讲道理我以前连竞赛图是啥都不知道。       首先求出强联通分量+dp是没有疑问的。那么考虑一个强联通分量,有一个结论是竞赛图一定存在哈密顿路径,然后存在哈密顿回路当且仅当强联通。下面给出构造方法。       首先求哈密顿路径(见代码或百度即可);然后将路径变成环,考虑一个环+一条延伸出去的链,那么要

2017-01-20 19:50:39

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!