- 博客(836)
- 收藏
- 关注
RSS订阅
原创 [一直更新中]WerKeyTom的口胡
前言因为要保证能力的提升，不能啥题都是写写。 所以开一个口胡题解坑。 可能以后有心情和能力也会来写一写收录的题。 至少留下一个思考过的痕迹。 实在太水可能就不口胡啦。 有些题也会写写。2017.3.13bzoj3679 计算可以被分解成1~9的乘积且在1e9内的数只有5194个 然后可以数位dpbzoj3756 直接给Trie建SAM是伪的。 这个伪指的是深...
2017-03-13 22:39:13
4193
原创 [一直更新中]错误及好东西
犯错合集及需要注意的东西1、在一个地图求最大面积的类问题中，要注意障碍结点的影响。 2、ll()，表示的是在运算后把括号内强制转化为类型ll，而(ll)表示后面的每个玩意都强制转化为类型ll。在做历史研究这道题时我WA就是因为我用的是ll()而不是(ll)。 3、splay每次splay操作后一定要记得更新root！ 4、可以使用树状数组就尽量不要使用线段树。在Gty的文艺妹子序列这道题
2015-12-30 20:33:54
3263
8
原创 [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
1021
原创 NOI2018金色记
DAY 0太热了不讲了。DAY 0.5笔试时揣了电源线(雾。 给给修跳水，我和可爱颖也打沙雕游戏，只打了细胞阶段+生物阶段。 美味鼠？烤了。 晚上想复习板子。 发现石头门0预告更了，是弹性界限的认知，于是搞了会石学。 然后想现学FWT的，最后也就背了背代码，可能还没记住呢。 给给修说一定烤几何，我信都不信！DAY 1__天下第一，这怎么跳闸了。 心态崩了。 ...
2018-07-23 22:08:46
4827
1
原创 [loj#560]Menci的序列
题目大意一个人长度为n的字符串s，只包含+和*。 选出一个子序列，然后你有一个ret，初始为0，按顺序扫你选出的这个子序列。 如果碰到的是+，ret+1，否则ret*2。 最大化ret%2^k。做法lca题解写的真麻烦。 首先我们可以看成，每个+贡献2^c，c为该+后面的*数量。 然后就能注意到： * + + + + * + 这两个是等价的。 因此假如出现连续三个+，...
2018-07-05 22:02:27
1198
原创 [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
693
原创 蓝雨
题目大意一个长度为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
1035
原创 [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
510
原创 [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\lt y，其效果是交换第xxx和第yyy个位置。每种本质不同的操作只能用一次。 这个操作序列需要满足，从头开始执行，最终序列变回原样。 要求判断无解。做法先考虑如何判断无解。 当...
2018-06-03 15:13:01
560
原创 青青草原播种计划
题目大意有nnn个可重集，支持下列操作： 往某个集合加入某个数。 让某个集合删除某个数。 将一个集合的所有数放入另一个集合中（然后该集合就空了）。 询问一个集合的mex以及最小的xxx使得xxx无法表示成子集和。 对于历史版本进行询问。 强制在线。做法1是加入，2是删除，3是合并。 值域线段树都能支持。 mex用值域线段树做。 第二个的话，可以考虑把值从小到大排序，如...
2018-05-30 08:49:33
11401
原创 小J真爱粉交流群
题目大意有数字的n*m网格图，DDD和YJQ在玩游戏。 DDD先把一个小人放在第一行某个格子上。获得该格子分数。 接下来每个时刻，YJQ先在任意上下相邻的格子间建墙，可以建任意个。 DDD移动小人向四相邻的位置走（如果没有墙）。并获得新格子分数（重复走重复获得）。 小人到达最后一行游戏结束，现在DDD的目标是最小化，YJQ的目标是最大化，问得分是多少。做法可以发现，DDD负...
2018-05-30 08:43:09
741
原创 小Y增员操直播群
题目大意有nnn个人，初始一个人一个联通块，编号都是000。 每次两个联通块合并，假设较小联通块大小是xxx，较大联通块编号为yyy的会与较小联通块大小是y mod xy mod xy\ mod\ x的连边，然后编号变成y+xy+xy+x，接下来合并两个联通块。 最终所有人都在一个联通块内。 现在给你最终联通块中所有连边情况，已知一天里联通块合并可...
2018-05-30 08:26:25
919
原创 幂
题目大意给你一个nnn，求最小正整数kkk，使得对于任意整数aaa都满足 ank≡a(mod n)ank≡a(mod n)a^{n^k}\equiv a(mod\ n) 或输出无解。做法首先发现nnn含有平方因子时是无解的。 假设nnn含有平方因子pcpcp^c，那么我们令a=npcpa=npcpa=\frac{n}{p^c}p时是不合法的。 因为nk≥n≥...
2018-05-26 21:22:42
491
原创 箱子
题目描述小猪佩奇和其他n-1个小伙伴们正在玩一个老套的游戏。 一个房间中，有n个随机打乱过的箱子放成一排，每个箱子里有一张纸条，写着一个人的名字。每个人要按一定顺序走进房间，打开最多k个箱子，如果其中没有自己的名字游戏就失败了。每个人走出房间的时候需要关上箱子。（游戏中箱子的顺序不会再被调换）游戏前他们可以商量出一个策略，但是游戏开始之后他们不能互相交流。 小猪佩奇想知道最优策略下游戏成功...
2018-05-22 16:15:13
692
原创 斐波那契
题目大意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
826
原创 CTSC2018心了记&APIO2018态了记&THUPC2018崩了记
day -1第二天早的飞机，先去广州住。 继续推石头门0，发现弹性界限的认知和私密镜里的圣痕剧情大量重复，爽快skip。 终于推完了无限远点的牵牛星，跳了ed，发现没进交叉坐标的星辰。 然后又来了一次没跳ed，发现还是没进。 然后才知道得从闭时曲线的碑文开始重走A线，可以接收到来自盟誓的文艺复兴发来的d-rine，然后通完无限远点的牵牛星就能进交叉坐标的星辰。 推完后还顺便看了dit...
2018-05-16 11:53:28
2493
2
原创 GDOI2018自爆记
DAY 0在一中暴躁。 出去喝水。 成功邀请SBAO和我一起坐在那玩SD游戏。 真的很SD。DAY 1开场试机半小时，一个排序就完事。T1久违的签到题，GDOI居然有送分难度的题了。 T2肝了2h才会，我太菜了。 T3反复看错，写了又删，中规中矩DS题。 T4心态崩了，只会20。估分大众分，只能苟到校内第四。 出分一看心态崩了，才200。 然后发现T2T4连...
2018-05-03 22:18:36
1510
3
原创 [UOJ#84]水题走四方
题目大意一颗树，两个人初始从根节点出发，每一步每个人可以选择原地不动或者走向某个儿子。一步后，一个人可以瞬移到另一个人所在节点上。 最少需要多少步，使得每个节点都被遍历过？做法我们可以认为存在一个本体以及一个分身，每次都是分身瞬移到本体的位置。 如果本体A和分身B在节点C分道扬镳，本体A在D节点瞬移至分身B所在的节点E，干脆一开始便让本体A往E走，分身B往D走。因此瞬移的总是分身。 最后一定是
2018-04-12 11:32:02
647
原创 [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
678
原创 [codechef]UASEQ
题目大意给定一个序列，修改至多k次，变成等差数列。 最小化{首项，公差}的字典序。 k<=min(n-2,10)。做法因为k<=n-2，一定有两个位置不会被修改。 随机两个位置，以它们作为不修改项。 做不会超时次。 n很小时，最优解一定能被枚举到。 n很大时，不被修改的位置有n-k个，正确率极高。#include<cstdio>#include<algorithm>#define f
2018-04-03 12:29:38
433
原创 [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^m mod f(x)。 可以发现g(A)=A^m mod f(A)=A^m。 因此我们可以多项式快速幂+取模求出g(x)，再代入A即可。#in
2018-04-03 12:26:37
607
原创 [loj2461]完美的队列
题目大意有n个队列，每个队列有一个上限aia_i。 当队列上限满时，如果还要push，其会先执行一次pop。 现在有mm个操作。 每次操作都会给一个区间的队列push同一个x。 要求回答每次操作后所有队列中数的种类数。做法当一个数xx进入第ii个队列，这个队列再push aia_i次会pop掉这个xx。 这个非常显然。 现在对于每个操作，我们需要知道最早在第几次操作后，这次操作加入的xx
2018-04-03 10:51:27
1535
原创 [Yandex.Algorithm 2018, second qualification round E]Bonsai
题目大意两颗树，有根带标号，儿子有顺序。 你每次操作可以选择一颗树，然后执行二选一： 1、删除一个叶子。 2、将某个节点相邻两个儿子合并，前面那个节点的儿子排在前面，后面那个节点的儿子排在后面。 问至少操作多少次能使得两棵树同构。做法将树用深度序表示。 两棵树同构当且仅当深度序同构。 然后考虑两种操作对树的影响，都是删除一个数。 但是删除一个树不只能被表示成这两种，还有一种是一个单儿子
2018-03-30 11:51:19
486
原创 [2017计蒜之道复赛]商汤智能机器人
题目大意从(0,0)出发，每次行走向量有(1,1),(2,0),(1,-1)。 求到(n,m)的方案数。 n,m 1e18。模数p是1e5+3。做法先转45度，并收缩1/2。 那么此时行走向量有(1,0),(1,1),(0,1)。 我们可以给出此时(0,0)到(n,m)的结论： ∑ni=0CinCim2i∑i=0nCniCmi2i\sum_{i=0}^nC_n^iC_m^i2...
2018-03-29 15:40:37
597
原创 Zkb
题目大意区间排序，区间求乘积十进制下的最高位。做法先转化询问。 对所有数取log10log10log_{10}。 那么乘法转化为加法。 设取logloglog后和为xxx，答案显然是⌊10x−⌊x⌋⌋⌊10x−⌊x⌋⌋\lfloor10^{x-\lfloor x\rfloor}\rfloor。 现在问题就是，区间排序，区间求和，怎么做？ 可以维护若干个排序块，这个可以用平衡树...
2018-03-28 07:56:12
601
原创 [bzoj3716]Muzeum
题目大意商场是一个平面直角坐标系。 lihua想要来偷珠宝，一共有nnn个珠宝，分布在不同的位置，第iii个珠宝在(axi,ayi)(axi,ayi)(ax_i,ay_i)有价值为aviaviav_i。 但是有mmm个保安，第iii个保安在(bxi,byi)(bxi,byi)(bx_i,by_i)，lihua贿赂他需要bvibvibv_i的代价。 每个保安都有一个相同的视野角度θ。 如...
2018-03-26 22:41:45
465
原创 [Neerc2013]Dictionary
题目大意给你n个长度不超过10的小写字母字符串。 请你构造一颗节点数最少的字典树。 使得对于任意一个人给定字符串，字典树中都存在一条祖先后代链对应的字符串与其相等。做法首先显然，如果字符串a包含字符串b，可以直接剔除字符串b。 我们考虑最优解，一定是按照某个顺序添加字符串进入字典树中。 假设现在有字符串c，可以找到其一个最长前缀，使得该前缀可以被字典树表示，然后把剩余后缀加...
2018-03-26 11:39:45
433
原创 [TCO2014]FrozenStandings
题目大意有n个人，每个人有一个数字xix_i。 现在你可以把某些人的xix_i加一。 问一共能造成多少本质不同的排名？ 两个人中数字大的排名靠前，数字一样编号小的靠前。做法双关键字让我们非常难受。 考虑设一个大数w，令ri=−xi∗w+ir_i=-x_i*w+i，然后令li=ri−wl_i=r_i-w。 那么现在就是一个人可以选择lil_i或rir_i，问排名数。 立刻变成了单关键字。
2018-03-24 11:49:27
668
原创 [SRM554-500]TheBrickTowerMediumDivOne
题目大意给你一个序列a，定义一个排列b的价值为∑n−1i=1max(bi,bi+1)\sum_{i=1}^{n-1}max(b_i,b_{i+1})。 请你给出一个价值最小的排列，使得其字典序最小。贪心首先，不会出现相邻三个组成了高峰。 否则我们将最高和次高交换，使得价值变得更优。 容易发现最后一定是一个V字形，低谷位置就是最小值。 因此可以得到贪心构造，按编号贪心构造V形左边，剩余排序后成
2018-02-28 10:25:28
468
原创 [SRM553-1000]YamanoteLine
题目大意有一个n个点的环，相邻两个点距离是正整数。 现在有若干个约束，是以下两种其中之一： 1、S与T的顺时针距离不小于L。 2、S与T的顺时针距离不大于L。 问环总长的解的方案数。差分约束不妨设D[i]表示0与i的顺时针距离，特殊的，D[n]表示整个环的总长，设为X。 显然，D[i+1]−D[i]>=1D[i+1]-D[i]>=1，等同于D[i]−D[i+1]≤−1D[i]-D[i+1]
2018-02-27 16:32:17
555
原创 GDKOI2018终焉记&WC2018并列记
由于时间跨度实在是非常的大，这次用日期而不是Day x来表示。 依然可能用比较流水账的风格叙述（即，自我满足+娱乐，篇幅废话略长，不会有别的人看完，不喜请勿喷，然后某个我不知道的是不是对我有意见的习惯点踩的不知道是谁，我也管不着，当然更没必要纠结）GDKOI2018终焉记1.25一如既往的叫夜宵吃。 开始了我的春物二周目。 因为对自己的本质写暴力水平已经有了B数，所以心态上非常平稳，这是老年选
2018-02-21 19:23:10
1511
2
原创 2017年终吹水
前言因为可能写的很散，因此就不说年终总结了，叫年终吹水吧。 吹啥水？一路历程，以及认识各位大佬的过程。1~2月月首的时候Drin_E给我说了一道他出的数论题（Jason曾不想做的数论题），我不小心听错了题，还思考出了解法，于是把这个题（陵陵曾玩的数论题）造好了出出来。然后拿去给一些人验了验，发现难度好像还可以。 打完期末考试，就进入了寒假，好像是这个时候开始得知还有清华冬令营这
2018-01-17 15:48:58
2032
4
原创 [2017集训队作业自选题#124]Path
题目大意给定 n 和 ai, 满足 a0≥a1≥⋯an−1≥0, 求出在 n 维空间中从 (0,0,…,0) 走到 (a0,a1,…,an−1), 每一步使某一维坐标增加 1 的方案中随机选出一种, 满足经过的所有点 (x0,x1,…,xn−1) 都满足 x0≥x1≥⋯≥xn−1 的概率. 答案模 1004535809 输出.结论先转化题意：有一个高度为m的表格，第i行有ai个格子，ai不上升，假设
2018-01-11 12:04:25
741
原创 [hdu6042]Journey with Knapsack
题目大意Rosemary有一个容积为2n的背包，还有n种物品，第i种物品的容积为i，有ai个，保证a是非负整数且递增（即ai>=0a_i>=0，ai<ai+1a_i<a_{i+1}）。 现在lihua摆出了m个装备帮助Rosemary完成他的旅行，第i个装备的容积为bi，Rosemary必须选择恰好一个装备以及若干个物品装进背包去旅行，要求背包装满，问有多少种方案。 两种方案不同，当且仅当选择的
2018-01-11 11:33:31
844
1
原创 [2017集训队作业自选题#149]小c的岛屿
前言感觉这题挺棒棒的。题目描述小c有n个岛屿。她为了管理岛上的人，决定让这些岛屿连通。 每个岛屿i有一个概率值pi，和一个友好列表Ai。 小c首先来到了1号岛屿，她会依次执行下面操作： 1、设现在在岛屿x，有px的概率产生一条无向边连接两个随机岛屿，这两个岛屿不会相同，也不会已经有边相连。（即在尚不存在的无向边中随机一条加入图中，不会加自环） 2、如果此时所有岛屿连通，她就会心满意足地离开。
2018-01-01 20:22:02
1412
2
原创 [2017集训队作业自选题#148]Simple Summation Problem
题目大意定义一个积性函数F。 若p为质数，F(pd)=pd−[d mod p!=0]F(p^d)=p^{d-[d\ mod\ p!=0]} 求F的前缀和。做法令G=F∗μG=F*\mu，那么G也是一个积性函数。 那么容易得到G(pd)=pd−[d mod p!=0]−pd−1−[(d−1) mod p!=0]G(p^d)=p^{d-[d\ mod\ p!=0]}-p^{d-1-[(d-1)\
2017-12-21 21:20:48
858
原创 [2017集训队作业自选题#134]Counting Divisors (square)
题目大意&题解同SPOJ DIVCNT2#include<cstdio>#include<algorithm>#include<cmath>#define fo(i,a,b) for(i=a;i<=b;i++)using namespace std;typedef long long ll;const int maxn=70000000+10;int pri[maxn/10],mu[m
2017-12-21 21:14:58
835
原创 [2017集训队作业自选题#119]众数MAX
题目大意两个长度为n的序列a和b，将它们分别任意排列，然后令c[i]=a[i]+b[i]c[i]=a[i]+b[i]，使c[i]的众数出现次数尽量多。 值域与n同阶。做法不妨令A[i]表示a中i的出现次数，B同理。 令ans[i]表示i作为众数的最多出现次数。 显然的暴力 ans[i]=∑ij=0min(A[j],B[i−j])ans[i]=\sum_{j=0}^imin(A[j],B[i-
2017-12-21 21:07:42
578
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人