HelloWorld10086-CSDN博客

原创【索引】AOAPC I: Beginning Algorithm Contests (Rujia Liu)

AOAPC I: Beginning Algorithm Contests (Rujia Liu)Volume 0. Getting StartedVolume 1. Elementary Problem SolvingVolume 2. Data StructuresVolume 3. Brute ForceVolume 4. Algorithm DesignVolume 5. Dy

2014-08-15 10:58:30 1225

原创 hdu 4403 A very hard Aoshu problem（dfs）

题意：给定一串数字，在这些数字中插入一些‘+’或者’=’ 使得两边相等思路：比较简单的dfs问题首先确定下等于号的位置，然后两边进行dfs。mymy codecode#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const

2015-09-25 15:06:47 905

原创 hdu 4407 SUM（容斥原理）

题意：有一个元素为 1~n 的数列AnA_n，有2种操作（最多1000次）： 1. 求某段区间 [a,b][a,b] 中与 pp 互质的数的和。 2. 将数列中某个位置元素的值改变。解析：刚刚开始的时候想成线段树了，看了题解才明白是用容斥原理来做。对于操作1，解的性质满足区间减法，则我们只需要考虑如何求 [1,n][1,n] 中与 pp 互质的数的和即可。由

2015-09-25 14:59:25 866

转载简说期望类问题的解法

近年的acm竞赛中，数学期望问题常有涉及，在以前也常让本人感到很头疼，近来突然开窍，掌握了基本的分析方法，希望对大家有帮助。写得浅薄，可能数学上不够严谨，只供理解。首先，来看下期望有啥基本的公式。对离散型随机变量x，其概率为p，有 E(x)=∑ipixiE(x)=\sum _{ i }^{ }{ { p }_{ i }{ x }_{ i } } 对随机变量A、B有 E(αA±βB)=αE(A)

2015-09-24 17:40:56 2644

原创 hdu 5442 Favorite Donut（kmp+最小表示法）

题意：有一个lenlen长度的环，问有没有字典序最大长度为lenlen的串在这个环里。如果有的话，且只有一个，输出其开头的下标（下标从1 开始）再输出0表示顺时针（从左至右），1 表示逆时针（从右至左）如果多个，输出开头下标最小的那个。如果顺时针，逆时针的字典序一样，且开头下标一样，优先输出输出顺时针。解析：参考了别人的题解，用最小表示法来做。循环字符

2015-09-24 14:55:44 794

原创 hdu 5452 Minimum Cut（树链剖分+差分前缀和）

题意：给一个无向图和它的一个生成树，要求找到一个最小割，使得有且只有一条生成树上的一条边属于割集。解析：因为生成树中只有一条边属于割集，那么割对生成树来说只是分成了两个子树，那么就考虑割生成树上割哪条边是最优的。首先对生成树进行建树剖，对于每条非树边的两个端点u和v，对 u –> v 在生成树上的简单路径上的边权值加一，最后找到所有边权值最小的边，就是属于最小割的边。

2015-09-22 20:01:11 1140

原创 hdu 5465 Clarke and puzzle （二维树状数组+nim博弈）

解析：利用二维树状数组来区间询问异或和，以及单点更新，然后利用nim博弈的结论判断胜负。mymy codecode#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N = 505;int n, m, q;struct B

2015-09-22 18:30:26 787

原创 hihocoder 1233 Boxes（bfs+状态压缩+hash表）

题意：有n个卡槽，放有体积不同的n个空盒子，每次你可以移动一个空盒子到相邻卡槽，但前提是相邻卡槽若已经有空盒子，那么要移动的空盒子体积必须小于已有的空盒子，问要移动多少步才能使得从左到右，每个卡槽空盒子的体积递增。解析：状态压缩，用一个longlong longlong的状态表示当前所有的状态，每个盘子所在的位置，每个盘子的位置用77位二进制表示，总共的状态为2472^{47}，因为每

2015-09-22 16:36:20 684

原创 hihocoder 1228 Mission Impossible 6（模拟文本编辑器）

题意：题目定义了几种操作： L:光标左移，假如已经在最左边则不动 R:光标右移动，假如已经在右边则不动 S:切换模式，先是插入模式，后是覆盖模式 D:删除右边, 或者删除位置C-D B:删除左边 C:复制位置C-C。且两个CC之间不能够存在除L,R以外的字符 V:粘贴，是覆盖模式那么把当前剪切板的内容，从当前光标的位置开始进行覆盖

2015-09-21 19:00:37 1045 2

原创 CodeForces 578C Weakness and Poorness（三分法+最大子段和）

题意：题目定义了两个变量： poornesspoorness表示一个区间内和的绝对值。 weaknessweakness表示一个所有区间最大的poornesss 题目要求你求一个xx使得 a1 − x, a2 − x, ..., an − xa_1 - x, a_2 - x, ..., a_n - x这个序列的weaknessweakness最小输出最小的wea

2015-09-19 10:17:56 1590

原创 hdu 3016 Man Down（线段树区间更新+dp）

题意：是男人就下100层相信很多人都玩过，这题就是简单的模拟这个游戏。有nn块木板，每块木板有4个属性，高h(h>0)，左边界，右边界，以及掉落在它上面，获得多少生命值，一个人从最高的木板开始往下跳，初始时生命值为100，问最后掉落到地面能获得的生命值最多为多少（如果途中生命值为≤0，那么这个人会死去），如果无法跳到地面，输出-1。解析：既然只能垂直下落，而且是落在最近的板上，

2015-09-16 16:55:25 830

原创 HDU 2896 病毒侵袭（AC自动机）

题意：给定几个模式串，看是否出现在主串中，如果出现在主串，输出这些模式串的标号。解析： AC自动机裸题。用所给的模式串构建AC自动机，然后用主串去匹配。将匹配到的结果插入set中，最后输出set。mymy codecode#include <cstdio>#include <cstring>#include <algorithm>#include <queue>

2015-09-16 16:32:07 492

原创 hdu 3037 Saving Beans（lucas定理模板）

题意：求在n棵树上摘不超过m颗豆子的方案，结果对p取模。解析：题目可以转换成 x1+x2+……+xn=mx_1+x_2+……+x_n=m 有多少组解，m在题中可以取0~m。利用插板法可以得出 x1+x2+……+xn=mx_1+x_2+……+x_n=m 解的个数为Cn−1n+m−1=Cmn+m−1C_{n+m-1}^{n-1}=C_{n+m-1}^m；则题

2015-09-16 15:19:04 1349

原创 hdu 5384 Danganronpa（AC自动机）

题意： f(A,B)表示：B在A中作为子串出现的次数。题目给出n个证据，m个子弹 Ai是证据，Bi是子弹，题目问：所有Bi对每个Ai造成的伤害是多少，即每个Bi在Ai中出现的次数总和。解析：记得当时多校比赛的时候，我不会AC自动机，用字典树水了一发，没想到过了，昨晚学习了一下AC自动机，再来做这题，发现简直就是AC自动机的水题。mymy codecode#includ

2015-09-16 15:04:46 584

原创 hdu 2222 Keywords Search（AC自动机）

题意：给你很多个单词，然后给你一篇文章，问给出的单词在文章中出现的次数。解析：直接套用AC自动机的模板。注意：每个单词在目标串中出现的话，只能记为一次。mymy codecode#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;cons

2015-09-16 14:50:13 477

原创 hdu 5433 Xiao Ming climbing （BFS+dp）

题意：小明因为受到大魔王的诅咒，被困到了一座荒无人烟的山上并无法脱离。这座山很奇怪: 这座山的底面是矩形的，而且矩形的每一小块都有一个特定的坐标(x,y)(x,y)和一个高度HH。为了逃离这座山，小明必须找到大魔王，并消灭它以消除诅咒。小明一开始有一个斗志值kk，如果斗志为0则无法与大魔王战斗，也就意味着失败。小明每一步都能从他现在的位置走到他的(N,E,S,W)

2015-09-16 14:42:59 626

原创 hdu 5446 Unknown Treasure（Lucas定理+中国剩余定理）

题意：求C(n,m)%(∏pi)C(n, m) \% (∏p_i)。pip_i小于10510^5，mm，nn，以及答案都是101810^{18}。解析：先使用LucasLucas定理求出对于每个pip_i，C(n,m)%piC(n, m) \% p_i的值。再使用中国剩余定理对模数和余数求解即可。证明：令 total=∏pitotal = ∏p_i，X=Cmn%(∏pi)X = C_n^m \%

2015-09-14 21:10:18 1331 1

原创 hdu 5444 Elven Postman（二叉搜索树）

题意：给出一颗二叉树的先序遍历，默认的中序遍历是1、2……n。给出q个询问，询问从根节点出发到某个点的路径。解析：就是构建一棵二叉搜索树，然后在二叉搜索树上面查找要查询的值，并输出路径。mymy codecode#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const in

2015-09-14 18:53:41 682

原创 hdu 5441 Travel（并查集+二分）

题意：一个nn个点的无向图，给出m条边的边权，给出q次询问，每次给出一个值，求用到所有边权不大于这个值的边的情况下，能够互相到达的点对的个数。解析：首先我们对边按照边权从小到大排序。构造一个前缀和数组sum[n]sum[n]，表示添加到第nn条边，有多小条能互相到达的点对数。还有一个要注意的是每增加一个联通块，假如联通块的个数为nn，那么增加的点对数为C2n∗2C_n^

2015-09-13 20:04:27 671

原创 hdu 5438 Ponds（线段树+dfs）

题意：有n个点，m条边，每个点都有权值。然后开始删除点，删点规则是如果这个点连接其他点的数量小于2，那么这个点可以删除。如果删除了某些点产生了其他可删除的点也将其删除。直到删除到不能为止。问最后剩余的联通块中，点的数量是奇数的联通块中的点的权值和是多少。解析：先算出所有点的度数，然后把这些度数存入线段树中，每次询问线段树找到等于最小的度数的节点，把和该最小度数的

2015-09-13 19:26:23 615

原创 HDU 1503 Advanced Fruits（LCS+输出路径）

题意：将两个字符串结合起来，他们的公共子串只输出一次解析：先做一遍LCS，然后记录下路径，然后把是LCS路径上面的点用两个标记数组分别标记一下，然后没有被标记过的位置分别输出，如果被标记过的位置，那么表示那个位置是相同的字符，这个位置只要输出一次。mymy codecode#include <cstdio>#include <cstring>#include <algorithm

2015-09-12 14:24:04 756

原创 HDU 1828 Picture（矩形周长的并+扫描线+离散化）

题意：求N个矩形周长的并。解析：矩形周长的并会比面积并难一些，但是理解之后发现也不是很难。参考这篇题解先离散化xx坐标，按yy从下到上扫描。统计每次加入一条扫描线总和的增加值，总和增加值 = 横向边增加的长度 + 纵向边增加的长度 prepre表示之前加入横向边时的长度，sum[1]sum[1]是利用线段树维护的当前横边的长度。这样可以

2015-09-09 16:42:28 696

原创 CodeForces 343D Water Tree（dfs序+线段树区间更新）

题意：给定一棵树，以及定义了3个操作1、把v点及其子树灌上水 2、把v点及v到根的路径去掉水 3、询问v点是否有水解析：先对这棵树做一遍dfs序，把树转成dfs_clock，这样每个点就可以对其子树进行区间更新。那么对于点v 出现的时间in[v]和消失的时间out[v] ，一定会把v子树下所有节点都夹在[in[v], out[v]]之中。对于操作1，就是把 [in[v], out[v]]改成1对

2015-09-08 21:35:05 588 2

原创 ZOJ 3724 Delivery（树状数组+离线处理）

题意：N个点，对于每个点i，都有一条连向i+1的有向边，另外有M条其他的有向边（姑且称作小道边），有Q个询问(u,v)(u,v)求uu到vv的最短路。解析：这题真的是思考了好久，也参考了很多大牛的博客，终于把这题给过了。这题让我理解到了，原来树状数组也可以维护最大值和最小值，真的是长见识了。以下解析，可能是这题网络上最详细的讲解了。刚一看感觉是最短路的题，但是再一想，有 n−1n-1 条有向边，

2015-09-08 21:03:44 523

原创 CodeForces 46D Parking Lot（线段树区间合并）

题意：有一条长度为L的街道，有N个操作，现在有两种操作： (1)”1 a”，表示有一辆长度为a的车开进来想找停车位；停车位必须满足与它前面的车距离至少为b，与后面的车距离至少为f；如果能找到这样的停车位，输出这辆车的起始位置（且这个位置最小），否则输出-1; (2)”2 a”，表示第a个事件里进来停车的那辆车开出去了; 解析：这题和POJ 3677 Hot

2015-09-07 19:24:58 833

原创 HDU 1540 Tunnel Warfare（线段树区间合并）

题意：题目定义了3种操作 D代表破坏村庄， R代表修复最后被破坏的那个村庄， Q代表询问包括x在内的最大连续区间是多少思路：和前面几道线段树的区间合并一样，在线段树的区间内，我们要用三个变量记录左边连续区间，右边连续区间和最大连续区间。这题主要的难点是怎么查询。我的查询函数是这么写的。int query(int o, int L, int R, in

2015-09-07 11:24:49 499

原创 HDU 2871 Memory Control（线段树区间合并+二分）

题意：模拟一个内存分配机制。 Reset：重置，释放所有空间 New x：申请内存为x的空间，输出左地址 Free x：释放地址x所在的内存块 Get x：查询第x个内存块，输出左地址解析：可以用一个vector来记录所有的内存块的区间。 New x操作可以利用如同POJ3667POJ 3667中的query操作查找到最右边的位置。然后把找到的区间二分插入

2015-09-06 18:58:43 430

原创 POJ 3667 Hotel（线段树区间合并）

题意：一家旅馆有N（1 ≤ N ≤ 50000）间房间，并且所有的房间都是连续排列在同一边，现在每个观光团需要入住房间，要求房间的编号为连续的r...r+Di−1r...r+D_i-1，并且r是最小的；参观者同样可能退房，并且他们每次退房都是编号为Xi...Xi+Di−1X_i...X_i +D_i-1 (1≤Xi≤N−Di+1)(1 ≤X_i ≤N-D_i+1)的房间。现在有

2015-09-06 10:05:19 473

原创 hdu 5430 Reflect（欧拉函数）

题意：从镜面材质的圆上一点发出一道光线反射N次后首次回到起点。问本质不同的发射的方案数。解析：mymy codecode#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = (int)1e6 + 5;int phi[N], n;void phi_t

2015-09-06 09:43:34 482

原创 hdu 5429 Geometric Progression（java 高精度+java输入外挂）

题意：给一个序列判断其是否是等比数列，每个数字A[i]不小于100位解析：（1）存在0的时候要全都是0,才能是Yes，存在0但不全是0则是No （2）不存在0，则A[i-1]*A[i+1]==A[i]*A[i]是否全都成立mymy codecodeimport java.math.*;import java.io.*;import java.util.*;class Inp

2015-09-06 09:31:19 574

原创 hdu 5428 The Factor（分解质因子）

题意：给一个序列，设所有项乘积为a，求a的因子中因子个数大于2的最小因子。解析：将每个数分解质因子，记录每个质因子的个数。然后从最小的质因子开始取（累乘），直到取够两个（因为1和其本身也是该数的因子），此时得到的结果就是满足条件的最小因子。mymy codecode#include <cstdio>#include <cstring>#include <algorithm

2015-09-06 09:26:19 713

原创 hdu 5023 A Corrupt Mayor's Performance Art（线段树区间合并）

题意：刚刚开始的时候所有的片段上的颜色都是2。在片段上着色，有两种操作，如下：第一种：P a b c 把 a 片段至 b 片段的颜色都变为 c 。第二种：Q a b 询问 a 片段至 b 片段有哪些颜色，把这些颜色按从小到大的编号输入，不要有重复。解析：很简单的线段树区间合并问题。对于1操作，可以利用线段树进行区间覆盖。对于2操作，每查询到一个有

2015-09-03 21:03:35 596

原创 HDU 4777 Rabbit Kingdom（树状数组+离线处理+尺取法）

题意：给你n个数，有m个查询，问区间[L,R]之间有多少个数与这个区间内的其他数都互质。解析：很显然，[L,R][L,R]区间内的答案就是一个区间内的数的个数，减去与其他数不互质的数即可，即离当前数 aia_i 左边最近的不互质的数的位置（设为L[i]）和右边最近的不互质的数的位置（设为R[i]）有一个在区间[L,R][L,R]内。那么问题就变成统计： (1) 区间[

2015-09-02 20:53:14 771

原创 hdu 4747 Mex（线段树区间更新+二分）

题目：给出一个序列，mex{}表示集合中没有出现的最小的自然数。然后求∑mex(i,j)\sum{mex (i , j)}。解析：思路转载自 cxlove 考虑左端点固定时的所有区间的mex值，这个序列是一个非递减序列，这点首先要明白。初始时，先求出mex[j]表示mex(1, j)。（可以用map求出）对于每一个左端点i，就是一个区间求和。（可以利用线段树维

2015-09-02 11:02:02 671

原创 hdu 4614 Vases and Flowers（线段树区间更新+二分）

题意：给你N个花瓶，花瓶的编号是从 0 到 N - 1，初始状态花瓶是空的，每个花瓶最多只能插一朵花。然后有2个操作：操作1 a b，往在a位置后面（包括a）插b朵花，输出插入的首位置和末位置。操作2 a b，输出区间[a,b][a , b]范围内的花的数量，然后全部清空。解析：很显然这是一道线段树的题目。区间更新，区间求和，这些基本的操作线段树都可以O(l

2015-09-01 17:37:02 472

原创 hdu 5423 Rikka with Tree（dfs）

解析：显然一棵树是独特的当且仅当任意处于每一个深度的点数是”1 1 1 1 … 1 1 x”。所以直接DFS一下求出每一个点到根的距离然后判断一下就好了。mymy codecode#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define pb push_backusing nam

2015-08-31 21:12:39 426

原创 HDU 4455 Substrings（dp+树状数组优化）

题意：给定一个序列ai，个数为n。再给出一系列w；对于每个w，求序列中，所有长度为w的连续子串中的权值和，子串权值为子串中不同数的个数解析：一直想不出来怎么转移，看了网络上面的题解才明白怎么做。 dp[i]dp[i]表示w=iw=i时所求的答案。 dp[1]=ndp[1]=n，这个很容易知道，dp[2]dp[2]中的子串就是删去dp[1]dp[1]中最后一个子串，再令每个子串加上其之后

2015-08-31 21:07:10 515

原创 hdu 5424 Rikka with Graph II（n个点n条边的汉弥尔顿路径判定）

解析：（转自这篇博客）：给一个n条边，n个顶点的图，判定是否存在哈密顿路。如果存在哈密顿路，此时路径中含有n-1条边，剩下的那一条要么是自环（这里不予考虑，因为哈密顿路必然不经过），要么连接任意两个点。不考虑自环，此时图中的点度数为1的个数必然不超过2个，有如下三种情况： 1、剩下的那条边连接起点和终点，此时所有点度数都是2，可以从任意一个顶点开始进行DFS，看能否找到哈密顿

2015-08-31 19:39:15 763

原创 Codeforces Round #318（ABCD）

A题意：每次操作可以让第一个数字加1，第一个数字之后的数字减1，问你最少变换多少可以使得第一个数字大于后面所有数字。解析：先保存下所有的数字，以及该数字出现的个数。直接用map，每次取得map中最大的数字让这个数字的个数减去1，再把a[0]加一，在把这个最大的数字减去1，存入map中，直至a[0]大于所有的数字，输出最少的操作次数。mymy codecode#include

2015-08-31 19:32:05 478

原创 HDU 3397 Sequence operation（线段树区间合并）

题意： 0 a b将区间[a,b]所有数全部变成0 1 a b将区间[a,b]所有数全部变成1 2 a b将区间[a,b]中所有数0 1互换，0变1，1变0 3 a b输出区间[a,b]中1的个数 4 a b输出区间[a,b]中最长连续1的个数解析：涉及到线段树的多种操作。 mxL[0]表示左边最长连续0的个数 mxR[0]表示右边最长连续0的个数

2015-08-30 14:56:12 522