2024.2.29 训练记录（4）

2024-03-01 15:12
文章标签 训练 记录 29 2024.2

本文主要是介绍2024.2.29 训练记录（4），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • CF 1933F Turtle Mission: Robot and the Earthquake
  • CF 1933G Turtle Magic: Royal Turtle Shell Pattern
  • CF 1826D Running Miles
  • CF 1820D The Butcher
  • CF 1768C Elemental Decompress

CF 1933F Turtle Mission: Robot and the Earthquake

题目链接

bfs，把图当做不动的，那么往下走就相当于往下两步，往右走就相当于往右下方走，往上走就相当于不动，当走到最后一列的时候再计算走到终点需要多少步（每走一步终点的相对位置都下移一格，根据走的步数可以推断人在最后一列时终点在哪一行）

debug里发现的一个易错点是：更新st数组的时候要在距离改变了之后再更新，距离没改变就不更新！！！

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int dx[] = {1, 2, 0}, dy[] = {1, 0, 0};void solve()
{int n, m;cin >> n >> m;vector<vector<int>> g(n, vector<int>(m));for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )cin >> g[i][j];queue<PIII> q;q.push({0, {0, 0}});vector<vector<int>> dist(n, vector<int>(m, INF));vector<vector<bool>> st(n, vector<bool>(m));st[0][0] = true;dist[0][0] = 0;int ans = INF;while (q.size()){auto t = q.front();q.pop();int x = t.second.first, y = t.second.second, d = t.first;if (y == m - 1){int end = (n - 1 + d) % n;if (end == x) ans = min(ans, dist[x][y]);else if (end > x) ans = min(ans, dist[x][y] + min(end - x, n - (end - x)));else ans = min(ans, dist[x][y] + min(x - end, n - (x - end)));continue;}for (int i = 0; i < 3; i ++ ){int nx = (x + dx[i]) % n, ny = y + dy[i];if (ny >= m) continue;if (st[nx][ny]) continue;if (i == 0){if (g[nx][ny] == 1) continue;if (dist[nx][ny] > d + 1){st[nx][ny] = true;dist[nx][ny] = d + 1;q.push({d + 1, {nx, ny}});}}else if (i == 1){if ((x == n - 1 && (g[0][y] == 1 || g[1][y] == 1)) || (x == n - 2 && (g[n - 1][y] == 1 || g[0][y] == 1)) || (x != n - 1 && x != n - 2 && (g[x + 1][y] == 1 || g[x + 2][y] == 1))) continue;if (dist[nx][ny] > d + 1){st[nx][ny] = true;dist[nx][ny] = d + 1;q.push({d + 1, {nx, ny}});}}else if (i == 2){if (dist[nx][ny] > dist[x][y] + 1){st[nx][ny] = true;dist[nx][ny] = dist[x][y] + 1;q.push({d + 1, {nx, ny}});}}}}if (ans != INF) cout << ans << '\n';else cout << -1 << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

CF 1933G Turtle Magic: Royal Turtle Shell Pattern

题目链接

又是喜闻乐见的找规律…

首先可以证明一定是两个两个连在一起（反证法画一下图就好了），就像是这样（下面这个例子是行的，列也可以）

xxoox
ooxxo
xxoox
ooxxo

所以最多只会有八种情况（行和列各四种），取模鉴定为诈骗

所以每添加一个直接判断会不会让哪一种情况无了就可以

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 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()
{// circle为0 square为1int n, m, q;cin >> n >> m >> q;cout << 8 << '\n';int ans = 8;vector<bool> st(9);while (q -- ){int a, b;string s;cin >> a >> b >> s;for (int i = 1; i < 9; i ++ ){if (st[i]) continue;if (i == 1){if (a % 2 == 1 && (b + 1) / 2 % 2 == 0 && s[0] == 'c') continue;else if (a % 2 == 1 && (b + 1) / 2 % 2 != 0 && s[0] == 's') continue;else if (a % 2 == 0 && (b + 1) / 2 % 2 == 0 && s[0] == 's') continue;else if (a % 2 == 0 && (b + 1) / 2 % 2 != 0 && s[0] == 'c') continue;else st[i] = true, ans -- ;}else if (i == 2){if (a % 2 == 1 && (b + 1) / 2 % 2 == 0 && s[0] == 's') continue;else if (a % 2 == 1 && (b + 1) / 2 % 2 != 0 && s[0] == 'c') continue;else if (a % 2 == 0 && (b + 1) / 2 % 2 == 0 && s[0] == 'c') continue;else if (a % 2 == 0 && (b + 1) / 2 % 2 != 0 && s[0] == 's') continue;else st[i] = true, ans -- ;}else if (i == 3){if (a % 2 == 1 && b / 2 % 2 == 0 && s[0] == 's') continue;else if (a % 2 == 1 && b / 2 % 2 != 0 && s[0] == 'c') continue;else if (a % 2 == 0 && b / 2 % 2 == 0 && s[0] == 'c') continue;else if (a % 2 == 0 && b / 2 % 2 != 0 && s[0] == 's') continue;else st[i] = true, ans -- ;}else if (i == 4){if (a % 2 == 1 && b / 2 % 2 == 0 && s[0] == 'c') continue;else if (a % 2 == 1 && b / 2 % 2 != 0 && s[0] == 's') continue;else if (a % 2 == 0 && b / 2 % 2 == 0 && s[0] == 's') continue;else if (a % 2 == 0 && b / 2 % 2 != 0 && s[0] == 'c') continue;else st[i] = true, ans -- ;}else if (i == 5){if (b % 2 == 1 && (a + 1) / 2 % 2 == 1 && s[0] == 's') continue;else if (b % 2 == 1 && (a + 1) / 2 % 2 == 0 && s[0] == 'c') continue;else if (b % 2 == 0 && (a + 1) / 2 % 2 == 1 && s[0] == 'c') continue;else if (b % 2 == 0 && (a + 1) / 2 % 2 == 0 && s[0] == 's') continue;else st[i] = true, ans -- ;}else if (i == 6){if (b % 2 == 1 && (a + 1) / 2 % 2 == 1 && s[0] == 'c') continue;else if (b % 2 == 1 && (a + 1) / 2 % 2 == 0 && s[0] == 's') continue;else if (b % 2 == 0 && (a + 1) / 2 % 2 == 1 && s[0] == 's') continue;else if (b % 2 == 0 && (a + 1) / 2 % 2 == 0 && s[0] == 'c') continue;else st[i] = true, ans -- ;}else if (i == 7){if (b % 2 == 1 && a / 2 % 2 == 1 && s[0] == 's') continue;else if (b % 2 == 1 && a / 2 % 2 == 0 && s[0] == 'c') continue;else if (b % 2 == 0 && a / 2 % 2 == 1 && s[0] == 'c') continue;else if (b % 2 == 0 && a / 2 % 2 == 0 && s[0] == 's') continue;else st[i] = true, ans -- ;}else if (i == 8){if (b % 2 == 1 && a / 2 % 2 == 1 && s[0] == 'c') continue;else if (b % 2 == 1 && a / 2 % 2 == 0 && s[0] == 's') continue;else if (b % 2 == 0 && a / 2 % 2 == 1 && s[0] == 's') continue;else if (b % 2 == 0 && a / 2 % 2 == 0 && s[0] == 'c') continue;else st[i] = true, ans -- ;}}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 1826D Running Miles

题目链接

一开始以为是区间dp，然后发现数据范围根本不能开二维数组qwq

题目要求 a[l] + a[k] + a[r] - (r - l)

转化一下 a[l] + l + a[k] + a[r] - r

处理一下 a[i] + i 和 a[i] - i ，再枚举 k 就行了

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;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);for (int i = 1; i <= n; i ++ ) cin >> a[i];vector<int> b(n + 1), c(n + 1);for (int i = 1; i <= n; i ++ ){b[i] = a[i] + i;c[i] = a[i] - i;}vector<int> maxb(n + 1), maxc(n + 1);int tmp1 = b[1], tmp2 = c[n];for (int i = 2; i <= n; i ++ ){maxb[i] = tmp1;tmp1 = max(tmp1, b[i]);}for (int i = n - 1; i >= 1; i -- ){maxc[i] = tmp2;tmp2 = max(tmp2, c[i]);}int ans = 0;for (int i = 2; i <= n - 1; i ++ ){ans = max(ans, a[i] + maxb[i] + maxc[i]);}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 1820D The Butcher

题目链接

这一题首先要想到，切第一刀的时候，切下来不动的那一块，要不长和原矩形相等，要不宽和原矩形相等，所以两种情况都判断一下

想到这一点之后还会因为实现方式被卡：如果横着切，也就是长不动，那就把所有长等于最大值的都删掉，宽里删掉相应的边，竖着切相反

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;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;map<int, multiset<int>> xx, yy;int s = 0;int maxx = 0, maxy = 0;for (int i = 0; i < n; i ++ ){int x, y;cin >> x >> y;maxx = max(maxx, x);maxy = max(maxy, y);xx[x].insert(y);yy[y].insert(x);s += x * y;}function<bool(int, int, int, map<int, multiset<int>>, map<int, multiset<int>>)> check = [&](int a, int b, int idx, map<int, multiset<int>> xx, map<int, multiset<int>> yy){int tmp = n;while (a > 0 && b > 0){int tt = tmp;if (idx == 1) // 横不动{for (auto t : xx[a]){b -= t;yy[t].erase(yy[t].find(a));tmp -- ;}xx.erase(a);idx ^= 1;}else if (idx == 0) // 竖不动{for (auto t : yy[b]){a -= t;xx[t].erase(xx[t].find(b));tmp -- ;}yy.erase(b);idx ^= 1;}if (tmp == tt) return false;}return true;};set<PII> ans;if (s % maxx == 0 && check(maxx, s / maxx, 1, xx, yy))ans.insert({maxx, s / maxx});if (s % maxy == 0 && check(s / maxy, maxy, 0, xx, yy))ans.insert({s / maxy, maxy});cout << ans.size() << '\n';for (auto t : ans)cout << t.first << ' ' << t.second << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

CF 1768C Elemental Decompress

题目链接

从小到大，每次贪心取数，不能取到合法数字就no

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;bool cmp(PII a, PII b)
{return a.second < b.second;
}void solve()
{int n;cin >> n;vector<PII> a(n);for (int i = 0; i < n; i ++ ){cin >> a[i].first;a[i].second = i;}sort(a.begin(), a.end());set<int> stp, stq;for (int i = 1; i <= n; i ++ ){stp.insert(i);stq.insert(i);}vector<PII> p(n), q(n);for (int i = 0; i < n; i ++ ){int x = a[i].first;p[i].second = a[i].second;q[i].second = a[i].second;int it;if (stp.find(x) != stp.end()){p[i].first = x;stp.erase(x);for (auto t : stq){it = t;break;}if (it > x){cout << "NO\n";return;}stq.erase(it);q[i].first = it;}else if (stq.find(x) != stq.end()){q[i].first = x;stq.erase(x);for (auto t : stp){it = t;break;}if (it > x){cout << "NO\n";return;}stp.erase(it);p[i].first = it;}else{cout << "NO\n";return;}}sort(p.begin(), p.end(), cmp);sort(q.begin(), q.end(), cmp);cout << "YES\n";for (auto t : p) cout << t.first << ' ';cout << '\n';for (auto t : q) cout << t.first << ' ';cout << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

这篇关于2024.2.29 训练记录（4）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/762884。

相关文章

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

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

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

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

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

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

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

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

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢？我尝试一种更为智能的方法：P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验，
阅读更多...
Spring Boot 配置文件之类型、加载顺序与最佳实践记录

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

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio
阅读更多...
MySQL INSERT语句实现当记录不存在时插入的几种方法

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面：本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE
阅读更多...
Python 中的异步与同步深度解析(实践记录)

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步：深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步
阅读更多...
Python Dash框架在数据可视化仪表板中的应用与实践记录

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash？1.1
阅读更多...
Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定
阅读更多...
国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后，需要到系统环境变量中添加两个变量2. 第3步 “在cmd中
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2