C. Monsters And Spells
怪兽会在第K秒出现，血量是H，任务是在它出现的时候消灭它。上一秒如果没有使用过魔法，那么这一秒只能施展1的魔法；如果上一秒使用过x的魔法，这一秒可以使用x+1的魔法。若魔法x>=H，则怪兽可以被消灭。使用x的魔法就会消耗x的魔力，问最少消耗魔力是多少。
直接从前往后遍历一遍是不可以的，存在H [ i ] > H [ i - 1 ] + K [ i ] - K [ i - 1 ]，为了避免这种情况，可以先dp消除这种情况，再从前往后遍历一遍就好了。
还有一种写法简单些，是区间合并，在时间轴上弄出所有的区间然后以左端点排个序，开始合并就好了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, mod = 1e9 + 7;
int k[N], h[N];
signed main ()
{int tt;cin >> tt;while(tt--){int n;cin >> n;for (int i = 1; i <= n; i++) cin >> k[i];for (int i = 1; i <= n; i++) cin >> h[i];for (int i = n - 1; i >= 1; i--) h[i] = max(h[i], h[i + 1] - (k[i + 1] - k[i]));int ans = 0;int last = 0;for (int i = 1; i <= n; i++){if (last + k[i] - k[i - 1] >= h[i]){if (k[i] - k[i - 1] >= h[i]){ans += h[i] * (h[i] + 1) / 2;last = h[i];}else {ans += (last + 1 + last + k[i] - k[i - 1]) * (k[i] - k[i - 1]) / 2;last += k[i] - k[i - 1];}}}cout << ans << endl;}return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, mod = 1e9 + 7;
int k[N], h[N];
struct node{int l, r;bool operator < (const node &k) const{if (l != k.l) return l < k.l;else return r < k.r;}
} a[N];
signed main ()
{int tt;cin >> tt;while(tt--){int n;cin >> n;for (int i = 1; i <= n; i++) cin >> k[i];for (int i = 1; i <= n; i++) cin >> h[i];for (int i = 1; i <= n; i++){a[i].l = k[i] - h[i] + 1;a[i].r = k[i];}sort(a + 1, a + 1 + n);int ans = 0;int l = a[1].l, r = a[1].r;for (int i = 2; i <= n; i++){if (a[i].l <= r) {r = max(r, a[i].r); //相交 更新右端点}else {ans += (1 + r - l + 1) * (r - l + 1) / 2; //不想交 统计答案l = a[i].l;r = a[i].r;}}ans += (1 + r - l + 1) * (r - l + 1) / 2;cout << ans << endl;}return 0;
}
鸡哥的 AI 驾驶
很久以前的一道二分题了。寒假闲来没事干，突然想到以前这题二分一下时间然后check好像可写。但是水平不够还是调了很久。。有一个bug不拿别人AC程序对拍是真想不到。。最后用并查集+二分过得。细节真的很重要啊。
思路：枚举时间，然后得到车子的新的位置，怎样判断车子有没有相撞呢？用并查集，相邻的车子只要型号相同，就并在一起。得到新的位置后排个序就知道和原来的相对位置有没有发生改变了，如果变了那就一定撞车了，反之则没有。
我的wa点：
1.二分区间枚举的太大了，太依赖1e18这个大数字，导致更新位置的时候炸long long。
2.如果好几辆车新的位置是相同的，如果又恰好最开始他们的相对位置有相邻在一起，我的排序排完后也还是把他们排到了一起，没有打乱顺序，导致答案错误。只要在cmp函数里加一行判断相等的时候的情况就好了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, mod = 1e9 + 7;
struct node{int p, v, t;bool operator < (const node &k) const {if (p != k.p) return p < k.p;return v > k.v;}
} a[N], b[N];
int fa[N];
int n, k;
int getf(int k)
{if (k == fa[k]) return k;else return fa[k] = getf(fa[k]);
}
int check(int mid)
{for (int i = 1; i <= n; i++){b[i].p = a[i].p + a[i].v * mid;b[i].v = i;b[i].t = getf(i);}sort(b + 1, b + 1 + n);for (int i = 1; i <= n; i++){if (b[i].t != getf(i)) return 1;}return 0;
}
signed main()
{// freopen("data.in","r",stdin);// freopen("data.out","w",stdout);cin >> n >> k;for (int i = 1; i <= n; i++) {scanf("%lld%lld%lld", &a[i].p, &a[i].v, &a[i].t);}sort(a + 1, a + 1 + n);for (int i = 1; i <= n; i++) {fa[i] = i;if (a[i].t == a[i - 1].t) fa[i] = i - 1;}for (int i = 1; i <= n; i++) getf(i);int l = 1, r = 5e9;while(l < r){int mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid + 1;}if (check(l)) cout << l - 1;else cout << -1;return 0;
}C. Strange Test
给定整数a,b，可以执行三种操作：
a++,b++,a|=b
求使得a==b的最小操作次数。
推式子，设a自增一些次数后变x，b自增一些后变y，那么ans=x-a+y-x+(x|y)-y+1。化简后得x+(x|y)-a-b+1。那么只要从a开始顺序枚举，然后构造出y，使得x|y尽量小，更新ans就好了。
由|操作的性质不难构造Y，就四种情况。
看到网上还有一些其他的方法，直接从a开始枚举，如果(i|b) == b，那么ans = min(ans, i - a + 1)；然后再从b开始枚举，如果(a | i ) = = i，那么ans = min(ans, i - b +1)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 1e9 + 7;
signed main()
{int tt;cin >> tt;while(tt--){int a, b;cin >> a >> b;int ans = b - a;for (int i = a; i <= b; i++){int x = 0;for (int j = 32; j >= 0; j--){if ((b>>j) & 1) x += (1ll << j);else if ((i >> j) & 1) {x += (1ll << j);break;}}ans = min(i + (i|x) - a - b + 1, ans);}cout << ans << endl;}return 0;
}B. Range and Partition
好题，一个数组和一个区间[x,y]。让数组其分成k块，每一块都满足：每一块中在区间[x,y]内的数的数量为cnt1，不在的为cnt2，要求cnt1>cnt2。题目要求求出这个区间[x,y]，使得y - x最小。
思路：一小块中在区间内的有cnt1个，这一块长度为len，则cnt1 > len - cnt1，即2 * cnt1 - len >= 1；所有块都满足这个条件，那么合并所有的不等式，就有了 2 * cnt1 - n >= k。
给数组排个序，枚举数组中的每个数为x，然后就能O（logn）或者O（1）的求出y。
O（logn）：直接二分枚举，判断上面的不等式是否满足即可。
O（1）：由不等式可得，cnt1 >= (n + k) / 2，因为是大于号，所以向上取整，所以cnt1 = (n + k + 1) / 2，此时就可以O（1）的求出y了。
求出x和y后，下面的输出怎么划分很简单，不必细说。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 1e9 + 7;
int a[N], b[N];
int n, k;
int sum[N];
int bsh(int x, int l, int r)
{while(l < r){int mid = (l + r) / 2;if (2*(mid - x + 1)-n>=k) r = mid;else l = mid + 1;}if (2 * (l - x + 1) - n >= k) return l;else return -1;
}
signed main()
{int tt;cin >> tt;while(tt--){cin >> n >> k;for (int i = 1; i <= n; i++) {b[i] = a[i] = 0;cin >> a[i];b[i] = a[i];}sort(b + 1, b + 1 + n);int x = 1, y = n;for (int i = 1; i <= n; i++){int pos = bsh(i, i, n);if (pos == -1) continue;if (b[pos] - b[i] < y - x) x = b[i], y = b[pos];}cout << x << " " << y << endl;for (int i = 1; i <= n; i++) {sum[i] = sum[i - 1];if (a[i] >= x && a[i] <= y) sum[i]++;}int last = 0, cnt = 0;for (int i = 1; i <= n; i++) {int cnt1 = 2 * (sum[i] - sum[last]) - (i - last);int cnt2 = 2 * (sum[n] - sum[i]) - (n - i);if (cnt1 > 0 && cnt2 > 0){if (cnt + 1 < k){printf("%lld %lld\n", last + 1, i);last = i;cnt++;}}else if (cnt1 > 0 && cnt + 1 == k) {printf("%lld %lld\n", last + 1, n);break;}}}return 0;
}
C. Road Optimization
题意有点不好说。。上一张题目带的图吧。
Total time is 3⋅5+1⋅8+4⋅3+2⋅6=47 minutes.
然后删除一些路标，求新的最小的时间。
简单dp，cf难度1700的dp好像也不是很难，不过这题主要是确定了状态后，转移的方程式就很好写了。
定义f[i][j]为至以第i个路标结尾，删了j个路标的最小时间。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 500 + 5, mod = 1e9 + 7;
int f[N][N], d[N], a[N];
signed main ()
{int n, l, k;cin >> n >> l >> k;for (int i = 1; i <= n; i++){cin >> d[i];}d[n + 1] = l;for (int i = 1; i <= n; i++){cin >> a[i];}memset(f, 0x3f3f3f3f, sizeof f);f[1][0] = 0;int ans = 1e18;for (int i = 1; i <= n + 1; i++){for (int j = 0; j <= min(k, i - 2); j++){for (int k = i - j - 1, p = 0; k <= i - 1; k++, p++){f[i][j] = min(f[i][j], f[k][p] + a[k] * (d[i] - d[k]));}if (i == n + 1) ans = min(ans, f[i][j]);}}cout << ans;return 0;
}
