5 wennitao

尚未进行身份认证

暂无相关简介

等级
TA的排名 18w+

Luogu3826 NOI2017 蔬菜

题面:luogu3826题意:有nnn种蔬菜,第iii种初始有cic_ici​个,每卖出一个获得aia_iai​的收益,卖出的第一个有额外sis_isi​的收益,每天会腐烂xix_ixi​个。每天最多卖mmm个蔬菜。给出kkk个询问,问卖pip_ipi​天蔬菜最多能获得多少收益。题解:蔬菜减少很不好处理,考虑按天数从后往前做,每天多xix_ixi​个蔬菜。因为每种蔬菜不会减少,如果往前一天来...

2019-07-08 15:28:41

Luogu3825 NOI2017 游戏

题面:luogu3825题意:nnn场比赛,三种车型A,B,CA, B, CA,B,C。每场比赛规定不能使用一种车型或是无限制,另有mmm条限制如果第iii场使用hih_ihi​车型,那么第jjj场必须使用hjh_jhj​车型。输出一个比赛车型的合法方案,或−1-1−1。n≤5×104n \le 5 \times 10^4n≤5×104,m≤105m \le 10^5m≤105,无限制场数≤8\...

2019-07-08 12:21:21

Luogu3824 NOI2017 泳池

题面:luogu3824题意:宽为nnn米,高为100110011001米的长方形网格,每个格子有qqq的概率是安全的。问以最下面一行为底边的最大的安全子矩阵的大小恰好为KKK的概率。n≤109n \le 10^9n≤109,k≤1000k \le 1000k≤1000题解:首先转化问题为求矩阵大小小于等于KKK的概率。答案即为≤K\le K≤K减去≤K−1\le K - 1≤K−1设dp[...

2019-07-07 22:24:14

Luogu3823 NOI2017 蚯蚓排队

题面:luogu3823题意:nnn只蚯蚓,每只蚯蚓有一个≤6\le 6≤6的长度,初始时每只蚯蚓一支队伍。给出mmm个操作。三种操作:将以iii结尾的队伍和以jjj开头的队伍合并,且iii的队伍在前。将iii和iii后面一只蚯蚓处断开,分为两支队伍。定义以第xxx只蚯蚓开始的长度为kkk的数字串为:从xxx开始的连续kkk只蚯蚓,它们的长度数字连成的字符串。定义给定一个字符串sss和...

2019-07-07 12:20:05

Luogu3822 NOI2017 整数

题面:luogu3822题意:有一个二进制整数初始为000。两种操作:加a⋅2ba \cdot 2^ba⋅2b;询问二进制下第kkk位的值。操作数n≤106n \le 10^6n≤106,∣a∣≤109|a| \le 10^9∣a∣≤109,0≤b,k≤30n0 \le b, k \le 30n0≤b,k≤30n题解:对加和减(对应aaa的正负)分别维护二进制数,记做incincinc和dec...

2019-07-07 10:41:14

Luogu4774 NOI2018 屠龙勇士

题面:luogu4774题意:有nnn条龙,初始生命值aia_iai​,恢复能力pip_ipi​,生命值为负时会恢复,当它生命值恰好为000时死亡。初始有mmm把剑,每把剑有攻击力。每次会选择攻击力≤\le≤龙初始生命值且攻击力最大的剑,若不存在则选择攻击力最小的剑。当击杀一条龙时,使用的剑会消失,同时会奖励一把新的剑。现在按照1→n1 \to n1→n的顺序杀龙,固定对每条龙攻击xxx次,求最...

2019-07-05 18:52:35

Luogu4770 NOI2018 你的名字

题面:luogu4770题意:给定一个串SSS。每次询问给出一个字符串TTT,问TTT有多少个不同的子串使得其也不是S[l…r]S[l … r]S[l…r]的子串。∣S∣≤5×105|S| \le 5 \times 10^5∣S∣≤5×105,q≤105q \le 10^5q≤105,∑∣T∣≤106\sum |T| \le 10^6∑∣T∣≤106题解:首先考虑部分分l=1,r=∣S∣l =...

2019-07-05 18:36:38

Luogu4769 NOI2018 冒泡排序

题面:luogu4769题意:给定一个排列ppp。求字典序严格大于ppp,且冒泡排序交换次数=∑i=1n∣i−pi∣= \sum _{i = 1} ^n |i - p_i|=∑i=1n​∣i−pi​∣的排列个数。n≤6×105n \le 6 \times 10^5n≤6×105题解:整理自luogu题解可以证明该问题等价于最长下降子序列的长度不能超过2。因为如果长度大于2,那么中间的元素会被...

2019-07-05 16:39:20

Luogu4768 NOI2018 归程

题面:luogu4768题意:给定一张nnn个点mmm条边的无向连通图,每条边有长度和海拔。给qqq个询问,强制在线,每次询问指定一个水位线ppp和出发点vvv,能够从vvv开始无代价走过若干条海拔大于ppp的边到达v′v'v′后,再从v′v'v′花路线长度的代价走到111号节点。求最小代价。n≤2×105,m≤4×105,q≤4×105n \le 2 \ti...

2019-07-05 16:21:48

扩展卢卡斯ExLucas

扩展Lucas定理用于求:(nm)mod  p\binom n m \mod p(mn​)modp,其中ppp不一定为素数求法首先对ppp进行素因数分解:p=∏ipikip = \prod _i p_i ^{k_i}p=∏i​piki​​显然pikip_i^{k_i}piki​​之间两两互素,因此如果能求出(nm)mod&Th...

2019-06-20 19:54:22

uoj455 雪灾与外卖

题面:uoj455题意:有nnn只老鼠和mmm个洞,每个洞有容量限制和一个费用。要求每只老鼠进一个洞,使所有老鼠的移动距离和加进洞费用和最小。题解:模拟费用流(贪心+反悔)将所有的老鼠和洞按位置排序。考虑先让老鼠向左边的洞匹配。维护老鼠和洞两个堆:MMM,HHH。老鼠移动的距离为右减左。当前是老鼠:坐标为xxx,从洞堆HHH中取出最优解vvv,则代价为x+vx+vx+v,这样只考虑了向左...

2019-06-10 20:59:38

bzoj3456 城市规划

题面:bzoj3456题意:求nnn个点的简单无向连通图的方案数题解:设g(n)g(n)g(n)为简单无向图的方案数,f(n)f(n)f(n)为简单无向连通图的方案数g(n)=2Cn2g(n) = 2^{C_n^2}g(n)=2Cn2​枚举111号点的连通块大小:g(n)=∑i=1nCn−1i−1f(i)g(n−i)g(n) = \sum _{i=1} ^n C_{n-1} ^{i-1} ...

2019-06-10 09:10:34

bzoj3625 小朋友和二叉树

题面:bzoj3625题意:一棵带点权的树的权值为所有点的权值和。给定mmm,求点权在给定集合中的权值为s(1≤s≤m)s(1 \le s \le m)s(1≤s≤m)的二叉树的个数。题解:设f(i)f(i)f(i)为权值为iii的二叉树个数,c(i)c(i)c(i)为集合中数的生成函数。f(n)=∑i=1nc(i)∑j=0if(j)∗f(n−i−j)f(n) = \sum _{i=1} ^...

2019-06-09 22:07:01

多项式除法

设AAA为nnn次多项式,考虑AR(x)=xnA(1x)A_R(x) = x^n A(\frac 1 x)AR​(x)=xnA(x1​)AR[i]=A[n−i]A_R[i] = A[n - i]AR​[i]=A[n−i]F(x)=Q(x)∗G(x)+R(x)F(x) = Q(x) * G(x) + R(x)F(x)=Q(x)∗G(x)+R(x)F(1x)=Q(1x)∗G(1x)+R(1x)F...

2019-06-09 13:05:50

多项式求逆

设AAA为原多项式,所求为多项式BBB即有A×B≡1mod  xnA \times B \equiv 1 \mod x^nA×B≡1modxn设A×B′≡1mod  xn2A \times B' \equiv 1 \mod x^{\frac n 2}A×B′≡1mo...

2019-06-09 11:01:52

bzoj5093 图的价值

题面:bzoj5093题意:定义一个带标号的图的价值为每个点度数的kkk次方的和 mod 998244353998244353998244353。求nnn个点带标号的简单无向图的价值和。n≤109n \le 10^9n≤109,k≤200000k \le 200000k≤200000题解:枚举每个点连多少条边:∑i=0n−1(in−1)⋅ik⋅2n(n−1)2−(n−1)\sum _{i=0}...

2019-06-09 10:28:26

bzoj4555 Tjoi2016&Heoi2016 求和

题面:bzoj4555题意:求∑i=0n∑j=0iS(i,j)⋅j!⋅2j\sum _{i=0} ^n \sum_{j=0} ^i S(i, j) \cdot j! \cdot 2^j∑i=0n​∑j=0i​S(i,j)⋅j!⋅2j mod 998244353998244353998244353,其中S(i,j)S(i,j)S(i,j)是第二类斯特林数。题解:第二类斯特林数S(i,j)S(i,...

2019-06-08 17:12:01

FFT快速傅里叶变换

前言FFT(Fast Fourier Transfromation),快速傅里叶变换,用于加速多项式乘法。朴素乘法:O(n2)O(n^2)O(n2)。FFT:O(nlogn)O(nlogn)O(nlogn)多项式的系数表示法与点值表示法系数表示法一个n−1n-1n−1次nnn项多项式f(x)f(x)f(x)可以表示为f(x)=∑i=0n−1aixif(x) = \sum _{i = 0...

2019-06-04 20:07:05

后缀自动机

后缀自动机基本描述后缀自动机:对于一个字符串SSS,它对应的后缀自动机是一个最小的确定有限状态自动机,接受且仅接受SSS的后缀。栗子:对于字符串S = “aabbabd​”,它的后缀自动机:其中红色状态是终结状态。对于SSS的后缀,都可以从SSS状态出发沿着字符标识路径转移,最后到达终结状态。特别的,对于SSS的子串,最终会走到一个合法状态;若不是SSS的子串,最后会无路可走。后缀自动...

2019-05-29 08:36:18

bzoj3512 DZY Loves Math IV

题面:bzoj3512题意:求∑i=1n∑j=1mφ(ij)\sum _{i=1} ^n \sum _{j=1} ^m \varphi (ij)∑i=1n​∑j=1m​φ(ij),1≤n≤1051 \le n \le 10^51≤n≤105,1≤m≤1091 \le m \le 10^91≤m≤109题解:nnn范围比较小,枚举nnn。即求S(n,m)=∑i=1mφ(ni)S (n, m) ...

2019-05-20 13:59:55

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。