Codeforces Round #241 (Div. 2) D-mysql教程-PHP中文网

Codeforces Round #241 (Div. 2) D

php中文网

发布： 2016-06-07 15:44:23

原创

1150人浏览过

题目链接：D. Population Size 题意：一些数字，要求分块，使得每一块都是等差数列，但是有些数字是-1，代表任意数字（但是要大于0），问最少需要分几块。思路：贪心。每次找到相邻两个确定数字，并且记录下第一个数字前有多少个-1，就能确定出公差，然后利

题目链接：d. population size

题意：一些数字，要求分块，使得每一块都是等差数列，但是有些数字是-1，代表任意数字（但是要大于0），问最少需要分几块。

思路：贪心。每次找到相邻两个确定数字，并且记录下第一个数字前有多少个-1，就能确定出公差，然后利用公差去判断前面的-1能不能填进去，如果不能ans就多1，然后从第二个确定数字位置开始找，如果可以，就利用公差一直找到能放的最后一个位置，然后下次从那个位置开始找。

Text-To-Pokemon口袋妖怪

输入文本生成自己的Pokemon，还有各种选项来定制自己的口袋妖怪

1494

查看详情

细节比较多，代码挫挫的:

#include <stdio.h>
#include <string.h>

const int N = 200005;
__int64 n, i, j;
__int64 a[N];

int main() {
	__int64 ans = 0;
	scanf("%I64d", &n);
	for (i = 0; i < n; i++)
		scanf("%I64d", &a[i]);
	i = 0;
	__int64 s1 = 0;
	while (i < n) {
		s1 = 0;
		while (a[i] == -1 && i < n) {
			s1++;
			i++;
		}
		__int64 s = i;
		if (i < n)
			i++;
		while (a[i] == -1 && i < n) {
			i++;
		}
		if (i == n) {
			ans++;
			break;
		}
		__int64 e = i, d;
		if ((a[e] - a[s]) % (e - s) == 0) {
			d = (a[e] - a[s]) / (e - s);
		}
		else {
			ans++;
			continue;
		}
		if (d > 0 && s1 > (a[s] - 1) / d) {
			ans++;
			i = e;
			continue;
		}
		__int64 sum = a[s];
		for (j = s + 1; j < n; j++) {
			sum += d;
			if (sum < 1) {
				i = j;
				ans++;
				break;
			}
			if (a[j] != -1 && sum != a[j]) {
				i = j;
				ans++;
				break;
			}
		}
		if (j == n) {
			i = n;
			ans++;
		}
	}
	printf("%I64d\n", ans);
	return 0;
}

登录后复制