• 等级
  • 188156 访问
  • 559 原创
  • 5 转发
  • 4898 排名
  • 88 评论
  • 166 获赞

集训队作业2018: 复读机(生成函数)

题意:群里有kkk个不同的复读机。为了庆祝平安夜的到来,在接下来的nnn秒内,它们每秒钟都会选出一位优秀的复读机进行复读。非常滑稽的是,一个复读机只有总共复读了ddd的倍数次才会感到快乐。问有多少种不同的安排方式使得所有的复读机都感到快乐(k≤1000,d≤3)(k\le1000,d\le3)(k≤1000,d≤3)。题解:挺妙的,一个人的生成函数是∑i=0∞[d∣i]i!xi\s...

2019-01-18 16:06:02

集训队作业2018: 喂鸽子(min-max容斥)

题意:小Z是养鸽子的人。一天,小Z给鸽子们喂玉米吃。一共有n只鸽子,小Z每秒会等概率选择一只鸽子并给他一粒玉米。一只鸽子饱了当且仅当它吃了的玉米粒数量≥k≥k≥k。小Z想要你告诉他,期望多少秒之后所有的鸽子都饱了。题解:min-max容斥枚举下集合大小,FFT预处理一下系数算min的期望即可。#pragmaGCCoptimize(2)#include<bits/stdc++...

2019-01-15 16:09:53

集训队作业2018: 取名字太难了(FFT)

题意:大概是求∏i=1n(x+i)\prod_{i=1}^n(x+i)∏i=1n​(x+i)系数模ppp意义下的分布。题解:分为(∏i=1p−1(x+i))⌊np⌋(\prod_{i=1}^{p-1}(x+i))^{\lfloor\frac{n}{p}\rfloor}(∏i=1p−1​(x+i))⌊pn​⌋,以及(∏i=1n mod&VeryThi...

2019-01-14 19:23:49

集训队作业2018: 树(点分治+K短路)

题解:最近学数分学到意识模糊,做到OI题冷静一下。联通块强制选根,然后用dfs序转化为一个路径然后就是做K短路了。用点分治即可在图大小为O(nlog⁡n)O(n\logn)O(nlogn)的图上做K短路,时间复杂度O(nlog⁡2n+klog⁡k)O(n\log^2n+k\logk)O(nlog2n+klogk)。#include<bits/stdc++.h>...

2019-01-12 16:50:06

Codeforces 802C :Heidi and Library (hard)(网络流)

传送门题解:比较简单的建图法就是看做小于k条流在一个n∗nn*nn∗n序列上流,其中一些位置是必须流的,然后做个上下界费用流。不过注意到肯定有一种方案使得这小于kkk条流是不相交的,于是可以直接看做有nnn个点,每个点拆点连−∞-\infty−∞的边,然后规定这个点必须是aia_iai​,然后跑个最小费用可行流,这样nnn个−∞-\infty−∞必定流满,此外其他加起来最小。最后加个n∗∞...

2018-11-30 17:33:51

Codeforces 806F:Test Data Generation(组合数学)

传送门题解:相当于是要求:∑u∑i=1⌊n2u⌋[i为奇数]∑j=1n−1[j为偶数](i−1j)\sum_{u}\sum_{i=1}^{\lfloor\frac{n}{2^u}\rfloor}[i为奇数]\sum_{j=1}^{n-1}[j为偶数]\binom{i-1}{j}u∑​i=1∑⌊2un​⌋​[i为奇数]j=1∑n−1​[j为偶数](ji−1​)然后注意这个jjj比较小,我...

2018-11-30 15:43:58

UOJ#433. 【集训队作业2018】串串(循环串/回文串)

传送门题解:这道题主要用到的几个性质(具体证明可以看题解):1.弱双回文串SSS的某个双回文划分ababab,满足aaa是SSS的最长回文前缀,或者bbb是SSS的最长回文后缀。2.弱双回文串SSS若有两个弱回文划分,则SSS为整周期串。3.弱双回文串SSS的周期为ttt,则其有∣S∣t\frac{|S|}{t}t∣S∣​个不同的弱回文划分。我们先计算本质不同的双回文串划分,然后减去算...

2018-11-27 20:26:49

集训队作业2018: 通信(区间DP)

题意:题解:想到了大概思路就是不会有相交的非链上的边,然而有一堆细节就鸽了。然后看题解其实就是暂时忽略两边的值来区间DP就行了,设置的状态还挺妙的,中间记个前缀后缀min优化一下,时间复杂度O(n3)O(n^3)O(n3)。#include<bits/stdc++.h>usingnamespacestd;#defineopt(x)memset(x,0x3f,si...

2018-11-27 11:36:00

UOJ#429. 【集训队作业2018】串串划分(循环串)

传送门题解:考虑设dpidp_idpi​表示以iii结尾的前缀的划分方案数,因为有2条件的限制,可以得到容斥式子:dpi=∑j(−1)C(Sj+1,i)dpjdp_i=\sum_{j}(-1)^{C(S_{j+1,i})}dp_jdpi​=j∑​(−1)C(Sj+1,i​)dpj​C(S)C(S)C(S)表示SSS的最小循环节循环的次数,相当于从前面某个位置转移过来,中间全用相同的串划...

2018-11-24 22:41:54

Atcoder AGC019简要题解

传送门ReverseandCompare发现两个串如果翻转后一样且中心不一样,则必定有一个是回文串。然后就只用统计两端字母不同的串的个数了。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=2e5+50;charch[N];intn,cnt[26],s;...

2018-11-22 09:10:59

UOJ#428. 【集训队作业2018】普通的计数题(牛顿迭代)

传送门题解:把0操作看做是叶子,1操作看做非叶节点,一个操作在另一个操作删除,则另一个操作为这个操作的父亲,于是转化成了满足以下条件的nnn个点的树的计数:1.父亲标号>儿子。2.若一个点为非叶节点,记其儿子中叶子节点的数量为TTT,则若其儿子中有非叶节点,T∈AT\inAT∈A,否则T∈BT\inBT∈B。首先可以发现的是BBB集合中有没有0都无所谓(因为必须选非空序列),...

2018-11-21 12:00:42

HDU6172:Array Challenge(Berlekamp-Massey算法)

传送门题解:大胆猜想有递推式,然后BM立水之。#include<bits/stdc++.h>usingnamespacestd;constintRLEN=1<<18|1;inlinecharnc(){ staticcharibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+frea...

2018-11-19 18:45:14

Codechef:Walk on Tree/TREEWALK(Berlekamp-Massey算法)

传送门题解:O(n3log⁡k)O(n^3\logk)O(n3logk)的优化应该都会。然后O(n2)O(n^2)O(n2)用BM求出递推式之后再O(n2log⁡k)O(n^2\logk)O(n2logk)用特征多项式优化一下就行了。#include<bits/stdc++.h>usingnamespacestd;constintRLEN=1<&a

2018-11-19 18:03:40

BZOJ1494: [NOI2007]生成树计数(Berlekamp-Massey算法)

传送门题解:直接打表+BM算出递推式,BM具体实现可以戳这里附上一份其丑无比的BM代码:constintL=4e2;namespacebm{ intcnt,a[N],fail[N],delta[N]; vector<int>R[N]; inlinevoidpt(vector<int>&vec){ for(int

2018-11-17 11:39:03

集训队作业2018:GAME(并查集)

题意:题解:把这个DP式子给列出来:fi=si+max⁡j{2∗aj−sj−fj}f_i=s_i+\max_j\{2*a_j-s_j-f_j\}fi​=si​+jmax​{2∗aj​−sj​−fj​}把这个后缀max⁡\maxmax记为mmm的话,每次就是m=max⁡{m,−2∗si−1−m}m=\max\{m,-2*s_{i-1}-m\}m=max{m,−2∗si−1​−...

2018-11-16 16:12:07

集训队作业2018: 青春猪头少年不会梦到兔女郎学姐(多限制容斥)

前言:虽然这道题的名字有点那啥,但是题还是很好的,听说是某道原题的加强版。题意:给定nnn种颜色的球,第iii种颜色的球数量为AiA_iAi​个,保证∑i=1nAi≤2∗105\sum_{i=1}^nA_i\le2*10^5∑i=1n​Ai​≤2∗105,对于这所有(∑Ai)!∏Ai!\frac{(\sum_{A_i})!}{\prodA_i!}∏Ai​!(∑Ai​​)!​的排列,一...

2018-11-16 14:19:53

Codeforces 809E: Surprise me!(Mobius反演)

传送门题解:对于每个iii,处理出:fi=∑a∑b[(vala,valb)==i]φ(vala)φ(valb)dis(a,b)f_i=\sum_a\sum_b[(val_a,val_b)==i]\varphi(val_a)\varphi(val_b)dis(a,b)fi​=a∑​b∑​[(vala​,valb​)==i]φ(vala​)φ(valb​)dis(a,b)那么ans=∑ifiiφ...

2018-11-13 22:02:47

Codechef:Binary Tree/COOK82E(Trie)

传送门题解:维护每个时刻完整的二叉树信息即可,具体可以用trie树实现,时间复杂度O(n)O(n)O(n)。#include<bits/stdc++.h>usingnamespacestd;constintRLEN=1<<18|1;inlinecharnc(){ staticcharibuf[RLEN],*ib,*ob; (ib==ob...

2018-11-13 19:34:51

Codechef:Painting Tree/KILLER(二进制分组)

传送门题解:这道题,一开始想到自然是线段树合并了,每个点维护个fi,jf_{i,j}fi,j​表示从jjj开始上到iii,其他内部配对的最小值。不过这样就要支持区间加二次函数求最大值,根据bzoj某道题的经验,显然是不能在线段树上搞的。然后仔细观察一下,发现这个(h−depx)(h-dep_x)(h−depx​)连续,进一步发现,这是一个关于depidep_idepi​的二次函数!所以启发式...

2018-11-13 16:38:36

Topcoder SRM 710 900pts:Hyperboxes(FMT)

题解:对于一维是否相交用2(m2)2^{\binom{m}{2}}2(2m​)来表示一下。然后多维直接FMT做并卷积即可,不过对于一维初始化就需要大力删去重复状态来剪枝了。#include<bits/stdc++.h>usingnamespacestd;constintmod=998244353;inlineintadd(intx,inty){retu...

2018-11-13 08:54:47

DZYO

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