- 博客(496)
- 收藏
- 关注
RSS订阅
原创 Atcoder：AGC004F Namori
传送门先考虑树，树是一个二分图。看到是二分图并且每次是对两边的同色的点反色可以想到转化：让奇数层的点为黑，偶数为白，变成每次可以交换两个点的颜色。把黑看成 −1-1−1，白看成 111，那么求一个子树和，考虑每一条边的贡献可以得到 ans=∑i=1n∣sumi∣ans=\sum_{i=1}^{n} |sum_i|ans=∑i=1n∣sumi∣如果根的 sumsumsum 不为 000，...
2019-03-02 16:43:24
476
原创 LOJ2522：[FJOI2018]邮递员问题(乱搞)
传送门乱搞。可以发现如果起点在左边界，终点在右边界的时候上下走的点一定是连续的(可能吧)那么可以设 fi,j,0/1f_{i,j,0/1}fi,j,0/1 表示当前上面到 iii，下面到 jjj，当前在上面/下面的最短距离。如果起点不在左边界，终点不在右边界，那么就乱搞。对于左边，如果向左的时候下去了再上来一定不会优与直接走过去，那么就分两种情况：左下右 或者 直接先左再次原路返回向右...
2019-02-28 11:50:20
371
原创 BZOJ5305: [HAOI2018]苹果树
传送门果然只有我这种菜鸡才会用这种菜鸡做法QwQ对于一类要求期望的题目，有一个无脑的做法：设概率为 fff，期望为 ggg每次合并两个二元组 <f1,g1>,<f2,g2><f_1,g_1>,<f_2,g_2&am
2019-02-22 22:27:44
208
原创 BZOJ5473: 仙人掌
传送门首先，所有连通块的个数的期望再减去每个点孤立的概率就是答案。设 did_idi 表示 iii 的度数，那么每个点孤立的概率为 12di\frac{1}{2^{d_i}}2di1考虑计算所有连通块的个数的期望对于一棵树来说，每次删除一条边会使得连通块的个数 +1+1+1，概率为 12\frac{1}{2}21，那么 n−1n-1n−1 条边的期望就是 1+n−121+\frac...
2019-02-22 14:38:52
219
原创 BZOJ5289: [Hnoi2018]排列
传送门第一步转化，令 q[p[i]]=iq[p[i]]=iq[p[i]]=i，那么题目变成：有一些 q[a[i]]&lt;q[i]q[a[i]]&lt;q[i]q[a[i]]<q[i] 的限制，qqq 必须为排列，求 max(∑i=1nw[i]q[i])max(\sum_{i=1}^{n}w[i]q[i])max(∑i=1nw[i]q[i])这个东西是可以建图的，i→...
2019-02-20 17:53:22
206
原创 BZOJ5322: [JXOI2018]排序问题
传送门不难看出期望就是 (n+m)!∏v=1max(cntv!)\frac{(n+m)!}{\prod_{v=1}^{max}(cnt_v!)}∏v=1max(cntv!)(n+m)!，cntvcnt_vcntv 表示 vvv 这个数出现的次数。贪心就是直接把 mmm 个数字每次选择一个 cntcntcnt 最小的加入，使得最后 [l,r][l,r][l,r] 内每个数字出现的的次数尽...
2019-02-20 10:36:02
199
原创 BZOJ5323：[JXOI2018]游戏
传送门不难发现，所有不能被其他数筛掉的数是一定要选的，只有选了这些数字才能结束假设有 mmm 个，枚举结束时间 xxx，答案就是 ∑(x−1m−1)m!(n−m)!x\sum \binom{x-1}{m-1}m!(n-m)!x∑(m−1x−1)m!(n−m)!x埃氏筛法即可求出 mmm# include <bits/stdc++.h>using namespace std;...
2019-02-20 09:40:53
233
原创 UOJ#328. 【UTR #3】量子破碎
传送门学过 FWTFWTFWT 看到操作 222 不难可以联想到 FWTFWTFWT考虑一遍 ⊕\oplus⊕ FWTFWTFWT 会把 ata_tat 变成什么at′=((−1)bitcount(x&amp;amp;t)+(−1)bitcount(y&amp;amp;t))axa_t&amp;#x27;=((-1)^{bitcount(x\&amp;amp;t)}+(-1)^{bitco...
2019-02-15 17:09:16
232
原创 Codeforces 750 F：New Year and Finding Roots
传送门首先如果一开始就找到了一个叶子，那么暴力去递归找它的父亲，每次随机一个方向(除了已知的儿子)走深度次，如果走到了一个叶子就不是这个方向(设根的深度为 111)这样子最后到达深度为 333 的点需要花费 111111 次注意到此时只有与该点距离不超过 222 的点可能是根，这样的没有询问过的点不超过 666 个所以只要询问 555 次，一共 161616 次如果一开始不是叶子，那么尝...
2019-02-15 14:33:35
181
原创 BZOJ3451：Tyvj1953 Normal
根据期望的线性性，答案就是 ∑\sum∑ 每个连通块出现次数的期望而每个连通块次数的期望就是 ∑\sum∑ 连通块的根与每个点连通次数的期望也就是对于一条路径 (i,j)(i,j)(i,j)，设 iii 为根，那么 iii 必须是这条路径第一个被选择的点，概率为 1dis(i,j)\frac{1}{dis(i,j)}dis(i,j)1，其中 dis(i,j)dis(i,j)dis(i,j) ...
2019-02-15 11:18:02
148
原创 Codeforces Global Round1 简要题解
Codeforces Global Round 1A模拟即可# include <bits/stdc++.h>using namespace std;typedef long long ll;int b, k, n, a[232333];int main() { int i, base = 1, v; scanf("%d%d", &b, &k);...
2019-02-13 16:24:41
164
原创 AGC008E：Next or Nextnext
传送门考虑转化成图论问题，iii 向 pip_ipi 连边，那么合法方案一定是形成了若干个简单环或自环考虑一个环内的情况：如果 ai=pia_i=p_iai=pi，那么 iii 向 aia_iai 连边的图和原图相比不变如果 ai=ppia_i=p_{p_i}ai=ppi，a. 环长为奇数且 &gt;1&gt;1>1，那么 iii 向 aia_iai...
2019-02-09 19:31:51
269
原创 AGC009：Eternal Average
传送门好神啊直接考虑一棵 n+mn+mn+m 个叶子的 kkk 叉树，根结点权值为 ∑i∈m(1k)deepi\sum_{i\in m}(\frac{1}{k})^{deep_i}∑i∈m(k1)deepi对于一个 deepdeepdeep 的序列如果 ∑i∈m(1k)deepi+∑i∈n(1k)deepi=1\sum_{i\in m}(\frac{1}{k})^{deep_i}+\...
2019-02-09 16:40:01
180
原创 Codeforces 981H：K Paths
传送门考虑枚举一条路径 u,vu,vu,v，求出所有边经过它的答案只需要求出 uuu 的子树内选出 kkk 个可以重复的点，使得它们到 uuu 的路径不相交不难发现，就是从 uuu 的儿子的子树内各自选一个以及可以选多次 uuu 自己设这个方案数为 fuf_ufu再设 sizeusize_usizeu 表示 uuu 的子树大小，sonuson_usonu 表示 uuu 的儿子集合...
2019-02-09 14:47:41
259
原创 AGC006C Rabbit Exercise
传送门设 fi,jf_{i,j}fi,j 表示兔子 iii 在当前 jjj 轮的期望位置对于一次操作 fi,j+1=12(2fi−1,j−fi,j)+12(2fi+1,j−fi,j)=fi−1,j+fi+1,j−fi,jf_{i,j+1}=\frac{1}{2}(2f_{i-1,j}-f_{i,j})+\frac{1}{2}(2f_{i+1,j}-f_{i,j})=f_{i-1,j}+f_{...
2019-02-08 11:00:46
166
原创 LOJ #2985. 「WC2019」I 君的商店
传送门搬题解QwQ首先最大值一定为 111，直接扫一遍两两比较 O(2N)O(2N)O(2N) 求出最大值设最大值位置为 aaa，对于任意两个没有确定的位置 x,yx,yx,y询问 [a,x+y][a,x+y][a,x+y]，如果 a≤x+ya\le x+ya≤x+y 那么 x,yx,yx,y 的最大值为 111，否则 x,yx,yx,y 最小值为 000再询问 [x,y][x,y][x...
2019-02-02 09:34:55
727
原创 LOJ#2983. 「WC2019」数树
传送门抄题解Task0Task0Task0，随便做一下，设 cntcntcnt 为相同的边的个数，输出 yn−cnty^{n-cnt}yn−cntTask1Task1Task1，给定其中一棵树设初始答案为 yny^nyn，首先可以发现，每有一条边和给定的树相同就会使得答案除去 yyy那么可以利用矩阵树定理，已经有的边权值为 y−1y^{-1}y−1，其它的连成完全图，权值为 111求解...
2019-02-01 22:42:23
207
原创 UOJ#410. 【IOI2018】会议
传送门首先可以设 f[l][r]f[l][r]f[l][r] 表示 [l,r][l,r][l,r] 的答案设 xxx 为区间 [l,r][l,r][l,r] 的最大值的位置，那么f[l][r]=min(f[l][x−1]+h[x]×(r−x+1),f[x+1][r]+h[x]×(x−l+1))f[l][r] = min(f[l][x-1]+h[x]\times (r-x+1),f[x+1][...
2019-02-01 10:49:58
312
原创 UOJ#272. 【清华集训2016】石家庄的工人阶级队伍比较坚强
传送门设运算 op1,op2op1,op2op1,op2，一个表示三进制不进位的加法，一个表示不退位的减法设 cnt1[x],cnt2[x]cnt1[x],cnt2[x]cnt1[x],cnt2[x] 分别表示 xxx 转成三进制后 1/21/21/2 的个数那么fi,x=∑fi−1,ybcnt1[x op2 y],cnt2[x op2 y]f_{i...
2019-01-27 17:16:27
258
原创 LOJ#6271. 「长乐集训 2017 Day10」生成树求和 加强版
传送门由于是边权三进制不进位的相加，那么可以考虑每一位的贡献对于每一位，生成树的边权相当于是做模 333 意义下的加法考虑最后每一种边权的生成树个数，这个可以直接用生成函数，在矩阵树求解的时候做一遍这个生成函数的模 333 意义下的循环卷积求出系数即可暴力多项式运算不可取考虑选取 333 个数字 xix_ixi，使得 xi3≡1(mod 109+7)x_i^3\equiv1(...
2019-01-25 23:15:06
347
原创 LOJ#6035. 「雅礼集训 2017 Day4」洗衣服
传送门先处理出每一件衣服最早什么时候洗完，堆+贪心即可然后同样处理出每件衣服最早什么时候烘干然后倒序相加取最大值# include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn(1e5 + 5);int l, n, m, d[maxn], w[maxn];ll ans,...
2019-01-25 16:34:08
268
原创 LOJ#6032. 「雅礼集训 2017 Day2」水箱
传送门首先可以有一个平方复杂度的 DPDPDP设 fi,jf_{i,j}fi,j 表示前面 iii 个小格，高度为 jjj 的最大答案令 hih_ihi 表示隔板 iii 的高度当 j≤hij\le h_ij≤hi 时，转移到 fi+1,k,k∈[0,hi]f_{i+1,k},k\in [0,h_i]fi+1,k,k∈[0,hi]否则 fi,j→fi+1,jf{i,j}\rig...
2019-01-24 21:58:43
300
原创 BZOJ5317：[JSOI2018]战争(闵可夫斯基和)
令 a∈A,b∈Ba\in A,b\in Ba∈A,b∈B 则移动向量 ω\omegaω 使得存在 b+ω=ab+\omega=ab+ω=a那么 ω\omegaω 需要满足 ω=a−b\omega=a−bω=a−b黑科技：闵可夫斯基和直接构造闵可夫斯基和 C=a+(−b)C={a+(−b)}C=a+(−b)余下问题便是判断输入的移动向量是否在 CCC 内可以强行使凸包的最下面为 (0,0...
2019-01-19 13:41:03
449
原创 BZOJ4977: [[Lydsy1708月赛]跳伞求生
传送门直接贪心考虑到 nnn 个人的贡献都是 aia_iai，另外 mmm 个人的贡献都是 ci−bic_i-b_ici−bi首先 ai&gt;bja_i&gt;b_jai>bj 的限制不好做，所以将 a,ba,ba,b 从小到大排序枚举 aia_iai ，每次把小于 aia_iai 的 bbb 加入优先队列，只要从中间选一个最大的匹配，之后将 −ai-...
2019-01-18 12:36:32
252
原创 BZOJ4675: 点对游戏
传送门考虑每一对幸运点对的贡献，假设有 vvv 对一共可以选择 xxx 个点，总共 nnn 个点那么答案就是v×An−2x−2x(x−1)Anx=v×x(x−1)n(n−1)v\times\frac{A_{n-2}^{x-2}x(x-1)}{A_{n}^{x}}=\frac{v\times x(x-1)}{n(n-1)}v×AnxAn−2x−2x(x−1)=n(n−1)v×x(x−1...
2019-01-17 09:36:09
224
原创 Codeforces 1097 Alex and a TV Show
传送门除了操作 333 都可以 bitsetbitsetbitset现在要维护Ci=∑gcd(j,k)=iAjBkC_i=\sum_{gcd(j,k)=i}A_jB_kCi=gcd(j,k)=i∑AjBk类比 FWTFWTFWT，只要求出 Ai′=∑i∣dAdA&#x27;_i=\sum_{i|d}A_dAi′=∑i∣dAd就可以直接按位相乘了求答案就是莫比乌斯反...
2019-01-17 08:51:06
307
原创 UOJ#349. 【WC2018】即时战略
传送门按照紫荆花之恋的做法，动态维护一下点分树的形态把点随机打乱每次从当前的根开始 exploreexploreexplore，如果已经有了就暴力跳到那个点否则加入这个点注意一条链的要单独处理# include <bits/stdc++.h># include "rts.h"using namespace std;typedef long long ll;cons...
2019-01-16 21:50:43
324
原创 UOJ#55. 【WC2014】紫荆花之恋
传送门暴力思路就是每次点分治计算答案点分治之后，条件可以变成 disi−ri≤rj−disjdis_i-r_i\le r_j-dis_jdisi−ri≤rj−disj每次只要查找 rj−disjr_j-dis_jrj−disj 的排名然后插入 disj−rjdis_j-r_jdisj−rj，随便拿个平衡树维护即可考虑如果带修改，就是动态点分治，每个点维护两个平衡树，一个表示...
2019-01-16 17:43:06
400
原创 CodeChef SADPAIRS：Chef and Sad Pairs
vjudge首先显然要建立圆方树对于每一种点建立虚树，考虑这一种点贡献，对于虚树上已经有的点就直接算否则对虚树上的一条边 (u,v)(u, v)(u,v),uuu 为父亲，假设上面连通块大小为 xxx，下面为 yyy切断 (u,v)(u, v)(u,v) 之间的点(不包括 uuu)都会有 x×yx\times yx×y 的贡献，差分一下贡献即可# include <bits/std...
2019-01-16 14:51:38
497
原创 BZOJ4771: 七彩树
传送门考虑维护每个颜色的虚树按照 dfndfndfn 顺序维护这些点，在这些点上 +1+1+1，相邻点的 lcalcalca 处 −1-1−1，这样，无论包含哪一个子树的几个点，子树权值和始终为 111可以用 set+LCAset+LCAset+LCA 实现现在变成了二维数点的问题，按照深度依次加入每个点用主席树维护，每个线段树维护 dfsdfsdfs 序即可# include <...
2019-01-16 10:30:52
205
原创 BZOJ1443: [JSOI2009]游戏Game
传送门这个博弈类似放骨牌，参见这道题所以就可以黑白染色之后跑二分图最大匹配，其中的不必匹配的点就是答案这些点是什么呢，yyyyyy 一下发现貌似就是残余网络中与 sss 或 ttt 在同一个强连通分量的点?# include &lt;bits/stdc++.h&gt;using namespace std;typedef long long ll;const int maxn(10...
2019-01-15 11:36:08
192
原创 UOJ#172. 【WC2016】论战捆竹竿
传送门首先这个题目显然就是先求出所有的 borderborderborder，问题转化成一个可行性背包的问题一个方法就是同余类最短路，裸跑 303030 分，加优化 505050 分首先有个性质borderborderborder 分成的等差数列的个数不超过 logloglog和回文树的性质的证明类似瞎画图一下就行了我们注意到可以一个一个等差数列的更新最短路要做到这个，必须能从之前的...
2019-01-15 09:22:52
366
原创 BZOJ3682: Phorni(后缀平衡树)
传送门后缀平衡树模板题用平衡树维护每一个后缀的排名关键在于查询两个后缀的大小可以用二分加hash，复杂度 log2nlog^2nlog2n 插入或者：每次前面插入一个字符，先比较两个后缀第一个字符的大小而后面的大小我们已经在平衡树上维护好了像这样分配权值给树上每个子树一个实数权值区间 [l,r][l,r][l,r]，这个点权值为 mid=l+r2mid=\frac{l+r}{2...
2019-01-12 16:48:11
190
原创 BZOJ3600：没有人的算术
传送门如果能给每个 pairpairpair 按照权值编号就好了假设之前已经有了所有的权值的编号，现在考虑编号新的 pairpairpair如果看过了陈立杰的论文的话，不难得到一个重量平衡树的做法给树上每个子树一个实数权值区间 [l,r][l,r][l,r]，这个点权值为 mid=l+r2mid=\frac{l+r}{2}mid=2l+r左子树 [l,mid][l,mid][l,mid...
2019-01-12 15:46:10
236
原创 UOJ#191. 【集训队互测2016】Unknown
传送门这个题目实际上可以建立出树，然后重链剖分维护一条链的凸包然后离线询问排序斜率做到 nlog2nnlog^2nnlog2n，或者点分治+平衡树也行但是这个题目卡空间，数组一不小心就爆了卡一卡也能过考虑其它空间常数小并且又好写的做法根据一般的二进制分组的方法，每次这个块满了就合并儿子的凸包这样显然不对，只要又删又加就假了我们换一种方法，每次这个块满了就合并线段树同一层前一个节点的儿...
2019-01-11 12:53:44
422
原创 UOJ#414. 【APIO2018】新家
传送门首先二分答案 midmidmid，问题变成求区间 [l−mid,r+mid][l-mid,r+mid][l−mid,r+mid] 在该年份的不同类型个数为 kkk关于年份的限制可以离线下来现在的问题就是区间数颜色，一个套路就是维护每个颜色的后继，即这个位置颜色的下一个位置那么，如果有 (−∞,l−mid](-\infty,l-mid](−∞,l−mid] 的某一个值大于 r+midr...
2019-01-11 09:02:59
236
原创 UOJ169. 【UR #11】元旦老人与数列
传送门考虑用 segment tree beatssegment~tree~beatssegment tree beats 那一套理论，维护区间最小值 mnmnmn 和严格次小值 sesese那么可以直接 mlog2nmlog^2nmlog2n 维护前三个操作考虑维护历史最小值，先维护历史最小标记写了写发现 maxmaxmax 那个修改不好操作对于...
2019-01-10 18:52:10
233
原创 UOJ#400. 【CTSC2018】暴力写挂
传送门看到要求两棵树的 lcalcalca 深度不太好操作考虑枚举第二棵树的 lcalcalca，这样剩下的都是只和第一棵树有关的而注意到 dis(x,y)=d(x)+d(y)−2d(lca(x,y))dis(x,y)=d(x)+d(y)-2d(lca(x,y))dis(x,y)=d(x)+d(y)−2d(lca(x,y))那么 d(x)+d(y)−d(lca(x,y))=12(dis(x...
2019-01-06 17:56:55
321
原创 BZOJ3925: [Zjoi2015]地震后的幻想乡
传送门根据期望的线性性，算出第 iii 小的边作为最小生成树的最大边的概率，设为 PiP_iPi那么根据题目的信息，答案就是 ∑im+1Pi\sum \frac{i}{m+1}P_i∑m+1iPi考虑计算 PiP_iPi，相当于在加入 iii 这条边的时候，前 i−1i-1i−1 条不连通，而 iii 条恰好连通设 gi,sg_{i,s}gi,s 表示点集 sss 中选择 iii...
2019-01-05 19:51:33
147
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人