题解wag-quaternary quaternary balance

## 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( ......

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

链接：[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 ......

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

## 思路 我们可以让两人先拿 $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) #### 明确维护目标 显然我强制修改强制查询的在线做法会超时，于是我考虑离线做法。 首先我们可以知道，树上的路径可以用和差关系线性表示 ......

# P3478题解 ## 题目描述 给定一个 $n$ 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。 一个结点的深度之定义为该节点到根的简单路径上边的数量。 ## 题解 本题为换根dp的模板题。 我们令 $dp[x]$ 为以 $x$ 为根节点的子树内的节点深度之和。令 $s ......

## 杂言 赛时想到做法，结果调 code 把自己心态调炸了，所以来写一篇题解（恼）。 另：此题与 [P9345 夕阳西下几时回](https://www.luogu.com.cn/problem/P9345) 几乎相同，可以此练手。 另另：本题多测，多测不清空，爆零两行泪。 ## 题意翻译 $a_ ......

# Simfonija 题解 [题目链接](https://www.luogu.com.cn/problem/P7382) ## 题意 给定两个长度为 $n$ 的数组 $A$ 和 $B$，你可以给 $A$ 数组中的所有元素加上 $X$（这里 $X$ 应该能是负数），并修改不超过 $K$ 个元素，使得 ......

# 2023/8/15 模拟赛题解 ## T1 Simfonija 准确来说场上只有这道是自己现做的（另外两道都是原题）。 [题目链接](https://www.luogu.com.cn/problem/P7382) ### 题意 给定两个长度为 $n$ 的数组 $A$ 和 $B$，你可以给 $A$ ......

## 题意 给定 $n$ 个数 $a_1, a_2, \cdots, a_n$，每次操作可以给其中的一个数加上 $2$ 的非负整数次幂。求最小的操作次数，使得这 $n$ 个数相等。 ## 题解 首先考虑如何计算操作次数，设 $maxa = \max\limits_{i = 1}^{n} a_i$，如 ......

## 题意 对于集合 ${1,2,\cdots,n}$，求它的子集族中，有多少个满足： 1. 任意两个子集互不相同； 2. $1,2,\cdots,n$ 都在其中至少出现了 $2$ 次。 $n \le 3000$，答案对 $M$ 取模。 ## 题解 第一个限制形同虚设，下面着重考虑第二个限制。考虑到 ......

## 题面 定义一个 $1 \sim n$ 的排列 $p$ 的「怪异度」为 $$\sum_{i=1}^n\left\lvert p_i-i\right\rvert$$ 求「怪异度」为 $k$ 的 $1 \sim n$ 的排列数，答案对 $10^9+7$ 取模。 ## 题解 考虑转化计算怪异度的过程， ......

## 题面 JOI 社为了扩大业务而开始了新社员招募。社员有 $N$ 名候补者，编号从 $1$ 到 $N$，每名候补者有称为评价值的一个确定整数。评价值高于某一个值的候补者全部都将被聘用，他们还将分为几个组别。如果 $a, b(a \lt b)$ 同时被聘用且 $c(a \le c\le b)$ 全 ......

[题目链接](https://atcoder.jp/contests/abc261/tasks/abc261_h) 震惊！这个题竟然被神犇 szs 放进了博弈论里！我真的没看出来除了题面还有哪里像博弈论（也许是因为我菜）。 转移方式很显然，按照题面说的做就行了。那么正解也就呼之欲出了。 但是我知道大 ......

## 题面 对于一个序列，若有 $(i,j)(i typedef long long valueType; typedef std::vector ValueVector; typedef std::pair ValuePair; typedef std::vector PairVector; ty ......

## 思路 思考贪心，容易得出我们只有不断往右跳跃才能走得更远。 所以，对于一个线段 $[l, r]$ 可以轻易到达 $[a, b]$，那么只对 $[l, b]$ 有用，这些点都可以跳到 $b$，$[b + 1, r]$ 这一部分不能往回跳，所以不用考虑。 那么我们就可以把这些线段都当成 $[l, ......

# STEP 1：分析 题目大意：给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。 这一题一眼看出是 P2010 的升级版，所以要先考虑到超时问题，因为如果一天一天地枚举，时间复杂度会非常高，所以我们不能直接枚举。因为题目只要"回文"，所 ......