- 博客(227)
- 收藏
- 关注
RSS订阅转载 HDU 5729 Rigid Frameworks (连通二分图计数DP)
参考1：http://blog.csdn.net/dpppbr/article/details/51972196参考2：https://www.johannesbader.ch/2013/09/project-euler-problem-434-rigid-graphs/[code]:#include#include#includeusing namespace std;ty
2016-07-28 10:39:34
477
原创 HDU 5735 Born Slippy (分块+树上可持久化)
官方博客讲的很清楚：点击打开链接在这里贴一下做树上可持久化的代码仅供参考。[code]:#include#include#includeusing namespace std;typedef long long LL;const int maxn = (1<<16)+5;const int sqrn = (1<<8)+5;const int MOD = 1e9+7;
2016-07-27 14:56:43
360
原创 HDU 5758 Explorer Bo (树形DP)
题目：给你一棵树，用最少的链去覆盖这棵树，求链的最小总长度。解析：num为叶子节点数，显然链数是(num+1)/2。如果是偶数，就是叶子节点到叶子节点，如果是奇数，那么就是在奇数-1情况下的树下加一条叶子到其祖先的链。偶数的情况：从一个非叶子节点出发，如果其子节点的叶子节点是偶数，则ans+=2，如果是奇数，ans+=1。奇数的情况：枚举一下那条单链所在的子树。设dp[u][i][
2016-07-27 14:46:54
990
原创 Hdu 5352 MZL's City （最小费用最大流）
解析：源点S与所有的1查询连边，容量为K，所有的查询与相关的节点连边，容量为1，图中节点1~n与T连边，容量为1，解即是最大流量。通过控制费用，越早的查询费用越大，从而获得最小字典序。[code]:#include#include#include#include//#pragma comment(linker, "/STACK:102400000,102400000")#d
2016-07-13 21:13:31
413
原创 Hdu 5351 MZL's Border (找规律+Java高精度)
解析：找到最大的i是|fib_i| [code]:import java.util.*;import java.math.*;import java.io.*;public class Main{ static BigInteger m,f[] = new BigInteger[1001],mod = BigInteger.valueOf(258280327); static
2016-07-13 21:09:23
255
原创 Hdu 5349 MZL's simple problem (水题)
解析：用一个multiset维护一下就好。[code]:#include#include#include#include#include#include#include#include#includeusing namespace std;int n;multiset ms;multiset::iterator it;void init(){ ms.
2016-07-13 21:04:33
242
原创 Hdu 5348 MZL's endless loop (构造)
解析：每找到一个单个的环，将其指定顺序后从图中出，最后会得到一个森林，对于每一棵树，从根节点开始根据出入大小指定方向即可。注意实现细节！[code]:#include#include#include#include#includeusing namespace std;typedef pair P;const int maxn = 1e5+5;const int ma
2016-07-13 21:02:32
236
原创 Hdu 5347 MZL's chemistry (打表)
[code]:#include#include#includeusing namespace std;double a[100] = {0,1312,2372.3,520.2,932,800.6,1086.5,1402.3,1313.9,1681,2080.7,495.8,737.7,577.5,786.5,1011.8,999.6,1251.2,
2016-07-13 20:59:13
224
原创 Hdu 5344 MZL's xor (杂)
解析：i!=j时(a[i]+a[j])^(a[j]+a[i]) = 0.因此只需统计2*a[i]即可。[code]:#includeusing namespace std;typedef long long LL;LL n,m,z,l;int main(){ int i,j,cas; LL value,ans; scanf("%d",&cas);
2016-07-13 20:57:57
195
原创 Hdu 5338 ZZX and Permutations（线段树+贪心）
解析：首先用set维护被Cirlcle Notation切开的不连续的各个段。然后从i开始，（p[i]为i的位置）找到其在set中的左右端点，左边的最大值为value_l，右边p[i]+1的值为value_r。若value_l>value_r，则｛p[value_l],p[value_l]+1,...,p[i] }为一个CircleNotation，并再用set维护剩下的段。若
2016-07-13 20:42:45
260
原创 Hdu 5336 XYZ and Drops（模拟）
解析：一秒一秒的来处理就好。[code]:#include#include#include#include#includeusing namespace std;const int maxn = 105;struct Node{ int x,y,sz;}a[maxn];struct Drop{ int x,y,dir,time; Drop(in
2016-07-13 20:31:20
376
原创 Hdu 5334 Virtual Participation (构造)
解析：首先找到第一个n使得n*(n+1)/2>=k，差值为x。然后看下面一个例子：28 = 1 2 3 4 5 6 727 = 1 1 3 4 5 6 726 = 1 1 3 3 4 5 625 = 1 1 1 4 5 6 724 = 1 1 1 4 4 6 723 = 1 1 1 4 4 6 622 = 1 1 1 4 4 4 721 = 1 2 3 4
2016-07-13 20:28:50
316
原创 Hdu 5328 Problem Killer (尺取)
解析：处理出公差和公比序列，然后尺取找出最大覆盖范围即可。[code]:#include#include#include#include#include#includeusing namespace std;const int maxn = 1e4+5;const double eps = 1e-6;struct Nod{ int b,next; vo
2016-07-13 20:13:05
245
原创 Hdu 5327 Olympiad （预处理）
水题，预处理一下就好[code]:#include#include#include#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1using namespace std;const int maxn = 1e5+5;int sum[maxn];bool check(int x){ int i,c[10];
2016-07-13 20:09:54
220
原创 Hdu 5326 Work(超水的树形DP)
[code]:#include#include#include#include#includeusing namespace std;const int maxn = 105;int n,m,num[maxn],deg[maxn];vector G[maxn];void init(){ int i; for(i = 1;i <= n;i++) G[i].
2016-07-10 20:38:11
252
原创 Hdu 5325 Crazy Bobo (拓扑排序)
解析：对于原树一条边(a,b)，令w[a] [code]:#include#include#include#include#includeusing namespace std;const int maxn = 5e5+5;struct Nod{ int b,next; void init(int b,int next){ this->
2016-07-10 20:36:33
288
原创 Hdu 5324 Boring Class (cdq分治)
解析：因为是最小字典序，所以从右往左DP。dp[i] = max(dp[j]+1) i =L[j],R[i]因为这是三维上的问题，自然的就能想到cdq分治了。在一个区间[l,r]内，先对[mid+1,r]递归，按L[]排序后建立一个对R的线段树，来计算[mid+1,r]的影响，再递归[l,r]。这里说的比较笼统，不过熟悉cdq分治的同学应该能立马明白我说的什么吧！[code]:
2016-07-10 20:33:45
332
原创 Hdu 5323 Solve this interesting problem（搜索）
解析：注意L/(R-L+1) [code]:#include#include#include#include#includeusing namespace std;typedef long long LL;const LL INF = 0x3f3f3f3f3f3f3f3f;LL l,r,ans;void dfs(LL l,LL r,int num){//print
2016-07-10 20:20:16
239
原创 Hdu 5319 Painter (模拟)
直接贪心去模拟就完，最坑的是那不是n*n的矩阵，m没告诉你，自己求。[code]:#include#include#include#include#includeusing namespace std;int n,m,a[55][55];char s[55][55];int dx[4] = {0,1,1,1};int dy[4] = {0,1,-1,1};void
2016-07-10 20:14:37
331
原创 Hdu 5318 The Goddess Of The Moon （dp+矩阵快速幂）
解析：dp[i][j]表示前 i 个数，以 第 j 个数结尾的方案数。因为每一层的转移都是相同的，所以处理出一个转移矩阵，通过快速幂即可快速求得结果。[code]:#include#include#include#include#includeusing namespace std;typedef long long LL;const LL INF = 0x3f3f3f3f
2016-07-10 20:09:59
293
原创 Hdu 5317 RGCDQ (dp+预处理)
解析：F(x)的最大值是7，直接通过dp统计各个值的前缀和即可。[code]:#include#include#include#include#includeusing namespace std;const int maxn = 1e6+5;int dp[maxn][9];int divide(int n){ int i,j,ans = 0; for
2016-07-10 20:06:29
219
原创 Hdu 5316 Magician （线段树区间合并）
解析：关键是处理奇偶的问题。正如官方题解所说，本题的子序列实际上可以根据起始数值下标的奇偶性分为四类。对于每一类，如果你熟悉线段树，那么可以看出这个问题是可以进行区间合并的。即如果知道一个区间[L, R]两个子区间 [L,mid], [mid+1,R]的信息，我们可以推出[L,R][L,R]的信息。维护四个值，表示起点终点的下标的奇偶性。[code]:#include#i
2016-07-10 20:02:19
244
原创 HDU 5308 I Wanna Become A 24-Point Master (暴力枚举+构造)
题意：let A be an array with 2n−1 numbers and at firsrt Ai=n (1≤i≤n). You need to print n−1 lines and the ith line contains one integer a, one char b and then one integer c, where 1≤a,c<n+i and b is "+
2016-07-09 09:34:10
343
转载 HDU 5302 Connect the Graph (构造)
原题解链接：http://www.cnblogs.com/shjwudp/p/4719279.html[code]:#include#include#include#includeusing namespace std;typedef pair P;int w[3],b[3],n;vector G[2];void init(){ G[0].clear();
2016-07-09 09:20:24
217
原创 HDU 5301 Buildings (乱搞)
解析：首先使得矩阵的n[code]:include#include#include#include#includeusing namespace std;int n,m,x,y;int main(){ int i,j,cas,u,v; while(~scanf("%d%d%d%d",&n,&m,&x,&y)){ if(n > m){
2016-07-09 09:14:58
206
原创 Codeforces 689E Mike and Geometry Problem(离散化+懒标记)
题意：给出n个线段[li,ri]，求任意k个线段所共同覆盖的点的总和。解析：对于每一条线段，区间[li,ri]加一，如果一个位置的值为m，那么最后的结果ans += C(m,k);如果只是离散化端点的话，没法求得中间部分被覆盖的点，所以在离散化时保证相邻两点中间留出一个1，对于中间的点，求出当前的值*(相邻两点实际距离-1)即是结果。[code]:#include#inclu
2016-07-09 09:03:10
407
原创 Codeforces 689D Friends and Subsequences(RMQ+二分)
题意：大小为n的序列a和b中，求(l,r)的个数，使得max(a[l..r]) = min(b[l...r])。解析：在固定l后，随着r的增加，max(a[l..r]) - min(b[l...r])是不减的。所以可以通过二分求得max(a[l..r]) = min(b[l...r])的两个边界。[code]:#include#include#include#includeu
2016-07-09 08:52:54
620
原创 HDU 5297 Y sequencew(容斥+收敛迭代）
题目：从1开始的无限长正整数序列(1,2,3,4,5,...)，剖去所有可以写成a^b的数(2解析：首先对于每一个r处理出对应容斥的数字，用vector记录下来以降低复杂度。开始的时候同样像的是二分，超时……看了一篇题解后，考虑序列的性质，向前迭代时是不断收敛的。（具体看代码）[code]:#include#include#include#include#include#
2016-07-06 10:25:23
254
原创 HDU 5296 Annoying problem （树状数组+dfs序+倍增）
题意：一颗n节点的带权无向树，一个初始为空的集合S，有两种操作：1 x 如果S中没有x，加入x ；2 x 如果S中存在x，删除x。每次操作完后求出使S集合连通的最小边权和。解析：设root为S集合的LCA。点i的左右时间戳为L[i],R[i]，ans为当前的权重和。当前集合S中添加节点x，如果x不在root的子树中，那么ans += dis[x]+dis[root]-2*dis[lca(x
2016-07-06 10:15:30
318
原创 HDU 5293 Tree chain problem（树形DP+树链剖分）
题意：一颗n节点树上有m条链，每条链有权重，求一个链的集合使权重和最大且两两不相交。解析：令dp[i]为以i为根的子树的最大权重和。如果i不在链上，则有dp[i] = sigma(dp[k]) k为i的子节点如果i在某一条链(u,v,w)上，那么dp[i] = w + sigma(dp[k]) k为链上所有节点的子节点。对于该值，我们可以统计统计链上节点的所有子节点dp的和 - 链上节
2016-07-06 09:55:18
370
原创 HDU 5289 Assignment (尺取+Set)
题意：n个数字中取出连续的一组数字使得任意两个差小于k，求方案数。解析：two points，用multiset维护一下区间差值即可。[code]:#include#include#includeusing namespace std;typedef long long LL;const int maxn = 1e5+5;int n,m;LL a[maxn];mul
2016-07-06 08:32:27
232
原创 HDU 5288 OO’s Sequence (数论)
题意：定义一个函数f(l,r) = i的个数使得在区间[l,r]中不存在a[i]%a[j]=0。∑i=1..n∑j=i..n f(i,j) mod （10^9+7）。解析：通过枚举因子，从前到后再从后到前求出能包含i的区间的左右端点的边界，即可。[code]:#include#include#includeusing namespace std;typedef long l
2016-07-06 08:27:20
188
原创 Codeforces 659F Polycarp and Hay (排序+并查集)
解析：将所有的cell按高度从大到小排序，然后每次放入值相同的cell，用并查集维护集合和集合大小，并判断是否满足条件即可。找到后搜索标记所有的位置。[code]:#include#include#include#include#include#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define lowbit
2016-06-01 11:37:26
353
原创 Codeforces 645E Intellectual Inquiry (贪心+DP)
解析：假设当前已经放了i个字符，c[p]为当前以p结尾的字符串的个数，sum = c[0] + .... c[25]。在放入第i+1个字符后，应该使sum尽可能大。假设放入的是字符t，那么新的c[t]的值为sum+1（所有串+自己），sum的变化量为1+sum-c[t]。找到最大的变化量，进行更新即可。但是这里有取模的操作，没法求出最大的变化量。所以，贪心的思考，使得变化量最大的那
2016-06-01 11:32:47
322
原创 Codeforces 625D Finals in arithmetic(构造)
解析：k位的数字n可能是有k位的a得来也可能由k-1位的a得来。先将n视为字符串s[1....k]以a是k位为例，设p为进位，l,r为左右端点起始l = 1,r = n,p = 0若p = 0,s[l..r] = a...b 那么a[r]+a[l] = b，再将a与b做差，差值只能为0和1，如果是其他值，则不能形成，如果是0，说明a[l+1]+a[r-1] 若p = 1,s[l
2016-05-31 16:41:55
475
原创 Codeforces 650C Table Compression (并查集+拓扑排序)
解析：不看tags都意识不到用图论。一个位置对应一个节点，对于每行每列，值相同的用并查集union一起，值不相同的，值小的节点指向值大的节点。压缩后节点的值是到该节点的最长的链的长度，可以通过拓扑排序求得。[code]:#include#include#include#includeusing namespace std;const int maxn = 1e6
2016-05-31 16:14:30
286
原创 Codeforces 637D Running with Obstacles (贪心)
解析：查看每对相邻的障碍，如果距离大于s，那么可以落地并在下一个障碍前起跳。对每次落地和起跳加以判断即可。[code]:#includeusing namespace std;typedef long long LL;const LL MOD = 1e9+7;int n,m,a[205];LL dp[2][205][1005];void sol(){ int i,
2016-05-31 15:55:19
304
原创 Codeforces 626F Group Projects (DP)
官方题解很详细This is a dynamic programming problem. Notice that the total imbalance of the groups only depends on which students are the maximum in each group and which are the minimum in each group.
2016-05-31 15:50:22
521
原创 CodeForce 626E Simple Skewness (贪心+三分)
题目：给出n个数字，求出一个子集，使得其平均数与中位数的差值最大。解析：首先将a[1...n]从大到小排序，在固定中位数的位置后，子集的构成必然是在中位数位置的两侧选取相同个，显然，每侧要尽量选取较大的值。可以发现，选取的个数与平均数具有凸函数性质，所以通过三分找到临界点。整体复杂度O(nlogn)。[code]:#includeusing namespace std;co
2016-05-31 10:47:46
271
原创 CodeForces 659G Fence Divercity (DP)
解析：设dp[i][j]为考虑前i个Fence，cut的部分包含第i个Fence，第i个Fence处理后的高度为j的方案数。则首先 1如果j反之，dp[i][j] = 1;得到转移方程后显然不能直接用，因为空间和时间都特别大，但是我们注意到，对于每一个i，我们只需要维护3个前缀和就可以完成方程的转移。设s[i][j] = dp[i][1]+dp[i][2]+...+dp[i][
2016-05-31 10:40:50
343
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人