- 博客(70)
- 收藏
- 关注
RSS订阅原创 FJOI2016 建筑师(组合数学)
FJOI2016 建筑师昨天考了场省选模拟赛,下来才知道是FJOI2016,不过T1,T2都没在OJ上找到?? T2倒是以前在紫书上面做到过类似的.同UVa 1638
2017-03-03 16:11:28
1304
原创 BZOJ 1176: [Balkan2007]Mokia (CDQ分治)
BZOJ 1176: [Balkan2007]Mokia题意概述:一个W∗WW*W的矩阵,每个格子的初始值为SS. 有两种操作: 1. 0 x y v 表示将(x,y)(x,y)点权值增加vv 2. 1 x1 y1 x2 y2 表示以(x1,y1)(x1,y1)为左上角,(x2,y2)(x2,y2)为右下角的子矩阵点权和题目分析:又来一道CDQ (๑•̀ㅂ•́)و✧对于询问子矩阵,将其转化成类
2017-02-15 21:58:11
638
原创 BZOJ 3262: 陌上花开 (CDQ分治)
BZOJ3262: 陌上花开题意概述有N朵花,对于每一朵花,有三个属性:ss,cc,mm. 当且仅当si>sj,ci>cj,mi>mjs_i>s_j,c_i>c_j,m_i>m_j,有花i比花j美丽. 一朵花的评级为比其他花更美丽的数量(不包括自己),输出评级为0 N−10~N-1的花的数量.题目分析:初学CDQ分治,写了一下午.orz……这是一个三维偏序的问题,可以用CDQ来搞一搞. 当然此
2017-02-15 21:18:26
1194
原创 BZOJ 1208: [HNOI2004]宠物收养所 (Treap)
BZOJ 1208: [HNOI2004]宠物收养所题目概述:有一家宠物收养所,提供两种服务:收养主人遗弃的宠物和让新主人领养宠物. 宠物收养所中总是会有两种情况发生:遗弃宠物过多和领养宠物人过多. 1.遗弃宠物多时,若来一个领养人,领养最接近要求的宠物,若有多只,优先选择小的. 2.领养人多时,若来一只宠物,领养要求最接近的领养,若有多人,优先选择小的. 求领养的宠物的人的不满意度之和,不
2017-01-04 18:56:35
977
原创 BZOJ 1588: [HNOI2002]营业额统计 (Treap/链表)
BZOJ 1588: [HNOI2002]营业额统计题目概述:依次给出n日的营业额,当日的营业额波动为和当日以前的营业额差值的绝对值,特别的,第一日的营业额波动为当日营业额,求n日的最小波动之和.题目分析:(刚学了Treap来练手……)解法一:既然是练习Treap,那就用Treap来做吧. 对于每一日,先求出它的前驱和后继,用与当前数相差小的更新答案. 注意处理没有前驱或者后继的情况.#incl
2017-01-04 15:14:12
944
原创 BZOJ 3224 Tyvj 1728 普通平衡树 (Treap)
BZOJ 3224 Tyvj 1728 普通平衡树题目概述:给n个操作,有6种操作: 1.插入一个数 2.删除一个数(若该数有多个,那么只删除一个) 3.查询一个数的排名(若有多个,取最小) 4.查询一个排名对应数 5.查询一个数的前驱(小于该数的最大数) 6.查询一个数的后继(大于该数的最小数)题目分析:如题目,是一道平衡树的版题,可以选择使用Treap实现.注意可能会有相同的数出现,
2017-01-03 19:15:22
967
原创 POJ 3237 Tree (树链剖分+线段树)
POJ 3237 Tree题目大意:给你n个结点的树,有三种操作: 1.CHANGE i v 将i号边边权变为v 2.NEGATE a b 将a点到b点路径上的边权取相反数 3.QUERY a b 找到a点到b点路径上的边权的最大值 输出所有3操作结果,指令结束标志为”DONE”. 有多组数据.题目分析:(又滚去做树链剖分的题,元旦放假前开始做到现在,233)将边权转化成相连两点中子节点的
2017-01-02 21:04:46
820
原创 BZOJ 3637: Query on a tree VI (树链剖分+树状数组)
BZOJ 3637: Query on a tree VI题意概述:给一棵n个结点的树,结点有黑白两色,一开始全为黑色. 对于q个操作,每个操作由两个整数op,u给出. 当op=0,将u点颜色反转. 当op=1,求与u点相连的点的个数(若两点及两点间路径上均为同色点,则两点相连,否则不相连),即求从u点往四周扩散的同色块大小.题目分析:(初学链剖,戳开了这个题,然后……d了一天的bug)在网上
2016-12-31 09:33:49
1447
原创 BZOJ 1036: [ZJOI2008]树的统计Count (树链剖分+线段树)
BZOJ 1036: [ZJOI2008]树的统计Count题目概述:n个结点的树,点有点权.有三种操作:1.单点修改点权,区间询问和,区间询问最值.题目分析:先用树链剖分将树剖分成多条链,再用线段树维护.代码:#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int maxn=30000
2016-12-29 21:31:34
611
原创 总结-树链剖分
总结-树链剖分(今天学会了树链剖分,\(^O^)/)以BZOJ1036为例,题目中要求树上的区间和,最值询问. 若不是在树上的话,很容易想到用线段树来来实现.树链剖分实质而树链剖分实际上也就是将树结构剖分成一条一条的链结构,实际上就是区间,以便于数据结构的操作. 就题目而言,若将树剖分成链,那么就很容易再在线段树的基础上维护.如何剖分?显然链的条数越少越好,那么对于一个点而言,他只能和其子节点中
2016-12-29 21:26:33
848
原创 LA 4270 Discrete Square Roots (扩展欧几里得+模方程)
LA 4270 Discrete Square Roots题目大意:在模n的意义下,非负整数x的离散平方根是满足0≤r<n0\leq r < n的整数,所以一个x可能会有多个离散平方根. 输入x,n,r(1≤x<n,2≤n≤109,1≤r≤n1\leq x < n,2\leq n\leq 10^9,1\leq r\leq n),输出数据编号和所有离散平方根,从小到大排序.题目分析:(又是一道扩欧的
2016-12-28 21:41:21
888
原创 UVa 10951 Polynomial GCD (数论)
UVa 10951 Polynomial GCD题目大意:给定两个ZnZ_n上的多项式f(x)f(x)和g(x)g(x),求出他们的gcdgcd,即ZnZ_n上的一个多项式r(x)r(x),使得其可以同时整除f(x)f(x)和g(x)g(x),且次数尽量大.你找到的多项式的最高项系数应当为11. (注意:ZnZ_n下的多项式即系数为[0,n)区间内的整十数,也就是说在n进制下的计算).题目分析:求
2016-12-28 17:23:28
559
原创 UVa 10692 Huge Mods (指数循环节)
UVa 10692 Huge Mods题目大意:给出模数mm和正整数a1,a2...an,a_1,a_2...a_n,求出aa...an21 mod ma_1^{a_2^{...^a_n}}\ mod\ m的值. (注意指数运算的顺序:234=2(34)=2812^{3^4}=2^{(3^4)}=2^{81}) (2≤m≤10000,1≤n≤10,1≤ai≤10002\leq m\leq 10
2016-12-28 11:38:26
393
原创 UVa 11768 Lattice Point or Not (扩展欧几里得)
UVa 11768 Lattice Point or Not题目大意:给两个点A(x1,y1)和B(x2,y2).其中x1,y1,x2,y2皆为0.1的整数倍,且绝对值不超过200000.统计线段AB经过的整点数.题目分析:(看来扩欧我还是不会欸,orz……)求直线上的整点要用到扩展欧几里得解线性方程. 先利用A,B两点表示出形如ax+by=cax+by=c形式的直线方程,得到 (注意A,B横纵
2016-12-28 07:49:03
842
原创 LA 4258 Metal (递推)
LA 4258 Metal题目大意:平面上有n个点,任意两点的x坐标不同.统计有多少种方案能将其连成单调多边形.满足多边形非相邻边不能有公共点,任意两条边不能相交,且与任意与y轴平行的直线与多边形的公共部分是一个点或一条线段(或者说该直线只能与多边形交于1个或者两个点). 题目分析:由满足条件可知,对于多边形的上下边缘一定不会回折(如上图),因为若某条线延伸出去又折回来,那么一定会使得公共部分变成
2016-12-26 16:48:42
683
原创 UVa 11481 Arrange the Numbers (组合数学+容斥原理)
UVa 11481 Arrange the Numbers题目大意:可以将序列1,2,3,...n1,2,3,...n任意重排,但重排后的前mm(m≤nm\leq n)个位置恰好有kk(k≤mk\leq m)个不变,求方案数除以1000000007的余数. (注意是前m个位置恰好有k个不变,也就是说前m个位置的另外m-k个必须改变)题目分析:首先,前m个位置恰好有k个不变,则有CkmC_{m}^{
2016-12-25 09:40:31
539
原创 LA 4064 Magnetic Train Tracks (极角排序)
LA 4064 Magnetic Train Tracks题目大意:在平面上给n个点(任意三点不共线),问这些点共组成了多少锐角或者直角三角形. (1≤n≤12001\leq n \leq 1200)题目分析:锐角三角形必须满足三个角都为锐角,并不利于统计.尝试统计不是锐角或者直角三角形,即——统计钝角三角形的个数. 统计钝角三角形只需要找到钝角即可,且钝角三角形仅有一个钝角,不会出现重复的情况
2016-12-24 08:42:38
585
原创 LA 3720 Highways (计数问题)
LA 3720 Highways题目大意:有一个n*m的点阵,问一共有多少条非水平非竖直的直线至少穿过其中两个点? (1≤n,m≤3001\leq n,m \leq 300)题目分析:可以发现,非水平非竖直的直线有两种:’/’和’\’,可以选择只统计其中一种来计算,下面选择’\’. 若将起始点坐标设为(0,0). 什么时候会出现重复直线,例如(0,0)-(4,6)就与(0,0)-(2,3)重合
2016-12-23 16:13:33
569
原创 UVa 11609 Teams (组合数学)
UVa 11609 Teams题目大意:有n(1≤n≤109)n(1\leq n\leq 10^9)个人,选一个或者多个人参加比赛,其中一名当队长.两种方案相同,当且仅当人员组成和队长相同,问有多少种方案. 输出方案数除以1000000007的余数.题目分析:(推个式子都要推半天,吃枣药丸)当选择一个人的时候有C1nC_{n}^{1}中方案,每种方案队长安排一种. … ans=1∗C1n+2
2016-12-22 21:58:38
359
原创 UVa 10892 LCM Cardinality (数论+组合数学)
UVa 10892 LCM Cardinality题目大意:输入正整数nn(n≤2∗109n \leq 2*10^9),统计有多少对正整数a≤ba \leq b,满足lcm(a,b)=nlcm(a,b)=n.输出n和形成的对数.题目分析:(想了好一会儿,orz……)若将数拆分成唯一分解式,可以发现 设a=pk11∗pk22∗...∗pknnb=pk′11∗pk′22∗...∗pk′nna=p_1
2016-12-22 16:58:08
597
原创 UVa 11889 Benefit (数论)
UVa 11889 Benefit题目大意:给两个整数A和C,求最小的整数B使得lcm(A,B)=C.若无解,输出”NO SOLUTION”(不含引号).题目分析:显然可知,若C%A!=0,则无解. 对于有解的情况,如下 设A=g∗p1B=g∗p2C=g∗p1∗p2A=g*p_1\\B=g*p_2\\C=g*p_1*p_2要使lcm(A,B)=Clcm(A,B)=C,则p1与p2p_1与p_
2016-12-22 14:39:56
461
原创 UVa 10828 Back to Kernighan-Ritchie (高斯-约当消元)
UVa 10828 Back to Kernighan-Ritchie题目大意:给出一个程序控制流图,从每个结点出发到其后继结点的概率相等.当执行完一个没有后继的结点后,程序终止.程序总是从编号为1的结点开始执行.求出多个询问结点的期望执行次数. 数据不超过100组,第一行为n(1≤n≤100)n(1\leq n\leq 100),结点编号为11到nn.以下若干行每行包含a,ba,b两个整数,以a
2016-12-21 17:24:55
460
原创 LA 3704 Cellular Automaton (矩阵快速幂)
LA 3704 Cellular Automaton题目大意:一个环被分成n份,每个格子取值为0~m-1.给定距离d,则每次操作后每个格子的值为与其距离不超过d的格子操作前的值之和除以m的余数. (1≤n≤500,1≤m≤106,0≤d<n/2,1≤k≤1071\leq n \leq 500,1\leq m \leq 10^6,0\leq d < n/2,1\leq k \leq 10^7)题目分
2016-12-21 14:41:08
458
原创 UVa 10870 Recurrences (矩阵快速幂)
UVA 10870 Recurrences题目大意:f(n)=a1f(n−1)+a2f(n−2)+a3f(n−3)+...+adf(n−d)f(n)=a_{1}f(n-1)+a_{2}f(n-2)+a_{3}f(n-3)+...+a_{d}f(n-d). 给出a1a_{1}~ada_{d},f(1)f(1)~f(d)f(d),nn,mm,求f(n)%mf(n)\%m. (1≤d≤15,1≤n≤2
2016-12-21 10:22:49
455
原创 LA 4119 Always an integer (数学)
LA 4119 Always an integer题目大意:给定一个形如(P)/D的多项式,其中P是若干个形如Cn^E的项之和,判断他是否在所有正整数处取到整数值. 其中系数C和次数E满足如下条件: 1.E是满足0<=E<=100的整数.若E=0,则Cn^E写成C;若E=1,则Cn^E写成Cn,但当C=±1时除外(C=1时,写成n;C=-1时,写成-n). 2.C为整数.若C=±1,且E不是0
2016-12-16 21:22:15
465
原创 总结-筛素数
总结-筛素数埃拉托斯特尼筛法 如上图所示,朴素的埃氏筛法从2~n对于每个没有被筛去的数——即素数,从该素数开始将i的各个倍数依次删去.int not_pri[maxn],pri[maxn],pcnt;void init_pri(int n){ not_pri[0]=not_pri[1]=1; for(int i=2;i<=n;i++) { if(!not_pri[
2016-12-16 16:28:48
362
1
原创 LA 3716 DNA Regions (二分/排序)
LA 3716 DNA Regions题目大意:给两条长度为n的DNA链A和B,找出一段最长的区间使得区间内的突变位置不超过p%p\%.即找出尽可能长的区间,使得区间内有不超过p%p\%的xx满足Ax≠BxAx \neq Bx. (1≤n≤150000,1≤p≤991\leq n \leq 150000,1\leq p \leq 99).题目分析:设sum[i]表示到i位置为止对应字母不同的个数.
2016-12-16 09:41:51
389
原创 LA 5052 Genome Evolution (思维)
LA 5052 Genome Evolution题目大意:给1~n的两个排列A,B,统计有多少个子集A,B均有,子集要满足是连续序列,且至少包含两个元素.(1<=n<=5000)题目分析:对于两个子集,要满足元素相同,且是连续序列,则长度要一致. 若确定某一个点i为在A序列中的右边界,那么A序列中每往左加入一个元素j,在B中也会对应有一个位置.显然此时能满足元素相同的要求. 那么还需要是连续序列
2016-12-15 22:02:41
547
原创 UVa 11361 Investigating Div-Sum Property (数位DP)
UVa 11361 Investigating Div-Sum Property题目大意:给定a,b,k三个正整数,统计在[a,b]之间的整数n中,有多少n自身是k的倍数,且n的各个数字(十进制)之和也是k的倍数.(1⩽a⩽b⩽2311\leqslant a\leqslant b\leqslant 2^{31})题目分析:这是一道典型的数位DP题. n非常大,若是直接枚举的话会超时,考虑利用加法原
2016-12-15 19:40:50
406
原创 LA 3516 Exploring Pyramids (递推)
LA 3516 Exploring Pyramids题目大意:给一棵多叉树,从根节点开始,每次尽量往左走,走不通则回溯,将遇到的字母顺次记录下来,得到一个序列.现在给一个序列,求有多少棵树可以与之对应.题目分析:定义状态dp(i,j)表示序列[i,j]可形成的树的种类数。 设序列为S,因为在回溯的过程中也要记录,所以在选择某两个位置i和j时,需保证S[i]=S[j]. 转移方程如下 dp(i
2016-12-15 14:49:01
358
原创 LA 4356 Fire-Control System (扫描法)
LA 4356 Fire-Control System题目大意:平面上有n个点,找到一个以(0,0)为圆心的扇形,至少覆盖k个点,使其面积尽可能小.题目分析:影响扇形面积的有两个因素:圆心角和半径,但是并不容易同时维护两个变量. 可以选择确定某一变量,使得另一变量尽可能小来使得面积尽可能小. 这里选择先确定半径,那么就会剩下一些点,再在这些点中筛选使其面积尽可能小.代码:#include<cma
2016-12-15 08:13:11
465
原创 LA 4851 Restaurant (扫描法)
LA 4851 Restaurant题目大意:有M*M网格,左下角(0,0),右上角(M-1,M-1).上面有n个餐厅,其中编号为1和2的分别是AB两宾馆的餐厅.对于一个位置,若存在与之前已有的任意餐厅位置相比,更靠近A或者B,就定义为”好位置”.问”好位置”的个数.(其中,两点间的距离为曼哈顿距离,即横纵坐标差的绝对值之和)题目分析:因为AB同纵坐标Y,所以尝试从xa移动到xb. 则设d数组,d
2016-12-14 21:06:17
613
原创 LA 4726 Average (单调队列+斜率优化)
LA 4726 Average题目大意:给一个长为n的01序列,要求选择一个连续序列,其长度不小于L,使得序列的平均值尽量大,若有多解,长度尽可能小,若仍有多解,起点编号尽可能小.题目分析:以序列长度为横坐标,1的个数为纵坐标,可以在坐标系上找到n个点,题目问题实际上转化成了求斜率,即斜率优化.用单调队列维护下凸包,O(n)复杂度. 具体论证参考 《浅谈数形结合思想在信息学竞赛中的应用》代码:#i
2016-12-14 16:02:31
598
原创 UVa 10125 Sumsets (中途相遇法)
UVa 10125 Sumsets题目大意:给一个整数集合S,找出最大的d,使得a+b+c=d,其中a,b,c,d是S中的不同元素. (元素个数1<=n<=1000,元素大小-536870912<=x<=+536870911).题目分析:最直接的手段是直接枚举a,b,c,d,当然时间复杂度很高O(n^4). 但是若将四个数拆分成两两枚举,即先枚举a+b,储存起来,再枚举d-c,查找是否存在a+b
2016-12-14 10:18:17
541
原创 LA 4253 Archery (暴力枚举/二分答案+枚举)
LA 4253 Archery题目大意:有n个与x轴平行的线段,每条线段是一个靶子(由D,L,R表示纵坐标为D,左右端点横坐标为L,R),问在x轴的[0,W]区间上是否存在位置可以使得箭穿过所有靶子.假设箭沿直线飞行,直到无穷远处,不同靶子纵坐标不同.题目分析:解法一(O(n^2)):将靶子两两进行枚举,判断i靶子左/右端点与j靶子右/左端点在x轴上的交点形成区间与原区间取交集,若为空,无解.解法一
2016-12-13 14:54:59
483
原创 LA 4850 Installations (排序+枚举)
LA 4850 Installations题目大意有n个安装服务,第i个服务需要si时间完成,截止日期为di,若在截止日期前完成,没有惩罚,若在截止日期后完成,若完成日期为ti,惩罚值为ti-di.即惩罚值为max(0,ti-di).求如何安排任务,使得最大的两个惩罚值之和最小.题目分析最开始把题看错了,看成是求最大的惩罚值最小,直接按照di排序.但是这种方法只能使得全局最优,并不一定是和最小.那么
2016-12-13 09:52:21
735
1
原创 LA 4094 WonderTeam (构造)
LA 4094 WonderTeam题目大意:有n支队伍,每两支队伍比赛两场,胜得3分,平得1分,负不得分.比赛结束评选一支梦之队,满足要求是:进球总数最多(不能并列)+胜利数最多(不能并列)+丢球数最少(不能并列).求梦之队的最低可能排名.题目分析:智商真是一天不如一天,╮(╯_╰)╭. 题解参考自这里 若梦之队某一场次的进球数极大,就可以满足进球数最多. 要使梦之队排名尽可能靠后,那么那只
2016-12-13 08:01:46
880
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人