4 fyc_kabuto

尚未进行身份认证

我要认证

一个蒟蒻程序员

等级
TA的排名 1w+

codeforces814E. An unavoidable detour for home

题意:设disxdis_xdisx​为x到1的唯一最短路(必须唯一),则满足每个点度数=dxd_xdx​且disx<=disx+1dis_x<=dis_{x+1}disx​<=disx+1​的图有多少种n<=50,2<=dx<=3n<=50,2<=d_x<=3n<=50,...

2019-02-28 21:49:22

codeforces1129D. Isolation

题意:将一个序列分段,每段至多有kkk个数恰好出现一次,问方案数题解:n2n^2n2dp很容易,当(l,r)(l,r)(l,r)满足条件时f[l−1]−>f[r]f[l-1]->f[r]f[l−1]−>f[r]考虑怎么快速求出所有满足条件的fff的和记录一下每种颜色最后出现位置和次后出现位置,可以将题意转化为区间加,为所有值<=k&...

2019-02-26 10:32:27

bzoj 5451: 字符串

题意:给定正整数m以及n个01串s1~sn,你需要求出长度为2m的反对称的包含这n个01串作为子串的01串的个数。对998244353取模。一个01串s是反对称的当且仅当它对于1<=i<=∣s∣1<=i<=|s|1<=i<=∣s∣都满足s[i]≠s[∣s∣−i+1]s[i]≠s[|s|-i+1]s[i]̸​=s[∣s∣−i+1...

2019-02-24 19:57:39

生成函数常用公式

1(1−ax)m=∑nCn+m−1m−1anxn\frac{1}{(1-ax)^m}=\sum_nC_{n+m-1}^{m-1}a^nx^n(1−ax)m1​=n∑​Cn+m−1m−1​anxnex=∑i=0xii!e^x=\sum_{i=0}\frac{x^i}{i!}ex=i=0∑​i!xi​ex+e−x2=∑i=0x2i(2i)!\frac{e^x+e^{-x}}{2}=\sum_{i=...

2019-02-22 10:35:44

loj6268. 分拆数

题意:求111~nnn的分拆数。题解:考虑其生成函数为F(x)=∑if(i)xiF(x)=\sum_if(i)x^iF(x)=∑i​f(i)xi那么F(x)=∏i=111−xiF(x)=\prod_{i=1}\frac1{1-x^i}F(x)=∏i=1​1−xi1​两边取对数得ln⁡F(x)=∑i=1ln⁡11−xi\ln F(x)=\sum_{i=1}\ln\frac1{1-x^i}...

2019-02-22 10:11:55

loj2409. 「THUPC 2017」小 L 的计算题 / Sum

题意:fk=∑i=1naikf_k=\sum_{i=1}^n a_i^kfk​=i=1∑n​aik​求出f1f_1f1​~fnf_nfn​题解:考虑构造fff的生成函数FFF设A(x)=∑jaijxjA(x)=\sum_j a_i^jx^jA(x)=∑j​aij​xj则F(x)=∑inA(i)F(x)=\sum_i^n A(i)F(x)=∑in​A(i)FFF的系数即是∑i=1nai...

2019-02-22 09:40:05

codeforces891ELust

题意:一个序列a,做k次下列操作:1、随机一个下标xxx,答案加上Πi=1,i!=xnai\Pi_{i=1,i!=x}^na_iΠi=1,i!=xn​ai​2、将axa_xax​减一。求答案的期望。题解:感受一下,可以发现答案是这个Πai−Π(ai−bi)\Pi a_i-\Pi(a_i-b_i)Πai​−Π(ai​−bi​)其中bib_ibi​表示iii被减了几次。那么设Fi(x)...

2019-02-21 20:01:00

[UOJ]#36. 【清华集训2014】玛里苟斯 线性基+分类讨论

题意:魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心,于是他想了一道数学题。SSS 是一个可重集合,S=a1,a2,…,anS={a1,a2,…,an}S=a1,a2,…,an。等概率随机取 S 的一个子集 A=ai1,…,aimA={ai1,…,aim}A=ai1,…,aim。计算出 AAA 中所有元素异或 xxx, 求 xkx^kxk 的期望。题解:tybcode:#in...

2019-02-15 15:31:37

3450: Tyvj1952 Easy

题意:某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:(我们来简化一下这个游戏的规则有nnn次点击要做,成功了就是ooo,失败了就是xxx,分数是按comb计算的,连续aaa个comb就有a∗aa*aa∗a分,comb就是极大的连续ooo。比如ooxxxxooooxxxooxxxxooooxxxooxxxxooooxxx,分数就是2∗2+4∗4=4+16=202*2...

2019-01-31 15:08:55

3133: [Baltic2013]ballmachine

题解:第一步,读懂题,可以看下discuss那么对每个球求出优先级,开个堆记录当前有什么空位再开个线段树记录每个点最上面的点的深度,倍增上去修改即可code:#include<queue>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>...

2019-01-30 09:36:41

3090: Coci2009 [podjela]

题意:有 N 个农民, 他们住在 N 个不同的村子里. 这 N 个村子形成一棵树.每个农民初始时获得 X 的钱.每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民.对于每个农民给定一个值 v_i, 求(1) 最少需要多少次操作, 使得每个农民最终拿到的钱 >= 给定的值.题解:想到树形背包dp就很好做了。显然每对人只会交易一次,所以总数不超...

2019-01-30 09:30:24

4665: 小w的喜糖

题意:求数字可重的错排。题解:考虑2n2^n2n容斥,枚举哪些位一样,就是∑T∈S(−1)∣T∣(n−∣T∣)!Π(ai−bi)!\sum_{T \in S}(-1)^{|T|}\frac{(n-|T|)!}{\Pi(a_i-b_i)!}∑T∈S​(−1)∣T∣Π(ai​−bi​)!(n−∣T∣)!​其中bib_ibi​为每种颜色已用个数。考虑dp这个式子,f[i][j]f[i][j]f...

2019-01-25 10:41:57

uoj 395. 【NOI2018】你的名字

题意:给出一个模式串SSS,多次询问询问串有多少本质不同的子串在s[l,r]s[l,r]s[l,r]中没有出现。题解:这题好像不是很难首先68分比较sb,对于每个TTT的前缀,只要能求出最短的还没有在TTT中出现过的,和最短的还没有在SSS中出现过的后缀,就能计算这个前缀的贡献。转为求最长的出现过的,就是sam经典操作。现在加上了l,rl,rl,r这个限制,影响的只有在SSS中的的部分...

2019-01-24 11:14:38

3106: [cqoi2013]棋盘游戏

题意:一个n*n(n>=2)棋盘上有黑白棋子各一枚。游戏者A和B轮流移动棋子,A先走。A的移动规则:只能移动白棋子。可以往上下左右四个方向之一移动一格。B的移动规则:只能移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。和通常的“吃子”规则一样,当某游戏者把自己的棋子移动到对方棋子所在的格子时,他就赢了。两个游戏者都很聪明,当可以获胜时会尽快获胜,只能输掉的时候会尽量拖延时间。...

2019-01-16 21:05:55

2119: 股市的预测

题意:问差分后相隔为b的相同子串对数题解:好题啊首先枚举子串的长度L有一个不错的思路是每隔L放一个障碍点,对于每个点统计穿过这个点的答案个数,能做到不重不漏对于关键点i,设l=i,r=i+B+Ll=i,r=i+B+Ll=i,r=i+B+L求出(1,l),(1,r)(1,l),(1,r)(1,l),(1,r)的lcs和(l,n),(r,n)(l,n),(r,n)(l,n),(r,n)...

2019-01-16 20:57:40

3734: [Ontak2013]Miny

题意:一个平面内有N个地雷,分布在X轴上。每个地雷爆炸后影响的范围是一个贺。在这圆内的地雷也会引爆。现在告诉你每个地雷所在坐标Xi及爆炸半径Ri。请问:这些雷中任一个被引爆后一共会有多少个雷爆炸,注意爆炸是会引起连锁反应的。题解:显然是线段树优化建图+拓扑。然而,因为懒,random_shuffle可以水过code:#include<cmath>#include<...

2019-01-16 20:49:10

3440: 传球游戏

题意:当被传到球之后,不同的人会做出不同的动作。第1类人,顺着传来的方向传给下一个人。第2类人,逆着传来的方向传给上一个人。第3类人,顺着传来的方向传给下面第二个人。第4类人,逆着传来的方向传给上面第二个人。现不知是从哪个人开始传,及开始传的方向,求有哪些人无论如何,最多只能碰到一次球题解:显然可以拆点,一种表顺时针传过来,一种逆时针,连向下一个点。那么就是奇环外向树森林了,拓扑...

2019-01-16 20:47:05

2728: [HNOI2012]与非

题意:定义a NAND b=!a&b,问用给出的数通过NAND操作能构成区间内多少个数。题解:经过各种实验,发现NAND操作可以替代任何其他逻辑运算操作。如a&b=!aNANDb,!a=aNANDa或和异或也显然可以。那么似乎我们可以构造出所有数了?但是有个问题,假如对于每个数都有第i位和第j为相等,显然最后这两位也是一样的。所以题意转化成了某些位置必须相同,且在[...

2019-01-15 11:45:42

2671: Calc

题意:问多少对a,ba,ba,b满足1≤a<b≤n1 \le a < b \le n1≤a<b≤n且(a+b)∣ab(a+b)|ab(a+b)∣ab题解:先考虑什么情况满足a+b∣aba+b|aba+b∣ab设d=gcd(a,b)d=gcd(a,b)d=gcd(a,b),则a′d+b′d∣a′b′d2−>a′+b′∣a′b′da&#x...

2019-01-15 08:58:41

hdu 5181 numbers

题意:问多少种出栈方式满足所有限制:xix_ixi​在yiy_iyi​前先出栈。题解:容易看出,一个合法的括号序列一定对应一棵先序遍历为0~n的树(加个虚根)。而这些限制就是当xi<yix_i<y_ixi​<yi​,则yiy_iyi​在xix_ixi​子树外,当xi>yix_i>y_ixi​>yi​,则yiy_iyi​在x...

2019-01-14 20:32:26

查看更多

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