bef-> NO.41

Veröffentlicht am

P2736 “破锣摇滚”乐队 Raucous Rockers

题目描述

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲，发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐，一首歌不能分装在两张CD中。CD数量可以用完，也可以不用完

不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：

1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注：第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)

2.选中的歌曲数目尽可能地多

输入输出格式

输入格式：

第一行： 三个整数：N, T, M.

第二行： N个整数，分别表示每首歌的长度，按创作时间顺序排列。

输出格式：

一个整数，表示可以装进M张CD盘的乐曲的最大数目。

输入输出样例

输入样例#1：

1
2
4 5 2
4 3 4 2

输出样例#1：

1
3

说明

题目翻译来自NOCOW。

USACO Training Section 3.4

题解

一道二维费用背包题，后面的物品后选就可以了。

显然我们将时间作为费用，但是由于并没用什么差异所以不用放进状态中。

然后我们用

表示我们将前i首歌放进j个光盘，最后一张剩余时间k的最大值，考虑全情况，尤其是可以新开一张的转移状态。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1005
int f[maxn][maxn] , n , m , T , v[maxn] , ans;
int max(int x , int y , int z)
{
	int k = x > y ? x : y;
	return k > z ? k : z;
}
int main()
{
	scanf("%d%d%d",&n,&T,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&v[i]);
	for(int i = 1 ; i <= n ; ++i){
		for(int j = m ; j >= 1 ; --j)
			for(int k = T ; k >= v[i]; --k){
				f[j][k] = max(f[j][k] , f[j-1][T] + 1, f[j][k - v[i]] + 1);
			}
	}
	printf("%d",f[m][T]);
}

P2440 木材加工

题目背景

要保护环境

题目描述

题目描述:

木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有

剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段木头越长越好，你的任务

是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，

我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为11和21，要求切割成到等长的6段，很明显能切割出来的小段木头长度最长为5.

输入输出格式

输入格式：

输入:

第一行是两个正整数N和K(1 ≤ N ≤ 100000，1 ≤ K ≤ 100000000)，N是原木的数目，K是需要得到的小段的数目。

接下来的N行，每行有一个1到100000000之间的正整数，表示一根原木的长度。

输出格式：

输出:

能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。

输入输出样例

输入样例#1：

1
2
3
4
3 7
232
124
456

输出样例#1：

1
114

题解

一眼二分答案，然后发现check只需要一个循环。。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#define maxn 100005
int p[maxn] , n , k;
inline int solve(int now)
{
	int ans = 0;
	for(int i = 1 ; i <= n ; ++i)
		ans += p[i] / now;
	return ans;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&p[i]);
	int l = 1 , r = 1000000000 , ans = 0;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(solve(mid) >= k)	ans = mid , l = mid + 1;
		else r = mid - 1;
	}
	printf("%d",ans);
}

P4949 最短距离

题目描述

给出一个 {N}N 个点 {N}N 条边的无向连通图。

你需要支持两种操作：

  1. 修改 第 {x}x 条边的长度为 {y}y ；
  2. 查询 点 {x}x 到点 {y}y 的最短距离。

共有 {M}M 次操作。

输入输出格式

输入格式：

输入共 N + M + 1 行：

第 1 行，包含 2 个正整数 N，M，表示点数即边数，操作次数。

第 2 行到第 N + 1 行，每行包含 3 个正整数 x，y，z，表示 x 与 y 间有一条长度 为 z 的边。

第 N + 2 到 N + M + 1 行，每行包含 3 个正整数 opt，x，y，表示操作种类，操作的参数（含义见【题目描述】）。

输出格式：

对于每次操作 2 输出查询的结果。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
4 5
1 2 11
1 3 12
2 3 13
1 4 15
2 2 3
1 2 1
2 2 3
2 2 4
2 3 4

输出样例#1：

1
2
3
4
13
12
26
16

说明

Luogu

题解

实现有点麻烦，NOIp以后再写（如果不退役的话），先随便说说思路，以后写个完整版。

基环树是在树上连了一条边。

首先我们找出这个环，标记上面的点，再以每个点为根求出其子树内的点的根（即环上的点，这样对于后面的点我们可以知道它们在环上的点）。

接下来我的做法比题解就优秀了，尤其是空间上

我们任意取环上一条边标记断边，然后以1为根HPD。

接下来将环上的边按顺序放到线段树上。（一条链）

同时维护一个变量为环上边权

修改每条边的时候假如是树边，就把HPD更新即可，假如是环上的边，更新上述三个。

对于每次查询，其答案为

belong数组是在找出环后对每个点子树内的点做的处理。

时间复杂度

以小常数通过本题