5 HelloWorld10086

尚未进行身份认证

追随大神的脚步

等级
TA的排名 3k+

hdu 4403 A very hard Aoshu problem(dfs)

题意:给定一串数字,在这些数字中插入一些‘+’或者’=’使得两边相等思路:比较简单的dfs问题首先确定下等于号的位置,然后两边进行dfs。mymycodecode#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;typedeflonglongll;const

2015-09-25 15:06:47

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

简说期望类问题的解法

近年的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

hdu 5442 Favorite Donut(kmp+最小表示法)

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

2015-09-24 14:55:44

hdu 5452 Minimum Cut(树链剖分+差分前缀和)

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

2015-09-22 20:01:11

hdu 5465 Clarke and puzzle (二维树状数组+nim博弈)

解析:利用二维树状数组来区间询问异或和,以及单点更新,然后利用nim博弈的结论判断胜负。mymycodecode#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;typedeflonglongll;constintN=505;intn,m,q;structB

2015-09-22 18:30:26

hihocoder 1233 Boxes(bfs+状态压缩+hash表)

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

2015-09-22 16:36:20

hihocoder 1228 Mission Impossible 6(模拟文本编辑器)

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

2015-09-21 19:00:37

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

hdu 3016 Man Down(线段树区间更新+dp)

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

2015-09-16 16:55:25

HDU 2896 病毒侵袭(AC自动机)

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

2015-09-16 16:32:07

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

hdu 5384 Danganronpa(AC自动机)

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

2015-09-16 15:04:46

hdu 2222 Keywords Search(AC自动机)

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

2015-09-16 14:50:13

hdu 5433 Xiao Ming climbing (BFS+dp)

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

2015-09-16 14:42:59

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

hdu 5444 Elven Postman(二叉搜索树)

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

2015-09-14 18:53:41

hdu 5441 Travel(并查集+二分)

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

2015-09-13 20:04:27

hdu 5438 Ponds(线段树+dfs)

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

2015-09-13 19:26:23

HDU 1503 Advanced Fruits(LCS+输出路径)

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

2015-09-12 14:24:04

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!