题解 | #牛客练习赛115 (AB)#

知乎版本

竞赛地址

Mountain sequence

固定最大的。

从大到小枚举元素。

对于当前元素，假设有num个，对于每一个，我们可以放左边，也可以放右边。

总共有(0,num),(1,num-1)...,(num-1,1),(num,0)这num+1种组合。

void solve() {
	scanf("%d", &n);
	map<int, int> mp;
	int mx = -1;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		++mp[a[i]];
		mx = max(mx, a[i]);
	}
	sort(a, a + n);
	int j = 0;
	for (int i = 0; i < n; ++i) {
		if (!i || a[i] != a[i-1]) {
			a[j++] = a[i];
		}
	}
	ll res = 1;
	for (auto p: mp) {
		if (p.first == mx) {
			continue;
		}
		res = M(res, p.second + 1);
	}
	printf("%lld\n", res); 
} 

Antiamuny wants to leaern binary search again

模拟下，每次优先取最大的部分（为了尽可能让下一轮的[l,r]区间长度大）。因为是除以2是向下取整，优先取右边部分。

#define debugging 0
void solve() {
	int l, r, cnt;
	scanf("%d%d%d", &l, &r, &cnt);
	int mid = -1;
	while (cnt > 0 && (l <= r)) {
		mid = (l + r) / 2;
		if (debugging)
			printf("cnt: %d (%d, %d):%d\n", cnt, l, r, mid);
		l = mid + 1;
		--cnt;
	}
	if (debugging) printf("cnt: %d\n", cnt);
	printf("%d\n", (cnt > 0 ? -1 : mid));
}