第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛（同步赛）总结 + 补题

第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛（同步赛）总结 + 补题

A题 切蛋糕

题目链接 ：https://ac.nowcoder.com/acm/contest/11746/A
基本思路是将1/k进行二进制拆分，比如说对于k=5，1 / 5 的二进制为 0.001100110011，则应存在5份大小为0.001的蛋糕，5份大小为0.0001的蛋糕，以此类推。
（看到2的几次方相加就应该想到二进制拆分）
代码不会写Orz，还不会实现，先留着之后补。

B题 小宝的幸运数组

题目链接 ：https://ac.nowcoder.com/acm/contest/11746/B
题目的思路大概是一个同余的相互跳的一个搜索之类的东西，很巧妙。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
ll T, n, k, ans, sum, t;
ll head[maxn];
int main() {
	for (scanf("%ld", &T);T;T--) {//学来的多组处理
		scanf("%ld%ld", &n, &k);
		ans = sum = 0;
		for (int i=0;i<=k;++i)	head[i] = -1;//head[x]表示的是第一次出现总和加到一起的余数为x的时候的a的位置是多少。这样可以一边加一边处理，如果某个数加到总和上之后和之前第一次的余数对应上了，说明这之间的数字的和可以被K整除。
		head[0] = 0;//显然对于余数为0来说，不需要有数字加上就行。
		for (int i=1;i<=n;++i) {
			scanf("%ld", &t);
			sum = (sum + t) % k;//维持一个加上当前值然后在k里的一个特征值。
			if (head[sum] != -1) 
				ans = max(ans, i - head[sum]);//维护答案 
			else 
				head[sum] = i;//如果第一次出现的话就保存位置
		}
		ans = ans == 0 ? -1 : ans;
		printf("%ld\n", ans);
	}
	return 0;
}

C题 上进的凡凡

这道题的思路是：
一个非降序数组的所有子串都为非降序，只要把给定数组分为若干个非降序部分（每个部分要尽可能长），然后计算子串数，对于长度为n的数组子串数为 n * (n + 1) / 2，遍历然后相加。
思路的正确性：一个非降序数组的所有子串都为非降序串。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100005;
typedef long long ll;

ll a[maxn];
ll sum, n;
int main() {
	ios :: sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)	cin >> a[i];
	for (ll i = 1,t = 1; i <= n; ) {
		t = i;
		t++;
		while (a[t] >= a[t - 1] && t <= n)
			t++;
		ll ans = t - i;
		sum += ans * (ans + 1)/2;
		i = t;
	}
	cout << sum << endl;
	return 0;
}

D Seek the Joker I

这题是个：巴什博弈（终于要学新东西了啊）。