• 等级
  • 126991 访问
  • 539 原创
  • 5 转发
  • 5129 排名
  • 68 评论
  • 123 获赞

51nod1819 :黑白树 V2(树链剖分)

传送门 题解: NOIP之前当然要做做NOIP题啦! 这道题并不难(想),把一个点的权值定为(u−fau)(u-fa_u)(u−fau​)乘上子树黑点个数,然后就相当于是支持查询链和,链修改,子树修改了,用了链剖分开维护奇偶的情况即可。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const ...

2018-11-09 18:06:30

Topcoder SRM 702 1000pts:FindingFriends(分治)

题解: 这道题很妙啊。 显然是要二分之后每个位置找到前后第一个合法位置,分别记为Li,RiL_i,R_iLi​,Ri​,然后要求包含任意一个。 这个时候我们只需要找到1∼n1\sim n1∼n中间第一个非法的位置,然后递归下去做就好了,问题是怎么找到这个非法位置。 显然这是一个区间内的二维偏序,也就是三维偏序,可以KD树做或者线段树+主席树做,不过复杂度多了一个log⁡n\log nlogn,这时...

2018-11-09 11:19:18

Topcoder SRM 700 1000pts:AnyNumber(DP)

题解: 首先放满一行之后我们强制规定他可以继续放,这样总方案数是A(∑∣S∣,n)A(\sum |S|,n)A(∑∣S∣,n),一个方案可能被算很多次。 处理出fi,jf_{i,j}fi,j​表示前iii个第一次放满行为jjj的概率,hi,jh_{i,j}hi,j​表示前iii个种选一些数放满第jjj行的值的总和(包括第iii个),然后这道题就可以做了。 对于fff的处理只需要背包即可,对于hhh...

2018-11-09 09:13:17

THUPC2017 I :Sum(牛顿恒等式)

题意: 给定数组A1...,AnA_1...,A_nA1​...,An​,对于所有1≤i≤k1 \le i \le k1≤i≤k,求Si=∑jAjiS_i = \sum_{j}A_j^iSi​=∑j​Aji​。 题解: 这道题要用到一个叫牛顿恒等式的玩意儿。 对于nnn次多项式f=∑i=0naixif=\sum_{i=0}^na_ix^if=∑i=0n​ai​xi(注意是首一多项式),设其几个根分...

2018-11-08 10:05:57

计蒜之道2017复赛:商汤智能机器人(组合数学)

传送门 题解: 日常划水。。 枚举一下步数,其实是要求∑t=0b(a+tb)(bt)\sum_{t=0}^b \binom{a+t}{b}\binom{b}{t}∑t=0b​(ba+t​)(tb​)。 不妨记其为S(a,b)S(a,b)S(a,b),发现模数很小,于是可以根据lucas定理递归到S(a/p,b/p)S(a/p,b/p)S(a/p,b/p)和S(a/p+1,b/p)S(a/p+1,b...

2018-11-07 22:22:17

集训队作业2018:Z-function(DP)

传送门 题解: 枚举相同位置的长度是多少,然后可以设计一个DP,fi,jf_{i,j}fi,j​表示第iii位,相同状态为jjj的方案数(注意这里要带个-1的系数方便容斥),然后发现这个状态数很少,就可以过了。 #include <bits/stdc++.h> using namespace std; typedef unsigned long long ULL; const in...

2018-11-07 19:10:56

UOJ#273. 【清华集训2016】你的生命已如风中残烛(组合数学)

传送门 题解: 首先所有位置先-1,然后考虑m!m!m!种排列,如果全部后缀和小等于0(前缀和大等于0)那么是个合法排列,否则不合法。 这个时候有个自然的想法就是把小于0的最小的位置(若有多个则选最靠后的)放到这个排列后面,然后就又对应着一个合法的排列了,不过这样做每个排列对应的方案可能不一样,这时候就有个经典做法,就是在最后面放一个-1,这个时候就变成了所有前缀大等于0,最后等于-1。此时我们会...

2018-11-07 12:08:33

UOJ#420. 【集训队作业2018】矩形(组合数学)

传送门 题解: 这种题再也不想做第二次了,思想很简单,但是细节贼多。 考虑每个aia_iai​(就是题面中的fif_ifi​)的贡献,显然是∑j=in(bhm)j∑k(j+k−ij−i)(ah)k\sum_{j=i}^n (bh^m)^j\sum_k\binom{j+k-i}{j-i} (ah)^kj=i∑n​(bhm)jk∑​(j−ij+k−i​)(ah)k。 不妨设fn=∑i=0n∑j=0m...

2018-11-06 15:53:39

UOJ#418. 【集训队作业2018】三角形(线段树合并)

传送门 题解: 加入一个数,相当于是先加上Ai=wiA_i=w_iAi​=wi​,再减去Bi=∑j∈soniwjB_i = \sum_{j \in son_i} w_jBi​=∑j∈soni​​wj​,然后代价就是一个操作序列的前缀最大值。 先考虑一下没有限制的的时候,怎么使得这个前缀最大值最小,我们可以分为两个部分:Ai−Bi<0,Ai−Bi≥0A_i - B_i \lt 0,A...

2018-11-05 22:45:22

UOJ#272. 【清华集训2016】石家庄的工人阶级队伍比较坚强(循环卷积)

传送门 题解: 看做一个nnn元333次方程在做循环卷积即可。 注意333次单位根可以直接扩域而不用去解三次剩余(只不过要卡常数)。 #include <bits/stdc++.h> using namespace std; const int RLEN=1<<18|1; inline char nc() { static char ibuf[RLEN],*ib,*ob...

2018-11-04 20:11:40

UOJ#271. 【清华集训2016】连通子树(虚树+倍增)

传送门 题解: 注意到每种颜色个数比较少,于是建出虚树后暴力背包,用倍增维护一下虚链上的DP值即可。 所以说你只需要5个倍增数组和一些卡常技巧加上无数的小细节就可以通过这道题了。 不说了我去睡觉了。 #include <bits/stdc++.h> using namespace std; typedef pair <int,int> pii; const int RLEN...

2018-11-03 01:24:06

UOJ#269. 【清华集训2016】如何优雅地求和(FFT)

传送门 题解: 把fff二项式变换一下就行了,变换可以用二项式反演。 #include <bits/stdc++.h> using namespace std; const int RLEN=1<<18|1; inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob) && (ob=(ib=i...

2018-11-02 15:49:11

UOJ#268. 【清华集训2016】数据交互(链分治)

传送门 题解: 首先一个显然重要的结论是两个链相交当且仅当一个链的lca在另一条链的路径上,或者lca相同。 先链剖,然后我们对于每个点计算以这个点为lca的最大路径,分为两种情况: 1.路径位于两个虚儿子中。这种情况很简单,因为每个点到根只有O(log⁡n)O(\log n)O(logn)条虚边,每个点维护一个multiset就行了。 2.一条位于实儿子中。每个点到根只有O(log⁡n)O(\l...

2018-11-02 14:48:15

BZOJ3112: [Zjoi2013]防守战线(单纯形+对偶原理)

传送门 题解: 单纯形立水之。 #include <bits/stdc++.h> using namespace std; typedef double DB; const int RLEN=1<<18|1; inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob) && (ob=(ib=i...

2018-11-01 21:50:46

51nod1538: 一道难题(特征多项式+多项式取模/求逆)

传送门 题解: 观察下这个等式,其实就是fn=∑ifn−aif_n = \sum_{i}f_{n-a_i}fn​=∑i​fn−ai​​。 前面的求逆预处理一下,后面的特征多项式倍增和取模就行了,时间复杂度O(klog⁡klog⁡m)O(k \log k \log m)O(klogklogm)。 注意a1a_1a1​可能大于23333,RE了半天。。 #include <bits/stdc++...

2018-11-01 20:26:13

多项式多点求值与快速插值

考虑给定多项式fff,如何求f(x1),f(x2),f(x3),...,f(xn)f(x_1),f(x_2),f(x_3),...,f_(x_n)f(x1​),f(x2​),f(x3​),...,f(​xn​)。 构造g=∏i=1n2(x−xi),h=∏i=n2+1n(x−xi)g=\prod\limits_{i=1}^{\frac{n}{2}}(x-x_i),h=\prod\limits_{i=...

2018-11-01 18:55:06

2017集训队作业自选题#111: 资源采集(KD树)

题解: KDtree查询矩阵,如果最后一次修改的时间全部一样,那么直接在子树里讨论两种情况,线段树合并支持查询。 否则暴力递归删除子树标记,容易知道复杂度为O(nnlog⁡n)O(n \sqrt{n} \log n)O(nn​logn)。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const...

2018-11-01 14:51:15

Codechef:Easy exam(斯特林数)

传送门 题解: 记xj,ix_{j,i}xj,i​表示第jjj轮掷骰子掷出iii。则ans=∏i=1L(∑j=1nxj,i)Fans=\prod_{i=1}^L(\sum_{j=1}^nx_{j,i})^Fans=i=1∏L​(j=1∑n​xj,i​)F 然后展开考虑单项贡献,显然一个单项式对于一个iii如果有jjj轮的xj,ix_{j,i}xj,i​出现,贡献为SF,znz‾S_{F,z}n^{...

2018-10-30 20:55:54

Codechef:Sum of Cubes/SUMCUBE(斯特林数)

传送门 题解: 把(∑ixi)k(\sum_ix_i)^k(∑i​xi​)k拆开考虑单项式贡献,然后就只用考虑h(h≤3)h(h \le 3)h(h≤3)条边,www个点同时存在的方案数了,关键部分三元环计数可以做到O(mm)O(m \sqrt{m})O(mm​)。 #include <bits/stdc++.h> using namespace std; typedef long l...

2018-10-30 11:12:27

Atcoder AGC018 简要题解

传送门 Coins 先转化为一个点只有两种属性xi,yix_i,y_ixi​,yi​,选出XXX个xix_ixi​,X+YX+YX+Y个xi+yix_i+y_ixi​+yi​的最大值。 如果固定选的集合那么肯定要选yiy_iyi​前kkk大的,我们枚举一下第kkk大的yiy_iyi​是多大然后在两边贪心即可。 #include <bits/stdc++.h> using namespa...

2018-10-29 16:28:46

DZYO

Never stop
关注
  • 计算机软件/Senior
  • 中国 四川省 眉山市
奖章
  • 持之以恒
  • 1024勋章