- A. Middle of the Contest
- #include <bits/stdc++.h>
- #define ll long long
- #define inf 0x3f3f3f3f
- #define il inline
- namespace io {
- #define in(a) a = read()
- #define out(a) write(a)
- #define outn(a) out(a), putchar('\n')
- #define I_int ll
- inline I_int read() {
- I_int x = 0, f = 1;
- char c = getchar();
- while (c <'0' || c> '9') {
- if (c == '-') f = -1;
- c = getchar();
- }
- while (c>= '0' && c <= '9') {
- x = x * 10 + c - '0';
- c = getchar();
- }
- return x * f;
- }
- char F[200];
- inline void write(I_int x) {
- if (x == 0) return (void) (putchar('0'));
- I_int tmp = x> 0 ? x : -x;
- if (x <0) putchar('-');
- int cnt = 0;
- while (tmp> 0) {
- F[cnt++] = tmp % 10 + '0';
- tmp /= 10;
- }
- while (cnt> 0) putchar(F[--cnt]);
- }
- #undef I_int
- }
- using namespace io;
- using namespace std;
- #define N 200100
- int m1,m2,h1,h2;
- int main() {
- scanf("%d:%d", &h1, &m1);
- scanf("%d:%d", &h2, &m2);
- int s = h1 * 60 + m1, t = h2 * 60 + m2;
- int mid = (s + t)>> 1, q1 = mid / 60, q2 = mid % 60;
- if(q1 <10) putchar('0'); printf("%d:",q1);
- if(q2 < 10) putchar('0'); printf("%d",q2);
- }
- B. Preparation for International Women's Day
因为 \(d_1+d_2=k\), 所以 \(d_1+d_2\%k=0\).
所以模一下存进对应剩余系里面, 然后对每个对应的剩余系统计一下即可.
- #include <bits/stdc++.h>
- #define ll long long
- #define inf 0x3f3f3f3f
- #define il inline
- namespace io {
- #define in(a) a = read()
- #define out(a) write(a)
- #define outn(a) out(a), putchar('\n')
- #define I_int ll
- inline I_int read() {
- I_int x = 0, f = 1;
- char c = getchar();
- while (c <'0' || c> '9') {
- if (c == '-') f = -1;
- c = getchar();
- }
- while (c>= '0' && c <= '9') {
- x = x * 10 + c - '0';
- c = getchar();
- }
- return x * f;
- }
- char F[200];
- inline void write(I_int x) {
- if (x == 0) return (void) (putchar('0'));
- I_int tmp = x> 0 ? x : -x;
- if (x <0) putchar('-');
- int cnt = 0;
- while (tmp> 0) {
- F[cnt++] = tmp % 10 + '0';
- tmp /= 10;
- }
- while (cnt> 0) putchar(F[--cnt]);
- }
- #undef I_int
- }
- using namespace io;
- using namespace std;
- #define N 200100
- int a[N], n, k, vis[N];
- int main() {
- memset(vis, 0, sizeof(vis));
- in(n); in(k);
- for(int i = 1; i <= n; ++i) in(a[i]), a[i]%=k, vis[a[i]]++;
- int ans = vis[0] / 2;
- if(k % 2 == 0) ans += vis[k / 2] / 2;
- for(int i = 1; i <(k + 1) / 2; ++i) {
- int j = k - i;
- ans += min(vis[i], vis[j]);
- }
- outn(ans*2);
- }
- C. Balanced Team
用双指针搞搞就好了 (因为有单调性).
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <vector>
- #include <queue>
- #include <cmath>
- #include <stack>
- #include <deque>
- #include <map>
- #include <set>
- #define ll long long
- #define inf 0x3f3f3f3f
- #define il inline
- namespace io {
- #define in(a) a = read()
- #define out(a) write(a)
- #define outn(a) out(a), putchar('\n')
- #define I_int ll
- inline I_int read() {
- I_int x = 0, f = 1;
- char c = getchar();
- while (c <'0' || c> '9') {
- if (c == '-') f = -1;
- c = getchar();
- }
- while (c>= '0' && c <= '9') {
- x = x * 10 + c - '0';
- c = getchar();
- }
- return x * f;
- }
- char F[200];
- inline void write(I_int x) {
- if (x == 0) return (void) (putchar('0'));
- I_int tmp = x> 0 ? x : -x;
- if (x <0) putchar('-');
- int cnt = 0;
- while (tmp> 0) {
- F[cnt++] = tmp % 10 + '0';
- tmp /= 10;
- }
- while (cnt> 0) putchar(F[--cnt]);
- }
- #undef I_int
- }
- using namespace io;
- using namespace std;
- #define N 300010
- int n, a[N];
- int main() {
- in(n);
- for(int i = 1; i <= n; ++i) in(a[i]);
- sort(a+1,a+n+1); int ans = 0;
- for(int l = 1, r = 1; l <= n; ++l) {
- while(a[r + 1] - a[l] <= 5 && r <n) ++r;
- ans = max(ans, r - l + 1);
- }
- printf("%d\n", ans);
- }
- D. Zero Quantity Maximization
其实题意就是统计相同的分数有多少个 (直接除 gcd 化成最简分数), 然后对于 0 0 要特殊统计 (一定能计入答案).
注意除 0 什么的就行了, 细节还是挺多的...
- #include <bits/stdc++.h>
- #define ll long long
- #define inf 0x3f3f3f3f
- #define il inline
- namespace io {
- #define in(a) a = read()
- #define out(a) write(a)
- #define outn(a) out(a), putchar('\n')
- #define I_int ll
- inline I_int read() {
- I_int x = 0, f = 1;
- char c = getchar();
- while (c <'0' || c> '9') {
- if (c == '-') f = -1;
- c = getchar();
- }
- while (c>= '0' && c <= '9') {
- x = x * 10 + c - '0';
- c = getchar();
- }
- return x * f;
- }
- char F[200];
- inline void write(I_int x) {
- if (x == 0) return (void) (putchar('0'));
- I_int tmp = x> 0 ? x : -x;
- if (x <0) putchar('-');
- int cnt = 0;
- while (tmp> 0) {
- F[cnt++] = tmp % 10 + '0';
- tmp /= 10;
- }
- while (cnt> 0) putchar(F[--cnt]);
- }
- #undef I_int
- }
- using namespace io;
- using namespace std;
- #define N 200100
- int a[N], b[N], n, m;
- map<pair<int, int>, int>mp;
- int main() {
- in(n); int ans = 0, s = 0;
- for(int i = 1; i <= n; ++i) in(a[i]);
- for(int i = 1; i <= n; ++i) {
- int x = read(), g = __gcd(a[i], x);
- if(!x && !a[i]) {
- ++s; continue;
- }
- if(!a[i]) continue;
- ans = max(ans, ++mp[make_pair(a[i]/g, x/g)]);
- }
- printf("%d\n", ans+s);
- }
- E. K Balanced Teams
设 \(f[i][j]\) 表示前 i 个人, 选了 j 个 team.
考虑继承 \(f[i][j]=f[i-1][j]\)
转移则为 \(f[i][j]=max\{f[k-1][j-1]+i-k+1\}(a[i]-a[k]<=5)\),
注意到 k 有单调性, 那么拿个指针维护一下最远的 k 就可以优化到 \(O(n^2)\) 了.
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <vector>
- #include <queue>
- #include <cmath>
- #include <stack>
- #include <deque>
- #include <map>
- #include <set>
- #define ll long long
- #define inf 0x3f3f3f3f
- #define il inline
- namespace io {
- #define in(a) a = read()
- #define out(a) write(a)
- #define outn(a) out(a), putchar('\n')
- #define I_int ll
- inline I_int read() {
- I_int x = 0, f = 1;
- char c = getchar();
- while (c <'0' || c> '9') {
- if (c == '-') f = -1;
- c = getchar();
- }
- while (c>= '0' && c <= '9') {
- x = x * 10 + c - '0';
- c = getchar();
- }
- return x * f;
- }
- char F[200];
- inline void write(I_int x) {
- if (x == 0) return (void) (putchar('0'));
- I_int tmp = x> 0 ? x : -x;
- if (x <0) putchar('-');
- int cnt = 0;
- while (tmp> 0) {
- F[cnt++] = tmp % 10 + '0';
- tmp /= 10;
- }
- while (cnt> 0) putchar(F[--cnt]);
- }
- #undef I_int
- }
- using namespace io;
- using namespace std;
- #define N 5100
- int vis[N], n, k;
- ll a[N], f[N][N];
- int main() {
- scanf("%d%d", &n, &k);
- for(int i = 1; i <= n; ++i) in(a[i]);
- sort(a+1,a+n+1);
- for(int j = 1; j <= k; ++j) {
- for(int l = 1, i = 1; i <= n; ++i) {
- f[i][j] = f[i - 1][j];
- while(l <i && a[i] - a[l]> 5) ++l;
- f[i][j] = max(f[i][j], f[l - 1][j - 1] + (i - l + 1));
- }
- }
- printf("%lld\n", f[n][k]);
- }
- /*
- f[i][j] 位置 i, 选了 j 个 team
- */
- F1. Spanning Tree with Maximum Degree
题意杀型题目... 题意是让原来度数最大的点, 弄出来生成树后, 度数还是和原来一样, 所以先把与度数最大的那个点连着的边放进生成树里面, 然后类似最小生成树那样用并查集判断是否需要这条边, 选出 n-1 条即可.
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <vector> #include <queue> #include <cmath> #include <stack> #include <deque> #include <map> #include <set> #define ll long long #define inf 0x3f3f3f3f #define il inline namespace io { #define in(a) a = read() #define out(a) write(a) #define outn(a) out(a), putchar('\n') #define I_int ll inline I_int read() { I_int x = 0, f = 1; char c = getchar(); while (c <'0' || c> '9') { if (c == '-') f = -1; c = getchar(); } while (c>= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } char F[200]; inline void write(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x> 0 ? x : -x; if (x <0) putchar('-'); int cnt = 0; while (tmp> 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt> 0) putchar(F[--cnt]); } #undef I_int } using namespace io; using namespace std; #define N 200100 int d[N], n, m; struct edge { int u, v; }e[N]; vector<int>G[N]; int f[N], ans[N][2], cnt; map<pair<int, int> , bool>mp; int find(int x) { if(f[x] == x) return x; return f[x] = find(f[x]); } int main() { in(n), in(m); for(int i = 1; i <= m; ++i) { in(e[i].u), in(e[i].v); d[e[i].u]++; d[e[i].v]++; G[e[i].u].push_back(e[i].v); G[e[i].v].push_back(e[i].u); if(e[i].u> e[i].v) swap(e[i].u, e[i].v); } int id = 0, sum = 0; for(int i = 1; i <= n; ++i) { f[i] = i; if(d[i]> sum) sum = d[i], id = i; } for(int i = 0, len = G[id].size(); i <len; ++i) { int x = find(id), y = find(G[id][i]); f[y] = x; x = id, y = G[id][i]; if(x> y) swap(x, y); ans[++cnt][0] = x, ans[cnt][1] = y; } for(int i = 1; i <= m; ++i) { if(cnt == n - 1) continue; if(mp.count(make_pair(e[i].u, e[i].v))) continue; int x = find(e[i].u), y = find(e[i].v); if(x != y) { f[y] = x; ans[++cnt][0] = e[i].u; ans[cnt][1] = e[i].v; } } for(int i = 1; i <= cnt; ++i) printf("%d %d\n", ans[i][0], ans[i][1]); return 0; } F2. Spanning Tree with One Fixed Degree
先把除了 1 以外的节点并起来, 那么就会出现几个联通块, 显然必须保证 1 到每个联通块都至少有一条边, 那么无解的判定条件就有了, 必须有的边不能超过 d,1 出去的边也不能超过 d. 然后就按类似最小生成树的流程把剩下的给并起来就好了
#include <bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f #define il inline namespace io { #define in(a) a = read() #define out(a) write(a) #define outn(a) out(a), putchar('\n') #define I_int ll inline I_int read() { I_int x = 0, f = 1; char c = getchar(); while (c <'0' || c> '9') { if (c == '-') f = -1; c = getchar(); } while (c>= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } char F[200]; inline void write(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x> 0 ? x : -x; if (x <0) putchar('-'); int cnt = 0; while (tmp> 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt> 0) putchar(F[--cnt]); } #undef I_int } using namespace io; using namespace std; #define N 200100 int d[N], n, m; struct edge { int u, v; }e[N]; int f[N], b[N][2], D, cnt, tot, ans[N][2], vis[N], t[N]; map<pair<int, int> , bool>mp; int find(int x) { if(f[x] == x) return x; return f[x] = find(f[x]); } int main() { in(n), in(m); in(D); for(int i = 1; i <= n; ++i) f[i] = i; for(int i = 1; i <= m; ++i) { in(e[i].u), in(e[i].v); if(e[i].u> e[i].v) swap(e[i].u, e[i].v); if(e[i].u != 1 && e[i].v != 1) { int x = find(e[i].u), y = find(e[i].v); f[y] = x; } else b[++tot][0] = e[i].u, b[tot][1] = e[i].v; } int now = 0; cnt = 0; memset(vis, 0, sizeof(vis)); for(int i = 1; i <= tot; ++i) { if(!vis[find(b[i][1])]) { vis[find(b[i][1])] = 1; ans[++now][0] = b[i][0], ans[now][1] = b[i][1]; mp[make_pair(b[i][0], b[i][1])] = 1; } } if(tot <D) return puts("NO"), 0; if(now> D) return puts("NO"), 0; int l = 1; for(int i = 1; i <= n; ++i) f[i] = i; for(int i = 1; i <= now; ++i) { f[find(ans[i][1])] = find(ans[i][0]); } for(int i = now + 1; i <= D; ++i, ++l) { while(mp.count(make_pair(b[l][0], b[l][1])) && l < tot) ++l; int x = find(b[l][0]), y = find(b[l][1]); f[y] = x; ans[i][0] = b[l][0], ans[i][1] = b[l][1]; } now = D; for(int i = 1; i <= m; ++i) { if(now == n - 1) break; if(e[i].u == 1 || e[i].v == 1) continue; int x = find(e[i].u), y = find(e[i].v); if(x != y) { f[y] = x; ans[++now][0] = e[i].u, ans[now][1] = e[i].v; } } puts("YES"); for(int i = 1; i < n; ++i) printf("%d %d\n", ans[i][0], ans[i][1]); return 0; }
来源: https://www.cnblogs.com/henry-1202/p/10507522.html