引言
没想到现在冬季选拔都这么难了……
题目传送门
本文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|，于是需要进行简单的分类讨论：
-
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)。 -
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，我们需要考虑矩形和线段障碍物的表示。我们发现矩形和线段都可以用一个“代表点”来表示，因此约定：
-
(rkx[x], rky[y])表示点(x, y)右上角，即第一象限的矩形。 -
(rkx[x], rky[y])表示平行x轴线段(rkx[x], rky[y]) -> (rkx[x] + 1, rky[y])。引入w[rkx[x]][rky[y]] = true表示上述线段存在障碍。 -
(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。
接下来推导一下被拦住的条件：
- 从矩形
(x, y)向北走：w[x][y+1] = true。 - 从矩形
(x, y)向东走：h[x+1][y] = true。 - 从矩形
(x, y)向南走：w[x][y] = true。 - 从矩形
(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的点。文章来源：https://www.toymoban.com/news/detail-415543.html
实现上：文章来源地址https://www.toymoban.com/news/detail-415543.html
-
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;
}
到了这里，关于【简单算法】2022SCUACM集训队冬季选拔全题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
