当前位置: 首页 > news >正文

[eJOI 2024] 奶酪交易 / Cheese

前言:

译者的语文成绩不怎么样啊。

解题思路:

假设农夫 \(i\) 所拥有的奶酪价值为 \(p_{i}\)

稍微细想一下 \(i\)\(j\) 交易这件事,因为钱的面值只有 \(2\) 的次幂,所以 \(j\)\(i\) 的钱的总面值一定是 \(B\) 的倍数,发现它实际上是想告诉我们:

\[p_{j}-p_{i}=A-k \times B \quad k \in \mathbb{Z} \]

\[p_{j}-p_{i} \equiv A \pmod{B} \]

在细想一下又能发现,我们不仅仅只知道 \(p_{j}-p_{i}\)\(B\) 的值,小于 \(B\) 的值我们也能知道。所以一次交易相当于告诉我们 \(p_{j}-p_{i}\) 模所有小于 \(B\) 的面值的差值。

注意到 \(B\) 的面值不会大于 \(2^{15}\),所以我们直接开 \(16\) 个带权并查集,第 \(i\) 个并查集中记录 \(fa_{x}\) 表示 \(x\) 的父亲,\(val_{x}\) 表示 \(p_{x}\) 在模 \(2^i\) 的意义下减 \(p_{fa_{x}}\) 的差值。

每次交易只要查询 \(i\)\(j\) 是否在并查集内是否有连边,差值是否正确即可。

\(x\) 所在的并查集和 \(y\) 所在的并查集合并的时候,我们知道的是 \(p_{x}\)\(p_{y}\) 之间的差 \(k\),那么这两个并查集的根节点之间的边权应为 \(k-val[x]+val[y]\)。(这部分请根据具体实现自行推断)

同时注意路径压缩时,\(x\) 的父节点变了,\(val_{x}\) 的值也要变。

\(B=-1\) 其实是容易的,只要将 \(B\) 当作一个足够大的值做就行了。

代码实现:

#include<bits/stdc++.h>
#define endl '\n'
#define LL long long
using namespace std;
const int N = 5e5 + 10;
int n, m;
struct DSU{int fa[N];LL val[N], mod;int find(int x){if(fa[x] == x) return x;int fat = find(fa[x]);val[x] = (val[x] + val[fa[x]]);return fa[x] = fat;}bool check(int x, int y, LL k){int fatx = find(x), faty = find(y);if(fatx != faty) return 1;return (((val[x] - val[y]) % mod + mod) % mod == k);}void merge(int x, int y, LL k){int fatx = find(x), faty = find(y);if(fatx == faty) return;fa[fatx] = faty;val[fatx] = k + val[y] - val[x];}
}T[17];
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m;for(int j = 0; j <= 15; j++) T[j].mod = (1 << j);T[16].mod = 0x3f3f3f3f3f3f3f3f;for(int i = 1; i <= n; i++) for(int j = 0; j <= 16; j++) T[j].fa[i] = i;for(int i = 1; i <= m; i++){LL x, y, val, B;cin >> x >> y >> val >> B;if(B != -1){int k = log2(B);for(int i = k; i >= 0; i--) if(!T[i].check(x, y, val & (T[i].mod - 1))) goto failed;for(int i = k; i >= 0; i--) T[i].merge(x, y, val & (T[i].mod - 1));}else{int k = 15;if(!T[16].check(x, y, val)) goto failed;for(int i = k; i >= 0; i--) if(!T[i].check(x, y, val & (T[i].mod - 1))) goto failed;for(int i = k; i >= 0; i--) T[i].merge(x, y, val & (T[i].mod - 1));T[16].merge(x, y, val);}cout << 1 << endl; continue;failed: cout << 0 << endl;}return 0;
}
http://www.hskmm.com/?act=detail&tid=14500

相关文章:

  • 逆向分析之switch语句
  • 批量查询设计桩号方法及文件格式
  • 搭建Python的运行开发环境
  • 【HBase 原理部署安装 01】
  • 打破数据壁垒,DMS Data Agent 开启智能分析之旅
  • Ruby IPAddr正则表达式拒绝服务漏洞分析与修复
  • 模型驱动的 AI Agent架构:亚马逊云科技的Strands框架技术深度解析
  • cache支持的软件操作
  • PHP 静态分析工具实战 PHPStan 和 Psalm 完全指南
  • tests-stats/regression.sh
  • 光隔离探头技术解析:高电压测量的安全革命​​
  • freertos.c解析 - 教程
  • 从缺陷管理到质量协作:现代Bug工具的范式升级
  • 【html组件】简易漫画阅读器
  • ubuntu安装mysql2
  • 高并发系统核心指标
  • 工程化知识管理新范式:DevOps驱动下的智能文档体系建设实践
  • 从零开始学Flink:数据转换的艺术
  • java创建线程池去实现某个任务(多线程)
  • 20250827_黔西南网信杯_丢失的数据
  • 敏捷已死?2025年项目管理软件支持的混合管理模式正成为新主流!
  • 螺旋矩阵-leetcode
  • 【第十一章】Python 调用 MySQL 全面指南:从基础到实践​ - 实践
  • 开源中国社区:AI驱动下的开发者生态革命
  • 日志清理脚本模板 - 一叶舟
  • 11.备库出现gap处理方法
  • [原创]《C#高级GDI+实战:从零开发一个流程图》第10章:鼠标拖动完成连线、拖动时实时显示半透明虚线连线效果、自定义连接点样式
  • 修改Abp中Auto API Controllers中 默认生成的 Put、Delete请求
  • 电阻-温度数据拟合工具(最小二乘法)
  • delphi clientdataset 中文过滤问题