2024.3.25-26 训练记录(23)

2024-04-02 08:52
文章标签 训练 记录 25 23 26 2024.3

本文主要是介绍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)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/869529

相关文章

apache的commons-pool2原理与使用实践记录

《apache的commons-pool2原理与使用实践记录》ApacheCommonsPool2是一个高效的对象池化框架,通过复用昂贵资源(如数据库连接、线程、网络连接)优化系统性能,这篇文章主... 目录一、核心原理与组件二、使用步骤详解(以数据库连接池为例)三、高级配置与优化四、典型应用场景五、注意事

SpringBoot实现文件记录日志及日志文件自动归档和压缩

《SpringBoot实现文件记录日志及日志文件自动归档和压缩》Logback是Java日志框架,通过Logger收集日志并经Appender输出至控制台、文件等,SpringBoot配置logbac... 目录1、什么是Logback2、SpringBoot实现文件记录日志,日志文件自动归档和压缩2.1、

qtcreater配置opencv遇到的坑及实践记录

《qtcreater配置opencv遇到的坑及实践记录》我配置opencv不管是按照网上的教程还是deepseek发现都有些问题,下面是我的配置方法以及实践成功的心得,感兴趣的朋友跟随小编一起看看吧... 目录电脑环境下载环境变量配置qmake加入外部库测试配置我配置opencv不管是按照网上的教程还是de

使用nohup和--remove-source-files在后台运行rsync并记录日志方式

《使用nohup和--remove-source-files在后台运行rsync并记录日志方式》:本文主要介绍使用nohup和--remove-source-files在后台运行rsync并记录日... 目录一、什么是 --remove-source-files?二、示例命令三、命令详解1. nohup2.

Linux搭建单机MySQL8.0.26版本的操作方法

《Linux搭建单机MySQL8.0.26版本的操作方法》:本文主要介绍Linux搭建单机MySQL8.0.26版本的操作方法,本文通过图文并茂的形式给大家讲解的非常详细,感兴趣的朋友一起看看吧... 目录概述环境信息数据库服务安装步骤下载前置依赖服务下载方式一:进入官网下载,并上传到宿主机中,适合离线环境

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

在Spring Boot中浅尝内存泄漏的实战记录

《在SpringBoot中浅尝内存泄漏的实战记录》本文给大家分享在SpringBoot中浅尝内存泄漏的实战记录,结合实例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录使用静态集合持有对象引用,阻止GC回收关键点:可执行代码:验证:1,运行程序(启动时添加JVM参数限制堆大小):2,访问 htt

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢?我尝试一种更为智能的方法:P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验,

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio