4 SFN1036

尚未进行身份认证

本人单身,一般不坑

等级
TA的排名 2k+

【Codeforces 1326F2 Wise Men (Hard Version)】【状压dp+容斥原理】

题意有nnn个点,有些点之间有边。对于111到nnn的每个排列PPP,构造长度为n−1n-1n−1的010101串strstrstr,其中str[i]=1str[i]=1str[i]=1当且仅当pip_ipi​和pi+1p_{i+1}pi+1​之间有边。对每个长度为n−1n-1n−1的串strstrstr,求有多少个排列构造出来的串等于strstrstr。n≤18n\le 18n≤18分析...

2020-03-20 21:43:56

【洛谷P6199 [EER1]河童重工】【点分治+虚树】

题意给出两棵树T1,T2T_1,T_2T1​,T2​,定义新图中两个点的距离为dis1(i,j)+dis2(i,j)dis_1(i,j)+dis_2(i,j)dis1​(i,j)+dis2​(i,j),其中disk(i,j)dis_k(i,j)disk​(i,j)表示在TkT_kTk​中iii到jjj的距离。求新图的最小生成树。n≤100000n\le 100000n≤100000分析先对...

2020-03-09 15:38:53

一句话题解2

洛谷P6158 封锁给出一个n∗nn*nn∗n的网格图,每条边有两个边权。求一个左上角到右下角的割使得(第一个边权之和)∗(第二个边权之和)(第一个边权之和)*(第二个边权之和)(第一个边权之和)∗(第二个边权之和)最小。n≤400n\le 400n≤400跟最小乘积生成树的做法类似,把每种方案看成二维平面上的一个点(∑x,∑y)(\sum x,\sum y)(∑x,∑y),其中x,yx...

2020-03-01 22:45:22

求把线段随机分段后第k短线段的期望长度

题意有一条线段,不妨设线段长度为111。现在在其中随机选n−1n-1n−1个点,使得该线段被分成nnn段。问长度第kkk短的段的期望长度是多少。分析先考虑如何计算最短那段的期望长度,即E(Lmin)E(L_{min})E(Lmin​)。考虑P(Lmin≥x)P(L_{min}\ge x)P(Lmin​≥x),相当于把每一段先剪掉xxx,然后把长度为1−nx1-nx1−nx的线段均分为nnn...

2020-02-23 17:44:46

【hdu 5126 stars(四维偏序)】【cdq套cdq+树状数组】

题意在三维空间内,支持单点加111和矩形求和。q≤5∗104q\le 5*10^4q≤5∗104分析把一个询问拆成八个,就转化为了四维偏序问题。可以用cdq+树套树或者kd树来做,也可以cdq套cdq,复杂度同样是O(nlog⁡3n)O(n\log^3 n)O(nlog3n).cdq套cdq就是先对第一维排序。处理时先递归左右两边,现在要处理左边对右边的询问,可以看成通过递归把第一维变为...

2020-02-17 21:36:23

【洛谷P5825 排列计数】【生成函数+二项式反演/欧拉数】

题意我们记一个排列PPP的升高为kkk当且仅当存在kkk个位置iii使得Pi<Pi+1P_i < P_{i+1}Pi​<Pi+1​。现在给定排列长度nnn,对于所有整数k∈[0,n]k\in [0,n]k∈[0,n],求有多少个排列的升高为kkk。n≤200000n\le 200000n≤200000做法一考虑钦定kkk个位置为<<<,其他位置不管。对...

2020-02-10 17:47:57

【洛谷P6072 [MdOI2020] Path】【回滚莫队+Trie】

题意给一棵nnn个节点的树,边有边权。定义一条路径的权值为边权的异或和。找两条节点不相交的路径,使得这两条路径的权值和最大。n≤30000n\le 30000n≤30000分析问题可以转化成对于每个点,求在该点的子树内和子树外分别找两个数,使得它们的异或的和尽可能大。求出dfs序并倍增,就可以转化成在区间中选两个数,使得这两个数的异或和尽可能大。用回滚莫队+Trie就好了。回滚莫队具...

2020-02-10 11:09:15

CSP-S 2019题解

格雷码从高位往低位做,每次通过kkk的当前位来得到这一位的答案。同时如果这一位的答案是111,则要把从前往后数变为从后往前数。时间复杂度O(n)O(n)O(n).#include<bits/stdc++.h>typedef unsigned long long ull;int n;ull k,bin[105];int main(){ scanf("%d%llu"...

2019-11-29 20:05:00

【Comet OJ - Contest #15 G 孤独的吉姆 6】【图论】

题意给一个nnn个点mmm条边的简单无向连通图,要删掉一些边,使得度数为奇数的点尽可能多。输出长度为mmm的010101串,000表示删掉第iii条边,111表示不删,要求输出字典序最大的方案。n≤6∗105,m≤9∗105n\le6*10^5,m\le9*10^5n≤6∗105,m≤9∗105分析比赛结束后几分钟调过了这题,错失了AK的大好机会。对于两个能够互相到达的点,我们可以通过对...

2019-11-23 23:29:45

【Comet OJ - Contest #15 E 栈的数据结构题】【离线+线段树】

题意有nnn个栈,编号为111到nnn,有以下三种操作:1、对编号在[l,r][l,r][l,r]中的每个栈执行push(v)push(v)push(v)操作。2、对编号为[l,r][l,r][l,r]中的每个栈执行pop()pop()pop()操作。3、查询某个栈中从栈顶开始第kkk个元素。n,q≤2∗105n,q\le2*10^5n,q≤2∗105分析注意到对于某个询问,找到在它...

2019-11-23 23:11:07

【hdu 6634 Salty Fish】【最小割+长链剖分】

题意给一棵nnn个节点的有根树,点有点权。有mmm个摄像机,第iii个摄像机会覆盖到以xix_ixi​为根的子树中距离xix_ixi​不超过kik_iki​的点,并且可以用cic_ici​的代价使该摄像机无效。问未被覆盖点权和-总花费的最大值。n,m≤300000n,m\le300000n,m≤300000分析首先可以最小割建图:sss往摄像头连流量为费用的边,摄像头往能覆盖的点连流量为i...

2019-11-16 11:20:03

【luogu P5655 基础数论函数练习题】【分治+数论】

题意给出nnn个数,有qqq次询问,每次询问一个区间内的lcm对1e9+71e9+71e9+7取模后的值。n,q,T≤300,1≤ai≤260n,q,T\le 300,1\le a_i\le 2^{60}n,q,T≤300,1≤ai​≤260分析在求一个区间的lcm的时候,可以把lcm表示成∏bi\prod b_i∏bi​的形式,其中bi∣aib_i|a_ibi​∣ai​。在新加入一个ai...

2019-11-16 00:11:29

【Codeforces 1257G Divisor Set】【Dilworth定理+分治FFT】

题意设x=p1p2⋯pnx=p_1p_2\cdots p_nx=p1​p2​⋯pn​,其中pip_ipi​为质数,要求在xxx的所有约数中选出尽可能多的数组成一个集合,使得集合内的数互不整除,NTT模数。n≤2∗105,pi≤3∗106n\le2*10^5,p_i\le3*10^6n≤2∗105,pi​≤3∗106分析比赛结束前几分钟才想到所以时间不够,果然退役之后手速下降的厉害啊。把每...

2019-11-14 01:08:10

【Comet OJ - Contest #14 E 飞翔的小鸟】【图论】

题意给一个nnn个点mmm条边的有向图,对每个点xxx求从111到xxx的所有路径中边权极差最大是多少。n≤200000,m≤500000n\le200000,m\le500000n≤200000,m≤500000分析先缩点,这样新图里的点也有了点权。假设先经过最小值再经过最大值,那么枚举经过最大值之前经过的最后一条边,预处理fxf_xfx​表示走到xxx经过的最大权值,就可以知道每一条...

2019-11-12 17:13:11

【2019 CCPC 哈尔滨站 G. Game Store】【Nim-K+线性基+bitset优化三进制加法】

题意题目链接有一个商店,商店里每天会增加一个石子集合,集合里有两堆石子数相同的石子,且每个集合有一个价格。Alice每天会在商店里选价格和尽量大的一些集合,满足把这些集合里的石子堆放在一起,然后Bob任意拿掉一些石子堆,无论Bob怎么拿,玩Nim-K游戏先手总有必胜策略。n≤500000,ai≤1018n\le500000,a_i\le 10^{18}n≤500000,ai​≤1018,强制...

2019-11-12 15:57:47

【2019 CCPC 哈尔滨站 H. Highway Buses】【点分树+最短路】

题意题目链接有一个nnn个点mmm条边的无向连通图,从每个点出发有一个花费cic_ici​和限制距离fif_ifi​,表示可以通过cic_ici​的花费到达与它最短距离不超过fif_ifi​的点。有TTT个时刻,每过一个时刻点iii的花费要加上wiw_iwi​。对k=1,...,nk=1,...,nk=1,...,n,求选择某一个时刻并从111出发,走到点kkk的最小花费。n≤200000,...

2019-11-10 23:38:31

【Codeforces gym102268A Angle Beats】【带花树算法】

题意给一个n∗mn*mn∗m的网格,其中有“*”和“.”和“+”,每次可以选择覆盖一个"+“或“*”和与它相邻的两个”.",如果选的是“*”则两个“.”必须相对。每个点只能被覆盖一次,问最多能覆盖多少次。n,m≤100n,m\le 100n,m≤100分析把每个“+”和“*”拆成两个点并连边,“+”的每个点对四周的“.”连边,“*”则一个点向上下方向连边,另一个点向左右方向连边,可以发现最...

2019-11-05 22:39:28

【Codeforces gym102268E Expected Value】【生成函数+Berlekamp-Massey算法】

题意给一个nnn个点的平面图,问从111随机游走到nnn的期望步数。n≤3000n\le 3000n≤3000分析注意到是平面图,所以边数不超过3n−63n-63n−6。设pip_ipi​表示走了iii步到nnn的概率,则pip_ipi​是一个nnn阶线性递推。先递推出pip_ipi​的前2n2n2n项,然后用BM算法求出其递推式,设pip_ipi​的生成函数为P(x)P(x)P(x)...

2019-11-05 17:45:09

【Comet OJ - Contest #11 F arewell】【FMT】

题意给一个nnn个点mmm条边的无向图,每条边(u,v)(u,v)(u,v)有从uuu指向vvv,从vvv指向uuu和消失三种情况,概率均为13\frac{1}{3}31​。问该图为DAG的概率是多少。n≤20n\le20n≤20分析设FSF_SFS​表示集合SSS中的点构成DAG的方案,ESE_SES​表示集合SSS中的边数,ES,TE_{S,T}ES,T​表示集合SSS和TTT之间的边...

2019-09-22 13:08:51

【bzoj 3501: PA2008 Cliquers Strike Back】【贝尔数】

题意给出n,mn,mn,m,求mBn mod Pm^{B_n}\bmod PmBn​modP,其中P=999999599P=999999599P=999999599是个质数。同时P=2×13×5281×7283+1P=2×13×5281×7283+1P=2×13×5281×7283+1n,m≤1018n,m\le10^{...

2019-09-15 09:54:11

查看更多

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