Post 60

Veröffentlicht am | Edited on

写POI吧。一直想写，对于高级算法突然失去动力

被sb题吊打中…

好了终于做出来了。。

[POI2012]BON-Vouchers

题目描述

Byteasar的糖果店有很美味的焦糖糖果卖。

对于每一个正整数C，保证有且仅有一个包裹包含c个糖果。

为了鼓励顾客们购买美味的糖果，Byteasar制作了m个代金券，并且保证每个包裹里都最多只有1张代金券。（一个包裹里有可能没有代金券）

Byteasar的购物狂欢节将于下周在Byteburg举行，并且将持续n天：在狂欢节的第k天会举办一个有a[k]个客人参加的party。

Byteasar对于第k天的早晨每个客人都会买东西这件事总是有着蜜汁自信（我也不知道为什么）。在第n天里，包含y×a[n]个糖果的包裹能够依次卖出（x为正整数）。举个栗子：如果n=2,a1=4，a2=2,那么在购物狂欢节的第一天，含有4（即a[1]）×1,4×2,4×3，4×4……个糖果的包裹能够卖出去，在第二天含有2（即a[2])×1个和2×3……个糖果的包裹能够卖出去。(因为2×2的包裹第一天已经被买走了）

现在Byteasar想要知道哪些顾客会拿到代金券。

他想要你编写一个程序来帮他解决问题。

输入输出格式

输入格式：

第一行输入一个正整数m ( 1≤m≤1 000 000），代表代金券的张数。

接下来m行的第k行有一个正整数b[k]，代表被Byteasar放入了代金券的包裹中的糖果数量。

数据保证以单调递增的形式给出。

接下来一行输入一个整数n,表示购物狂欢节的天数。

接下来n行的第k行有一个正整数a[k]表示参加第k天购物狂欢节的客人数量。

保证至少有50%以上的测试点所有的数值都不会大于5000（所以……这是暴力分？）

输出格式：

第一行输出一个整数z表示有z个含有代金券的包裹被售出。

接下来z行以单调递增的形式给出拿到代金券的客人编号。

顾客从第一天的第一个开始编号，一直到最后一天的最后一名顾客

由 @姜澜 提供翻译 @Wolfycz提供建议

题目描述

The candy shop owned by Byteasar sells delicious caramel candy.

For every positive integer cc there is exactly one package that contains cc candies; currently no new deliveries are expected.

To encourage customers to buy the sweets, Byteasar has planted mm vouchers for an annual supply of chocolate into some packages, making sure to put at most one voucher in each package.

The carnival starts next week in Byteburg, and it will last nn days; on the kk-th day of the carnival a party with a_ka**k guests will be held.

Byteasar is confident that on the kk-th day’s morning each of those guests is going to buy, in his own store, the smallest package of candy available whose content can be equally distributed between the party guests. For example, if n=2n=2, a_1=4, a_2=2, then on the first day of the carnival he expects to sell the packages containing four, eight, twelve, and sixteen candies, selling those with two and six candies on the second day.

Now he is wondering which customers will end up with the packages holding the vouchers.

He has asked you to write a program that will determine this for him.

输入输出格式

输入格式：

On the first line of the standard input there is a single integer mm (1\le m\le 1\ 000\ 0001≤m≤1 000 000) that denotes the number of vouchers.

The kk-th of the mm lines that follow holds an integer b_kb**k (1\le b_k\le 1\ 000\ 0001≤b**k≤1 000 000)denoting the size (i.e., the number of candies inside) of a package in which Byteasar has placed the kk-th voucher.

These numbers are given in an increasing order.

Then the next line contains a single integer nn (1\le n\le 1\ 000\ 0001≤n≤1 000 000) that denotes the number of carnival days.

The $k$-th of the $n$ lines that follow holds an integer $a_k$($1\le a_k\le 1\ 000\ 000$)denoting the number of guests attending the kk-th party.

You may assume that in tests worth at least 50% of the total points none of the numbers given on the input exceeds 5\ 0005 000.

输出格式：

In the first line of the standard output your program should print an integer zz - the number of packages with vouchers sold.

The following zz lines should specify the numbers of those customers who bought a package with a voucher, in an increasing order.

The customers are numbered from 11 in the order of their purchases.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
4
1
6
8
16
3
4
2
4

输出样例#1：

1
2
3
4
3
2
4
6

题解

英语水平有待提高，读英语读半天看不懂。。

题意是说每个数取到平方个前面没取过的当前人数$a_k$的倍数，问你哪些编号的人取到给定的那些数。

一开始只会暴力得了67

和NOIP2018D1T2真是有异曲同工之妙。。

特点就是如果你观察出一些显而易见的事实，这道题就会非常的容易。

否则就非常困难（我想歪的时候各种枚举处理约数和倍数，貌似是$O(nlog^2n)$但是编程复杂度极高。。。。）

我们发现相同的数只需要在上一个数枚举到的位置继续枚举就可以保证时间复杂度为$O(nlnn)$

虽然还是会有重复枚举，比如一个数的约数或倍数在前就可能在轮到它时枚举一些前面已经拿走的，但是只需要标记一下跳过并且多枚举一个新倍数保证正确性即可，并不会影响时间复杂度。。。

这种题大概就是想出来很简单，想不出来就凉凉。。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#define maxn 1000005
int a[maxn], n , m , c[maxn] , pos[maxn];
bool vis[maxn] , gt[maxn] , p[maxn];
long long s;
std::vector<int> ans;
int main()
{
//	freopen("5.in","r",stdin);
//	freopen("data.out","w",stdout);
	scanf("%d",&m);
	for(int i = 1; i <= m ; ++i)
		scanf("%d",&a[i]) , p[a[i]] = true;
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
	{
		int x;
		scanf("%d",&x);
		int k = pos[x] + x;
		for(int j = pos[x] + 1 ; j <= k && 1ll * j * x <= 1000000; ++j)
		{
			if(gt[j*x] == true){
				++k;
				continue;
			}
			else if(p[j*x]) ans.push_back(s + j - (k-x));
			gt[j*x] = true;
		}
		pos[x] = k;
		s += x;
	}
		printf("%d\n",(int)ans.size());
		for(int i = 0 ; i < (int)ans.size() ; ++i)
			printf("%d\n",ans[i]);
			

}

Generic Cow Protests, 2011 Feb

题目描述

约翰家的N 头奶牛正在排队游行抗议。一些奶牛情绪激动，约翰测算下来，排在第i 位的奶牛的理智度为Ai，数字可正可负。

约翰希望奶牛在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小组的理智度之和必须大于或等于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛必须是连续位置的。除此之外，分组多少组，每组分多少奶牛，都没有限制。

约翰想知道有多少种分组的方案，由于答案可能很大，只要输出答案除以1000000009 的余数即可。

输入输出格式

输入格式：

• 第一行：单个整数N，1 ≤ N ≤ 100000

• 第二行到第N + 1 行：第i + 1 行有一个整数Ai，−10^5 ≤ Ai ≤ 10^5

输出格式

单个整数：表示分组方案数模1000000009 的余数

输入输出样例

输入样例#1：

1
2
3
4
5
4
2
3
-3
1

输出样例#1：

1
4

说明

解释:如果分两组，可以把前三头分在一组，或把后三头分在一组；如果分三组，可以把中间两头分在一组，第一和最后一头奶牛自成一组；最后一种分法是把四头奶牛分在同一组里。

题解

这些DP都好套路啊，没劲。

设$f_{i}$表示前$i$头的答案，转移只需要枚举最后一段（枚举最后一段是因为这样复杂度最小，想枚举两段当然也OK。。。）

$fi = \sum{j=0}^{j-1}f_{j}[s_i-s_j >= 0]$

时间复杂度$O(n^2)$

然后就获得了70pts

不过这么水的题当然得切掉，显然是个平衡树优化DP

然后我就RE到只有30pts

然后我看了看，仔细检查了一下发现取模本来是：

1
d[x] %= mod

结果写成了

1
d[x] %= dt

然后出现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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <ctime>
#define maxn 100005
const int mod = (int)1e9+9;
int a[maxn] , n;
long long s[maxn] , f[maxn];
namespace Treap
{
#define lc ch[0][x]
#define rc ch[1][x]
	int ch[2][maxn] , p[maxn] , tot , rt;
	long long k[maxn] , d[maxn] , st[maxn];
	void treap(){
		srand(time(NULL));
	}
	inline void pushup(int x){
		st[x] = d[x] + st[lc] + st[rc];
	}
	inline void rot(int& x , int op)
	{
		int sn = ch[op][x];
		ch[op][x] = ch[op^1][sn];
		ch[op^1][sn] = x;
		pushup(x) , x = sn , pushup(x);
	}
	inline void newnode(int& x , int val , int dt)
	{
		x = ++tot;
		k[x] = val;
		d[x] = st[x] = dt;
		p[x] = rand() % 992912443;
	}

	void ins(int& x , long long val , long long dt)
	{
		if(!x){
			newnode(x , val , dt);
			return ;
		}
		st[x] += dt , st[x] %= mod;
		if(val <= k[x]){
			ins(lc , val ,dt);
			if(p[lc] < p[x]) rot(x , 0);
		}
		else {
			ins(rc , val , dt);
			if(p[rc] < p[x]) rot(x , 1);
		}
	}

	inline long long find(int x , long long key)
	{
		long long ans = 0;
		while(x)
		{
			if(k[x] <= key) ans += d[x] + st[lc] , x = rc , ans %= mod;
			else x = lc;
		}
		return ans;
	}
}


int main()
{
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	scanf("%d",&n);
	Treap::treap();
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&a[i]) , s[i] = s[i-1] + a[i];
//	f[0] = 1;
	Treap::ins(Treap::rt , 0 , 1);
//	puts("OK");
	for(int i = 1 ;  i <= n ; ++i)
	{
		f[i] = Treap::find(Treap::rt , s[i]);
		Treap::ins(Treap::rt , s[i] , f[i]);
//		for(int j = 0 ; j < i ; ++j)
//			f[i] += f[j] * ((s[i] - s[j]) >= 0) , f[i] %= mod;
	}
	printf("%lld",f[n]);
}

其实上面都是3.1写的233

[POI2005]SKA-Piggy Banks

题目描述

Byteazar the Dragon has NN piggy banks. Each piggy bank can either be opened with its corresponding key or smashed. Byteazar has put the keys in some of the piggy banks - he remembers which key has been placed in which piggy bank. Byteazar intends to buy a car and needs to gain access to all of the piggy banks. However, he wants to destroy as few of them as possible. Help Byteazar to determine how many piggy banks have to be smashed.

TaskWrite a programme which:

reads from the standard input the number of piggy banks and the deployment of their corresponding keys,finds the minimal number of piggy banks to be smashed in order to gain access to all of them,writes the outcome to the standard output.

Byteazar the Dragon拥有N个小猪存钱罐。每一个存钱罐能够用相应的钥匙打开或者被砸开。Byteazar已经将钥匙放入到一些存钱罐中。现在已知每个钥匙所在的存钱罐，Byteazar想要买一辆小汽车，而且需要打开所有的存钱罐。然而，他想要破坏尽量少的存钱罐，帮助Byteazar去决策最少要破坏多少存钱罐。

任务：

写一段程序包括：

读入存钱罐的数量以及相应的钥匙的位置，求出能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量并将其输出。

输入输出格式

输入格式：

The first line of the standard input contains a single integer NN (1\le N\le 1\ 000\ 0001≤N≤1 000 000) - this is the number of piggy banks owned by the dragon. The piggy banks (as well as their corresponding keys) are numbered from 11 to NN. Next, there are NN lines: the (i+1)(i+1)’st line contains a single integer - the number of the piggy bank in which the ii‘th key has been placed.

第一行：包括一个整数N（1<=N<=1000000)，这是Byteazar the Dragon拥有的存钱罐的数量。

存钱罐（包括它们对应的钥匙）从1到N编号。

接下来有N行：第i+1行包括一个整数x，表示第i个存钱罐对应的钥匙放置在了第x个存钱罐中。

输出格式：

The first and only line of the standard output should contain a single integer - the minimal number of piggy banks to be smashed in order to gain access to all of the piggy banks.

仅一行：包括一个整数，表示能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量。

输入输出样例

输入样例#1：

1
2
3
4
5
4
2
1
2
4

输出样例#1：

1
2

题解

一看就是图论题。

首先假如砸开$x$可以打开$y$，意味着$y$可以开启或间接开启的$x$都可以开启。

那我们连$y->x$

假如两个互相连了，可以发现就是等价的一个点。

讨论一个强联通分量发现只需要任何一个点就可以开启整个SCC

然后最后我们发现入度为0 的统计一下就行（最小性非常显然，因为每个点必定属于一个入度为0的点的控制，单独开启它最少还要开启入度为0的那个点，与最小性矛盾，应该直接开启入度为0的那个点）。

然后我们仔细一想发现这是并查集，虽然时间复杂度高了但是编程复杂度下降了，互相连的点也不需要预先处理好了

统计联通块即可。

时间复杂度$O(nlogn)$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1000005
int a[maxn] , f[maxn] , n , ans;
bool vis[maxn];

inline int find(int x){
	return f[x] == x ? x : f[x] = find(f[x]);
}

int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		f[i] = i;
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&a[i]) , f[find(i)] = find(a[i]);
	for(int i = 1 ; i <= n ; ++i)
		if(!vis[find(i)]) ans ++ , vis[find(i)] = true;
	printf("%d",ans);
}

[POI2006]KRA-The Disks

题目描述

For his birthday present little Johnny has received from his parents a new plaything which consists of a tube and a set of disks. The aforementioned tube is of unusual shape. Namely, it is made of a certain number of cylinders (of equal height) with apertures of different diameters carved coaxially through them. The tube is closed at the bottom, open at the top. An exemplary tube consisting of cylinders whose apertures have the diameters: 5cm, 6cm, 4cm, 3cm, 6cm, 2cm and 3cm is presented in the image below.

The disks in Johnny’s plaything are cylinders of different diameters and height equal to those forming the tube.

Johnny has invented a following game: having a certain set of disks at his disposal, he seeks to find what depth the last of them would stop at, assuming that they are being thrown into the centre of the tube. If, for instance, we were to throw disks of consecutive diameters: 3cm, 2cm and 5cm, we would obtain the following situation:

As you can see, upon being thrown in, every disk falls until it gets stuck (which means that it lies atop a cylinder, aperture of which has a diameter smaller than the diameter of the disk) or it is stopped by an obstacle: the bottom of the tube or another disk, which has already stopped.

The game being difficult, Johnny constantly asks his parents for help. As Johnny’s parents do not like such intellectual games, they have asked you - an acquaintance of theirs and a programmer - to write a programme which will provide them with answers to Johnny’s questions.

TaskWrite a programme which:

reads the description of the tube and the disks which Johnny will throw into it from the standard input,computes the depth which the last disk thrown by Johnny stops at,writes the outcome to the standard output.

一个框，告诉你每一层的宽度。

向下丢给定宽度的木块。

木块会停在卡住他的那一层之上，异或是已经存在的木块之上。

询问丢的最后一个木块停在第几层。

输入输出格式

输入格式：

The first line of the standard input contains two integers nn and mm (1\le n,m\le 300\ 0001≤n,m≤300 000) separated by a single space and denoting the height of Johnny’s tube (the number of cylinders it comprises) and the number of disks Johnny intends to throw into it, respectively. The second line of the standard input contains nn integers r_1,r_2,\cdots,r_nr1,r2,⋯,r**n (1\le r_i\le 1\ 000\ 000\ 0001≤r**i≤1 000 000 000 for 1\le i\le n1≤i≤n) separated by single spaces and denoting the diameters of the apertures carved through the consecutive cylinders (in top-down order), which the tube consists of. The third line contains mm integers k_1,k_2,\cdots,k_mk1,k2,⋯,k**m (1\le k_j\le 1\ 000\ 000\ 0001≤k**j≤1 000 000 000 for 1\le j\le m1≤j≤m) separated by single spaces and denoting the diameters of consecutive disks which Johnny intends to throw into the tube.

输出格式：

The first and only line of the standard output should contain a single integer denoting the depth which the last disk stops at. Should the disk not fall into the tube at all, the answer should be 00.

输入输出样例

输入样例#1：

1
2
3
7 3
5 6 4 3 6 2 3
3 2 5

输出样例#1：

1
2

题解

好恶心的细节题啊。

显然是比当前数小的位置-1的地方就是最后一个落的位置。

先说最容易想的数据结构优化暴力寻找前驱。

分块或线段树可以做到$O(n\sqrt{n})$与$O(nlogn)$

然后一交喜闻乐见WA到65.

然后怎么也想不出哪错了。

思考了一下，由题意得位置单调不下降，因此直接前缀最小值移动指针找那个位置即可。

然后一交又65…

CNM

然后仔细想啊想看题解发现好像要再减个1

总之思路对了就好了，反正也有65

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#define maxn 2000005
#define sqrtn 1000
int r[maxn] , n , p[maxn] , m , las , pos[maxn] , st , L[sqrtn] , R[sqrtn] , num , mn[maxn] , k[maxn];
inline void pre()
{
	st = (int)std::sqrt(n);
	for(int i = 1 ; i <= n / st ; ++i)
		L[i] = R[i-1] + 1 , R[i] = i * st;
	num = n / st;
	if(R[num] < n) L[num + 1] = R[num] + 1 , R[num + 1] = n , ++num;
	for(int i = 1 ; i <= num ; ++i)
		for(int j = L[i] ; j <= R[i] ; ++j)
			pos[j] = i , mn[i] = std::min(mn[i] , r[j]);
}

inline int solve(int k , int x)
{
	for(int i = L[k] ; i <= R[k] ; ++i)
		if(r[i] < x)
			return i;
	return -1;
}

inline int QPRE(int l , int rr , int x)
{
	if(rr < l) return -1;
	if(pos[l] == pos[rr])
	{
		for(int i = l ; i <= rr; ++i)
			if(r[i] < x)
				return i;
		return -1;
	}
	int cl = l;
	for( ; L[pos[cl]] != cl ; ++cl)
		if(r[cl] < x)
			return cl;
	for( ; pos[cl] != pos[rr] ; cl = L[pos[cl] + 1])
		if(mn[pos[cl]] < x)
			return solve(pos[cl] , x);
	for(int i = cl ; i <= rr ; ++i)
		if(r[cl] < x)
			return cl;
	return -1;
}
	

int main()
{
	std::memset(mn,0x7f,sizeof(mn));
	std::memset(k,0x7f,sizeof(k));
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&r[i]) , k[i] = std::min(k[i-1] , r[i]);
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d",&p[i]);
	pre();
	las = n + 1;
	int rr = n;
	for(int i = 1 ; i <= m ; ++i)
	{
		int k = QPRE(1 , las - 1, p[i]);
	   	if(k == -1) las --;
		else las = k - 1;
		if(!las) break;
//		while(k[rr] < p[i] && rr) --rr ;
//		--rr;
//		if(!rr){
//			puts("0");
//			return 0;
//		}
	}	
	printf("%d",rr+1);
}