题解1071 cf

[原题](https://codeforces.com/contest/1845/problem/C) [翻译](https://www.luogu.com.cn/problem/CF1845C) 以为是数位dp，想了很久，最后发现贪心好巧妙 但其实数位dp也能做，只是写起来比较麻烦，(而且我看错题 ......

#P1262 间谍网络’s题解 ####**题目描述** 给你一个**有向图**，可以付出代价获取一些指定的点。 在获取之后要求能以获取的点为**出发点**，将整个图都访问到，求**最小的代价**。 ####**思路** 既然需要令总的代价**最少**，那么如果通过买一个点就可以访问到的所有点，自然 ......

先考虑暴力 **dp**。设 $f_{u,x}$ 表示在子树 $u$ 中选出的节点集合的 $w$ 最小值为 $x$ 的情况下，最大的节点集合的大小。有两种转移（选不选 $u$）： $f_{u,x}\gets \sum\limits_{v\in \text{substree}_u} f_{v,\ge ......

# CF1305F Kuroni and the Punishment 不难发现答案上界为 $n$。 考虑我们能做什么？我们可以对一个 gcd 快速求出最少操作次数。 这启发我们将 gcd 确定在某个范围后暴力对每个 gcd 做上面的操作。 gcd 怎么来？从 $a$ 中来。如果确定 $a_i$ 的 ......

首先发现后缀和前缀比较不好看，所以翻转第二个字符串，记为 $T'$。 这样就变成了操作两个字符串的前缀。 观察发现，操作 $k$ 等价于交换 $S[1\sim k]$ 和 $T'[1\sim k]$，然后翻转 $S[1\sim k]$ 和 $T'[1\sim k]$。 结论 1：同一个下标上的字符对 ......

## Description 给定 $n,k$，求： $$\displaystyle\sum_{i=1}^{n}{\binom{n}{i}\times i^k}$$ $1\leq k\leq 5000,1\leq n\leq 10^9$。 ## Solution 看到那个 $i^k$ 很不爽，但是 ......

首先我们考虑第一种情况怎么处理，显然我们可以给原数列的每个数开一个$vector$，每加一个数丢到对应的$vector$后面就行了。 再看第二个操作，你考虑新加一个数会有什么影响。 原来的两个$vector$是这样的： ![image](https://img2023.cnblogs.com/blo ......

[传送门](https://www.luogu.com.cn/problem/AT_arc158_c) ## 题目分析 我们可以先从简单一点的情况开始分析，如果现在 $a_{[i]},a_{[j]}$ 都**不会进位**，那么最后的 $f(a_{[i]}+a_{[j]})=f(a_{[i]})+f( ......

### 题目大意 奥列格和伊戈尔打算开一个公司，他们对于公司的取名有不同的意见。 他们两个各有一个长度相等的字符串，公司的名字最初是全由 $\texttt{?}$ 构成的一个字符串，两人轮流操作，在自己的字符串中选出一个字符取代公司名字中的某一个 $\texttt{?}$，使用后该字符就在当前操作者 ......

A 题解：不会 #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include ......

[题面传送门](https://www.luogu.com.cn/problem/CF1656H) 首先有一个暴力的想法：依次查看左边每个数，对于左边每个数，计算右边未被删除的点与这个点的 $\gcd$ 的 $LCM$，如果这个 $LCM$ 等于当前这个数，说明这个点可以被左边的 $LCM$ 整除， ......

[题面传送门](https://www.luogu.com.cn/problem/CF1844G) 这个真的很容易想到吗？ 首先定 $1$ 为根，设每个点的深度是 $d_i$，则两个点之间的距离是 $d_{i}+d_{i+1}-2d_{LCA(i,i+1)}$。题目中相当于给出了 $n-1$ 个方程 ......

### 题目大意 定义括号序列为只包括 $\texttt{(}$ 和 $\texttt{)}$ 的字符串。一个匹配的括号序列（简记为 RBS）满足，可以在其中加入 $1$ 和 $+$，将其转化为合法的代数式，例如： + $\texttt{()()}$ 和 $\texttt{(())}$ 是匹配的； ......

链接：[P2073 送花](https://www.luogu.com.cn/problem/P2073 "P2073 送花") ## 题意： 有若干朵花，每个有两个属性（美丽值和价格）。你需要维护 $3$ 种操作： - 1.添加一朵花（如果之前有价格相同的忽略此操作） - 2.删除最贵的花 - 3 ......

在 $S=[1,n]\cap \mathbb Z$ 中选出一个最大子集 $T$ 使得其任意两元素差不为 $x$ 且不为 $y$，求 $|T|$。$n\le 10^9,x,y\le 22$。 通项，打表找规律套结论，或者矩乘。都是错的。考虑一个周期性。 注意到有 $n=x+y$ 的包。上结论，将对于 ......

就是 $m$ 组询问**补图的最小生成树**上的树链最大值。有两种基本思路求这棵树。 第一种，Kruskal，基于找到最小的边使两端点不连通。考虑补图中 $(x,y)$ 的边权，它是原图最小生成树上的树链最大值。从小到大枚举补图的边，相当于从小到大枚举原图最小生成树的边 $(u,v,w)$，然后： ......

一棵树，点权 $a_i(a_i\le n)$，无边权，求 $$\sum_{i\ne j}\varphi(a_ia_j)\text{dis}(i,j)$$ 首先，你没有任何手段求 $10^{10}$ 级别的一堆离散的 $\varphi$。于是 $$\varphi(xy)=\frac{\varphi(x ......

## [题面](https://www.luogu.com.cn/problem/AT_agc064_a) # 题目大意 给定一个正整数 $N$，要求构造一个序列。对于每一个在 $1$ 到 $N$ 之间的整数 $i$，序列中包含了 $i$ 个，并且将该序列首尾相接拼成环后，相邻两项之差大于等于 $1 ......

>作为惩罚，GY被遣送去帮助某神牛给女生送礼物貌,~~~~似是个好差事~~~~ 但是在GY看到礼物之后，他就不这么认为了。 某神牛有N个礼物，且异常沉重，但是GY的力气也异常的大(-_-b)， 他一次可以搬动重量和在w(w题目概述 有N件物品，每件物品有自己的重量，每件物品只能选一次。 选取任意件物 ......

# CF1854D Michael and Hotel 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1854D) [Codeforces](https://codeforces.com/problemset/problem/1854/D) ......

# P2034题解 ## 题目描述 给定一行 $n$ 个非负整数 $a_1 \cdots a_n$。现在你可以选择其中若干个数，但不能有超过 $k$ 个连续的数字被选择。你的任务是使得选出的数字的和最大。 ## 题解 正难则反，考虑将原问题转化为从 $a$ 中选若干数使得，任意两数差不大于 $k$, ......

# ZS Shuffles Cards 题解 我们把每一次抽一些数字牌再抽到 joker 视作一局游戏。 ## 每局期望轮数 首先考虑 $f_i$ 表示每一局游戏抽出 $i$ 张牌的概率。 那么就是先抽出 $i - 1$ 张数字牌，再抽出一张 joker 。 概率就是 ： $$ f_i = \fra ......

### 题目大意 $n$ 个带权点，$m$ 条无向边，删除一个点就要付出所有与之连接且没有被删除的点的点权之和的代价。 求删除所有点的最小代价。 ### 思路 考虑点的贡献异常麻烦，我们可以把点的贡献转化为边的贡献。 对于一条边，我们有如下几点： 1. 伴随着所有的点被删掉，所有的边也会被删掉； 2 ......

## 思路 这个题是一个简单的构造题。~~竟然比 T2 简单，也是少见~~ 我们可以首先从 $1$ 开始不断乘以 $2$，像这样：$1, 2, 4, 8, 16\cdots,2^x$，直到什么时候超过 $n$ 就停止。 这样相邻两个数字就可以凑出 $1, 2, 4, 6, \cdots,2^{x- ......

## 思路 **注意：所有变量名与原题面相同。** 因为 $1$ 号点必须吃一块饼干，所以我们可以在 $1$ 立一个不可删除的商店，记为 $s_0$。 **注意：如果 $1$ 号附近本身就有一个商店，那就不用立。** 然后我们可以在 $n + 1$ 的位置立一个不可删除的商店，作为一个结束标志，记为 ......

## 思路 我们可以让两人先拿 $c$ 里面的，因为 $a$ 和 $b$ 肯定是自己的，那么公共的“我”也要抢的越多越好，所以我们都要先拿 $c$ 里面的。 如果 $c$ 是奇数，那么先手一定多拿 $1$ 个 $c$ 里面的，相当于先手可以拿 $a + 1$ 个，后手可以拿 $b$ 个； 如果 $c ......

[题面](https://codeforces.com/problemset/problem/1060/E) 由题意可知，在原图中经过边数为 $2$ 的一对点，在新图中经过边数为 $1$。所以每对点在新图中的距离为： $$ \begin{aligned} \lceil \frac{dis(i,j)} ......

# P3572题解 ## 题面翻译 有 $n$ 棵树排成一排，第 $i$ 棵树的高度是 $d_i$。 有 $q$ 只鸟要从第 $1$ 棵树到第 $n$ 棵树。 当第 $i$ 只鸟在第 $j$ 棵树时，它可以飞到第 $j+1, j+2, \cdots, j+k_i$ 棵树。 如果一只鸟飞到一颗高度大于 ......

### (离线做法)ABC133F 题解 题目链接：[ABC133F](https://www.luogu.com.cn/problem/AT_abc133_f) #### 明确维护目标 显然我强制修改强制查询的在线做法会超时，于是我考虑离线做法。 首先我们可以知道，树上的路径可以用和差关系线性表示 ......

## [CF1858B The Walkway](https://codeforces.com/contest/1858/problem/B "CF1858B The Walkway") 降智题，但是这种题放B着实有点恶心 考虑每两个相邻点对$x$,$y$对于答案的贡献，显然是$\frac{s_y- ......