SDUT 3513 皮卡丘的梦想(二进制+线段树)解题报告


题面

皮卡丘的梦想
Time Limit: 1000ms Memory limit: 65536K

题目描述
一天,一只住在 501 的皮卡丘决定发奋学习,成为像 LeiQ 一样的巨巨,于是他向镇上的贤者金桔请教如何才能进化成一只雷丘。
金桔告诉他需要进化石才能进化,并给了他一个地图,地图上有 n 个小镇,并且标注了每个小镇上可收集的进化石。
但是皮卡丘拿到地图就蒙圈了,他可不知道自己到底需要哪种进化石,而且由于经费有限,他只能去某几个相邻的小镇,所以他机智地找到了善于编程的你,询问你这些镇上可收集的进化石有哪些,然后再自己决定行程。

输入
首先输入一个整数 T (1 <= T <= 10),代表有 T 组数据。
每组数据的第一行输入一个整数 n (1 <= n <= 100000),代表有 n 个小镇。
接下来的 n 行表示第 1 个到第 n 个的小镇的信息。每行先输入一个整数 m (0 <= m <= 30),代表这个小镇上进化石的种类数,紧接着输入 m 个整数,代表进化石的种类编号(编号从 1 开始,不超过 30)。
之后的一行输入一个整数 q (1 <= q <= 25000),代表皮卡丘有 q 次询问。 接下来的 q 行每行输入两个整数 l, r (1 <= l <= r <= n),表示他想询问从第 l 个到第 r 个小镇上可收集的进化石有哪几种。

输出
对于每组输入,首先输出一行 "Case T:",表示当前是第几组数据。
接下来对于每一次询问,按编号升序输出所有可收集的进化石。如果没有进化石可收集,则输出一个小豪的百分号 "%"(不要问我为什么,出题就是这么任性)。

示例输入
1
3
2 3 10
3 1 2 4
0
3
1 2
2 3
3 3

示例输出
Case 1:
1 2 3 4 10
1 2 4
%

提示

来源
bLue


























SDUT 2778 小明的花费预算(二分答案)解题报告


题面

小明的花费预算
Time Limit: 1000ms Memory limit: 65536K

题目描述
小明终于找到一份工作了,但是老板是个比较奇怪的人,他并不是按照每月每月的这样发工资,他觉得你想什么时候来取都可以,取的是前边连续几个月中没有取的工资,而小明恰好是一个花钱比较大手大脚的人,所以他希望每次取得钱正好够接下来的n个月的花费。
所以让你把这n个月分成正好m组。每个组至少包含一个月,每组之中的月份必须是连续的,请你为他分组,使得分得的组中最大的总花费最小。

输入
第一行是两个整数,n(1 ≤ n ≤ 100,000)和m (1 ≤ m ≤ n)
接下来的n行是连续n个月的花费,第i+1行是第i个月的花费。

输出
输出满足最大的总花费最小的那个组的总花费。

示例输入
5 3
3
2
9
4
1

示例输出
9

提示
将5个月分为3组,第一组(3,2),第二组(9),第三组(4,1),第二组的总花费最大为9,若按其他的方式分,花费最大的那一组的总花费将>=9.

来源
lwn

















SDUT 3100 动态规划?(动态规划)解题报告


题面

动态规划?
Time Limit: 1000ms Memory limit: 65536K

题目描述
动态规划作为《运筹学》的一个分支,被广泛的用于解决较为复杂的经济管理问题,以达到的最优抉择,获得最大经济收益为目的。也因其多变性,非常的频繁的出现在信息学竞赛的赛场上。
动态规划的核心思想为不断将问题分解为子问题,一直到可以较容易的得到最优答案,再去决定其父问题的决策,因为很大程度的避免了重复子问题的抉择,故可以节约大量时间。

现在问题来了,有一个一维数组,存储了n个正整数,下标依次为0,1,2,….,n-1。
现在要从中选取一部分数,你要给出一个选择方案使得你的方案满足下列要求:

  1. 这部分元素的下标应满足st,st+5, st+52 , st+53, … , st+5x (0 <= st < n ,st <= st+5x < n)。
  2. 在满足第一条要求的方案中,应选取其累加和最大的一种的方案。

输入
多组输入。
对于每组输入:
第一行输入一个n(1 <= n <= 100000)。
接下来的一行有n个整数y(-100000 <= y <= 100000)。

输出
对于每组数据,输出一个整数代表你的方案的累加和。

示例输入
10
1 2 3 4 5 6 7 8 9 10
3
1 -10 2
3
-1 -2 -3

示例输出
15
2
-1

提示

来源
zmx





















SDUT 3014 硬币问题(动态规划)解题报告


题面

硬币问题
Time Limit: 1000ms Memory limit: 65536K

题目描述
芳芳有N(1<=N<=1000)个硬币,这些硬币排成一列,有正有反。我们定义这样一种操作,把[l,r]区间上的硬币都翻过来(1<=l<=r<=N).
芳芳想知道经过一次这样的操作后,最多有多少正面朝上的。
1代表正面,0代表反面。
比如:0 1 0 三个数,把区间1-3进行操作,数字就会变成1 0 1 正面向上的个数为2.

输入
本题有多组测试数据,每组数据有两行.
第一行包含一个数字N. 第二行有N个数字,1表示正面,0表示反面.

输出
每组数据输出一行.

示例输入
4
1 0 0 1

示例输出
4

提示

来源
第六届山东理工ACM网络编程擂台赛决赛














SDUT 3068 为了相同的前缀-方程式计算(数学)解题报告


题面

为了相同的前缀-方程式计算
Time Limit: 1000ms Memory limit: 65536K

题目描述
输入a,b,c,找出所有符合下列方程的x,且x为最少1位,最多9位的正整数;
x = b·s(x)^a + c, (s(x)是指正整数x的各位数之和)。

输入
多组输入,每一组输入为三个整数a,b,c(1 ≤ a ≤ 5; 1 ≤ b ≤ 10000;  - 10000 ≤ c ≤ 10000 );

输出
第一行输出符合条件的有多少个x,第二行输出所有符合条件的x(若x为0,则第二行不输出)。

示例输入
3 2 8
1 2 -18

示例输出
3
10 2008 13726
0

提示

来源
ff