4 WerKeyTom_FTD

尚未进行身份认证

我是一只来自中山纪念中学高三的oier,请多多指教

等级
TA的排名 1k+

[CF1019C]Sergey's problem

题目大意一个有向图无自环图,找到一个点集S满足:点集内任意两个不同的点x和y,满足d(x,y)>=2。对于任意一个不在点集内的点y,存在一个点集内的点x,满足d(x,y)<=2。构造对于任意图都存在解,构造性解法可以证明这点。找到任意一点w,将w以及w的出边指向的点都删去,对剩余的图找到一个解S‘’。如果存在一个u->w,且u在S’内,我们直接令S...

2018-08-12 10:54:30

NOI2018金色记

DAY0太热了不讲了。DAY0.5笔试时揣了电源线(雾。给给修跳水,我和可爱颖也打沙雕游戏,只打了细胞阶段+生物阶段。美味鼠?烤了。晚上想复习板子。发现石头门0预告更了,是弹性界限的认知,于是搞了会石学。然后想现学FWT的,最后也就背了背代码,可能还没记住呢。给给修说一定烤几何,我信都不信!DAY1__天下第一,这怎么跳闸了。心态崩了。...

2018-07-23 22:08:46

[loj#560]Menci的序列

题目大意一个人长度为n的字符串s,只包含+和*。选出一个子序列,然后你有一个ret,初始为0,按顺序扫你选出的这个子序列。如果碰到的是+,ret+1,否则ret*2。最大化ret%2^k。做法lca题解写的真麻烦。首先我们可以看成,每个+贡献2^c,c为该+后面的*数量。然后就能注意到:*++++*+这两个是等价的。因此假如出现连续三个+,...

2018-07-05 22:02:27

[UER#6 C]逃跑

要求的是方差,实际就是求所有情况下经过不同位置的个数和以及经过不同位置的平方和,设为ddd和d2d2d2。一共有四种方向向量,任意走法对应一种向量序列。先预处理W(i,x,y)W(i,x,y)W(i,x,y)表示长度为iii,和为(x,y)(x,y)(x,y)的向量序列有多少种。如何求ddd,当然是很简单的。每个坐标显然可以独立统计贡献,我们希望在每个坐标第一次被走到时统计到它。...

2018-06-25 17:23:46

蓝雨

题目大意一个长度为nnn的序列,每个元素都是[1,n][1,n][1,n]。一个区间代表的序列是将其元素排序。现在求出区间代表序列字典序按高到低排名在区间[p,q][p,q][p,q]的区间。q-p<=100000。做法我们如何快速比较两个区间代表序列的字典序?主席树维护区间哈希即可。那么只要我知道第p个,可以用经典做法推到第q个。关键是第p个。考虑逐...

2018-06-25 17:18:26

[SRM695-900]BearEmptyCoin

题目大意有一个两面为空的硬币,正面和反面有区别。你需要甩kkk次,每次其会有一面朝上,如果该面为空,你填一个整数上去,若不为空,获得该分数。你希望最大化分数和为sss的概率。做法如果s mod k=0s mod k=0s\mod\k=0显然我们不管哪面都会填s/ks/ks/k,输出2k2k2^k。你能决定的是第一次摇到第2个面时,...

2018-06-03 15:27:49

[CF804E]The same permutation

题目大意一个长度为nnn的排列,现在你要构造一个长度为n(n−1)2n(n−1)2\frac{n(n-1)}{2}的操作序列,每个操作形如(x,y)(x,y)(x,y)满足x<yx<yx\lty,其效果是交换第xxx和第yyy个位置。每种本质不同的操作只能用一次。这个操作序列需要满足,从头开始执行,最终序列变回原样。要求判断无解。做法先考虑如何判断无解。当...

2018-06-03 15:13:01

青青草原播种计划

题目大意有nnn个可重集,支持下列操作:往某个集合加入某个数。让某个集合删除某个数。将一个集合的所有数放入另一个集合中(然后该集合就空了)。询问一个集合的mex以及最小的xxx使得xxx无法表示成子集和。对于历史版本进行询问。强制在线。做法1是加入,2是删除,3是合并。值域线段树都能支持。mex用值域线段树做。第二个的话,可以考虑把值从小到大排序,如...

2018-05-30 08:49:33

小J真爱粉交流群

题目大意有数字的n*m网格图,DDD和YJQ在玩游戏。DDD先把一个小人放在第一行某个格子上。获得该格子分数。接下来每个时刻,YJQ先在任意上下相邻的格子间建墙,可以建任意个。DDD移动小人向四相邻的位置走(如果没有墙)。并获得新格子分数(重复走重复获得)。小人到达最后一行游戏结束,现在DDD的目标是最小化,YJQ的目标是最大化,问得分是多少。做法可以发现,DDD负...

2018-05-30 08:43:09

小Y增员操直播群

题目大意有nnn个人,初始一个人一个联通块,编号都是000。每次两个联通块合并,假设较小联通块大小是xxx,较大联通块编号为yyy的会与较小联通块大小是y mod xy mod xy\mod\x的连边,然后编号变成y+xy+xy+x,接下来合并两个联通块。最终所有人都在一个联通块内。现在给你最终联通块中所有连边情况,已知一天里联通块合并可...

2018-05-30 08:26:25

题目大意给你一个nnn,求最小正整数kkk,使得对于任意整数aaa都满足ank≡a(mod n)ank≡a(mod n)a^{n^k}\equiva(mod\n)或输出无解。做法首先发现nnn含有平方因子时是无解的。假设nnn含有平方因子pcpcp^c,那么我们令a=npcpa=npcpa=\frac{n}{p^c}p时是不合法的。因为nk≥n≥...

2018-05-26 21:22:42

箱子

题目描述小猪佩奇和其他n-1个小伙伴们正在玩一个老套的游戏。一个房间中,有n个随机打乱过的箱子放成一排,每个箱子里有一张纸条,写着一个人的名字。每个人要按一定顺序走进房间,打开最多k个箱子,如果其中没有自己的名字游戏就失败了。每个人走出房间的时候需要关上箱子。(游戏中箱子的顺序不会再被调换)游戏前他们可以商量出一个策略,但是游戏开始之后他们不能互相交流。小猪佩奇想知道最优策略下游戏成功...

2018-05-22 16:15:13

斐波那契

题目大意F[0]=0,F[1]=1,F[n]=F[n-1]+F[n-2]。现在要求gcd(aF[n]+bF[n+1],cF[n]+dF[n+1])。a,b,c,d<=1000,n<=1e18。做法我们可以先辗转相除。即(a,b,c,d)=(c,d,a%c,b-(a/c)d)。辗转到最后会把c变成0。问题变成求gcd(aF[n]+bF[n+1],cF[...

2018-05-22 15:58:52

CTSC2018心了记&APIO2018态了记&THUPC2018崩了记

day-1第二天早的飞机,先去广州住。继续推石头门0,发现弹性界限的认知和私密镜里的圣痕剧情大量重复,爽快skip。终于推完了无限远点的牵牛星,跳了ed,发现没进交叉坐标的星辰。然后又来了一次没跳ed,发现还是没进。然后才知道得从闭时曲线的碑文开始重走A线,可以接收到来自盟誓的文艺复兴发来的d-rine,然后通完无限远点的牵牛星就能进交叉坐标的星辰。推完后还顺便看了dit...

2018-05-16 11:53:28

GDOI2018自爆记

DAY0在一中暴躁。出去喝水。成功邀请SBAO和我一起坐在那玩SD游戏。真的很SD。DAY1开场试机半小时,一个排序就完事。T1久违的签到题,GDOI居然有送分难度的题了。T2肝了2h才会,我太菜了。T3反复看错,写了又删,中规中矩DS题。T4心态崩了,只会20。估分大众分,只能苟到校内第四。出分一看心态崩了,才200。然后发现T2T4连...

2018-05-03 22:18:36

[UOJ#84]水题走四方

题目大意一颗树,两个人初始从根节点出发,每一步每个人可以选择原地不动或者走向某个儿子。一步后,一个人可以瞬移到另一个人所在节点上。最少需要多少步,使得每个节点都被遍历过?做法我们可以认为存在一个本体以及一个分身,每次都是分身瞬移到本体的位置。如果本体A和分身B在节点C分道扬镳,本体A在D节点瞬移至分身B所在的节点E,干脆一开始便让本体A往E走,分身B往D走。因此瞬移的总是分身。最后一定是

2018-04-12 11:32:02

[TCO2014 3B]OnePointNineNine

题目大意现在平面上有n个点,已知有一个常数D。任意两点的距离要么<=D,要么>=1.99D。请问有多少点集的子集,满足任意两点距离>=1.99D。n<=1000。解法我们肯定是把距离<=D的点对连边。然后相当于独立集计数。可以考虑把等价点缩在一起:两个点如果它们之间有连边,然后其余连边完全相同,则显然该两点等价。即{u}or{u的邻居}={v}or{v的邻居}接下来有一个结论

2018-04-12 11:09:10

[codechef]UASEQ

题目大意给定一个序列,修改至多k次,变成等差数列。最小化{首项,公差}的字典序。k<=min(n-2,10)。做法因为k<=n-2,一定有两个位置不会被修改。随机两个位置,以它们作为不修改项。做不会超时次。n很小时,最优解一定能被枚举到。n很大时,不被修改的位置有n-k个,正确率极高。#include<cstdio>#include<algorithm>#definef

2018-04-03 12:29:38

[bzoj4162]shlw loves matrix II

题目大意给你n∗nn*n的矩阵AA,求AmA^m。特征多项式这是一个特征多项式IDE练习题。矩阵A的特征多项式f(x)为det(A-Ix)。可以发现f(A)=0。如何求f(x)?代入n+1个点值求行列式,再插值插出f(x)。设g(x)=x^mmodf(x)。可以发现g(A)=A^mmodf(A)=A^m。因此我们可以多项式快速幂+取模求出g(x),再代入A即可。#in

2018-04-03 12:26:37

[loj2461]完美的队列

题目大意有n个队列,每个队列有一个上限aia_i。当队列上限满时,如果还要push,其会先执行一次pop。现在有mm个操作。每次操作都会给一个区间的队列push同一个x。要求回答每次操作后所有队列中数的种类数。做法当一个数xx进入第ii个队列,这个队列再pushaia_i次会pop掉这个xx。这个非常显然。现在对于每个操作,我们需要知道最早在第几次操作后,这次操作加入的xx

2018-04-03 10:51:27

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!