E
想求 长为 \(l\) ~ \(r\) 的区间,且区间内的数字种类 恰好 为 \(k\) 的区间数
由于 恰好为 \(k\) 种数 不好求,所以利用 容斥 思想,转换为 至少 k 种 - 至少 k - 1种
由于区间长度是变化的,双指针使用起来很麻烦,可以利用 前缀和 思想 转换为 长度至少为 r 的区间数 - 长度至少为 l - 1 的区间数
利用双指针实现即可
void yqmr()
{int n, k, l, r; cin >> n >> k >> l >> r;vector<int> a(n);for(int i = 0; i < n; i++) cin >> a[i];auto f = [&](int l) -> int{ //长度小于等于l,数字种类小于等于k的区间数if(l == 0) return 0;auto g = [&](int k) -> int {if(k == 0) return 0;int cnt = 0, j = 0, ans = 0;map<int, int> mp;for(int i = 0; i < n; i++) {if(mp[a[i]]++ == 0) cnt++;while(cnt > k || i - j + 1 > l) {if(--mp[a[j++]] == 0) cnt--;}ans += i - j + 1; //以i为右端点符合条件的区间数}return ans;};return g(k) - g(k - 1);};cout << f(r) - f(l - 1) << '\n';
}
F
总次数=d+休息次数
想让 总次数 最少,就是让 休息次数 最少
休息 是为了分段,减小伤害,避免累积;伤害 越小,就不需要更多的休息次数
想要 伤害越小 ,就要把伤害均分到每一段,一段后休息一次是最优的
void yqmr()
{int h, d; cin >> h >> d;int l = 0, r = d;auto f = [&](int x) {return x * (x + 1) / 2;}; //求长度为x的一段的伤害值auto check = [&](int x) {int q = d / (x + 1), r = d % (x + 1); //需要r段(q + 1)长度return f(q) * (x + 1 - r) + f(q + 1) * r < h + x;};while(l <= r) {int mid = l + r >> 1;if(check(mid)) r = mid - 1;else l = mid + 1;}cout << d + l << '\n';
}