比赛链接:21.7.14-NUAA暑期集训
比赛码:NUAAACM20210714
目录
并查集模板,结果用二进制表示,注意要快读。
#include <cstdio> #include <iostream> using namespace std; int fa[4000010], ans; inline int read() { char ch = getchar(); int ans = 0, f = 1; while (ch < '0' || ch > '9') { if (ch == '-') { f = -1; } ch = getchar(); } while (ch >= '0' && ch <= '9') { ans = (ans << 3) + (ans << 1) + (ch ^ 48); ch = getchar(); } return ans * f; } int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void uni(int x, int y) { int fax = find(x); int fay = find(y); if (fax != fay) { fa[fax] = fay; } } int main() { int n = read(), m = read(); for (int i = 1; i <= n; ++i) { fa[i] = i; } for (int i = 0; i < m; ++i) { int act = read(); if (act == 0) { int x = read(), y = read(); uni(x, y); } else { int x = read(), y = read(); ans = ((ans << 1) + (find(x) == find(y))) % 998244353; } } printf("%d", ans); return 0; }
\(cin,cout\)貌似会超时,要用\(scanf,printf\)或者快读,考察对\(lazy\)标记的使用。
#include <ctype.h> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define ll long long struct node { ll tree, left, right, lazy; } a[4000005]; ll n, m, add, ans, x, y, act; ll read() { char x = getchar(); ll ans = 0LL, f = 1LL; while (!isdigit(x)) { if (x == '-') f = -1LL; x = getchar(); } while (isdigit(x)) { ans = (ans << 3) + (ans << 1) + (x ^ 48); x = getchar(); } return ans * f; } void create(ll l, ll r, ll k) { a[k].lazy = 0, a[k].left = l, a[k].right = r; if (l == r) { a[k].tree = read(); return; } ll mid = (l + r) / 2; create(l, mid, k * 2); create(mid + 1, r, k * 2 + 1); a[k].tree = a[k * 2].tree + a[k * 2 + 1].tree; return; } void load(ll k) { ll l = k * 2, r = k * 2 + 1; a[l].lazy += a[k].lazy; a[r].lazy += a[k].lazy; a[l].tree += a[k].lazy * (a[l].right - a[l].left + 1); a[r].tree += a[k].lazy * (a[r].right - a[r].left + 1); a[k].lazy = 0; return; } void change(ll k) { if (a[k].left >= x && a[k].right <= y) { a[k].tree += add * (a[k].right - a[k].left + 1); a[k].lazy += add; return; } if (a[k].lazy) load(k); ll mid = (a[k].left + a[k].right) / 2; if (x <= mid) change(k * 2); if (y >= mid + 1) change(k * 2 + 1); a[k].tree = a[k * 2].tree + a[k * 2 + 1].tree; return; } void inquery(ll k) { if (a[k].left >= x && a[k].right <= y) { ans += a[k].tree; return; } if (a[k].lazy) load(k); ll mid = (a[k].left + a[k].right) / 2; if (x <= mid) inquery(k * 2); if (y >= mid + 1) inquery(k * 2 + 1); return; } int main() { n = read(); m = read(); create(1, n, 1); while (m--) { act = read(), x = read(), y = read(); if (act == 1) { add = read(); change(1); } if (act == 2) { ans = 0LL; inquery(1); printf("%lld\n", ans); } } return 0; }
树状数组模板,注意要开\(long\) \(long\)。
#include <iostream> #include <cstring> using namespace std; long long bit[1000010]; int n, q, act, l, r; int lowbit(int x) { return x & (-x); } void update(int x, int k) { while (x <= n) { bit[x] += (long long)k; x += lowbit(x); } } long long getSum(int x) { long long ans = 0; while (x > 0) { ans += bit[x]; x -= lowbit(x); } return ans; } int main() { ios::sync_with_stdio(false); while (cin >> n >> q) { memset(bit, 0, sizeof(bit)); for (int i = 1, x; i <= n; ++i) { cin >> x; update(i, x); } while (q--) { cin >> act >> l >> r; if (act == 2) { cout << getSum(r) - getSum(l - 1) << endl; } else { update(l, r); } } } return 0; }
用两个双向队列\(deque\)模拟单调队列来维护区间,一个单调递增,一个单调递减,使当前区间的最大最小值分别出现在两个队列的队首。
#include <cstdio> #include <deque> #include <iostream> using namespace std; int n, k, a[1000010]; int main() { deque<int> maxn, minn; scanf("%d%d", &n, &k); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); } for (int i = 0; i < k; ++i) { // 单调队列 while (!minn.empty() && a[i] < minn.back()) { minn.pop_back(); } minn.push_back(a[i]); while (!maxn.empty() && a[i] > maxn.back()) { maxn.pop_back(); } maxn.push_back(a[i]); } // 窗口移动求最小 for (int i = k; i < n; ++i) { cout << minn.front() << " "; if (minn.front() == a[i - k]) { minn.pop_front(); } while (!minn.empty() && a[i] < minn.back()) { minn.pop_back(); } minn.push_back(a[i]); } cout << minn.front() << " "; cout << endl; // 窗口移动求最大 for (int i = k; i < n; ++i) { cout << maxn.front() << " "; if (maxn.front() == a[i - k]) { maxn.pop_front(); } while (!maxn.empty() && a[i] > maxn.back()) { maxn.pop_back(); } maxn.push_back(a[i]); } cout << maxn.front() << " "; cout << endl; return 0; }
正解是带权并查集,这里选用了一种开三倍并查集的思想。
开了三倍大小的标记数组来表示三个物种,\(1\)到\(n\)为\(A\)物种,\(n+1\)到\(2 \times n\)为\(B\)物种,\(2 \times n + 1\)到\(3 \times n\)为\(C\)物种。
如果\(u\)吃\(v\),则相对的\(u+n\)与\(v\)为一个物种,\(u+2\times n\)与\(v + n\)为一个物种,\(u\)与\(v + 2\times n\)为一个物种。
通过并查集关联同一物种。
#include <iostream> #include <cstdio> #include <ctype.h> using namespace std; #define MAXN 100010 #define INF 100000000 #define ll long long ll read() { // fast read ll ans = 0; int f = 1; char x = getchar(); while (!isdigit(x)) { if (x == '-') f = -1; x = getchar(); } while (isdigit(x)) { ans = (ans << 3) + (ans << 1) + (x ^ 48); x = getchar(); } return ans * f; } int fa[150050], n, k, act, u, v, ans; int find(int x) { // find father return fa[x] == x ? x : fa[x] = find(fa[x]); } int main() { n = read(), k = read(); for (int i = 1; i <= n; ++i) { fa[i] = i; fa[i + n] = i + n; fa[i + n * 2] = i + n * 2; } while (k--) { act = read(), u = read(), v = read(); if (u > n || v > n) { ans++; continue; } else if (act == 1) { if (find(u) == find(v + n) || find(v) == find(u + n)) { ans++; } else { // same father fa[find(u)] = find(v); fa[find(u + n)] = find(v + n); fa[find(u + n * 2)] = find(v + n * 2); } } else { if (find(u) == find(v + n) || find(u) == find(v)) { ans++; } else { // u -> v fa[find(u + n)] = find(v); fa[find(u + n * 2)] = find(v + n); fa[find(u)] = find(v + n * 2); } } } cout << ans; return 0; }
正解如下:
// 带权并查集 #include <cstdio> #include <iostream> using namespace std; int f[50005], d[50005], n, k, d1, x, y, ans; int find(int x) { if (x != f[x]) { int xx = f[x]; f[x] = find(f[x]); d[x] = (d[x] + d[xx]) % 3; } return f[x]; } int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) { f[i] = i; d[i] = 0; } for (int i = 1; i <= k; i++) { scanf("%d%d%d", &d1, &x, &y); if ((d1 == 2 && x == y) || (x > n || y > n)) { ans++; continue; } if (d1 == 1) { if (find(x) == find(y)) { if (d[x] != d[y]) ans++; } else { d[f[x]] = (d[y] - d[x] + 3) % 3; f[f[x]] = f[y]; } } if (d1 == 2) { if (find(x) == find(y)) { if (d[x] != (d[y] + 1) % 3) ans++; } else { d[f[x]] = (d[y] - d[x] + 4) % 3; f[f[x]] = f[y]; } } } printf("%d\n", ans); return 0; }
ST表模板。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int num[50005], minn[50005][50], maxn[50005][50], n, q; void stPreWork() { for (int i = 1; i <= n; ++i) { minn[i][0] = num[i]; maxn[i][0] = num[i]; } for (int j = 1; (1 << j) <= n; ++j) { for (int i = 1; i + (1 << j) - 1 <= n; ++i) { minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]); maxn[i][j] = max(maxn[i][j - 1], maxn[i + (1 << (j - 1))][j - 1]); } } } int stQuery(int l, int r) { int k = 0; while (l + (1 << (k + 1)) - 1 <= r) { k++; } return max(maxn[l][k], maxn[r - (1 << k) + 1][k]) - min(minn[l][k], minn[r - (1 << k) + 1][k]); } int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; ++i) { scanf("%d", &num[i]); } stPreWork(); for (int i = 1, l, r; i <= q; ++i) { scanf("%d%d", &l, &r); printf("%d\n", stQuery(l, r)); } return 0; }
通过并查集来建立信息传递关系。
#include <iostream> using namespace std; int n, fa[200010], ans = 0x3f3f3f3f, cnt, x; int get(int x) { cnt++; return fa[x] == x ? x : get(fa[x]); } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; ++i) { fa[i] = i; } for (int i = 1; i <= n; ++i) { cnt = 0; cin >> x; if (get(x) == i) { ans = min(ans, cnt); } else { fa[i] = x; } } cout << ans; return 0; }
由于任意一个数\(n\)可以表示为\(n=p^{a_1}_1 + {p}^{a_2}_2+...\),\(p_1,p_2...\)为质数。
所以\(n=p_i^{a_i} \times x\),由题意知\(a_i\)只能为\(1\)或\(2\),否则无法拆分出符合条件的情况。
当\(a_i\)为\(1\)时,一个素数有两种拆分方式,所以贡献为\(2\);当\(a_i\)为\(2\)时,只有将一个\(p_i\)分配到\(x\)里去,且\(x\)本身不可整除\(p_i\)时,才能满足条件,因此贡献为\(1\)。
可得到递推式:\(\left\{
\begin{matrix}
&f(n)=2\times f(x),&a_i=1 \\
&f(n)=f(x),&a_i=2 \\
&f(n)=0,&an=3
\end{matrix}
\right.\)。
再用前缀和记录结果。每次查询为\(O(1)\)。
#include <cstdio> #include <iostream> using namespace std; #define N 20000010 bool vis[N]; int f[N], prime[N], T, n; long long sum[N]; void init() { int cnt = 0; f[1] = 1; for (int i = 2; i <= N; ++i) { if (!vis[i]) { prime[++cnt] = i; f[i] = 2; } for (int j = 1; j <= cnt && (prime[j] * i) < N; ++j) { int num = i * prime[j]; vis[num] = true; if (i % prime[j]) { f[num] = 2 * f[i]; } else if (i % (prime[j] * prime[j]) == 0) { f[num] = 0; } else { f[num] = f[i / prime[j]]; break; } } } for (int i = 1; i <= N; ++i) { sum[i] = sum[i - 1] + f[i]; } } int main() { init(); scanf("%d", &T); while (T--) { scanf("%d", &n); printf("%lld\n", sum[n]); } return 0; }