a18700013354-CSDN博客

转载 Codeforces805

A.Fake NP题意：给定两个整数L R，求[L,R]中公因子不为1的数的最大个数。题解：显然要想数量尽量多，公因子就不会很大，所以枚举公因子（素数）即可，注意特判L==R的情况代码：#include <cstdio>#include <cstring>#include <cstdlib>#include <...

2019-03-15 20:04:00 189

转载 Codeforces357

A.Group of Students代码：#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int...

2019-03-12 20:36:00 134

转载 Codeforces1079

A.Kitchen Utensils代码：#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int ...

2019-03-06 16:51:00 144

转载 Codeforces1099

A.Snowball代码：#include <cstdio>#include <climits>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace ...

2019-03-05 17:08:00 155

转载 Codeforces1047

A.Little C Loves 3 I题意：给定一个整数N，问是否存在整数a b c使得a+b+c=N且a b c均不为3的倍数题解：考虑到mod3的余数只有0 1 2，所以直接取1,1,N-2 或 1,2,N-3 或 2,2,N-4代码：#include <cstdio>#include <cstring>#include &l...

2019-02-27 16:30:00 189

转载 Codeforces1130

A.Be Positive题意：给定一个数列，求数列中一半及以上的数是正数、负数还是零。代码：#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using ...

2019-02-26 16:21:00 95

转载 BZOJ3203 SDOI2013 保护出题人凸包+三分法

题意：给定N组询问和D，初始时集合为空，每组询问先向集合的开头插入一个元素xi，然后给出一个数pi，求最小的yi使得\[{y}_{i}\left({p}_{i}+D\left(i-1 \right) \right)\geq {x}_{i}\]题解：设Si=$\sum\limits_{j = 1}^i{x}_{j}$，显然yi=$max\left \{ \frac{{S}_{i}-{S...

2017-04-02 17:21:00 81

转载 BZOJ4048 SDOI015 双旋转字符串 Hash

题意：给定两个字符串集合S T，每个集合内的所有字符串长度均相同，求有多少对字符串<Si,Tj>使得两个字符串拼接后，左右两半满足双旋转性质（一个字符串按照任意一个位置旋转后与另一个字符串重合）题解：把较小的集合Hash后，暴力枚举另一个集合内的字符串。#include <cstdio>#include <cstdlib>#in...

2017-03-25 11:32:00 89

转载 BZOJ3231 SDOI2008 递归数列矩阵乘法

题意：设an=c1an-1+c2an-2+……+ckan-k,sn=a1+a2+……+an。给定a1到ak与c，求sn-sm-1题解：以k=3为例\[\left( {\begin{array}{*{20}{c}}{{a_{n - 2}}}&{{a_{n - 1}}}&{{a_n}}&{{s_n}}\end{array}} \right) = \left( {\...

2017-03-25 10:42:00 78

转载 BZOJ3226 SDOI2008 校门外的区间线段树

题意：给定一个空的数集，要求维护：1、区间求并 2、区间求交 3、区间求差 4、区间异或。每次操作后原区间变为操作后的区间，每个操作的区间可开可闭，求所有操作后的区间题解：把每个点拆成开和闭两个，线段树维护就好。最后统计答案的时候暴力枚举每个位置即可#include <cstdio>#include <cstring>#include &l...

2017-03-18 22:40:00 80

转载 BZOJ3198 SDOI2013 spring HASH+容斥原理

题意：给定6个长度为n的数列，求有多少个数对(i,j)（(i,j)≡(j,i)）使得i和j位置恰好有K个数相同，其中0≤K≤6题解：设fi=至少有K个数相同的位置对的数量，用2^6枚举每一种可能，根据容斥原理，答案就是\[\sum\limits_{i = K}^N {{f_i}C_i^K{{\left( { - 1} \right)}^{i - K}}} \]至于多乘一个组合...

2017-03-17 22:26:00 68

转载 BZOJ3990 SDOI2015 排序 DFS

题意：给定一个长度为2^N的序列和N个操作，每个操作i为将2^N分为2^(N-i+1)段，然后任意交换其中两段，求有多少种不同的交换方案使得序列升序题解：由于一个合法的方案中，交换操作的先后顺序，方案依然合法，所以我们只需要确定使用哪些操作。按i的大小从小到大枚举每一个操作i，然后将序列分为2^(N-i)段，看有多少段不是递增的。如果有两段以上显然无解，如果有一段那么直接折半...

2017-03-11 22:47:00 85

转载 BZOJ3124 SDOI2013 直径 DFS

题意：给定一棵树，求这棵树直径的长度和所有直径有多少个公共点。题解：求直径感觉DFS比BFS好写太多，但是大数据本地爆栈OJ却不爆……思路和BFS版的差不多，第一问是个裸题。因为书中任意两点间有且仅有一条路径，所以所有直径的公共点一定是连续的一段。我们从左向右枚举直径上所有点，如果一个点到直径外一点的距离等于到直径左端的距离，那么这个点就是连续的公共点的最左边的一个，同理可找到最右边...

2017-03-11 18:41:00 80

转载 BZOJ2282 SDOI2011 消防 BFS+单调队列

题意：给定一棵树，求树上一条长度不大于S的路径，使得树上所有点到该路径的最大距离最小。题解：首先，所求路径一定在树的直径上，否则我们总可以用树的直径来扩展出更大的最大距离。设fi为i为路径左端点时，直径的右端点到i的距离；gi为i为路径右端点时，直径的左端点到i的距离；hi为i的与直径没有交集的子树中，到i的最远距离。对于一个确定的路径ab，显然我们有\[Dist = \ma...

2017-03-11 17:22:00 98

转载 BZOJ2241 SDOI2011 打地鼠枚举

题意：给定一个N*M数字矩阵，求一个全1矩阵，使得该矩阵在经过复制后，在满足每次放置的位置不存在0的情况下，放置的矩阵数最少，求最少次数。题解：由于数据很小所以可以暴力枚举所求矩阵的长和宽然后检验。由于所求矩阵的大小一定是所有数和的因数，然后矩阵越大放的次数就越少，所以倒序枚举。#include <cstdio>#include <climits&g...

2017-03-11 16:18:00 111

转载 BZOJ1927 SDOI2010 星际竞速费用流

题意：给定一张有向图，边均由编号较大的点连向编号较小的点，每个点都有一个权值a，表示可以从任意一个点转移到i点，花费a[i]的费用。求遍历每个点一次且仅一次的最小费用，起点终点任意，保证有解。题解：拆点，费用流决定经过的点的顺序，由于瞬移到i的费用与之前经过的点无关，所以可以直接从S向每个点i连流量为1费用为a[i]的边。#include <cstdio>...

2017-03-10 21:54:00 77

转载 BZOJ1925 SDOI2010 地精部落一般DP

题意：求1-N组成的长度为N的数列中，除了两端外，中间任意一个位置i均满足（ai-1＜ai &&ai+1＜ai）或（ai-1>ai && ai+1>ai）题解：考场上遇到这种题果断暴力设f[i][j]为1-i组成的数列，1-j其中一个为开头，且开头为山峰的方案数，转移分为两部分：f[i][j-1]：不选j为开头f[i-1][i-j+1]...

2017-03-04 22:58:00 85

转载 BZOJ1880 SDOI2009 Elaxia的路线最短路+拓扑排序

题意：给定两个点对和一张无向图，求两个点对的最短路中，重边边权和的最大值题解：首先从给出的四个点出发跑出到其他所有点的最短路，然后判断哪些边是重边。找出所有重边后，将其构有向图，在该图上用拓扑排序求最长路。开始的时候枚举每一条边我没有建反向边，而是每次判定的时候互换一下边的始末点看是否合法，结果最后一个点死活过不去。后来上网搜题解才知道，必须建反向边，与原边分别判断。果然偷懒...

2017-03-04 20:08:00 89

转载 BZOJ1878 SDOI2009 HH的项链树状数组

题意：给定一个颜色序列，每组询问给出区间[l,r]，求[l,r]中不同颜色的数量题解：首先把所有颜色离散化，然后离线，将询问按右区间升序排列。从1-N把整个序列扫一遍，设Pos[i]为第i个颜色最后出现的位置，假定当前扫到的位置为i，则更新Pos[a[i]]，那么问题变成了：求一个序列（Pos）中，大于等于一个数（L）的数的数量。用树状数组维护Pos=j的数的数量，每次查询树...

2017-03-04 17:53:00 86

转载 BZOJ1876 SDOI2009 SuperGCD 其他

题意：求两个大正整数的GCD题解：出题人的愿意肯定是觉得SDOI不出大模拟说不过去，嘛，考场上这么出肯定没问题不过BZOJ允许使用Python就是个错误……a=(int)(input())b=(int)(input())while b!=0: t=a a=b b=t%bprint(a)View Code说句题外...

2017-03-04 14:21:00 76

转载 BZOJ1875 SDOI2009 HH去散步矩阵乘法

题意：给定一张无向图，求A到B的路径中，经过的边数为T且不存在连续的两步经过同一条边的路径条数。题解：没有第二个条件的话矩阵快速幂可做。有第二个条件我们可以边化点，然后虚拟两个节点S和T作为起点和终点，其中S与含A的边相连，T和含B的边相连，由于走到B需要额外的一步，因此求邻接矩阵的T+1次幂#include <cstdio>#include <cs...

2017-03-04 14:09:00 100

转载 BZOJ1227 SDOI2009 虔诚的墓主人树状数组+组合数学

题意：给定一个N*M的01矩阵，设li,j,ri,j,ui,j,di,j分别为(i,j)正上，正下，正左，正右1的数量，求$\sum\limits_{(i,j) \equiv 0} {C_{{l_{i,j}}}^KC_{{r_{i,j}}}^KC_{{u_{i,j}}}^KC_{{d_{i,j}}}^K} $，其中1的数量≤100000题解：首先离散化，设N M为离散化后的行列数。先...

2017-03-04 12:22:00 78

转载 BZOJ3993 SDOI2015 星际战争二分法+网络流

题意：有N个机器人护甲分别为ai，M个武器攻击力分别为bi/s，每个武器可以攻击的机器人不同，求摧毁所有机器人的最短时间，时间可以为小数题解：实数上二分答案。好久没写网络流都不会开空间了……#include <cmath>#include <cstdio>#include <cstring>#include <cstd...

2017-03-03 23:53:00 92

转载 BZOJ3578 GTY的人类基因组计划2 HASH

题意：有N个人M个房间，初始时所有人都在1号房间，维护：1、让某个人去某个房间 2、假如[l,r]中所有的人还未一起统计过，Ans+=人数。输出Ans题解：集合HASH get根据异或的性质，a^x^x=a，因此一个集合的HASH值就是其所有元素的异或起来的值接下来就是STL大法好将每个房间看成一个集合，每个人赋一个初始rand，set存储当前所有HASH值没有出现...

2017-02-28 23:44:00 103

转载 BZOJ3240 NOI2013 矩阵游戏快速幂+矩阵乘法+逆元

题意：给定a b c d n m，fi,j满足f1,1=1 fi,j=afi,j-1+b fi,1=cfi-1,m+d，求fn,m%P题解：a=1且c=1时\[{f_{n,m}} = 1 + b(m - 1)n + d(n - 1)\]否则\[\left( {\begin{array}{*{20}{c}}{{f_{n,m}}}&{bd}\end{array}} \ri...

2017-02-28 23:41:00 69

转载 BZOJ3130 SDOI2013 费用流二分法+网络流

题意：给定一张图，求：1、最大流 2、最大流方案中，流量最大的一条边题解：第一问裸题第二问显然Bob要把所有的费用加在流量最大的边上，因此我们二分最长边，每条边的流量改为min{二分出的最大流量,当前边的流量}，跑最大流检验。注意可以是实数流量，比如说：<1,2,3> <3,2,3> <2,4,2> <2,5,2> &...

2017-02-28 23:32:00 72

转载 BZOJ2768 JLOI2010 冠军调查网络流

题意：有N个人，每个人有一个初始想法(0/1)和ki个朋友，安排每个人的最终想法，使得|违心的人数+不同意见的朋友的对数|最小题解：S向每个0连流量为1的边，表示违心；同理每个1向T连流量为1的边。如果两人是朋友，连一条流量为1的边，表示可以对立。然后网络流/最小割走起。#include <queue>#include <cstdio>...

2017-02-28 23:29:00 72

转载 BZOJ1058 ZJOI2007 报表统计线段树+平衡树

题意：给定一个序列，维护：1、插入一个元素 2、求相邻两个元素中，差值绝对值的最小值 3、求序列排序后相邻两个元素中，差值绝对值的最小值题解：MIN_GAP：如果我们把数看成一组一组，每次插入数字都在一组的最后插入，那么答案只有可能在组内和组间两个位置产生，定义l[i]为一组数中最左边的数，r[i]为一组数中最右边的数，新插入的数为x，那么用|x-l[i]|取min来更新组内...

2017-02-28 23:26:00 200

转载 BZOJ2875 NOI2012 随机数生成器矩阵乘法+快速幂

题意：Xn+1=(aXn+c)%M，求XN%G题解：矩阵乘法裸题#include <cstdio>#include <cstring>#include <cstdlib>#include <climits>#include <iostream>#include <algorithm&gt...

2017-02-28 23:23:00 111

转载 BZOJ3926 ZJOI2015 诸神眷顾的幻想乡后缀自动机+DFS

题意：给定一颗字符树，求树中路径所构成的不同的字符串的数量，其中AB和BA视作不同的字符串题解：题目里有这样一句话：太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过20个。一共有10W个点，却只有20个叶子……因此树上所有的字串就是以叶子为起点搜索出的所有字串，丽洁姐真的好善良啊- -（无雾）这样从每个点开始就能跑出来一颗Trie树，对Trie构造广义后缀自动机—...

2017-02-28 23:20:00 87

转载 BZOJ4516 SDOI2016 生成魔咒后缀自动机

题意：初始时给定一个空串，在其后不断加字符，求每次加入后不同子串的数量题解：当时拿到这个题一眼看出用后缀数组啥的，然而我并不会QAQ……不耸，不会后缀数据结构我们会HASH是不是，于是用HASH水了30分，能进R2真是命大2333讲题的时候标算用的后缀数组，不过看他写了半个黑板就感觉好麻烦。YTS大神说这题是个后缀自动机模板题，瞬间感觉自动机啥的都好厉害，于是回来后补了个后缀...

2017-02-28 23:18:00 73

转载 BZOJ2555 SubString 后缀自动机+LCT/暴力

题意：给定一个字符串，维护：1、在当前字符串后面插入一个字符串 2、询问一个字符串在当前字符串中出现的次数。强制在线题解：维护自动机，一个字符插入之后其祖先的出现次数全部++，这个可以拿LCT或者暴力来维护，链上修改单点查询。#include <cstdio>#include <cstring>#include <cstdlib&g...

2017-02-28 23:15:00 71

转载 BZOJ3998 TJOI2015 弦论后缀自动机

2017-02-28 23:13:00 94

转载 BZOJ2324 ZJOI2011 营救皮卡丘最短路+费用流

题意：给定一张无向图，有K个人，每一时刻K个人可以同时走（也可以停在一个节点），在到达i之前必须先到达i-1，求从0到N，K个人走的最小距离和（只需一个人到达即可）题解：用Floyd跑出任意两个城市i j间的最短路，更新的前提是k<j（要到达城市j必须先到达1->j-1）将每个城市拆成两个点A B，u v间连费用为w的边，i为任意一个城市，按如下方式建图：...

2017-02-28 23:10:00 86

转载 BZOJ2245 SDOI2011 工作安排费用流

题意：有n类产品，其中第i类产品共需要Ci件。有m名员工，员工能够制造的产品种类有所区，一件产品必须完整地由一名员工制造，对于员工i，他的愤怒值与产品数量之间的函数是一个Si+1段的分段函数。当他制造第1~Ti,1件产品时，每件产品会使他的愤怒值增加Wi,1，当他制造第Ti,1+1~Ti,2件产品时，每件产品会使他的愤怒值增加Wi,2……设Ti,0=0,Ti,si+1=+∞，那么当他制造...

2017-02-28 23:06:00 77

转载 BZOJ3876 AHOI2014 支线剧情费用流

题意：给定一张有向图，求一个路径集合，集合中的路径满足：1、起点为1，终点出度为0 2、集合中的路径覆盖了所有的点 3、在满足前两个条件的基础上，路径权值和最小题解：显然是个带下界的有源费用流。按照如下方式建模，对于一条边权为w的边(u,v)和任意一个点xx向T连容量为k费用为0的边，表示其后每条路经都必须跑一次。x向1连容量为INF费用为0的边，表示从任意一个点都可...

2017-02-28 23:02:00 82

转载 BZOJ2879 NOI2012 美食节费用流

题意：有N种菜，M位厨师，每位厨师做每种菜的时间不同。有K个人，每个人点ki个菜，求最小等待时间。题解：和BZOJ1070一个题，不过多了一个N，因此考虑优化。显然决策倒数第K个菜的前提是倒数第K-1个菜已经决定完成，因此SPFA每搜出一条路径，就在这个厨师这里加边。说白了就是动点。#include <queue>#include <cstd...

2017-02-28 22:58:00 83

转载 BZOJ1070 SCOI2007 修车费用流

题意：给定N辆车和M个人，每个人修每辆车的时间不同，安排修理顺序使得修理这N辆车时间总和最小题解：将每个工作人员拆点，某个车b向ai连边表示工作人员a倒数第i个修理该车，显然其对答案的贡献（该边费用）就是w[b][a]*i（其后所有等待的车都要受其影响，而之前的车都不会）。构图两排点，左边是车，右边是拆点后的工作人员，建立S和T跑最小费用流即可。printf坏掉了死活保留...

2017-02-28 22:55:00 84

转载 BZOJ1877 SDOI2009 晨跑费用流

题意：给定一张有向图，求1到N：1、最多有多少条不相交的路径 2、在第一问的基础上，求所有路径的最小距离和题解：拆点之后费用流裸题#include <queue>#include <cstdio>#include <cstring>#include <cstdlib>#include <climits...

2017-02-28 22:51:00 98

转载 BZOJ1189 HNOI2007 紧急疏散evacuate 网络流+BFS+二分法

题意：一个N M的矩形区域。格子如果是'.'，那么表示这是一块空地；如果是'X'，那么表示这是一面墙，如果是'D'，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制。每一秒钟只能有一个人移动到门的位置，一...

2017-02-28 22:47:00 80

空空如也

空空如也