A:枚举一下就行了...居然wa了一发，题目一定要看清
#include<bits/stdc++.h> using namespace std; int n; int main() { cin >> n; int mid = n / 2 - ((n & 1) == 0); for(int i = n / 2; i; --i) { if(__gcd(i, n - i) == 1) { printf("%d %d ", i, n - i); return 0; } } return 0; }
B:这道题有点恶心，就是判断当前能不能每三个点有一个居民，判断一下就可以了
#include<bits/stdc++.h> using namespace std; int n, k; int main() { cin >> n >> k; if(k == 0) { puts("0 0"); return 0; } if(n == k || k == 0) printf("0 "); else printf("1 "); int tmp1 = (n + 1) / 2, tmp2 = (n + 2) / 3, t = n % 3; if(k < tmp2) printf("%d ", k * 2); else printf("%d ", n - k); return 0; }
C:这种题只能贪心吧，似乎cf这种配对题都是贪心，开个set查询前继后继
#include<bits/stdc++.h> using namespace std; const int N = 300010; struct data { long long c; int id; bool friend operator < (data a, data b) { return a.c > b.c; } } a[N]; int n, k; int answer[N]; set<long long> s; int main() { cin >> n >> k; for(int i = 1; i <= n; ++i) scanf("%lld", &a[i].c), a[i].id = i, s.insert(i + k); sort(a + 1, a + n + 1); long long ans = 0; for(int i = 1; i <= n; ++i) { long long t1 = *(s.lower_bound(a[i].id)), t2 = *(s.upper_bound(a[i].id)), tmp; if(abs(a[i].id - t1) < abs(a[i].id - t2)) tmp = t1; else tmp = t2; s.erase(tmp); ans += abs(a[i].id - tmp) * a[i].c; answer[a[i].id] = tmp; } cout << ans << endl; for(int i = 1; i <= n; ++i) printf("%d ", answer[i]); return 0; }
D:考试时想了会弃了...觉得大概是枚举一下...事实上枚举一下维护前缀后缀和就行了
#include<bits/stdc++.h> using namespace std; const int N = 1000010; const long long inf = 1000000010; struct data { int pos, cost; data(int pos, int cost) : pos(pos), cost(cost) {} }; vector<data> v1[N], v2[N]; int n, m, k, day, cnt; int vis[N], can1[N], can2[N]; long long sum; long long sum1[N], sum2[N], mn[N]; int main() { cin >> n >> m >> k; for(int i = 1; i <= m; ++i) { int d, f, t, c; scanf("%d%d%d%d", &d, &f, &t, &c); day = max(day, d); if(t == 0) v1[d].push_back(data(f, c)); else v2[d].push_back(data(t, c)); } for(int i = 1; i <= n; ++i) mn[i] = inf, sum += inf; for(int i = 1; i <= day; ++i) { for(int j = 0; j < v1[i].size(); ++j) { data tmp = v1[i][j]; if(tmp.cost < mn[tmp.pos]) { sum -= mn[tmp.pos]; sum += tmp.cost; mn[tmp.pos] = tmp.cost; } if(vis[tmp.pos] == 0) { vis[tmp.pos] = 1; ++cnt; } } sum1[i] = sum; if(cnt == n) can1[i] = 1; // printf("cnt = %d sum1[%d] = %lld can1[%d] = %d ", cnt, i, sum1[i], i, can1[i]); } memset(vis, 0, sizeof(vis)); sum = 0; cnt = 0; for(int i = 1; i <= n; ++i) mn[i] = inf, sum += inf; for(int i = day; i ; --i) { for(int j = 0; j < v2[i].size(); ++j) { data tmp = v2[i][j]; if(tmp.cost < mn[tmp.pos]) { sum -= mn[tmp.pos]; sum += tmp.cost; mn[tmp.pos] = tmp.cost; } if(vis[tmp.pos] == 0) { vis[tmp.pos] = 1; ++cnt; } } sum2[i] = sum; if(cnt == n) can2[i] = 1; // printf("cnt = %d sum2[%d] = %lld can2[%d] = %d ", cnt, i, sum2[i], i, can2[i]); } long long ans = 1ll << 60; // puts("------------------------"); for(int i = 1; i <= day - k + 1; ++i) { // printf("can1[%d] = %d can2[%d] = %d ", i, can1[i], i + k + 1, can2[i + k + 1]); if(can1[i] && can2[i + k + 1]) ans = min(ans, sum1[i] + sum2[i + k + 1]); } cout << ((ans == 1ll << 60) ? -1 : ans) << endl; return 0; }
E:考试时候石乐志觉得主席树爆空间...写了个莫队...然后错了...发现题目看错莫队做不了GG...其实很简单，静态查询区间点数,主席树维护一下，然后容斥做一下加减法就行了
#include<bits/stdc++.h> using namespace std; const int N = 200010; int size[N * 30], lc[N * 30], rc[N * 30], root[N]; int n, q, cnt; void update(int l, int r, int &x, int last, int pos) { size[x = ++ cnt] = size[last] + 1; lc[x] = lc[last]; rc[x] = rc[last]; if(l == r) return; int mid = (l + r) >> 1; if(pos <= mid) update(l, mid, lc[x], lc[last], pos); else update(mid + 1, r, rc[x], rc[last], pos); } int query(int l, int r, int x, int y, int a, int b) { if(l > b || r < a) return 0; if(l >= a && r <= b) return size[x] - size[y]; int mid = (l + r) >> 1; return (query(l, mid, lc[x], lc[y], a, b) + query(mid + 1, r, rc[x], rc[y], a, b)); } int main() { cin >> n >> q; for(int i = 1; i <= n; ++i) { int x; scanf("%d", &x); update(1, n, root[i], root[i - 1], x); } while(q --) { int l, d, r, u; scanf("%d%d%d%d", &l, &d, &r, &u); long long ans = (long long)n * (long long)(n - 1) / 2ll, tmp; tmp = query(1, n, root[n], root[0], 1, d - 1); ans -= tmp * (tmp - 1) / 2ll; tmp = query(1, n, root[n], root[0], u + 1, n); ans -= tmp * (tmp - 1) / 2ll; tmp = query(1, n, root[l - 1], root[0], 1, n); ans -= tmp * (tmp - 1) / 2ll; tmp = query(1, n, root[n], root[r], 1, n); ans -= tmp * (tmp - 1) / 2ll; tmp = query(1, n, root[n], root[r], u + 1, n); ans += tmp * (tmp - 1) / 2ll; tmp = query(1, n, root[l - 1], root[0], u + 1, n); ans += tmp * (tmp - 1) / 2ll; tmp = query(1, n, root[n], root[r], 1, d - 1); ans += tmp * (tmp - 1) / 2ll; tmp = query(1, n, root[l - 1], root[0], 1, d - 1); ans += tmp * (tmp - 1) / 2ll; printf("%lld ", ans); } return 0; }