4 Freopen

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 5k+

字符串作业(三)

LOJ #6158. A + B Problem给出一个数字,求在其中两位之间插入一个加号后得到的答案末尾000最多的个数。题解:第二个数的末尾就是原串的末尾,所以如果需要和第一个数加起来末尾为000,那么从后往前扫,第二个数为000的位在不进位的情况下第一个数的对应位需要是000,不为000的位的对应位xxx应该是10−x10 - x10−x,然后开启进位模式所有数的对应位都是9−x9-x9−x,然后求一个原串和转换后的串的最长公共前缀即可得出答案,可以写exkmp\rm exkmpexkmpAC

2020-07-06 17:36:39

20200704模拟赛

T1sub1sub1sub1没有问号的情况下,考虑如何线性判定。考虑每两位当作一组,对于每组有如下两种操作:将两位依次压入栈中;将第一位与栈中全部元素合并后,再将第二位压入栈中。可以发现栈中的情况可以看作是关于下一个压入元素的函数,即 G[a,b](x)G[a, b](x)G[a,b](x),表示当 $x = 0 $时返回 aaa,x=1x = 1x=1 时返回 bbb。假设当前栈中情况为 G[a,b](x)G[a, b](x)G[a,b](x),考虑压入两位 c,dc, dc,d,容易根据

2020-07-04 16:13:58

CF1278F Cards 加强版

题目设p=1mp = \frac 1mp=m1​ans=∑i=0k{ki}pi(ni)i!=∑i=0k∑j=0i(ij)(ni)pi(−1)j(i−j)k=∑j=0k(−1)j(nj)∑i=jk(n−ji−j)pi(i−j)k=∑j=0k(−1)jpj(nj)∑i=0k−j(n−ji)piik=∑i=0kikpi∑j=0k−i(−p)j(nj)(n−ji)=∑i=0kikpi(ni)∑j=0k−i(−p)j(n−ij)\begin{aligned} ans &= \sum_{i=0}^k \be

2020-07-03 22:38:34

LOJ #2476. 「2018 集训队互测 Day 3」蒜头的奖杯(三元环计数)

题目泰勒应天下大雨!类似于SDOI2018SDOI2018SDOI2018旧试题。给DDD,EEE,FFF卷上μ\muμ。得到D′,E′,F′D',E',F'D′,E′,F′。原式变为∑i,j,kAiBjCk∑a∣i,a∣jDa′∑b∣i,b∣kEb′∑c∣j,c∣kFc′\sum_{i,j,k} A_iB_jC_k \sum_{a|i,a|j} D'_a \sum_{b|i,b|k} E'_b \sum_{c|j,c|k} F'_ci,j,k∑​Ai​Bj​Ck​a∣i,a∣j∑​Da′​b∣i

2020-07-03 21:12:58

各种反演等数学难题

CF997C Sky Full of Stars求n×nn\times nn×n的网格内每个格子染三种颜色,其中至少有一行或一列是同一种颜色的方案数。转化为求没有一行或一列颜色相同。直接枚举相同的行列数进行容斥:=3∑i=0n(ni)(−1)i∑j=0n(nj)(−1)j3(n−i)(n−j)+2∑i=1n(ni)(−1)i3n(n−i)(3i−3)−2×3n2=3∑i=0n(ni)(−1)i(3n−i−1)n+2∑i=1n(ni)(−1)i3n(n−i)(3i−3)−2×3n2\begin{ali

2020-07-03 11:36:28

生成函数、组合数学

[ARC089D] ColoringBalls咕着咕着[ARC096C] Everything on It容斥,枚举有kkk种元素用了≤1\leq 1≤1次,其中有jjj种元素用了111次。则答案为:∑k=0n(−1)k(nk)22n−k∑j=0k(kj)∑p=0j{jp}2(n−k)p\sum_{k=0}^n(-1)^k\binom nk2^{2^{n-k}}\sum_{j=0}^k \binom kj\sum_{p=0}^j \begin{Bmatrix}j\\p\end{Bmatrix}

2020-07-02 19:54:52

线性代数,概率与期望题单

「SDOI2017」龙与地下城CodeForces - 506E Mr. Kitayuta’s Gift LOJ #6295. 无意识之外的捉迷藏

2020-07-01 20:44:50

保序回归问题在序列上的特殊做法

LG P4331 [BalticOI 2004]Sequence 数字序列远古论文题。所以就可以单调栈维护区间的LpL_pLp​均值,如果前面的均值比后面大则合并区间。最后单调栈中的区间的LpL_pLp​均值就是一个可行方案。注意L2L_2L2​等均值是可以O(1)O(1)O(1)求的,比如上面的论文。但是L1L_1L1​的均值是中位数,还得写可并堆,这种情况真的罕见。再来一道例题:2020 Petrozavodsk Winter Camp, Jagiellonian U Contest

2020-06-30 22:44:55

多项式题单

LOJ #556. 「Antileaf’s Round」咱们去烧菜吧求混合背包(某一体积的物品可能有无限个也可能有有限个),得到体积和为1...n1...n1...n的方案数。热身题。如果一个体积为vvv的物品有无限个,那么其关于体积的普通生成函数为∑i=0xvi=11−xv\sum_{i=0}x^{vi} = \frac 1{1-x^v}∑i=0​xvi=1−xv1​如果一个体积为vvv的物品有KKK个,那么其关于体积的普通生成函数为∑i=0Kxvi=1−xv(K+1)1−xv\sum_{i=0}

2020-06-30 15:33:00

难题训练(二)

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest.Problem G. Invited Speakers给出两个大小为nnn的点集,其中所有点的横纵坐标都不一样,给两个点集做匹配,两个点之间的匹配是坐标系中若干条平行于坐标轴的首尾相连的线段,求使得不同匹配不相交的匹配方案。因为横纵坐标都不一样,按照横坐标排序两个点集,然后对位匹配,确定一个大常数CCC,走ai→(ai.x,C+i)→(C+i,C+i)→(C+i,−C−i)→(bi.x,−C−i)

2020-06-27 09:55:56

难题训练(一)

「EC Final 2019」狄利克雷 k 次根题意:给出一个函数的前nnn项g(1),g(2)....g(n)g(1),g(2)....g(n)g(1),g(2)....g(n),求它在狄利克雷卷积意义下的kkk次根fff的前nnn项,这里的狄利克雷卷积是指h(n)=∑d∣nf(d)g(nd) mod ph(n) = \sum_{d|n} f(d)g(\frac nd)\bmod ph(n)=∑d∣n​f(d)g(dn​)modp。n≤1e5n \leq 1e5n≤1e5做法:容易发现fp=ϵf^p

2020-06-25 19:05:34

两类递推数列

此博客是抄论文的,你可以认为是转载的1.线性递推数列有限数列显然是线性递推数列。无限数列aia_iai​设其生成函数为A(x)A(x)A(x)那么如果A(x)A(x)A(x)能被表示为C(x)B(x)\frac {C(x)}{B(x)}B(x)C(x)​的形式,其中B(x)[x0]=1B(x)[x^0] = 1B(x)[x0]=1,则A(x)A(x)A(x)是线性递推数列。常数项为111是因为递推式你要让∑j=0bjai−j=0\sum_{j=0}b_ja_{i-j} = 0∑j=0​bj​ai−

2020-06-22 22:18:39

[NOI2019]序列(模拟费用流)

题目费用流建出来大概是下面的图(没有写边权的边都是容量∞\infty∞,费用为000)所以这个图有444种流法(其实有555种,但是第555种在实际实现中可以被这444种覆盖。)1.1.1.类似于A→D→D′→JA \rightarrow D \rightarrow D' \rightarrow JA→D→D′→J的流,直接把ai+bia_i+b_iai​+bi​选中。2.2.2.类似于A→D→F→G→C′→JA\rightarrow D \rightarrow F \rightarrow G\r

2020-06-22 16:56:31

CQOI 2020 无事可记

联合省选是真的无聊Day0Day0Day0复习了一堆Day1Day2Day1Day2Day1Day2都没考的知识点。Day1Day1Day1T1.冰火战士线段树上二分即可。写完之后才发现是最高温度,逼的我又写了个线段树二分,发现要跑6s,就懒得卡常了,出来发现自己还是跑的很快的Code\mathcal CodeCode#include<bits/stdc++.h>#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)#d

2020-06-22 11:34:45

BZOJ 5384 有趣的字符串题(区间本质不同回文串数量)

题意:多次求区间本质不同回文串数量。我们知道区间本质不同子串个数是SAM+LCT+BIT。所以区间本质不同回文串个数就是PAM+SegmentTree+BIT。为什么可以搏一搏LCT变线段树呢?因为PAM同时有着组合border的离谱性质。套用区间本质不同子串个数的做法。那么我们需要离线后移动右端点RRR,然后更新一系列PAM上的节点的最后一次出现的时间并且在BIT上维护关于[L,R][L,R][L,R]内的本质不同回文串个数。考虑PAM上一条链,满足每个祖先都是后代的回文后缀,也就一定是b

2020-06-18 15:56:16

计算几何作业(下)

HDU 3320 openGL重要的就是绕任意轴旋转这个离谱操作。我们把绕一个轴顺时针旋转视为正方向(从轴的负方向往正方向看。)其中坐标系如图所示:那么容易发现绕zzz轴旋转正的α\alphaα的角度。相当于在OxyOxyOxy平面上顺时针绕α\alphaα,也就是x′=rcos⁡(θ+α)=xcos⁡α−ysin⁡α,y′=rsin(θ+α)=ycos⁡α+xsin⁡α=sin⁡αx+cos⁡αyx' = r\cos(\theta + \alpha) =x\cos\alpha-y\sin\a

2020-06-17 15:13:35

计算几何作业(上)

好多HDU的题,我想死。HDU 6325 Problem G. Interstellar Travel求从左到右字典序最小上凸壳,注意这个题不能选多个重点。AC Code\mathcal AC \ CodeAC Code#include<bits/stdc++.h>#define maxn 200005#define LL long long#define Ct const#define rep(i,j,k) for(int i=(j),LIM=(k);i&l

2020-06-16 11:58:24

仙人掌、圆方树、支配树、舞蹈链作业(下)

HDU 4694 Important Sisters求从nnn出发,每个点的所有支配点的编号和。支配树,有够板。AC Code\mathcal AC \ CodeAC Code#include<bits/stdc++.h>#define maxn 50005#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)#define per(i,j,k) for(int i=(j),LIM=(k);i>=LI

2020-06-15 22:38:18

支配树学习笔记

博客1博客2好了上面两篇博客应该是全网关于支配树最重要的博客了。接下来就是定一个小目标,把模板缩到20行。显然不行注意:这个模板对多组数据不友好,对图不联通可以求,但是注意有些坑。Code\mathcal CodeCode#include<bits/stdc++.h>#define maxn 300005#define maxm 300005#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)#define per(

2020-06-15 21:28:43

仙人掌、圆方树、支配树、舞蹈链作业(上)

[APIO2018] Duathlon 铁人两项求有多少个三元组(s,c,f)(s,c,f)(s,c,f)满足s,c,fs,c,fs,c,f互不相同,而且在给定的图上存在一条从sss经过ccc到达ttt的简单路径。建出圆方树,两个圆点s,fs,fs,f可以选择的ccc为路径中所有的点双中的点,定义方点的权值为其所代表的点双的点数,圆点的权值为−1-1−1,那么两个圆点可以选择的点数就是路径上的权值和(因为sss和fff是圆点,所以c=sc=sc=s或ttt的情况是被减去了的),反过来dpdpdp每个点被

2020-06-15 18:03:47

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取