题解codeforces round 1805

CF996A Hit the Lottery 直接贪心尽可能的分配到 \(k_5\)，剩下的依次分配给 \(k_4,k_3,k_2,k_1\)。 #include<iostream> #include<cstdio> using namespace std; int n; int k[6]; int ......

目录A. How Much Does Daytona Cost?B. Aleksa and Stack A. How Much Does Daytona Cost? 判断数 k 包不包含在数组里面即可 B. Aleksa and Stack 选定初始数为2, 3，后面的遍历 法二：全奇数即可，因为奇 ......

题面 给定 \(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\) 的位 ......

A 已知一个字符串 \(n\le 1e3\) 中的若干信息，：\((x,y,z)\) 表示 \(x\) 后缀和 \(y\) 后缀的 \(\text{LCP}=z\). 求满足条件的字典序最小的字符串。 已知 \(a_{x+i}=a_{y+i}(i<z)\)，考虑维护并查集，一定相同的在一个集合。 然 ......

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

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

昨天晚上生病，没比（血亏） A: 就是看k有没有在序列里 B: 随便放一个大的号码然后加 i，应该就可以过了 C: 就是我们最少要拿 k*(k+1)/2, 最多可以拿 k*(n+n-k+1)/2。 啊，你问我怎么证明在这两个值里就一定可以拿到（当然是猜的！！） D: 让f[x]表示当前出了多少次。然 ......

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

SMU Autumn 2023 Round 5 A - Everyone Loves to Sleep 思路：将小于睡觉时间的闹钟加24：00，找到最小的时间min，答案即为min-睡觉时间 #include<bits/stdc++.h> using namespace std; //#define ......

Preface 好久没现场打CF了（玩CC玩的.jpg），但这场久违的打的还不错，把Kusanagi_Misuzu这个小号也打上橙了 虽然开场的时候状态不佳写的巨慢，但后面还是靠着ztc带我做出E1成功题数反超上大分 接下来要考虑启动第三个小号了，只敢打Div2的FW是这样的 A. Increasi ......

洛谷传送门 AtCoder 传送门 看到和度数有关的（基环）树计数，可以想到 Prufer 序。 如果要计数一棵树，那么答案就是 \(\binom{n - 2}{d_1 - 1, d_2 - 1, \ldots, d_n - 1}\)。因为度数为 \(d\) 的点在 Prufer 序中恰好出现 \( ......

没什么好说的，一题不会。 D1T1. 面基之路 考虑瓶颈在于最后一个网友的面基时间。 Trick：可以看作 所有网友都在同一时间（显然一定也是同一位置）面基，因为各个网友和 hehe 桑本人都是独立行动，而且可以原地不动。 也就是求一个最快的集合点（包括顶点和各边的中点）。直接边转点，枚举最短路之和 ......

给一个数组 \(a_1， a_2, \cdots, a_n\) 。可以执行以下操作任意次： 选择 \(l, r (1 \leq l < r \leq n)\) ，对于任意 \(l \leq i \leq r\) ，同时执行所有 \(a_{l + i} = a_{l + i} \& a_{r - i} ......

Codeforces Round 899 (Div. 2) A. Increasing Sequence 点击查看代码 #include<bits/stdc++.h> using namespace std; const int maxn=105; int t,n; //map<int,bool> ......

水题。 发现根据限制 \(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)），但是我去看了一眼。那个也非常简单，不 ......

SMU Autumn 2023 Round 5 A. Everyone Loves to Sleep 把时间都转成分钟,然后存起来,二分找到离他睡觉点最近的一个时间段,减去他的睡觉点,如果最近的在第二天,则把中间的这段时间加起来 #include <bits/stdc++.h> #define in ......

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

这是我的vp,不是正真的contest. A: 不想多说，读者应该可以做到的！！！ B: 让g=product(移除掉0的a)： 如果有多过1个0答案肯定是0。 如果只是有1个0答案就是g。 没有0，答案就是max(g/a[i]*(a[i]+1)) 任何 i。 C: 没有仔细想那个profit的fo ......

赛后四题 B题直接枚举不存在的元素即可 C题的trick有点像之前abc的某道题，对于奇数位置它一定可以贡献，对于偶数位置，如果它有数选了，那么它就能够贡献。 \(f[i]\)表示到前i个且至少选了一个的最大答案。 #include<cstdio> #include<algorithm> #incl ......

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

给一个字符串，包含字符 \(B\) ， \(R\) ，\(?\) 。其中 \(?\) 可能为 \(B\) 或 \(R\) 。 规定不完美数为字符串中相同字符连续出现的次数，询问一个字符串的最少可能不完美数。 观察到 \(BR\) 或 \(RB\) 需要尽可能多，于是考虑尽可能让相邻字符不同。 容易证 ......

给一个数组 \(a_1, a_2, \cdots, a_n\) ，定义 \(s = \sum_{i = 1}^{n} a_i\) 。 询问有多少个 \(a\) 的子序列满足 \(\sum a_{i_k} = s - 1\) 。 显然要选出一个 \(1\) 不加入子序列，任意一个 \(0\) 可以加入 ......