4 lyd729

尚未进行身份认证

中山纪念中学初三OIer蒟蒻

等级
TA的排名 8k+

AFO

AFO

2019-05-04 22:34:16

多项式exp,ln,求逆板子

题目是jzoj5923#include<cstdio>#include<cstring>#include<algorithm>#definefo(i,a,b)for(inti=a;i<=b;++i)#definefd(i,b,a)for(inti=b;i>=a;--i)#definemax(x,y)((x

2019-02-16 20:56:49

【类欧几里得算法】【JZOJ 6025】Cannon

DescriptionAnalysis一个很自然的想法是,由于k很大,我们二分一个分数,统计网格有多少个比它大先不考虑如何二分分数,假装我们已经得到了分数ab\dfrac{a}{b}ba​,如何统计比它大的个数呢?直线上整点个数,妈妈我会类欧类欧我们要求的是这个f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum_{i=0}^n\lfloor\dfrac{...

2019-02-16 20:22:20

任意模数FFT & 第一类斯特林数模板

JZOJ5688#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#definefo(i,a,b)for(inti=a;i<=b;++i)#definefd(i,a,b)for(inti=a;i&

2019-01-17 17:52:20

【JZOJ 5992】万家灯火

Description给定一棵N(N<=1e5)个点树,每个点有0/1的权值,有M(M<=1e5)次操作1x表示将x点的权值xor12xd表示查询与x点距离不超过d的点集中的连通块数,其中两个点之间右边当且仅当这两个点权值都为1,特别地x点与任何点没有边相连Analysis0->白,1->黑连通块数=点数-边数动态点分治+树状数组维护各个深度的黑点数/...

2019-01-11 22:45:19

tree

Description给你一棵n个点的树,你需要在树上选择恰好m条点不相交的,点数至少为k的路径,使得路径所覆盖的点权和尽可能大。求最大点权和。数据保证有解。n<=1.5e5凸优化+长链剖分存档题Code#include<cstdio>#include<cstring>#include<algorithm>#include&amp

2019-01-10 16:27:17

【JZOJ 5990】Bear

DescriptionlinkAnalysis朴素dp是逐行逐格转移注意到nnn较小,mmm较大一个显然的想法是看看能否逐列逐格转移,很可惜不行,因为考虑棋盘覆盖顺序,行的限制优先于列但是考虑行和列覆盖情况什么时候会冲突,只可能是形如2*2的小正方形里,左下和右上对右下格覆盖的时候冲突了,并且我们知道右上的优先级更高这启示了我们可以以左往右逐个斜线,每条斜线再从上到下的顺序来dp,记...

2019-01-07 21:47:20

【Codeforces 1097G】Vladislav and a Great Legend

Description原题链接Analysis∑Xf(X)k=∑X∑i=0kS(k,i)i!(f(X)i)\sum_{X}f(X)^k=\sum_X\sum_{i=0}^kS(k,i)i!{f(X)\choosei}X∑​f(X)k=X∑​i=0∑k​S(k,i)i!(if(X)​)考虑对于i=1…k,dp出(f(X)i){f(X)\choosei}(if(X)​)dp选...

2019-01-05 20:55:37

NOIP 2018 退役记

Day0一年过去,又从二中回到了六中,还换了酒店。吃饭自行解决好评。我年龄越是增长,心态反而越无所谓。不知道这样是好是坏。由于当天没有写代码,晚上睡前写了一道题找找手感。Day1国际酒店没有西式早餐差评可以试机好评六中键盘差评8:30准时开始8:31发现T1是原题,主程序3行秒了8:32发现T2不会做8:35发现T2重要结论,然后就会做了8:40写完前两题然后心态有...

2018-11-13 12:30:19

【UOJ #390】【UNR #3】百鸽笼

Description给定nnn个正整数aia_iai​,令N+1=∑aiN+1=\suma_iN+1=∑ai​将执行NNN次操作,每次等概率随机选择一个非零的aia_iai​并令其减一,显然NNN次操作结束之后有且仅有一个ai=1a_i=1ai​=1对于一开始的nnn个aia_iai​,分别求出它们最后为111的概率n,ai≤30n,a_i\leq30n,ai​≤30Analys...

2018-11-06 15:07:00

【bzoj 2122】【jzoj 5936】逛公园

共q组询问,n,q<=4e4Analysis任意起点终点不好做,先考虑fix了起点终点后,对于给定x0,从l走到r的答案。不妨设它为f(l,r,x0)对于任意给定x0,f(l,r,x0)均可以O(r-l)求出,这样我们得到了一个O(nq)的暴力接下来需要发现一个本题最关键的性质:f(l,r,x0)=min(f(l,r,+∞),x0+s(l,r)),s(l,r)=dl+...+drf...

2018-10-29 16:55:37

NOIP 2018 前的几场模拟

10/20从15号到今天20号,我打了4场模拟,中间有一场我是验题人总的来说还是比较悲惨的整体的一个现象是,我做比赛的时候很少写对拍。现在想想,虽有挂分,但是都不多。包括之前很多正式比赛我也很少写对拍,主要是因为有大样例/pretest/实时看成绩赛制的存在,外加时间紧迫导致的。常常高估自己的代码能力,导致出现写不完正解又没写暴力,前面的水题还没拍的情况。不管是NOIP考场上还是平时模...

2018-10-20 22:11:05

新·自我剖析

基于上一年写的update思维能力对于数学论相关的反应迟钝对于特别抽象的会有畏难心理对于繁琐讨论会有逃避心理(不一定是坏事,可能换个脑子会想到更简单的做法)比较喜欢在普通模型上深入思考训练方面:**计数**,树上问题(包括dp,数据结构等),多项式泛做“中国式”题目:从近年NOI->THU/PKU-WC/SC->CTSC->各省省选每日一题,限...

2018-09-05 21:33:52

「NOI2018」冒泡排序

Description给定1~n的排列p,求所有长度为n的字典序严格大于p的排列中有多少个能被拆分成不超过两个上升子序列。(其实原题是,求有多少个排列进行冒泡排序后交换次数恰为一个下界12∑1≤i≤n|i−pi|12∑1≤i≤n|i−pi|\frac{1}{2}\sum_{1\leqi\leqn}|i-p_i|,这和上面是等价的,可以通过打表找规律发现)n<=6e5A...

2018-08-21 22:17:13

Trie上的后缀数组

亦称为广义后缀数组DefinitionLCS=LongestCommonSuffixLCP=LongestCommonPreffixSvSvS_v表示Trie上节点v到根的路径形成的字符串Intro由于在Trie上,自带去重功能显然LCS(Su,Sv)=deplca(u,v)LCS(Su,Sv)=deplca(u,v)LCS(S_u,S_v)=dep_{lc...

2018-08-15 21:38:20

Another Me

囿于CSDN各种坑,开了博客园

2018-06-24 17:24:55

【JZOJ 5746】一道比较强的 自然数幂和 板题

Description给定m,km,km,k,共TTT次询问,每次输入一个nnn,求∑ni=1ik∑i=1nik\sum_{i=1}^ni^k在modmmodm\bmodm意义下的值mmm的最大质因子≤3∗105≤3∗105\leq3*10^52≤n,m,k≤1018,1≤T≤3∗1032≤n,m,k≤1018,1≤T≤3∗1032\leqn,m,k\leq10^{18},1...

2018-05-28 22:16:33

CTSC/APIO 2018 咕咕记

Preface省选结束后还能继续逃几天文化课的学习,还是很资瓷的日期从5.6一直到5.14号,时间很长就不用Dayx的形式了本文大概是记录每天日程的流水账5.5坐车到广州机场附近住了一晚,一个人一间房体验极佳(除了经常有飞机飞过)由于忘带电脑晚上基本上是看番度过的5.6早上的飞机,5.75.85.95.105.115...

2018-05-15 12:35:24

GDOI 2018 绝望记

Preface考前的三轮模拟稳步前进,感觉状态调整不错NOIP考了个竞争力很低的分数,所以进队只可能靠运气目标大致是被卡校线?能Au就已经是超越自我了,省队毕竟太难在中山一中,我们也算是主场参赛。占据地利,每天可以回家休息。Day1看了座位表,左边坐着爷稳稳(yww)神犇,心态崩了开场半个小时试机,先作死打了一发半年没打过的SA,因为记不得了打得很慢,20min终于...

2018-05-02 12:48:08

HNOI 2018 游记

#前言为什么我又现在才写一个星期前的游记QAQ,马上都要自己省的省选了还来这里吹水。。。还有,这是今年第几次来长沙了?。。为什么一点紧张感都没有啊,吃枣药丸啊#Day0上午坐高铁出发,几乎全程补ditf+打sif酒店在长沙市中心,旁边就是雅礼,放眼望去发现雅礼占地面积真的小,却有着与面积不成比例的清北人数。。。可怕来的时候还有些下雨,下午顶着大风大雨跟着一堆人跑去五一广场浪,鞋子湿...

2018-04-23 12:33:19

查看更多

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