3 alan_cty

尚未进行身份认证

蒟蒻一只 别打脸(⊙o⊙)哦

等级
TA的排名 5k+

[Comet OJ - Contest #7]简要题解?

似乎由于是NOI前所以没什么dalao打混了个rk4_(:з」∠)_签到题相邻两个数gcd=1#include<cstdio>#include<cstring>#include<algorithm>#definefo(i,a,b)for(inti=a;i<=b;i++)#definefd(i,a,b)for(inti=a;...

2019-07-21 23:26:27

NOI2019退役记

退役失败QwQ

2019-07-21 23:13:11

[Comet OJ - Contest #6 E]字符串

Description给出一个长度为n的字符串S,定义f(S)为S的所有n∗(n+1)/2n*(n+1)/2n∗(n+1)/2个子串,两两求LCP的和对于每个i,求出f(S[i…n]),答案对998244353取模n<=200000Solutionlog^2的做法有很多这里就不一一说了数据结构学傻了.jpg先考虑两个后缀l和r的所有前缀互相匹配的答案,显然只和后缀长度和LCP有...

2019-07-11 15:23:08

[Comet OJ - Contest #6 F]permutation

Description给出n,求有多少个长度为n的排列没有长度为2~n-1的连续段n<=10^5Solution生成函数学艺不精.jpg特判掉n<=2,我们考虑一般情况首先数排列等价于数析合树,我们考虑根节点的形态若根为合点,则儿子排列为单调上升/下降,且不存在一个儿子为合点,且这个儿子的儿子也为上升/下降显然上升=下降,设G(x)表示根为合点且儿子单调上升的析合树数量...

2019-07-10 20:23:01

[模板]BM优化线性递推

又水了一篇博客=w=namespaceBM{ vector<int>h[N]; intcnt,fail[N],d[N],an[N],mx,k,f[N],g[N],p[N],trs[30][N]; voidmult(int*a,int*b,int*c){ fo(i,0,2*k-2)g[i]=0; fo(i,0,k-1)fo(j,0,k-1)(g[i...

2019-07-04 17:08:20

[LOJ6677]EntropyIncreaser 与菱形计数

Description求将边长为a,b,c的六边形分解成若干个小菱形的方案数如图为a=b=c=6的情况当a=b=c=2时答案为20,如图所示a,b,c<=10^6Solution这东西怎么看都是一个3维的东西。。。你感受一下,这个想当于在一个a*b的网格上堆箱子,第i个格子最多堆c个箱子,且个数要<=其左边和上边的箱子数这个还是没法做,但是还是可以看成下图的网格图,从左...

2019-07-03 20:44:30

[校内模拟]光影交错

Description有一个盒子,每个时刻有pl的概率往里面放一个白球,有pd的概率往里面放一个黑球,1-pl-pd的概率什么都不干,然后每个时刻末尾有p的概率直接结束过程问所有满足“白球数量大于黑球数量”的时刻的数量的期望所有读入的实数均保留5位小数Solution其实是JS的省队集训考虑设f[i]表示,所有满足有i个球的时刻的期望,g[i]表示,i个球中,白球>黑球的概率那...

2019-07-03 17:43:38

[校内模拟]三格骨牌

DescriptionT次询问,每次将一个nm的棋盘分成nm/3块大小为3的四连通块,再给每个四连通块标号,使得每块的标号不同,并且对于一个格子,其左边和上边的标号要小于等于其本身的标号问方案数,对10^9+7取模T<=10,n,m<=10^4Solution考虑按标号从小到大填连通块,那么每次填完后的图形必然是左上角的一块考虑这一块的轮廓线,必然只有往上和往右的,那么我们...

2019-07-01 17:41:18

[校内模拟]为了部落

DescriptionT次询问,每次询问给出n,m,k,P,问n个点的所有有标号生成森林中,连通块数为m的方案中,从每棵树中选择一个度数<=k的点的方案数对P取模的方案数n<=10^9,m,k<=100Solution我们先选关键点,再数生成树显然任意m个点的方案数是相等的,我们只需要指定m个关键点,答案乘上(nm)\binom{n}{m}(mn​)考虑枚举这m个点的...

2019-07-01 17:18:42

[Comet OJ - Contest #6 ]简要题解?

图游戏n-1-m的奇偶性#include<cstdio>#include<cstring>#include<algorithm>#definefo(i,a,b)for(inti=a;i<=b;i++)#definefd(i,a,b)for(inti=a;i>=b;i--)usingnamespacestd;in...

2019-06-29 22:23:48

[校内模拟]字符串

Description定义一个字符串S的权值f(S)为,其所有不同后缀两两的LCP的最大值给出一个字符串S,每个位置有权值aim次询问,每次询问给出[l,r,x],求一个[l,r]的子区间[a,b],满足f(S[a,b])>=x,且max(ai)最小n,m<=5e4Solution这题分成两部分1:给出[L,R],求f(S[L,R])考虑SAM,枚举parent树上的一...

2019-06-29 22:13:17

[校内模拟]抬头仰望梦的脚步

Description一棵二叉搜索树,插入n次,第i次插入的节点权值为(a+bn)%m,问第n次插入的点的深度T<=5e4,n<=1e16,a,b,m<=1e8Solution定义val(n)表示第n个数的权值,suf(v)表示所有的(a+bn)%m中,大于v的最小的数,pre(v)表示小于v的最大的数当n>m/gcd(m,b)时,后面的点构成循环,只需要计算第一...

2019-06-29 22:01:34

[校内模拟]喜欢最最痛

Description有一棵n个点的树,边有边权。有m条额外边,第i条的边权为ai,对于每个i∈[0,m],问加入前i条额外边后,从1出发经过所有树边至少一次最后回到1的最短路径的长度。n,m<=10^5Solution容易发现这题分为两部分,先求出an[i]表示选择树上i条不相交的链的长度最大值,然后对于每个前缀i,求一个j,使得an[j]-前i个a的前j小最大an的话可以考虑...

2019-06-27 22:14:13

[APIO2019]桥梁

Description给出一张n个点m条边的图,每条边有边权di有q次操作,第i次操作会修改一条边的边权,或者问从点x出发,只经过边权>=y的边,能到达多少个点n<=50000,m,q<=10^5Solution数据结构学傻了.jpg考虑对操作分块,我们只考虑一段操作带来的影响将这个操作块内的询问和修改分开,将询问按权值排序,将所有边按边权排序,先不考虑修改操作的边...

2019-06-26 16:20:30

[校内模拟]Invert

Description在一个n*n的棋盘上,每个格子要么是黑色,要么是白色有两个人在博弈,每次操作者可以选择一个白色格子,和一个不超过k的正整数a,然后将以这个格子为右下角的边长为a的正方形反色,需要保证这个正方形不越界,无法操作者输问先手是否必胜白色的格子为给出的m个矩形的并k,n<=1e9,m<=5e5Solution考虑另一个游戏,每个格子有若干个koishi,每次...

2019-06-03 15:39:17

THUPC2019/CTS2019 记

Day-?考完省选直接到了北京十一中集训做模拟赛天天摸鱼颓废感觉药丸饭堂好评(就是贵了点Day0去THUPC报道和samjiaBAJim范老师zzy和孔老大组队逛THU晚上睡的有点晚Day1/0土豆oj好评果然又咕了,扫雷启动看题先做母亲节题,由于懒得思考写了个一天一天往前推然后samjia上来秒了B,我负责看后面几题发现这个J可能是个流就先写了写完才发现不对冷...

2019-05-19 22:12:16

BM模板

我之前可能学了假的BMnamespaceBM{ vector<int>h[N]; intcnt,fail[N],d[N],mx; vector<int>work(intn,int*a){ h[cnt=mx=0].clear(); fo(i,1,n){ intnow=-a[i]; for(unsignedj=0;j<h[c...

2019-05-08 22:30:49

GDSOI2019退役记

退役失败QwQ

2019-05-02 17:33:14

[ZJOI2019]开关

Description有一个n位二进制数,一开始为0每一轮中对于每一个i,有pi∑pip_i\over\sump_i∑pi​pi​​的概率将这一位异或上1,每轮操作独立问第一次变成目标状态的期望步数n<=100,∑pi<=50000Solution考虑设F(x)表示在n步时变为目标状态的概率,显然有F(x)=∏epix+(−1)tie−pix2F(x)=\prod{e^...

2019-04-30 15:26:59

[CF865G]Flowers and Chocolate

Description有n种花,第i种一朵有pi片花瓣有m种巧克力,第i种一盒有ci块你现在想要买N朵花,并且买和这N朵花的花瓣总数相同的巧克力两种方案不同当且仅当买的花或巧克力的有序集不同问方案数n<=10,m<=100,pi<=1e9,N<=1e18,ci<=250Solution考虑花的生成函数,因为是有序集所以是P(x)=(∑xpi)NP(x)...

2019-04-28 22:10:57

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。