- 博客(179)
- 收藏
- 关注
RSS订阅原创 停更
BZOJ4552 Tjoi2016&Heoi2016排序Description在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]...
2018-09-20 07:32:14
369
原创 BZOJ4547 Hdu5171 小奇的集合 【矩阵快速幂优化递推】
BZOJ4547 Hdu5171 小奇的集合Description有一个大小为n的可重集S，小奇每次操作可以加入一个数a+b(a,b均属于S)，求k次操作后它可获得的S的和的最大值。（数据保证这个值为非负数）Input第一行有两个整数n,k表示初始元素数量和操作数，第二行包含n个整数表示初始时可重集的元素。对于100%的数据，有 n<=105，k<=109，|ai|<...
2018-09-19 14:50:48
251
原创 BZOJ1113 Poi2008 海报PLA【单调栈】【水】
BZOJ1113 Poi2008 海报PLADescriptionN个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.Input第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 PosteringOutput最少数量的海报数.Sample Input51 21 32 22...
2018-09-19 13:13:07
260
原创 BZOJ1510 POI2006 Kra-The Disks 【模拟】
BZOJ1510 POI2006 Kra-The DisksLINK还是粘题面吧，但是图就算了DescriptionJohnny 在生日时收到了一件特殊的礼物，这件礼物由一个奇形怪状的管子和一些盘子组成. 这个管子是由许多不同直径的圆筒(直径也可以相同) 同轴连接而成. 这个管子的底部是封闭的,顶部是打开的. 下图是由直径为: 5cm, 6cm, 4cm, 3cm, 6cm, 2cm a...
2018-09-19 12:56:37
258
原创 BZOJ 2530 Poi2011 Party 【枚举】
BZOJ 2530 Poi2011 PartyDescriptionByteasar intends to throw up a party. Naturally, he would like it to be a success. Furthermore, Byteasar is quite certain that to make it so it suffices if all inv...
2018-09-19 11:55:56
218
原创 BZOJ4292 PA2015 Równanie 【暴力水题】
BZOJ4292 PA2015 RównanieDescription对于一个正整数n，定义f(n)为它十进制下每一位数字的平方的和。现在给定三个正整数k,a,b，请求出满足a<=n<=b且k*f(n)=n的n的个数。Input第一行包含三个正整数k,a,b(1<=k,a,b<=10^18,a<=b)。Output输出一个整数，即满足条件的n的个数。S...
2018-09-19 11:40:51
159
原创 BZOJ1801 Ahoi2009 chess 中国象棋 【DP+组合计数】*
BZOJ1801 Ahoi2009 chess 中国象棋Description在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.Input一行包含两个整数N，M，中间用空格分开.Output输出所有的方案数，由于值比较大，输出其mod 9999973Sample Input1 3Samp...
2018-09-19 11:22:57
225
原创 【干货】高精度模板【加，减，乘，快速幂】
#include<bits/stdc++.h>using namespace std;#define N 1010#define LL long long#define fu(a,b,c) for(int a=b;a<=c;++a)#define fd(a,b,c) for(int a=b;a>=c;--a)const int Base=10000;struc...
2018-09-19 10:02:22
483
原创 BZOJ1220 HNOI2002 跳蚤 【容斥原理+高精度】*
BZOJ1220 HNOI2002 跳蚤DescriptionZ城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的...
2018-09-19 09:59:53
193
原创 BZOJ1412 ZJOI2009 狼和羊的故事 【网络流-最小割】
BZOJ1412 ZJOI2009 狼和羊的故事Description“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是...
2018-09-19 07:44:56
237
原创 BZOJ1816 Cqoi2010 扑克牌【二分答案】
BZOJ1816 Cqoi2010 扑克牌Description你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量...
2018-09-19 07:39:21
459
原创 BZOJ2431 HAOI2009 逆序对数列 【DP】*
BZOJ2431 HAOI2009 逆序对数列Description对于一个数列ai{a_i}ai，如果有i<j且ai&gt;aja_i&gt;a_jai>aj，那么我们称aia_iai与aja_jaj为一对逆序对数。若对于任意一个由1~n自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个？Input第一行...
2018-09-18 22:11:57
204
原创 BZOJ3209 花神的数论题 【组合数学+数位DP+快速幂】*
BZOJ3209 花神的数论题Description背景众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。描述话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。花神的题目是这样的设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你派(Sum(i)),也就是 sum(1)—sum...
2018-09-18 21:05:22
187
原创 BZOJ3444 最后的晚餐【细节题+组合数学】*
BZOJ3444 最后的晚餐Description【问题背景】高三的学长们就要离开学校，各奔东西了。某班n人在举行最后的离别晚餐时，饭店老板觉得十分纠结。因为有m名学生偷偷找他，要求和自己暗恋的同学坐在一起。【问题描述】饭店给这些同学提供了一个很长的桌子，除了两头的同学，每一个同学都与两个同学相邻（即坐成一排）。给出所有信息，满足所有人的要求，求安排的方案总数（这个数字可能很大，请输...
2018-09-18 19:07:25
286
原创 BZOJ3609 Heoi2014 人人尽说江南好【推理+结论】
BZOJ3609 Heoi2014 人人尽说江南好Description小 Z 是一个不折不扣的 ZRP（Zealot Round-game Player，回合制游戏狂热玩家），最近他 想起了小时候在江南玩过的一个游戏。在过去，人们是要边玩游戏边填词的，比如这首《菩萨蛮》就是当年韦庄在玩游戏时填 的：人 人 尽 说 江 南 好， 游 人 只 合 江 南 老。然而我们今天不太关心人们填的...
2018-09-18 18:20:10
251
原创 BZOJ4236 JOIOJI 【map】
BZOJ4236 JOIOJIDescriptionJOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。最近，JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成，并且想让“J、O、I”三个字母的出现次数恰好相同。JOIOJI桑家有一份祖传的卷轴，上面写着一首长诗，长度为N，由“J、O、I”三个字母...
2018-09-18 17:37:16
228
原创 BZOJ4245 ONTAK2015 OR-XOR 【位运算+贪心】*
BZOJ4245 ONTAK2015 OR-XORDescription给定一个长度为n的序列a[1],a[2],…,a[n]，请将它划分为m段连续的区间，设第i段的费用c[i]为该段内所有数字的异或和，则总费用为c[1] or c[2] or … or c[m]。请求出总费用的最小值。Input第一行包含两个正整数n,m(1<=m<=n<=500000)，分别表示序列...
2018-09-18 17:02:13
203
原创 BZOJ4517 Sdoi2016 排列计数 【DP+组合计数】*
BZOJ4517 Sdoi2016 排列计数Description求有多少种长度为 n 的序列 A，满足以下条件：1 ~ n 这 n 个数在序列中各出现了一次若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的满足条件的序列可能很多，序列数对 10^9+7 取模。Input第一行一个数 T，表示有 T 组数据。接下来 T 行，每行两个整数 n、m...
2018-09-18 15:43:49
236
原创 BZOJ4590 Shoi2015 自动刷题机 【二分】
BZOJ4590 Shoi2015 自动刷题机Description曾经发明了信号增幅仪的发明家SHTSC又公开了他的新发明：自动刷题机–一种可以自动AC题目的神秘装置。自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序，每秒，自动刷题机的代码生成模块会有两种可能的结果：A.写了x行代码。B.心情不好，删掉了之前写的y行代码。（如果y大于当前代码长度则相当于全部删...
2018-09-18 15:27:27
183
原创 BZOJ1227 SDOI2009 虔诚的墓主人【树状数组+组合数】【好题】*
BZOJ1227 SDOI2009 虔诚的墓主人Description小W 是一片新造公墓的管理人。公墓可以看成一块N×M 的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地。当地的居民都是非常虔诚的基督徒，他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚，他们希望自己的墓地拥有着较高的虔诚度。一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看...
2018-09-17 22:55:45
203
原创 BZOJ1260 CQOI2007 涂色paint 【区间DP】
BZOJ1260 CQOI2007 涂色paintDescription假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标...
2018-09-17 15:10:01
157
原创 BZOJ1853 Scoi2010 幸运数字 【枚举+容斥】
BZOJ1853 Scoi2010 幸运数字Description在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。...
2018-09-16 18:03:18
182
原创 BZOJ4373 算术天才⑨与等差数列 【线段树】*
BZOJ4373 算术天才⑨与等差数列Description算术天才⑨非常喜欢和等差数列玩耍。 有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。 他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。 当然，他还会不断修改其中的某一项。 为了不被他鄙视，你必须要快速并正确地回答完所有问题。 注意：只有一个数的数...
2018-09-16 15:44:10
183
原创 LOJ2425 NOIP2015 运输计划 【二分+LCA+树上差分】*
LOJ2425 NOIP2015 运输计划LINK题意：给你一颗树，可以将任意一条边的权值变成0，然后求m条路径的长度的最小值思路： 先二分最后的距离ans，然后我们把路程大于ans的所有路径拿出来 然后把这些路径的交求出来，用树上差分的方法 然后对这个交（用点集转化成边集，就是每个点的上一条边）取一个最大值 然后判断这些边减去这个最大值之后会不会小于等于a...
2018-09-15 22:24:06
223
1
原创 LOJ2424 NOIP2015 子串 【DP】*
LOJ2424 NOIP2015 子串LINK题目大意是给你两个序列，在a序列中选出k段不重叠的子串组成b序列，问方案数首先我们不考虑相邻的两段，把所有相邻段当成一段进行计算然后设dpi,j,k,0/1dpi,j,k,0/1dp_{i,j,k,0/1}表示a使用了i为，b匹配到j位，一共有k段，当前这一位选不选的方案数然后转移显然: dpi,j,k,0=dpi−1,...
2018-09-15 22:22:29
177
原创 BZOJ1345 Baltic2007 序列问题Sequence 【思维题】*
BZOJ1345 Baltic2007 序列问题SequenceDescription对于一个给定的序列a1,…,an，我们对它进行一个操作reduce(i)，该操作将数列中的元素ai和ai+1用一个元素max(ai，ai+1)替代，这样得到一个比原来序列短的新序列。这一操作的代价是max(ai，ai+1)。进行n-1次该操作后，可以得到一个长度为1的序列。我们的任务是计算代价最小...
2018-09-14 19:30:56
209
原创 BZOJ4602 Sdoi2016 齿轮 【带权并查集】*
BZOJ4602 Sdoi2016 齿轮Description现有一个传动系统，包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v，并提供了一个传动比x : y。即如果只考虑这两个组合齿轮，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。传动比为正表示若编号为u的齿轮顺时针转动，则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动，则编号为v的齿轮...
2018-09-14 19:14:13
362
原创 LOJ2422 NOIP2015 斗地主 【搜索+贪心】*
LOJ2422 NOIP2015 斗地主LINK题目大意很简单，就是问你斗地主的一分手牌最少多少次出完然后我们发现对于一种手牌状态，不考虑顺子的情况是可以贪心做掉的然后我们直接枚举一下顺子出牌情况就可以了LOJ上的数据随便写点基本贪心就行了如果想过UOJ上的加强版的话还是把中间那一部分毒瘤的特判更优情况加上吧当然也有个Smallfat大神用DP做掉的...
2018-09-14 14:17:49
204
原创 LOJ2421 NOIP2015 信息传递 【tarjan求最小环】
LOJ2421 NOIP2015 信息传递LINK题目大意就是给你一个有向图，求最小环有一个很奇妙的性质叫做每个点只有一条出边然后我们考虑对每个强联通分量进行考虑发现每个强联通分量内的边数一定和点数相等 也就是说一个强连通的大小就是这个环的长度然后就可以来一个很常规的tarjan算一下就好了#include&lt;bits/stdc++.h&gt;...
2018-09-13 19:59:54
556
原创 LOJ2613 NOIP2013 华容道 【最短路】*
LOJ2613 NOIP2013 华容道LINK这是个好题，具体题意比较麻烦可以直接看LINK中的链接然后考虑我们可能的移动方式首先我们需要把白块移动到需要移动块S的附近（附近四格）然后我们就可以考虑怎么对S进行移动操作一：把S和白块互换位置操作二：把白块从S的一个方向移动到另一方向（方便交换位置）第一种操作的代价是1很显然，后一种操作我们每次移动的最...
2018-09-13 19:55:11
187
原创 LOJ2503 NOIP2014 解方程 【HASH】
LOJ2503 NOIP2014 解方程LINK题目大意就是给你一个方程，让你求[1,m][1,m][1,m]中的解，其中系数非常大看到是提高T3还是解方程就以为是神仙数学题后来研究了一下高精之类的算法发现过不了多少分后面佬说这题是hash然后就雾考虑对于一个式子f(x)=0f(x)=0f(x)=0肯定会满足f(x)%prime=0f(x)%prime=...
2018-09-12 19:14:21
202
原创 LOJ2500 NOIP2014 飞扬的小鸟 【背包DP】*
LOJ2500 NOIP2014 飞扬的小鸟LINK题目大意就是说有n个柱子，在每一秒你可以选择不点下降高度y和点p次上升x∗px∗px*p，若果当前位置加上x∗px∗px*p大于上界m，就会停在m。 如果可以成功穿越所有柱子输出最小点击次数，否则输出最多可以穿越的柱子数量感觉是非常显然的DP，如果不点就是一个01背包，在点的时候是一个完全背包 所以可以设dp[i][j...
2018-09-11 20:52:40
211
原创 LOJ2611. NOIP2013 积木大赛 【线段树】
LOJ2611. NOIP2013 积木大赛LINK题目大意是给你一个目标状态数组 每次你可以选择一个连续区间加上一个值，求最小操作次数我是神奇的脑子 最近做数据结构疯了 然后看见这题就数据结构了好像网上还没有这种做法逆向考虑这个过程 我们直接从目标数组删去一个连续区间我们先考虑对于一个区间肯定一次删掉min(l&nbsp;to&nbsp;r)min...
2018-09-08 20:15:20
262
原创 LOJ2609. NOIP2013 火柴排队 【树状数组】
LOJ2609. NOIP2013 火柴排队LINK题目大意： 给你两个数列，定义权值∑ni=1(ai−bi)2∑i=1n(ai−bi)2\sum_{i=1}^n(a_i-b_i)^2 问最少的操作次数，最小化权值首先需要发现几个性质 1. 最小权值满足任意i,j不存在ai&gt;aj,bi&lt;bjai&gt;aj,bi&lt;bja_i>a_j,b_i...
2018-09-08 19:34:32
191
原创 51nod 1244 莫比乌斯函数之和 【杜教筛】
51nod 1244 莫比乌斯函数之和莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。具体定义如下： 如果一个数包含平方因子，那么miu(n) = 0。例如：miu(4), miu(12), miu(18) = 0。 如果一个数不包含平方因子，并且有k个不同的质因子，那么miu(n) = (-1)^k。例...
2018-09-07 22:09:20
202
原创 Codeforces 954H Path Counting 【DP计数】*
Codeforces 954H Path CountingLINK题目大意：给你一棵n层的树，第i层的每个节点有a[i]a[i]a[i]个儿子节点，然后问你树上的简单路径中长度在1&nbsp;n∗2−21&nbsp;n∗2−21~n*2-2之间的每个有多少条因为直接计算过每个节点的路径并不好算 所以可以算一算从每个节点出发的路径的个数 f[i][j]f[i][j]f[i...
2018-09-02 22:05:28
201
原创 Codeforces 834D The Bakery 【线段树优化DP】*
Codeforces 834D The BakeryLINK题目大意是给你一个长度为n的序列分成k段，每一段的贡献是这一段中不同的数的个数，求最大贡献是第一次做线段树维护DP值的题 感觉还可以，虽然看了一下这题是用线段树维护DP值然后说思路 有一个很显然的思路是这样的: dpi,jdpi,jdp_{i,j}表示前i个数分成j段的最大贡献 dpi,j=max(dp...
2018-09-02 20:47:25
181
原创 BZOJ3963: [WF2011]MachineWorks 【CDQ+斜率优化DP】*
BZOJ3963: [WF2011]MachineWorksDescription你是任意性复杂机器公司(Arbitrarily Complex Machines, ACM)的经理，公司使用更加先进的机械设备生产先进的机器。原来的那一台生产机器已经坏了，所以你要去为公司买一台新的生产机器。你的任务是在转型期内尽可能得到更大的收益。在这段时间内，你要买卖机器，并且当机器被ACM公司拥...
2018-09-02 12:58:48
220
原创 BZOJ4518 Sdoi2016 征途 【斜率优化DP】 *
BZOJ4518 Sdoi2016 征途DescriptionPine开始了从S地到T地的征途。 从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。 Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。 Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。 帮助Pine求出...
2018-09-01 23:21:37
210
原创 BZOJ3566 SHOI2014 概率充电器 【概率DP】
BZOJ3566 SHOI2014 概率充电器Description著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器: “采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧! ” SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每...
2018-09-01 21:07:26
226
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人