题解1203 div cf

题目大意： 给出长度为\(n(1\le n\le 10^5)\)的数组\(a\)，构造数组\(b\)使得\(a_i=MEX\{b_1,b_2,...,b_1\}\) 首先考虑当\(b_1,b_2,...,b_n\)为什么数时，\(a_n=MEX\{b_1,b_2,...,b_n\}\)。 然后再考虑 ......

待补 CF1866 C 考虑在每个边权为 1 的边 \((u,v)\) 计算贡献。考虑 \((u,v)\) 被经过 \(m\) 次，表示为 \(r_1,\dots,r_m\) 。\(r_1,r_2\) 之间的 0 边被计算 \(1\) 次，\(r_2,r_3\) 之间的 0 边被计算 \(2\) 次 ......

前言 首先就是不太会打 CF，主要体现在晚上熬夜太难受，不过这场的状态还是挺好的。 然后就是时间把握不好，CCF 和模拟赛基本都是 \(3h\) 到 \(4h\)，而 CF 只有 \(2h\) 左右。所以时间很紧，像这场，明明后面的题会做也没时间做了。 赛时实况： A B C D E F G √ √ ......

思路分析 前言 一道比较简单的数学题。 解法 根据题意可以推算出最大值 $v=\Big(1-\dfrac{1}{2{M+1}}\Big)\times2{2{E-1}}=A\times10B$。因为两边都比较大，所以可以同时求以 $10$ 为底的对数：$\lg v=\lg(2{M+1}-1)-(M+1 ......

洛谷题目链接 AT原题 考虑构造出来的序列 \(a\) 的特征，因为每次会给 \(a_i\) 加 \(1\)，\(a_j\) 加 \(2\)，所以每次操作后 \(\sum a_i\) 会加上 \(3\)。 所以有\(\sum a_i =3m\) 。 又因为每次操作只给一个数加 \(1\)，所以每次操 ......

SMU Autumn 2023 Round 1(Div.1) A. Set or Decrease(枚举) 题意就是你可以进行两种操作,将\(a_i-1\)或者令\(a_i\)等于\(a_j\),然后使得\(\sum\limits_{i=1}^{n}a_i \leq k\),求最少的操作步数 首先我 ......

题目链接 题解 知识点：构造。 首先反证法容易证明一个结论：每次增加一个字符，本质不同的回文子串至多增加一个。 那么无解的条件就是，\(c_i - c_{i-1} > x_i -x_{i-1}\) ，即距离不够数量的增加。 其他情况均有解，可以考虑利用 abc 作尾部填充，因为其只在一开始提供 \( ......

CF29D Ant on the Tree 题目知识点：LCA。 题目传送门 题意 给定一棵以 \(1\) 为节点的树，再给定树的所有叶子节点的一个序列。 现在执行一个操作：从 \(1\) 开始遍历每个节点，并返回根，要求每条边经过的次数一定为 \(2\) 。 问是否能够使得访问节点序列中叶子节点的 ......

题目链接 description 给定一个长度为 \(n\) 的序列 \(a\)，求一个最小的正整数 \(x\)，使得它不是这个序列任意区间的最小公倍数。 值域 \(W=10^9\) solution 显然答案最大的数量级为 \(O(n\log n)\)，记 \(m=n\times (\lfloor ......

题目链接 description 如上图，\((0,0),(0,m),(n,0),(n,m)\) 是四个口袋。一个台球从整点 \((x,y)\) 按照给定的初始方向出发（方向只可能平行于坐标轴或和坐标轴呈 45° 夹角），当它和一个口袋的坐标重合时游戏结束。 给定 \(n,m,x,y\) 以及球初始 ......

题目大意： 给定一些指令，计算需要多大的舞台。 这是一道大模拟！！！ 只要遍历每次指令，然后判断是否摔倒，摔倒输出`-1`否则记录，最后求出面积就行了。 最后附上代码 1 #include <bits/stdc++.h> 2 using namespace std; 3 const int xx[] ......

题意 给定一个环形 01 序列，每次变化时，对于每个位置，如果前一个值是 1 ，则当前值翻转。求变化 B 次后的序列。 思路 由于 B 的值很大，所以如果对每一次变化进行模拟，效率非常低下。 不难发现，每一次变化后的状态完全是由当前状态决定的，而 N 的范围很小，所以可能的状态总数 2^N 也不是很 ......

一道递推 由于对于一个数 x ,可得 x+10-x=10（废话） 于是问题就变成了 0+m 次,然后 x+m 就变成 0+x+m （还是废话） 于是可以写一个递推。 首先对于函数 f(m) 可分为 m ≤ 9 和 m>9 ,然后可得出递推式结果为 1 或 f(m-9)+f(m-10) ，所以我们可以 ......

题目链接 description 定义数列 \(f\)，当 \(i>k\) 时，\(f_i=\prod\limits_{j=1}^k f_{i-j}^{b_k}\) 模 998244353 。 已知数组 \(b\) 且 \(f_1,f_2,\dots,f_{k-1}\) 均等于 1，给定 \(n,m ......

Link A Two Vessels 十分甚至九分地简单 #include<bits/stdc++.h> using namespace std; int t; int a,b,c; int main(){ scanf("%d",&t); while(t--){ scanf("%d%d%d",&a, ......

康了康唯一的题解，说没必要用DP，我就给出DP的解法。 这其实是道水题，唯一的坑是有可能楼上没有开的灯，坑了我们机房的一堆人（ WA on test 4 ），剩下的就是DP。 我们用 a[n][0],表示第 n 层的第一个房间，用 a[n][1]，表示第 n 层的最后一个房间。 这里提供一个收集型的 ......

题目链接 description \(f_k(x)\) 表示所有长度为 \(x\) ，元素取值范围为 \([1,k]\) 中的整数的序列 \(\{a\}\)，满足 \(\gcd(a_1,a_2,\dots,a_x)=1\) 的序列的个数。 给定 \(n,k\leq 2\times 10^6\) 分别 ......

## 主要题意：有 $n$ 个礼物，要两两合并，然后除以 $k$ 最后求和最大。 ## 思路：先加入每个数除以 $k$ 的商（单独组成 $k$ 的个数），然后全部 $ \bmod \ k$ 存入数组，排序，最后双指针一个前一个后求两个余数可以大于等于 $k$ 的两个礼物。 ## 代码： ```cpp ......

## 主要题意：> 有 $n$ 个任务，必须在 $s_i$ 到 $t_i$ 之间完成，求每个任务最大可以完成多久（优先前面的最大）。## 思路> 就拿一个变量记录当前时间，然后贪心选择 $a[i].t$ 和 $ a[i + 1].t$ 中的最小值，（应为至少也要给下一个任务留 $1$ 的时间），最后 ......

题目链接 description 写个数据结构，支持区间加斐波那契数列和区间求和。 模 1e9+9。 solution 设 \(A=\begin{bmatrix}1&1 \\ 1 & 0 \end{bmatrix}\)。 则 \(\begin{bmatrix} F_{n+1}& F_{n} \end ......

【题解】[ABC318G] Typical Path Problem 题目链接 G - Typical Path Problem 题意概述 给定一个 \(n\) 个点 \(m\) 条边的无向连通图。 给定三个该图上的不同顶点 \(A,B,C\)，问是否存在一条从 \(A\) 到 \(C\) 的简单路 ......

原题 翻译 Chtholly可爱捏 我们先考虑如果\(n \cdot c \leq m\)我们要怎么做，我们可以发现里面一定存在一个数出现了\(\geq \lceil \frac{m}{c} \rceil\)，不妨设这个数为\(x\)，因此我们只需要把所有数都改成\(x\)就可以了 等等好像不对，我 ......

题目链接 description 给定 \(0\leq a_1,a_2\leq 2*10^9, -2*10^9\leq b_1,b_2,L,R \leq 2* 10^9\) 求 \(\sum\limits_{x=\max(L,b1,b2)}^R [a_1\mid x-b_1][a_2\mid x-b ......

C. Divisor Chain 看到样例2中的\(5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1\)想到了是不是应该把\(x\)向着\(2^n\)去凑，凑到了之后通过不断的减去\(2^{n-1}\)最后达到\(1\)，然后就可以朝着这个方向 ......

题目大意： 给出一个长度为\(n(1\le n\le 10^{5})\)的序列\(a_1,a_2,...,a_n\)，计算\(\sum_{1\le l<r\le n}\sum_{l\le i<j\le r}[a_i=a_j]\) \(\sum_{1\le l<r\le n}\sum_{l\le i< ......

[题目链接](https://codeforces.com/problemset/problem/1043/F) ## description 给定一个正整数集合 $\{a\}$，求其大小最小的最大公约数为 1 的子集大小。 不存在输出 -1 $n\leq 3\times 10^5$ 值域 $W\l ......

[题目链接](https://codeforces.com/problemset/problem/1833/G) # 题解 **知识点：贪心，树形dp。** 当 $3 \not \mid n$ 时，显然无解。 考虑一种贪心策略，从叶子节点往上只，要以当前节点为根的子树大小能被 $3$ 整除，就立刻切 ......

### [题目链接](https://www.luogu.com.cn/problem/P1419) ## description 给定一个长度为 $n$ 的序列（值域为 $[-10^4,10^4]$）和正整数 $st,ed$。 求一个区间，使得其长度 $\in [st,ed]$ 且平均值最大，输出 ......

[题目链接](https://codeforces.com/problemset/problem/449/E) ## description 给定整数 $n,m\leq 10^6$ 求以 $(0,0)$ 为左下角，$(n,m)$ 为右上角构成的区域内每个格子被包含在的简单正方形（顶点都在区域内且在格 ......

根据题意，我们可以发现这是一道树形 dp。首先考虑设计状态，注意到 $k$ 较小，那么我们可以在 dp 数组里面塞一维来维护特殊颜色点的个数。然后题目里有颜色编号的大小限制，所以第三维用 $0/1/2$ 来分别表示当前颜色小于/等于/大于 $k$ 的情况。那么这样的话就是用 $f_{i,j,0/1/ ......