网站导航
> 文章列表 > 【简单算法】2022SCUACM集训队冬季选拔全题解

【简单算法】2022SCUACM集训队冬季选拔全题解

网友: 文章列表 2024-03-21 22:41:26

【简单算法】2022SCUACM集训队冬季选拔全题解

文章目录

    • 引言
    • D、F-签到题，略
    • A-Atcoder_abc165_f-树上最长严格上升子序列模板
      • 法一：维护`g`数组+二分查找+撤销操作
      • 法二：线段树
    • B-CF1433D-简单图论构造题
    • C-479E-前缀和优化dp
    • E-CF1620E-并查集
    • G-Atcoder_abc168_f-离散化+bfs
    • H-CF1458A-更相减损法
    • I-CF1184E1-二分答案+最小生成树+LCA
    • J-CF1151B-拆位

引言

没想到现在冬季选拔都这么难了……

题目传送门

本文juejin：https://juejin.cn/post/7222531019319722039/

本文CSDN：https://blog.csdn.net/hans774882968/article/details/130184851

作者：hans774882968以及hans774882968以及hans774882968

D、F-签到题，略

A-Atcoder_abc165_f-树上最长严格上升子序列模板

参考：https://www.cnblogs.com/ycx-akioi/p/AtCoder-abc165.html

最长严格上升子序列树上版本。经典问题有两种做法：树状数组、维护g数组+二分查找。但把问题搬到树上后，我们遇到一个问题：在回溯的时候，需要对数据结构进行撤销操作。所幸这两种数据结构都可以做到。

法一：维护g数组+二分查找+撤销操作

回顾一下经典问题的做法：g[v]表示dp为v的所有点中最小的a值，比如数组2, 3, 100, 99, 98中dp值为3的点为i = 3,4,5，那么g[3] = min(a[3~5]) = 98。可以证明g严格单增。那么我们需要找到最大的idx，使得g[idx] < a[i]，则dp[i] = idx + 1，在实现时，只需要使用lower_bound。更新时，直接覆盖即可：g[dp[i]] = a[i]，通过反证法可以证明覆盖操作的正确性。

对g数组只进行了单点修改，因此只需要记住单点修改前的值，就能完成撤销操作。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)const int N = 2e5 + 5;int n, a[N], dp[N], ans[N], g[N];
vector<int> G[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}void dfs (int u, int ufa) {dp[u] = lower_bound (g, g + n + 1, a[u]) - g;int ori_g = g[dp[u]];g[dp[u]] = a[u];ans[u] = max (dp[u], ans[ufa]);for (int v : G[u]) {if (v != ufa) dfs (v, u);}g[dp[u]] = ori_g;
}int main() {read (n);rep (i, 1, n) read (a[i]);rep (i, 2, n) {int x, y;read (x, y);G[x].push_back (y);G[y].push_back (x);}g[0] = 0;rep (i, 1, n) g[i] = INT_MAX >> 1;dfs (1, 0);rep (i, 1, n) printf ("%d\\n", ans[i]);return 0;
}

法二：线段树

最原始的数据结构C描述如下：vector<int> C[N]的C[v]表示权值v的所有dp值。进入节点：dp[u] = max(max(...C[1~a[u]-1]))，修改操作：C[a[u]].push(dp[u])。出节点前：C[a[u]].erase(dp[u])。信息压缩一下，只保留最大值，则操作描述如下：int C[N]表示权值v的最大dp值，初值取min(...a) - 1即可。进入节点：dp[u] = max(...C[1~a[u]-1])，修改操作：tmpC = C[a[u]], C[a[u]] = max(tmpC, dp[u])。出节点前：if(dp[u] > tmpC) C[a[u]] = tmpC else 无操作。可以发现这里只涉及区间查询和单点修改，用线段树维护即可。

参考链接说需要使用multiset，事实证明也存在不用multiset的做法。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)const int N = 2e5 + 5;int n, a[N], dp[N], ans[N];
vector<int> G[N];int nd[N << 2];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}inline void pushup (int x) {nd[x] = max (nd[ls (x)], nd[rs (x)]);
}void build (int x, int l, int r) {if (l == r) {nd[x] = 0;return;}int mid = (l + r) >> 1;build (ls (x), l, mid);build (rs (x), mid + 1, r);pushup (x);
}void mdy (int p, int v, int x, int l, int r) {if (p == l && r == p) {nd[x] = v;return;}int mid = (l + r) >> 1;if (p <= mid) mdy (p, v, ls (x), l, mid);if (p > mid) mdy (p, v, rs (x), mid + 1, r);pushup (x);
}int qry (int ql, int qr, int x, int l, int r) {if (ql > qr) return 0;if (ql <= l && r <= qr) {return nd[x];}int mid = (l + r) >> 1;int ans = 0;if (ql <= mid) ans = max (ans, qry (ql, qr, ls (x), l, mid) );if (qr > mid) ans = max (ans, qry (ql, qr, rs (x), mid + 1, r) );return ans;
}void dfs (int u, int ufa) {dp[u] = qry (1, a[u] - 1, 1, 1, n) + 1;ans[u] = max (dp[u], ans[ufa]);int tmp_v = qry (a[u], a[u], 1, 1, n);mdy (a[u], max (dp[u], tmp_v), 1, 1, n);for (int v : G[u]) {if (v != ufa) dfs (v, u);}if (dp[u] > tmp_v) mdy (a[u], tmp_v, 1, 1, n);
}void discrete() {vector<int> b (a + 1, a + n + 1);sort (b.begin(), b.end() );b.resize (unique (b.begin(), b.end() ) - b.begin() );rep (i, 1, n) a[i] = lower_bound (b.begin(), b.end(), a[i]) - b.begin() + 1;
}int main() {read (n);rep (i, 1, n) read (a[i]);discrete();rep (i, 2, n) {int x, y;read (x, y);G[x].push_back (y);G[y].push_back (x);}build (1, 1, n);dfs (1, 0);rep (i, 1, n) printf ("%d\\n", ans[i]);return 0;
}

B-CF1433D-简单图论构造题

首先，按照“邮编号”开桶。如果只有1个桶，则输出NO；否则输出YES：我们任选其中一个桶b0，再选择里面的一个点b0[0]，连接b0[0]和桶外所有点，接着选择一个不同的桶b1，连接b1[0]和b0里b0[0]以外的所有点。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 1e4 + 5;int n, a[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int main() {int T;read (T);while (T--) {read (n);map<int, vector<int>> mp;rep (i, 1, n) {read (a[i]);mp[a[i]].push_back (i);}if (mp.size() == 1) {puts ("NO");continue;}puts ("YES");int tmp = 0, u[2];for (auto x : mp) {u[tmp] = x.second[0];if ( (++tmp) >= 2) break;}int val0 = a[u[0]], val1 = a[u[1]];rep (i, 1, n) {if (a[i] != val1) {printf ("%d %d\\n", u[1], i);}}rep (i, 1, n) {if (i != u[1] && a[i] == val1) {printf ("%d %d\\n", u[0], i);}}}return 0;
}

C-479E-前缀和优化dp

一看就是计数dp的题，但第一眼看到这题，会有使用刷表法的冲动。但使用刷表法需要进行区间修改，似乎要动用线段树。所以我们还是抑制住冲动，看普通的打表法能否解决。

定义dp[i][j]为运行了i次电梯且停留在j层的方案数。于是有边界条件：dp[i][0] = dp[i][b] = 0, dp[0][a] = 1。为了获得状态转移方程，需要考虑哪些楼层x能到j层，即需要解|x-j| < |x-b|，于是需要进行简单的分类讨论：

  1. j < b。首先有x <= j-1。然后令x-j = b-x，得x = (b+j)/2。如果b+j是偶数，则为j < x <= (b+j)/2-1；奇数则为j < x <= (b+j)/2-0.5。归纳得j < x <= floor((b+j-1)/2)。
  2. j > b。首先有j+1 <= x <= n。然后令x-b = j-x，得x = (b+j)/2。如果b+j是偶数，则为(b+j)/2+1 <= x < j；奇数则为(b+j)/2+0.5。归纳得floor((b+j)/2)+1 <= x < j。

综上，为了求出dp[i]数组，只需要支持查询dp[i-1]这个数组的区间和。我们同时维护dp数组和前缀和数组s即可。

另外，dp, s数组显然都可以滚动优化，这题不卡空间我就不写了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 5e3 + 5;
const int mod = 1e9 + 7;int n, a, b, k, dp[N][N], s[N][N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int main() {read (n, a, b, k);dp[0][a] = 1;rep (i, 1, n) s[0][i] = (s[0][i - 1] + dp[0][i]) % mod;rep (i, 1, k) {rep (j, 1, n) {if (j == b) continue;if (j < b) {dp[i][j] = ( (s[i - 1][j - 1] + s[i - 1][ (b + j - 1) / 2] - s[i - 1][j]) % mod + mod) % mod;} else {dp[i][j] = ( (s[i - 1][n] - s[i - 1][j] + s[i - 1][j - 1] - s[i - 1][ (b + j) / 2]) % mod + mod) % mod;}}rep (j, 1, n) s[i][j] = (s[i][j - 1] + dp[i][j]) % mod;}printf ("%d\\n", s[k][n]);return 0;
}

E-CF1620E-并查集

操作2“值为x的都替换为y”可以理解为集合的合并，因此可以考虑用并查集。但我们需要知道至少一个值为x的数的下标，所以需要引入一个mp哈希表，mp[x]表示某一个值为x的数的下标。接下来，考虑到需要输出答案，我们需要维护并查集的val数组，val[find(i)]表示下标i的数值，但只能查询集合的代表元find(i)得到。

维护mp的时候要小心，不要把预期应该存在的键值对给删除了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 5e5 + 5;int n = 0, fa[N], val[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int find (int x) {return x == fa[x] ? x : (fa[x] = find (fa[x]) );
}int main() {int q;read (q);map<int, int> mp;while (q--) {int op, x, y;read (op);if (op == 1) {read (x);++n;if (mp.count (x) ) {fa[n] = fa[find (mp[x])];} else {mp[x] = n;fa[n] = n;val[n] = x;}} else {read (x, y);if (!mp.count (x) ) continue;int idx_x = mp[x];if (mp.count (y) ) {int fx = find (idx_x), fy = find (mp[y]);if (fx != fy) {fa[fx] = fy;}}mp.erase (x);val[find (idx_x)] = y;mp[y] = idx_x;}}rep (i, 1, n) printf ("%d%c", val[find (i)], " \\n"[i == n]);return 0;
}

G-Atcoder_abc168_f-离散化+bfs

这题我不会，参考：https://blog.csdn.net/C2022lihan/article/details/118713084。代码比较整洁。

首先是离散化：把所有出现过的x和y坐标值分别进行离散化，记为rkx, rky数组。这样我们就认为整个平面被划分为若干个矩形，每个矩形的面积不一定是1。接下来我们只需要实现一个标准BFS。但为了实现BFS，我们需要考虑矩形和线段障碍物的表示。我们发现矩形和线段都可以用一个“代表点”来表示，因此约定：

  1. (rkx[x], rky[y])表示点(x, y)右上角，即第一象限的矩形。
  2. (rkx[x], rky[y])表示平行x轴线段(rkx[x], rky[y]) -> (rkx[x] + 1, rky[y])。引入w[rkx[x]][rky[y]] = true表示上述线段存在障碍。
  3. (rkx[x], rky[y])表示平行y轴线段(rkx[x], rky[y]) -> (rkx[x], rky[y] + 1)。引入h[rkx[x]][rky[y]] = true表示上述线段存在障碍。

于是一条水平线段障碍物(rkx[x1], rky[y]) -> (rkx[x2], rky[y])需要设置w[rkx[x1]~rkx[x2]-1][rky[y]] = true，一条竖直线段障碍物(rkx[x], rky[y1]) -> (rkx[x], rky[y2])需要设置h[rkx[x]][rky[y1]~rky[y2]-1] = true。

接下来推导一下被拦住的条件：

  1. 从矩形(x, y)向北走：w[x][y+1] = true。
  2. 从矩形(x, y)向东走：h[x+1][y] = true。
  3. 从矩形(x, y)向南走：w[x][y] = true。
  4. 从矩形(x, y)向西走：w[x][y] = true。

最后考虑一下面积无穷的判定。因为离散化会产生vx, vy数组，所以我们在更新面积前，发现这两个数组有越界的情况，就是面积无穷。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 3e3 + 5;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};int n, m, w[N][N], h[N][N];
vector<int> vx, vy;
vector<vector<int>> tmp1, tmp2;
bool vis[N][N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int find_x (int v) {return lower_bound (vx.begin(), vx.end(), v) - vx.begin();
}int find_y (int v) {return lower_bound (vy.begin(), vy.end(), v) - vy.begin();
}int main() {read (n, m);vx.push_back (0);vy.push_back (0);rep (i, 1, n) {int x, y, z;read (x, y, z);vx.push_back (x);vx.push_back (y);vy.push_back (z);tmp1.push_back ({x, y, z});}rep (i, 1, m) {int x, y, z;read (x, y, z);vx.push_back (x);vy.push_back (y);vy.push_back (z);tmp2.push_back ({x, y, z});}sort (vx.begin(), vx.end() );sort (vy.begin(), vy.end() );vx.resize (unique (vx.begin(), vx.end() ) - vx.begin() );vy.resize (unique (vy.begin(), vy.end() ) - vy.begin() );re_ (i, 0, n) {int x = find_x (tmp1[i][0]), y = find_x (tmp1[i][1]), z = find_y (tmp1[i][2]);re_ (j, x, y) w[j][z] = true;}re_ (i, 0, m) {int x = find_x (tmp2[i][0]), y = find_y (tmp2[i][1]), z = find_y (tmp2[i][2]);re_ (j, y, z) h[x][j] = true;}queue<pii> q;int sx = find_x (0), sy = find_y (0);q.push ({sx, sy});vis[sx][sy] = true;LL ans = 0;while (!q.empty() ) {pii u = q.front();q.pop();int x = u.first, y = u.second;ans += 1LL * (vx[x + 1] - vx[x]) * (vy[y + 1] - vy[y]);re_ (i, 0, 4) {int nx = x + dx[i], ny = y + dy[i];if (i == 0 && w[nx][ny]) continue;if (i == 1 && h[nx][ny]) continue;if (i == 2 && w[x][y]) continue;if (i == 3 && h[x][y]) continue;if (nx < 0 || nx + 1 >= vx.size() || ny < 0 || ny + 1 >= vy.size() ) {puts ("INF");return 0;}if (vis[nx][ny]) continue;vis[nx][ny] = true;q.push ({nx, ny});}}printf ("%lld\\n", ans);return 0;
}

H-CF1458A-更相减损法

gcd的题，除了考虑辗转相除法和质因数，偶尔也要考虑更相减损法，尤其是碰到加法的时候。我们把b视为变量，a视为常量，由gcd(x,y) = gcd(y, x-y)：

(a[1]+b[1], a[2]+b[1]) = (a[2]+b[1], a[1]-a[2])
(a[2]+b[1], a[3]+b[1]) = (a[3]+b[1], a[2]-a[3])
(a[3]+b[1], a[4]+b[1]) = (a[4]+b[1], a[3]-a[2])
((...a[1~4]+b[1])) = (a[2]+b[1], a[3]+b[1], a[4]+b[1], g0)

可以看到，问题规模减少1，而g0是只与a有关的常量。问题规模再度减少时，我们发现所得的差值也都是a[i]-a[i+1]的形式，所以g0在问题规模减少的过程中始终不变。于是ans[j] = (g0, a[1]+b[j])。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 2e5 + 5;int n, m;
LL a[N], b[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int main() {read (n, m);rep (i, 1, n) read (a[i]);rep (i, 1, m) read (b[i]);sort (a + 1, a + n + 1);LL g0 = 0;dwn (i, n, 2) g0 = __gcd (g0, a[i] - a[i - 1]);rep (i, 1, m) printf ("%lld%c", __gcd (g0, a[1] + b[i]), " \\n"[i == m]);return 0;
}

I-CF1184E1-二分答案+最小生成树+LCA

坦白说这题我看不懂题解，所以用了自己的做法……首先考虑二分答案。对于当前边权mid，我们先任求一个MST，然后考虑连接一号边(u, v)（即使已经在MST也可以做这个假想操作）。这样会构成一个环，从u到v的唯一路径的边权最大值大于等于mid等价于当前边权可行。

这个做法的思想是非常朴素的，所以代码量也是比较大的，很符合题目名。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 1e5 + 5;int n, m, dep[N], fa[N], par[N], wei[N];
vector<pii> G[N];struct E {int u, v, w;bool operator < (const E &rhs) const {return w < rhs.w;}
};
vector<E> edg, ori;void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int find (int x) {return x == fa[x] ? x : (fa[x] = find (fa[x]) );
}void dfs (int u, int ufa, int w = 0) {dep[u] = dep[ufa] + 1;par[u] = ufa;wei[u] = w;for (auto x : G[u]) {int v = x.first;if (v == ufa) continue;dfs (v, u, x.second);}
}bool jdg (int mid) {edg = ori;edg[0].w = mid;sort (edg.begin(), edg.end() );rep (i, 1, n) fa[i] = i;rep (i, 1, n) G[i].clear();int e_cnt = 0;for (auto x : edg) {int fu = find (x.u), fv = find (x.v);if (fu == fv) continue;G[x.u].push_back ({x.v, x.w});G[x.v].push_back ({x.u, x.w});fa[fu] = fv;if ( (++e_cnt) >= n - 1) break;}dfs (1, 0);int u = ori[0].u, v = ori[0].v;if (dep[u] < dep[v]) swap (u, v);int mx_w = 0;while (dep[u] > dep[v]) mx_w = max (mx_w, wei[u]), u = par[u];while (u != v) {mx_w = max ({mx_w, wei[u], wei[v]});u = par[u];v = par[v];}return mx_w >= mid;
}int main() {read (n, m);rep (_, 1, m) {int u, v, w;read (u, v, w);ori.push_back ({u, v, w});}int l = 0, r = 1000000000;while (l < r) {int mid = (l + r + 1) >> 1;if (jdg (mid) ) l = mid;else r = mid - 1;}printf ("%d\\n", r);return 0;
}

J-CF1151B-拆位

拆位以后考虑起来就简单了：拆位后矩阵为01矩阵，如果存在某个位能够满足异或等于1，则这一位的方案就是一种可行方案。

对于全是0和全是1的列，计算一个bas。接下来分类讨论：bas == 0，则要求存在至少1个既有0又有1的列；否则已经满足。为了实现简单，可以考虑把判定过程和求答案的过程分开写，而不是耦合地写。接下来对于有答案的情况，我构造了一种可行的方案：如果bas == 0，对于既有0又有1的列全部任选一个为0的点即可；如果bas == 1，对于既有0又有1的列，第一次遇到就去任选一个为1的点，否则去任选一个为0的点。

实现上：

  1. typ[n]数组表示第i行的类型，既有1又有0、只有0、只有1。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)const int N = 500 + 5;int n, m, a[N][N], typ[N];void dbg() {puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {cout << f << " ";dbg (r...);
}
template<typename Type>inline void read (Type &xx) {Type f = 1;char ch;xx = 0;for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {read (x);read (r...);
}int main() {read (n, m);rep (i, 1, n) rep (j, 1, m) read (a[i][j]);vector<int> ans;re_ (k, 0, 10) {int bas = 0, free_cnt = 0;rep (i, 1, n) {int x0 = -1, y0 = -1, x1 = -1, y1 = -1;rep (j, 1, m) {if (a[i][j] >> k & 1) {x1 = i;y1 = j;} else {x0 = i;y0 = j;}}if ( (~x0) && (~x1) ) {++free_cnt;typ[i] = 3;} else if (~x1) {bas ^= 1;typ[i] = 2;} else {typ[i] = 1;}}if (bas) {rep (i, 1, n) {if (typ[i] == 3) {rep (j, 1, m) if (! (a[i][j] >> k & 1) ) {ans.push_back (j);break;}} else {ans.push_back (1);}}break;} else if (free_cnt) {bool met_free = false;rep (i, 1, n) {if (typ[i] == 3) {if (!met_free) {met_free = true;rep (j, 1, m) if (a[i][j] >> k & 1) {ans.push_back (j);break;}} else {rep (j, 1, m) if (! (a[i][j] >> k & 1) ) {ans.push_back (j);break;}}} else {ans.push_back (1);}}break;}}if (ans.size() ) {puts ("TAK");re_ (i, 0, ans.size() ) printf ("%d%c", ans[i], " \\n"[i + 1 == ans.size()]);} else {puts ("NIE");}return 0;
}
网络标签：

相关问题