BZOJ 1833: [ZJOI2010]count 数字计数

Description给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。Input输入文件中仅包含一行两个整数a、b,含义如上所述。Output输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。Sample Input1 99Sample Output9 20 20 20 20 20 20 20 20 20HINT30%的数据中,a<=b<=10^6;100%的数据中,a<=b<=10^12。Solution又是一道数位 DP 的题,照旧写记忆化搜索,需要处理一下前导零的情况。Code#i- 阅读剩余部分 -

BZOJ 1026: [SCOI2009]windy数

Descriptionwindy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数?Input包含两个整数,A B。Output一个整数Sample Input【输入样例一】1 10【输入样例二】25 50Sample Output【输出样例一】9【输出样例二】20HINT100%的数据,满足 1 <= A <= B <= 2000000000 。Solution数位 DP 入门题,记忆化搜索一波就可以了。Code#include <cstdi- 阅读剩余部分 -

HDU 2089: 不要62

Problem Description杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。不吉利的数字为所有含有4或62的号码。例如:62315 73418 88914都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。Input输入的都是整数对n、m(0<n≤m<1- 阅读剩余部分 -

HDU 3555: Bomb(不要49)

Problem给定一个 n ,求 [1, n] 有多少个数包含 49。Code数位 DP#include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #define long unsigned long long using namespace std; long a[100]; long dp[100][3]; /* dp[i][0] 前 i 位不包含 49 的个数 dp[i][1] 前 i 位以 9 开头但不包含 49 的个数 dp- 阅读剩余部分 -

主席树学习笔记

主席树就是可持久化线段树,可以随时访问任何一个历史版本的线段树,所有操作的时间复杂度和线段树完全一致,是 O(logn),空间变成了 O(nlogn),是一种十分优秀的数据结构。对于线段树来说,每次操作都只会更改 logn 个节点,我们可以单独把这些节点存下来,然后剩下的节点和前一个版本的线段树共用就可以了,这样对于 n 个操作就需要存储 nlogn 个节点,这样空间复杂度 O(nlogn) 就证明出来了。具体来说怎么和前一个版本的线段树共用节点从而降低空间占用呢?当我们修改了一个节点,那么他的左右孩子中肯定有一个需要修改,那么修改其中的一个孩子,而另一个孩子我们直接指向上- 阅读剩余部分 -

BZOJ 1733: [Usaco2005 feb]Secret Milking Machine 神秘的挤奶机

Description约翰正在制造一台新型的挤奶机,但他不希望别人知道.他希望尽可能久地隐藏这个秘密.他把挤奶机藏在他的农场里,使它不被发现.在挤奶机制造的过程中,他需要去挤奶机所在的地方T(1≤T≤200)次.他的农场里有秘密的地道,但约翰只在返回的时候用它.农场被划分成N(2≤N≤200)块区域,用1到200标号.这些区域被P(1≤P≤40000)条道路连接,每条路有一个小于10^6的长度L.两块区域之间可能有多条道路连接.为了减少被发现的可能,约翰不会两次经过农场上的任何一条道路.当然了,他希望走最短的路. 请帮助约翰寻找这T次从仓库走到挤奶机所在地的路线.仓库是区域- 阅读剩余部分 -

POJ 1185: 炮兵阵地

Description司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵- 阅读剩余部分 -

BZOJ 3891: [Usaco2014 Dec]Piggy Back

题目描述给定一个N个点M条边的无向图,其中Bessie在1号点,Elsie在2号点,它们的目的地为N号点。Bessie每经过一条边需要消耗B点能量,Elsie每经过一条边需要消耗E点能量。当它们相遇时,它们可以一起行走,此时它们每经过一条边需要消耗P点能量。求它们两个到达N号点时最少消耗多少能量?输入The first line of input contains the positive integers B, E, P, N, and M. All of these are at most 40,000. B, E, and P are described abov- 阅读剩余部分 -

BZOJ 3299: [USACO2011 Open]Corn Maze玉米迷宫

Description今年秋天,约翰带着奶牛们去玩玉米迷宫。迷宫可分成NxM个格子,有些格子种了玉 米,种宥玉米的格子无法通行。 迷宫的四条边界上都是种了玉米的格子,其屮只有一个格子 没种,那就是出口。 在这个迷宫里,有一些神奇的传送点6每个传送点由一对点组成,一旦 走入传送点的某个结点, 机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的,如果你定到了另一头,机器也会把你送回来。 奶牛在一个单位的时间内只能向相邻的四个方向移动一格,不过传送机传送是瞬间完成 的。 现在W西在迷宫里迷路了,她只知道目前的位罝在哪里,请你帮助她用最短的时间走出 迷宫吧。Input第- 阅读剩余部分 -

BZOJ 3300: [USACO2011 Feb]Best Parenthesis

Description计算“平衡字符串”的分数,“平衡字符串”是指由相同数量的‘(’和‘)’组成, 且以‘(’开头,以‘)’结尾的字符串。 计算规则: 字符串“()”的得分是1. 如果,平衡字符串“A”的得分是是S(A),那么字符串“(A)”得分是2*S(A) ; 如果,“A”,“B” 得分分别是S(A)和S(B),那么平衡字符串“AB”得分为S(A)+S(B) 例如:s("(())()") =s("(())")+s("()") = 2s("()")+1 = 21+1 = 3.Input第1行:N,平衡字符串长度 第2至N+1行:Linei+1 整数0或1,0代表字符‘(’- 阅读剩余部分 -

BZOJ 3393: [Usaco2009 Jan]Laserphones 激光通讯

DescriptionInput第1行输入w和H,之后W行H列输入地图,图上符号意义如题目描述.Output最少的对角镜数量.Sample Input7 8 ....... ......C ......* *****.* ....*.. ....*.. .C..*.. .......Sample Output3Solution搜索,类似于最短路,不过要加一维方向,整体类似于 SPFACode#include <bits/stdc++.h> #define long long long using namespace std; inline void read(i- 阅读剩余部分 -

BZOJ 2197: [Usaco2011 Mar]Tree Decoration

Description约翰正在装饰他家的圣诞树。圣诞树上有个 N 个结点,第一个结点是根,其余结点都有唯一的父亲结点,第 i 个结点的父亲是 P i 。由于根没有父亲,所以记 P 1 = −1。约翰可以在每个结点上挂载装饰物,但费用是变化。在第 i 个结点上挂载一个装饰物需要花费 C i元钱。奶牛对这个圣诞树上每个结点都有特殊的装饰需求,对于第 i 个结点,奶牛要求以它为根的子树上必须有 D i 个装饰物。请问约翰在哪些结点上挂载装饰物,才能满足奶牛的要求,并且使得装饰费用最少?Input第一行:单个整数 N,1 ≤ N ≤ 10 5第二行到 N 行:第 i+1 行有三个整- 阅读剩余部分 -

BZOJ 2020: [Usaco2010 Jan]Buying Feed, II

DescriptionFJ开车去买K份食物,如果他的车上有X份食物。每走一里就花费X元。 FJ的城市是一条线,总共E里路,有E+1个地方,标号0~E。 FJ从0开始走,到E结束(不能往回走),要买K份食物。 城里有N个商店,每个商店的位置是X_i(一个点上可能有多个商店),有F_i份食物,每份C_i元。 问到达E并买K份食物的最小花费Input第1行:K,E,N 第2~N+1行:X_i,F_i,C_i.Output一个整数,花费。Sample Input2 5 3 3 1 2 4 1 2 1 1 1Sample Output7Solution由于路程原因,每个物品的单价需要- 阅读剩余部分 -