4 SFN1036

尚未进行身份认证

本人单身,一般不坑

等级
TA的排名 2k+

【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

贝尔数学习小记

贝尔数贝尔数是一个数列,其第nnn项BnB_nBn​定义为nnn个带标号元素的集合划分方案数,不难发现Bn=∑k=1nS(n,k)B_n=\sum_{k=1}^nS(n,k)Bn​=k=1∑n​S(n,k)其中S(n,k)S(n,k)S(n,k)表示第二类斯特林数。同时容易得到递推式Bn+1=∑k=0n(ni)BiB_{n+1}=\sum_{k=0}^n\binom{n}{i}B_iBn+1...

2019-09-14 19:55:39

【bzoj 3730: 震波】【动态树分治】

题意给出一棵树,点有点权,每次询问距离一个点不超过kkk的点的点权和,或者修改一个点的点权,强制在线。n≤100000n\le100000n≤100000分析把点分树建出来,然后对每个分治中心用树状数组维护到该点距离为定值的点权和,以及到他点分树上父亲距离为定值的点权和。查询的时候每次沿着父亲往上跳,在计算当前点贡献时需要减去上一个点所在子树的贡献。时间复杂度O(nlog⁡2n)O(n\...

2019-09-08 21:31:36

【2019 ACM/ICPC徐州站 H function】【min25筛】

题意题目链接设n=p1a1…pkakn=p_1^{a_1}\dots p_k^{a_k}n=p1a1​​…pkak​​,则定义f(n)=a1+⋯+akf(n)=a_1+\dots+a_kf(n)=a1​+⋯+ak​。给出nnn,求∑i=1nf(i!)\sum_{i=1}^nf(i!)i=1∑n​f(i!)n≤1010n\le10^{10}n≤1010分析显然要求的是∑p∈P∑k≥1∑i=...

2019-09-08 10:08:03

【hdu 2516 取石子游戏】【斐波那契博弈】

题意111堆石子有nnn个,两人轮流取,先取者第111次可以取任意多个,但不能全部取完。以后每次取的石子数不能超过上次取子数的222倍。取完者胜。问先手是否必胜。n<231n<2^{31}n<231分析结论:先手必败当且仅当nnn是斐波那契数。证明:当n=2n=2n=2时显然成立。若对于[1,n−1][1,n-1][1,n−1]上述结论均成立当n&...

2019-09-07 20:49:30

查看更多

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