本文主要是介绍2024.3.25-26 训练记录（23），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- CF 1385E Directing Edges
- CF 1288D Minimax Problem
- CF 1363E Tree Shuffling
- CF 514C Watto and Mechanism
CF 1385E Directing Edges
题目链接
拓扑排序
首先我们只看有向边组成的图，如果有环那就不可能符合条件，直接no
如果没环就一定符合条件，因为我们知道在拓扑图中，拓扑序小的可以通向拓扑序大的，相反不行，所以我们直接将无向边中拓扑序小的指向大的就可以
#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;vector<vector<int>> g(n + 1);vector<PII> ed;vector<int> ind(n + 1);for (int i = 0; i < m; i ++ ){int op, u, v;cin >> op >> u >> v;if (op == 1){g[u].push_back(v);ind[v] ++ ;}ed.push_back({u, v});}vector<int> top(n + 1, -1);int idx = 0;queue<int> q;for (int i = 1; i <= n; i ++ ){if (ind[i] == 0){q.push(i);top[i] = idx ++ ;}}while (q.size()){auto t = q.front();q.pop();for (int i = 0; i < g[t].size(); i ++ ){int j = g[t][i];ind[j] -- ;if (ind[j] == 0){top[j] = idx ++ ;q.push(j);}}}if (idx != n){cout << "NO\n";return;}cout << "YES\n";for (auto t : ed){int u = t.first, v = t.second;if (top[u] > top[v]) cout << v << ' ' << u << '\n';else cout << u << ' ' << v << '\n';}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}
CF 1288D Minimax Problem
题目链接
二分 + 状压
很有代表性的一题，记住
不是答案具有二段性才能用二分，如果能在二分的时候更新你想要的答案一样可以二分
这题就是，大于等于mid就记为1，否则记为0，然后因为只有八位，完全可以用二进制表示
#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;vector<vector<int>> a(n + 1, vector<int>(m));for (int i = 1; i <= n; i ++ )for (int j = 0; j < m; j ++ )cin >> a[i][j];int l = 0, r = 1e9;int ans1 = 1, ans2 = 1;auto check = [&](int x){int tmp = 0;vector<int> st((1 << m) + 1);for (int i = 1; i <= n; i ++ ){tmp = 0;for (int j = 0; j < m; j ++ ){if (a[i][j] >= x) tmp += (1 << j);}st[tmp] = i;}for (int i = 0; i < (1 << m); i ++ ){for (int j = 0; j < (1 << m); j ++ ){if (st[i] && st[j] && (i | j) == (1 << m) - 1){ans1 = st[i];ans2 = st[j];return true;}}}return false;};while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}cout << ans1 << ' ' << ans2 << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}
CF 1363E Tree Shuffling
题目链接
第三道2000！
首先建图跑dfs，维护当前结点以及上方的最小的代价，再维护每个结点需要1转0和0转1的个数，每次处理小的那个就可以
#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin >> n;vector<int> a(n + 1), b(n + 1), c(n + 1);vector<int> chg1(n + 1), chg0(n + 1), mina(n + 1, INF);for (int i = 1; i <= n; i ++ ) cin >> mina[i] >> b[i] >> c[i];vector<vector<int>> g(n + 1);for (int i = 0; i < n - 1; i ++ ){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}int ans = 0;function<void(int, int)> dfs = [&](int u, int fa){if (b[u] == 0 && c[u] == 1) chg1[u] = 1;else if (b[u] == 1 && c[u] == 0) chg0[u] = 1;for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i];if (j == fa) continue;mina[j] = min(mina[u], mina[j]);dfs(j, u);ans += 2 * min(chg1[j], chg0[j]) * mina[j];int tmp = min(chg1[j], chg0[j]);chg1[j] -= tmp;chg0[j] -= tmp;chg1[u] += chg1[j];chg0[u] += chg0[j];}};dfs(1, 0);ans += 2 * min(chg1[1], chg0[1]) * mina[1];int tmp = min(chg1[1], chg0[1]);chg1[1] -= tmp;chg0[1] -= tmp;if (chg1[1] || chg0[1]){cout << "-1\n";return;}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}
CF 514C Watto and Mechanism
题目链接
这一题的两个收获，一个是学会了字符串哈希，还有接触到了之前没碰到过的字典树上dfs
字符串哈希做法：
#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 3e5 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int base = 131;
const int mod1 = 1e12 + 39;
const int mod2 = 1e9 + 9;
const int INF = 0x3f3f3f3f3f3f3f3f;int n;
int hash_set[N];
int p[N];int hash_cal(string s)
{int res = 0;for (int i = 0; i < s.size(); i ++ )res = (res * base % mod1 + s[i] - 'a') % mod1;return res;
}bool check(string s)
{int res = hash_cal(s);for (int i = 0; i < s.size(); i ++ ){for (int j = 0; j < 3; j ++ ){if (j == s[i] - 'a') continue;int tmp = (res + (j - (s[i] - 'a')) * p[s.size() - i - 1] % mod1 + mod1) % mod1;int pos = lower_bound(hash_set, hash_set + n, tmp) - hash_set;if (hash_set[pos] == tmp) return true;}}return false;
}void solve()
{p[0] = 1;for (int i = 1; i < N; i ++ ) p[i] = p[i - 1] * base % mod1;int m;cin >> n >> m;for (int i = 0; i < n; i ++ ){string s;cin >> s;hash_set[i] = hash_cal(s);}sort(hash_set, hash_set + n);for (int i = 0; i < m; i ++ ){string s;cin >> s;if (check(s)) cout << "YES\n";else cout << "NO\n";}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}
字典树上dfs做法
#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 3e5 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int base = 131;
const int mod1 = 1e12 + 39;
const int mod2 = 1e9 + 9;
const int INF = 0x3f3f3f3f3f3f3f3f;int nxt[N][3], cnt = 1;
bool st[N];void insert(string s)
{int p = 0;for (int i = 0; i < s.size(); i ++ ){int c = s[i] - 'a';if (!nxt[p][c]) nxt[p][c] = cnt ++ ;p = nxt[p][c];}st[p] = true;
}bool check(string& s, int p, int d, bool flag)
{if (d == s.size() && flag && st[p]) return true;if (d >= s.size()) return false;int c = s[d] - 'a';if (nxt[p][c]){if (check(s, nxt[p][c], d + 1, flag)) return true;}if (flag) return false;for (int i = 0; i < 3; i ++ ){if (c == i || !nxt[p][i]) continue;if (check(s, nxt[p][i], d + 1, true)) return true;}return false;
}void solve()
{int n, m;cin >> n >> m;for (int i = 0; i < n; i ++ ){string s;cin >> s;insert(s);}for (int i = 0; i < m; i ++ ){string s;cin >> s;if (check(s, 0, 0, false)) cout << "YES\n";else cout << "NO\n";}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}
这篇关于2024.3.25-26 训练记录（23）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
