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));
}