Veröffentlicht am | Edited on

「一本通 5.5 例 4」旅行问题

题目描述

原题来自：POI 2004

John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 nnn 车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。

任务：判断以每个车站为起点能否按条件成功周游一周。

输入格式

第一行是一个整数 nnn，表示环形公路上的车站数；

接下来 n 行，每行两个整数，分别表示表示第 iii 号车站的存油量和第 iii 号车站到下一站的距离。

输出格式

输出共 nnn 行，如果从第 iii 号车站出发，一直按顺时针（或逆时针）方向行驶，能够成功周游一圈，则在第 iii 行输出 TAK，否则输出 NIE。

样例

样例输入

1
2
3
4
5
6
5
3 1
1 2
5 2
0 1
5 4

样例输出

1
2
3
4
5
TAK
NIE
TAK
NIE
TAK

数据范围与提示

对于全部数据，

题解

一道单调队列的思维题。

注意题目中说的，必须任意时刻有油，又考虑到从起点到当前点会有剩下的油（如果剩负的不合法），显然可以想到前缀和，对于每个点和路长之差的前缀和（即剩余油量）。

然后破环为链

这样我们只需要在倍长的链上做区间RMQ即可（即判断链上一个长度为n的区间是否某一时刻前缀值小于区间左端点减一的前缀值，那意味着中途没油了）

再反着跑，请注意细节，由此导致第一次提交因为下标问题而得了0分。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 1000005
long long s[maxn*2] , p[maxn] , d[maxn] , n;
bool f[maxn] , g[maxn] , tmp[maxn];
std::deque<int> q;
int main()
{
    scanf("%lld",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld%lld",&p[i],&d[i]);
    for(int i = 1 ; i <= n ; ++i)
        s[i] = p[i] - d[i] + s[i-1];
    for(int i = n + 1 ; i <= n * 2 ; ++i)
        s[i] = p[i-n] - d[i-n] + s[i-1];
    for(int i = 1 ; i <= n ; ++i)
    {
        while(!q.empty() && s[q.back()] > s[i]) q.pop_back();
        q.push_back(i);
    }
    if(s[q.front()] > 0)    f[1] = true;
    for(int i = n + 1 ; i <= 2 * n - 1 ; ++i)//for each i - n + 1 as a begin
    {
         while(!q.empty() && s[q.back()] > s[i]) q.pop_back();
         while(!q.empty() && q.front() <= i - n)    q.pop_front();
         q.push_back(i);//i-n+1 ~ i Min value
         if(s[q.front()] >= s[i - n])   f[i-n+1] = true;
    }
    
    int fn = d[n];
    for(int i = n ; i > 1 ; --i)
    	d[i] = d[i-1];
	d[1] = fn;
    std::memset(s,0,sizeof(s));
    while(!q.empty()) q.pop_back();
    for(int i = 1 ; i <= n ; ++i)
    	s[i] = s[i-1] + (p[n-i+1] - d[n-i+1]);
    for(int i = n + 1 ; i <= 2 * n - 1; ++i)
    	s[i] = s[i-1] + (p[n-i+1+n] - d[n-i+1+n]);
    for(int i = 1 ; i <= n ; ++i)
    {
        while(!q.empty() && s[q.back()] >= s[i]) q.pop_back();
        q.push_back(i);
    }
    
    if(s[q.front()] > 0)    g[n] = true;
    for(int i = n + 1 ; i <= 2 * n - 1 ; ++i)//for each i - n + 1 as a begin
    {
         while(!q.empty() && s[q.back()] > s[i]) q.pop_back();
         while(!q.empty() && q.front() <= i - n)    q.pop_front();
         q.push_back(i);//i-n+1 ~ i Min value
         if(s[q.front()] >= s[i - n])   tmp[i-n] = true;
    }
	for(int i = 1 ; i <= n-1 ; ++i)
		g[n-i] = tmp[i];
    for(int i = 1 ; i <= n ; ++i)
    	if(f[i] || g[i])
    		printf("TAK\n");
    	else printf("NIE\n");
}

「一本通 5.5 例 5」Banknotes

题目描述

原题来自：POI 2005

Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有 nnn 种面值的硬币，面值分别为 b1,b2,⋯,bnb_1, b_2,\cdots , b_nb1,b2,⋯,bn。但是每种硬币有数量限制，现在我们想要凑出面值 kkk，求最少要用多少个硬币。

输入格式

第一行一个数 nnn；

接下来一行 nnn 个整数 b1,b2,⋯,bnb_1, b_2,\cdots , b_nb1,b2,⋯,bn；

第三行 nnn 个整数 c1,c2,⋯,cnc_1,c_2,\cdots ,c_nc1,c2,⋯,cn，表示每种硬币的个数；

最后一行一个数 kkk，表示要凑的面值数。

输出格式

第一行一个数表示最少需要付的硬币数。

样例

样例输入

1
2
3
4
3
2 3 5
2 2 1
10

样例输出

1
3

数据范围与提示

对于全部数据，

题解

一开始想了个生成函数的做法。。

我们知道，幂形式相乘底数相同的指数相加。

因此我们可以构造一个生成函数让价值在指数幂上，底数是x。。

也即是：

然后展开后对于第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
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 205
#define maxk 20005
#define maxlog 15
int n , x[maxn] , y[maxn] , f[maxk] , w[maxn*maxlog] , c[maxn*maxlog] , tot , k;
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&x[i]);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&y[i]);
	scanf("%d",&k);
	std::memset(f,0x7f,sizeof(f));
	f[0] = 0;
	for(int i = 1 ; i <= n ; ++i)
	{
		int k = 0;
		while((1<<k) <= y[i]){
			y[i] -= (1<<k);
			w[++tot] = x[i] * (1<<k);
			c[tot] = (1<<k);
			++k;
		}
		if(y[i])
			w[++tot] = x[i] * y[i] , c[tot] = y[i];
	}
	for(int i = 1 ; i <= tot ; ++i)
		for(int j = k ; j >= w[i] ; --j)
			f[j] = std::min(f[j] , f[j-w[i]] + c[i]);
	printf("%d",f[k]);
}