_傲寒-CSDN博客

原创【hdu4652】Dice 期望dp 推公式

Dice 题目描述题目传送门一个骰子有 mmm 面，现在要求掷出如下情形的期望次数：连续 nnn 次结果都相同连续 nnn 次结果都不同数据范围： n≤m≤106n \le m \le 10^6n≤m≤106 题解没啥好说的= =就推推公式问题1 f(0)=1+f(1)f(i)=1+1mf(i+1)+m−1mf(1)=1m+1mf(i+1)+(1−1m)f(0)(i=0,1,.....

2018-10-03 10:21:20 194

原创【hdu1055】【贪心】color a tree

Color a tree 题目描述给一棵nnn个点的树，每个点有一个点权cicic_i，求一长度为nnn的排列ppp，最小化 S=∑i=1nicpiS=∑i=1nicpi S=\sum_{i=1}^nic_{p_i} 题解设没有染色的点的集合是V0V0V_0，V0V0V_0中当前可以染色的点（即根节点）的集合为V1V1V_1。设uuu为V0V0V_0中点权最大的点，即cu=...

2018-08-16 12:47:16 217

原创【BZOJ1095】【ZJOI2007】捉迷藏括号序列+线段树维护

原题链接 1095: [ZJOI2007]Hide 捉迷藏 Time Limit: 40 Sec Memory Limit: 162 MB Submit: 2109 Solved: 868 [Submit][Status][Discuss] Description 捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决

2016-03-13 19:56:36 2316 1

原创【BZOJ3326】数数数学题

3326: [Scoi2013]数数Time Limit: 1 Sec Memory Limit: 64 MB DescriptionFish 是一条生活在海里的鱼，有一天他很无聊，就开始数数玩。他数数玩的具体规则是： 1. 确定数数的进制B 2. 确定一个数数的区间[L, R] 3. 对于[L, R] 间的每一个数，把该数视为一个字符串，列出该字符串的每一个（连续的）子串对应的B进制

2016-02-16 14:26:40 1480 4

原创【BZOJ1556】墓地秘密 DP

Description费尽周折，终于将众将士的残骸运送到了KD军事基地地底层的大型墓地入口。KD的伙伴和战友们都参加了这次重大的送葬仪式。右边是一扇敞开的大门，进去便是墓地了，左边是一堵凹进去的墙，没有什么特别的地方。部队缓缓进入右边的门，一切。。。就这么结束了么。。。。。此时， F却没有跟上队伍，在一般MM都会有的强烈的第六感之下，她来到了左边这堵墙前一探究竟。扫去了重重的灰尘之后，墙上一块凹

2016-02-13 15:08:48 776

原创【LA7402】colorful tree 数据结构

As we all know, frogs live on trees and have different colors. N frogs are living on a tree. The tree consists of N nodes with node 1 as the root, each frog occupies a node. Frogs have different col

2016-02-12 14:32:24 2059

原创【uva12345】dynamic len 树状数组套线段树

原题传送门 In python, we can use len(start(a[L:R])) to calculate the number of distinct values of elements a[L], a[L + 1], … , a[R − 1]. Here are some interactive examples that may help you understand ho

2016-02-11 14:58:48 1453

原创【BZOJ3110】【ZJOI2013】K大数查询

3110: [Zjoi2013]K大数查询Time Limit: 20 Sec Memory Limit: 512 MB Description有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c 如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。Input第一行N，M 接下来M行，每行形如1 a

2016-02-10 21:42:41 1640 3

原创【BZOJ2759】一道动态树的好题

2759: 一个动态树好题Time Limit: 10 Sec Memory Limit: 128 MB Description有N个未知数x[1..n]和N个等式组成的同余方程组： x[i]=k[i]*x[p[i]]+b[i] mod 10007 其中，k[i],b[i],x[i]∈[0,10007)∩Z 你要应付Q个事务，每个是两种情况之一：一.询问当前x[a]的解 A a 无

2016-02-10 12:06:18 2230 1

原创【BZOJ1367】sequence

1367: [Baltic2004]sequenceTime Limit: 20 Sec Memory Limit: 64 MB Description Input Output一个整数R Sample Input794820141518 Sample Output13 HINT所求的Z序列为6,7,8,13,14,15,18. R=13 为了方便，我们先解决所求数列不递减的情况。

2016-02-08 21:35:56 626

原创【BZOJ1833】【ZJOI2010】count 数字统计

1833: [ZJOI2010]count 数字计数Time Limit: 3 Sec Memory Limit: 64 MB Description给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。 Input输入文件中仅包含一行两个整数a、b，含义如上所述。 Output输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。 S

2016-02-05 17:52:08 1980 1

原创【BZOJ3290】花神的数论题

3209: 花神的数论题Time Limit: 10 Sec Memory Limit: 128 MB Description背景众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。描述话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。花神的题目是这样的设 sum(i) 表示 i 的二进制表示中 1 的个数。给

2016-02-05 15:36:15 587

原创【BZOJ4370】【IOI2015】horses 数据结构平衡树+线段树

4370: [IOI2015]horses马Time Limit: 30 Sec Memory Limit: 1500 MB Description像他的祖先一样，Mansur喜欢繁殖马匹。目前，他拥有哈萨克斯坦最大的马场。以前情况可不是这样，N年前Mansur年轻时，他只拥有一匹马，但他一直梦想着成为富豪，最终,他美梦成真。按照时间的先后顺序将年份编号为0到N-1（即N-1年是最近的一年）

2016-02-04 23:23:55 1218

1009: [HNOI2008]GT考试Time Limit: 1 Sec Memory Limit: 162 MB阿申准备报名参加GT考试，准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2…Am(0<=Ai<=9)有M位，不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为0Input第一行输入N,M,K.接

2016-02-02 22:25:59 715

原创【BZOJ2002】弹飞绵羊

第一道LCT，纪念一下~#include<iostream> #include<cstdio> #define maxn 200000 using namespace std; int n; int ch[maxn+10][2],fa[maxn+10],sz[maxn+10]; int rc(int f,int o){return ch[f][1]==o;} void pushup(int o){

2015-11-18 19:35:56 321

原创【NOIP2015】【BZOJ4326】运输计划

4326: NOIP2015 运输计划Time Limit: 20 Sec Memory Limit: 128 MB Submit: 30 Solved: 18 [Submit][Status][Discuss] Description公元 2044 年，人类进入了宇宙纪元。L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星

2015-11-11 09:35:37 5927 1

原创 color a tree【hdu1055】【POJ2054】贪心

POJ链接 hdu链接 Color a TreeProblem Description Bob is very interested in the data structure of a tree. A tree is a directed graph in which a special node is singled out, called the “root” of the tree,

2015-10-29 10:10:05 665

原创游戏【SCOI2009】【BZOJ1025】递推

原题链接 1025: [SCOI2009]游戏Time Limit: 1 Sec Memory Limit: 162 MB Submit: 1636 Solved: 1035 [Submit][Status][Discuss] Descriptionwindy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排

2015-10-27 16:48:31 435

原创【BZOJ1037】【ZJOI2008】生日聚会Party 递推

原题链接 1037: [ZJOI2008]生日聚会PartyTime Limit: 10 Sec Memory Limit: 162 MB Submit: 1707 Solved: 1015 [Submit][Status][Discuss] Description今天是hidadz小朋友的生日，她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中，打算坐成一排玩

2015-10-21 12:52:37 1195

原创【BZOJ1064】【NOI2008】假面舞会

原题链接 1064: [Noi2008]假面舞会Time Limit: 10 Sec Memory Limit: 162 MB Submit: 1239 Solved: 612 [Submit][Status][Discuss] Description一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己

2015-10-11 22:33:07 355

原创【hdu4427】【zoj3662】math magic 背包+厉害的优化

zoj链接 hdu链接 Math Magic Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1653 Accepted Submission(s): 550Problem Description Yesterday, my

2015-10-09 21:49:58 452

原创【BZOJ1044】【HAOI2008】木棍分割动态规划

原题链接题意：有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果mod 10007。数据范围 n<=50000, 0<=m<=min(n-1,1000). 1<=Li<=100

2015-09-16 15:18:20 431

原创【UVA10537】最短路 dijkstra算法

原题链接题目大意：点有城镇和村庄两种，经过城镇时收取身上百分之五的货物的过路费（向上取整），经过村庄时只收取一个单位的过路费，问从某一点出发且到达指定终点时，身上至少携带指定数量的货物，问出发时至少带多少货物。思路：从终点开始倒推，村庄比较好办，城镇比较麻烦，要解一个含整除的方程，博主使用的是二分法……如果有更好的方法还请指教。详情见代码。#include<iostream> #includ

2015-09-14 20:06:59 422

原创【NOI2005】【BZOJ1149】【vijos1834】瑰丽的华尔兹

题目链接：https://vijos.org/p/1834 http://www.lydsy.com/JudgeOnline/problem.php?id=1499 描述你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼·布德曼·T.D.·柠

2015-09-11 19:20:24 479

原创【SCOI2009】【BZOJ1026】windy数

点击前往BZOJ原题 1026: [SCOI2009]windy数Time Limit: 1 Sec Memory Limit: 162 MB Submit: 4078 Solved: 1827 [Submit][Status][Discuss] Descriptionwindy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在

2015-09-11 19:14:20 334

原创【UVA1146】NOW OR LATER 2-SAT问题

题目大意：有n架飞机需要着陆。每架飞机都可以选择“早着陆”和“晚着陆”两种方式之一，且必须选择一种。第i架飞机的早着陆时间为Ei，晚着陆时间为Li,不得在其他时间着陆。你的任务是为这些飞机安排着陆方式，使得整个着陆计划尽量安全。换句话说，如果把所有飞机的实际着陆时间安照从早到晚的顺序排列，相邻两个着陆时间间隔的最小值（称为安全间隔）应尽量的大。输入格式：输入包含若干组数据。每组数据第一行为飞

2015-09-07 19:58:44 564

原创【POJ3261】字符串哈希

原题题意不再赘述。可以二分答案把每个子串哈希之后统计出现个数……就好了……哈希方法不明白的可以参照白书3.4.3。#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #define maxn 20010 typedef unsigned long long LL; usin

2015-08-26 19:54:17 385

原创【hdu4333】扩展kmp算法

原题链接思路比较简单。把原串扩大一倍，然后以原串为模板串，用扩展kmp算法求出每个位置的最大前缀即可。（WA了一天了，也不知道改了哪个地方就对了…………）#include<iostream> #include<cstdio> #define maxl 1000100 using namespace std; char s1[maxl*2],s2[maxl*2]; int len,pre[maxl

2015-08-24 18:47:06 392

原创【BZOJ1212】【HNOI2004】L语言

挺简单的Trie加DP，直接贴代码：#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define maxl 1100010 using namespace std; char st[20],T[maxl]; int len; struct Trie{ int sz; int ch[300

2015-08-23 20:42:32 416

原创【SCOI2007】【BZOJ1071】组队

原题链接：原题地址 DescriptionNBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为minV，身高最矮的球员高度为minH，那么这支球队的所有队员都应该满足: A * ( height – minH ) + B * ( speed – minV ) <= C 其中A和B，C为给定的经验值。这个式子很容易理解，如果一个球队的

2015-08-21 08:20:25 393

原创 [BZOJ1069][SCOI2007]最大土地面积

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1069 如果枚举四边形的四条边，时间复杂度为O（n^4）,无法承受。可以换个角度，枚举四边形的对角线，在对角线两侧求出最大三角形面积并相加，则降为O（n^3）。若使用旋转卡壳法，时间复杂度降为O（n^2），可参考白书4.3.3。附AC代码： #include #include

2015-08-19 20:55:01 902

原创 hdu1007

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1007 题意：求最近点对，并且输出这个最小值的一半。采用的是分治算法，其中也涉及到归并思想。详细的内容可以参考算导三十三章第四节\(^o^)/~ #include #include #include #include #include #define maxn 100010 #define

2015-08-18 17:01:43 448

function2的博客