kzssCCC

摘要： https://ac.nowcoder.com/acm/contest/110811/G 题意概述 给定两个长度为 \(n\) 的数组 \(a,b\) 和两个参数 \(k_1,k_2\)，求满足： \(i \lt j\) \(k_1 \oplus a_i \oplus a_j \lt k_2 \op 阅读全文

摘要： https://codeforces.com/problemset/problem/2127/E 题意概述 给定一棵根为 \(1\) 的有根树，每个节点有权值 \(w_i\) 和 颜色 \(c_i\)，有一些节点没有颜色，即 \(c_i=0\)。 称节点 \(u\) 为 \(cutie\) 当且仅当 阅读全文

摘要： https://www.luogu.com.cn/problem/P5357 首先建 \(trie\) 树，将模式串逐个插入，记录每个模式串在 \(trie\) 树中对应的最后一个位置。 将 \(0\) 节点的孩子全部入队，做 \(bfs\)。 当前节点为 \(u\)，遍历每一条边 \(c\)（\( 阅读全文

摘要： 题意概述 给定一个键盘，有 \(0,1,\cdots,9\) 的数字按键，其中有 \(k\) 个不可用，保证按键 \(0\) 可用。给出一种构造方案使得按出的数为 \(m\) 的倍数，如果不存在输出 \(-1\)。 \(1\le m \le 10^7\)。 思路 要让按出的数是 \(m\) 的倍数， 阅读全文

摘要： 根据定理： \[\varphi(n) = n\cdot \prod_{p\mid n}{(1-\frac{1}{p})} \]直接分解质因数求即可，时间复杂度 \(\mathcal{O}(\sqrt n)\)。 代码 auto cal = [&](ll x){ ll res = x; for (ll 阅读全文

摘要： 题意概述 \(A\) 有实力值 \(x\)，初始为 \(0\)。有 \(n\) 场比赛，每场比赛有难度 \(a_i\) 和 隐藏分 \(b_i\)。\(A\) 只会打难度 \(a_i \ge x\) 的比赛，之后他的实力值变成 \(\max(x,b_i)\)。 通过调整比赛的顺序，计算 \(A\) 阅读全文

摘要： https://codeforces.com/problemset/problem/2150/C 题意概述 共有 \(n\) 个物品，每个物品有一个价值 \(V_i\)。总共进行 \(n\) 轮，每轮由 \(A\) 或 \(B\) 拿物品，每个人都有一个偏好序列 \(a,b\)，他们每次会拿偏好序列 阅读全文

摘要： https://www.luogu.com.cn/problem/P2765 题意概述 有 \(n\) 根柱子，依次放编号为 $1,2,\cdots $ 的球，每次只能在一根柱子的最上方放球，同一根柱子任意相邻两个球的编号之和必须是完全平方数。 求最多能放多少个球，并构造方案。 思路 考虑用有向边刻 阅读全文

摘要： https://www.luogu.com.cn/problem/P3386 左端点到右端点连容量为 \(1\) 的边，超级源点到每个左端点连容量为 \(1\) 的边，每个右端点到超级汇点连容量为 \(1\) 的边，求最大流即可。 代码 //author:kzssCCC #include <bits 阅读全文

摘要： https://www.luogu.com.cn/problem/P5905 使用 \(spfa\) 求出初始势能，之后边权变成 \(w+h_u-h_v\) 一定非负，跑 \(dijkstra\) 即可。 为了处理负环，先虚拟出超级源点，向所有点连边权为 \(0\) 的边，从这个点开始求势能。可以通 阅读全文