题解at_abc 321 abc

A - Rolling Dice 28 投 n 次骰子，总点数有没有可能是 k ？ B - Factorial Yen Coin 51 好题，值得知道的贪心 面值为 \(1!,2!,3!,4!,5!,\cdots\) 的纸币各 \(100\) 张，问凑出 \(n(n\le 1e7)\) 块钱（不找零 ......

题面 给定 \(N\) 个正整数对 \((a_i, b_i)\) 和两个初始为空的集合 \(S, T\)，你可以选择将每个数对的两个元素划分到两个不同的集合中。求 \[\max\operatorname{lcm}(\gcd\limits_{x \in S}x, \gcd\limits_{y \in ......

20230927 P4370 [Code+#4] 组合数问题2-sol Statement 传送门 给你两个数 \(n,k\) , 要求对于组合数 \(C_{a}^{b}\) 找到任何 \(k\) 个, 让他们的和最大, 且组合数各不相同, 当且仅当 \(a,b\) 不完全相同时,组合数不同。 So ......

CF364D Ghd 题解 题目大意 给定一个长度为 \(n\) 的序列 ，你需要从中选出一个元素个数不少于 \(\left\lceil{\frac{n}{2}}\right\rceil\) 的子序列，使得这个子序列中所有元素的 \(\gcd\) 最大。 分析 数据范围吓人。 \(10^6\)，但是 ......

CF1882D - Tree XOR 知识点：换根 DP 。 主要难点是要思考如何操作使得代价最小，这个过程是一个贪心的过程。想到怎么操作，计算答案的过程就是一个板子换根了。 题意 给定一颗 \(n\) 个节点的树，点 \(i\) 具有权值 \(a_i\) 。现在需要你不断执行以下操作，使得树上所有 ......

题意 给定正整数 \(N\)，求满足如下条件的正整数对 \((x, y)\) 的数量： \(1 \le x, y \le N\) \(x^2 - y\) 为完全平方数（\(0\) 也是完全平方数） （\(1 \le N \le 10^{12}\)）。 题解 因为 \(x^2 - y\) 为完全平方数 ......

Codeforces Round 900（Div.3） E~F E. Iva & Pav 因为按位与的结果不会随着越多数字的增加而增加，因此我们可以利用这个性质二分出右端点，只需要一个可以查询区间的数据结构即可。 或者是按位考虑第 \(i\) 个数字的第 \(k\) 位，后缀最近的 \(0\) 的位 ......

怎么有人现在才学 ACAM 呢。 好像比 SAM 简单挺多啊，也不记得当时是哪里看不懂。 AC 自动机（✔） 自动 AC 机（✘） 概述 ACAM(Aho–Corasick Automaton)，是用来解决多模式串匹配的字符串算法。它的结构是个 DAG，其中点表示状态，边表示转移。这一点上各种自动机 ......

A - 321-like Checker \(\color{gray}{22}\) 直接模拟 void solve() { int n; cin >> n; int lst = -1; for(int i = n; i; i /= 10) { int u = i % 10; if(u <= lst) ......

CF 是没题考了吧，每场都出二进制拆位。 思路 首先我们可以二分 \(r\)，因为 \(r\) 越大，按位与一定只会小于等于 \(r\) 小的情况。 那么，我们可以用 \(num_{i,j}\) 记录 \(a_j\) 第 \(i\) 位的二进制情况。 如果我们对 \(num_{i,j}\) 做一个前 ......

前言 赛时代码可能比较难看。 A 判定 \(a\) 中是否有 \(k\) 即可。 赛时代码 B 奇怪的构造题。 令 \(a_1=1,a_2=3\)，其他项由上一项加一开始枚举判定可行性即可，可以简单证明时间复杂度为 \(O(n)\)。 赛时代码 C 容易发现当 \(x\in \left[\dfrac ......

目录题目链接思路分析代码 题目链接 P4819 思路分析 首先考虑这道题的连通性。容易发现这种类型的题目会容易产生环形的状态转移。假设我们知道了其中的一个点是否是黑白点，那么我们就可以知道所有点是否是黑白点。容易陷入一个误区：我们只能通过一个点知道他所相邻的最直接的点，如何确定相邻的点的状态？注意本 ......

Codeforces Round 742 Div2 A-D题解 A. Domino Disaster 这题就是说给出一些2x1 tile，然后给出2xn的第一行构造，问第二行 这个刚开始想着是啥dp，一看那么多人过了果断改思路，发现这题就是个模拟题，就是把U换成D，D换成U，L和R不影响，然后输出就 ......

水题。 发现根据限制 \(M_{i,j}=M_{j,i}\) 可以知道除了主对角线上的点，其他的点都是成对出现的。也就是说如果有一条要求的 \(a_i\) 为奇数，那么至少有一个 \(c_i\) 在主对角线上。 记 \(S=\sum\limits_{i=1}^{k} (a_i\equiv 1\pmo ......

CF1791G2 Teleporters (Hard Version) 题解 题目大意 题意挺清楚的，给个传送门吧。 分析 比较简单的贪心题，很容易就能看出来是贪心，也很容易就能看出来贪什么。 我没做简单版（Teleporters (Easy Version)），但是我去看了一眼。那个也非常简单，不 ......

T1 derby 你考虑直接贪心进行匹配即可，就是说对于每一个 \(1\) 去匹配最大的 \(0\) #include<bits/stdc++.h> using namespace std; int n,m; vector<int> A[2],B[2]; int main(){ freopen("d ......

2023-09-26 题目 难度&重要性(1~10): 题目来源 luogu 题目算法 组合数学 解题思路 前置知识 范德蒙德卷积公式：\(\sum\limits_{i=0}^kC_{n}^{i}\times C_{m}^{k-i}=C_{n+m}^k\)。 至于证明请看此篇文章。 Sol 我们这道 ......

在 \(V\times V\) 的平面上，\(n\) 次修改，每次给定 \(x,y,v\)，令 \(a,b\) 为不超过 \(x,y\) 的最大的 \(2\) 的整数次幂，则所有 \((x+pa,y+qb)(p,q为自然数)\) 都加上 \(v\)，最后有 \(m\) 次单点询问一个位置的值。 \( ......

C - Not Equal 285 求长度为 n，两两不同，且满足 \(1\le a_i\le c_i\) 的数组的数量 数组 c 排序，答案就是 \(\prod\limits_i(c_i-(i-1))\)，其中 \(i-1\) 个位置被前面占了 D - Collision 686 给定一棵树，q ......

## _Description_ 有一个长度为 $n$ 的 ```01```字符串 $s$，其中部分位置已给出，在 ```?```的位置处需填入一个 ```1```或 ```0```。 一个填充方案是好的，当且仅当存在 $m$ 个不同的 $i$ 满足 $1\le i ......

题意 若非负数列 \(A\) 中任意 \(i(2 \leq i \leq N-1)\) ，都有 \(2A_i \leq A_{i-1} + A_{i+1}\)，则称 \(A\) 为凸数列。 问长为 \(N\) ，且数列中所有项的和为 \(M\) 的凸数列有多少个，答案对 \(10^9+7\) 取模。 ......

P8074 SVEMIR \(Solution\) ： 这道题目乍一看感觉好难... 因为有绿色的加持，再加上一进题目就看见了头疼的三维坐标，不知道的还以为需要用到什么非常高大上的知识来解决这道题，其实只需要用到最小生成树就行了。 不会最小生成树的请出门左转：P3366 【模板】最小生成树 然后来仔 ......

CF1106D 题解 暑期学校军训第一天模拟赛的题，相对而言比较简单 题意： 题意其实很简单，就是有一个无向图，需要你从\(1\)号节点出发，然后一次遍历所有的点，输出其中字典序最小的遍历 思路 说说思路吧，这题既然要遍历图上所有点，那首先就会想到 \(\texttt{BFS}\) 或 \(\tex ......

E - Complete Binary Tree 首先我们只考虑x子树中的答案，非常明显，一定是一个连续的区间，那么我们只需要找到两个端点即可，左端点一直往左走即可，但是右端点要注意，如果走不了，如果左端点存在，说明n就是我们的右端点。 处理完子树之后往上跳即可，因为树高只有60 #include< ......

F - typewriter 直接容斥即可，每次选出它们的并集。 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define fo(i,a,b) for (int (i) ......

神仙题 看到没人交题解，我来交一发。 \(Part\ 0:\)我瞎扯扯 我做这题时想着先把耗费魔法值为负的做掉，然后最后再做一段魔法值为正的，但是不好做，做不了。 这个东西也贪心不了，因为你魔法值和伤害这两个东西拆不开，然后就什么都做不了了。 本篇题解中没有什么心路历程，又不能分析出什么动机，因为笔 ......

CF1863 题解 A 条件很简单：如果总共的 '+' 号加上开始上线人数不到 \(n\) 人，就不可能。实时记录人数，如果某一时刻大于等于 \(n\) 人在线上，就一定是。剩余情况则可能。 #include<bits/stdc++.h> using namespace std; int main( ......

C - Colorful Candies 359 固定大小滑动窗口内不同颜色数 D - National Railway 1507 给定矩阵 \(a\) 和数 \(c\)，任选不重合的两点 \((i,j),(i',j')\)，求 \(a_{i,j} + a_{i',j'} + c(|i-i'|+|j ......

RobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinC... ......

SuntoryProgrammingContest2023（AtCoder Beginner Contest 321） - AtCoder D 题意：给定常数 \(k\) 和长度为 \(n\) 的数组 \(a\) 和长度为 \(m\) 的数组 \(b\)，求 \(\sum_{i=1}^n\sum_{ ......