题解034f agc

## 思路 分组背包模版题，不多说。 # 代码 ```cpp #include #define ll long long #define ld long double using namespace std; inline void read(int &x) { x=0; short flag=1; ......

## 思路 先枚举出 $n$以内的4次方数 然后dp. # 代码 ```cpp #include #define ll long long #define ld long double #define min(x,y) (x'9') { if(c=='-')flag=-1; c=getchar(); ......

## 思路 这道题和 [NOIP2005 普及组] 采药的思路差不多 不同的是，这道题是完全背包，采药则是01背包。 转移方程为：```dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//滚动数组优化``` # 代码 ```cpp #include #define ll long ......

# 第二次比赛题解 ## [P1138 第 k 小整数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P1138?contestId=120025) **主要了解set的用法,set会自动去重和排序** ```c ......

## 思路 01背包模版题 转移方程为：```dp[j]=max(dp[j],dp[j-ti]+wi);//滚动数组优化``` # 代码 ```cpp #include #define ll long long #define ld long double using namespace std; ......

## 思路 ### 01背包模版题，唯一不同的是加了一个条件就是价格与重要度的乘积。 转移方程为：```dp[j]=max(dp[j],dp[j-w[i]]+w[i]*v[i]);``` 这里加了滚动数组优化。 ## 代码 ```cpp #include #define ll long long # ......

思维 + dp。 如果像题意那样先放球再染色的话不是很好做。 所以考虑有 $n$ 个白球，$n$ 种其他颜色的球各 $k-1$ 个。 那么限制就是说对于每个前缀，白球的个数 $\ge$ 其他颜色球的种数。 所以就可以设 $f_{i,j}$ 为放了 $i$ 个白球，$j$ 种颜色的 $k-1$ 个球的 ......

【大联盟】20230626 集查并（dsu） 题解 AT_toyota2023spring_final_g 【Git Gud】 zyx /bx ## 题目描述 [here](https://atcoder.jp/contests/toyota2023spring-final/tasks/toyota ......

# Description 给定一个由 `J`、`O`、`I` 组成的字符串，求最多能拆分成多少 `JOI` 或 `IOI`。 对于所有数据，$1\leq \vert S\vert\leq 10^6$。 # Solution 先处理出 $\text{pre}_i$ 为前缀 `J` 和 `I` 的数量 ......

恐怖 zak 将这题加强，出到模拟赛。直接把 $A_i,B_i\le 10^5, C_i\le 5$ 变成了 $A_i,B_i,C_i\le 10^9$。 非常恐怖。 ## 题目描述 [here](https://www.luogu.com.cn/remoteJudgeRedirect/atcode ......

[原题链接](https://www.luogu.com.cn/problem/P4552 "原题链接") 第一步对于学过差分的人应该不难想 定义差分数组 $dis \quad s.t. \quad dis[i] = a[i] - a[i-1] $ 那么不难发现问题一只要让 $dis[2] ... ......

[TOC] ## CSP 模拟 1 [来自学长的馈赠 2](https://www.cnblogs.com/CDOI-24374/p/16503427.html) . ## CSP 模拟 2 ### F 考虑 $x$ 只能在 $a_1\oplus b_i$ 里选，那么分别代入暴力检验即可 . 时间复 ......

[幽灵乐团](https://www.luogu.com.cn/problem/P5518) ### 题目大意 $T$ 组数据，每组数据给定 $A,B,C$，求： $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\Big(\frac{\text{lcm}(i,j)} ......

[problem](https://www.luogu.com.cn/problem/P9352) & [blog](https://www.cnblogs.com/liangbowen/p/17571984.html)。 HerryHuang 的 DP 专题中最喜欢的一题，抢第一篇题解 /fend ......

# Description 给定 $n$ 条鱼，每条鱼有长度和颜色。你可以选出若干条鱼，需要满足最大长度小于最小长度的两倍。定义两种养鱼方案不同仅当它们三种颜色之一的出现次数不同，求不同的养鱼方案数。 对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5$。 题目链接：[ ......

### Statement $T$ 次给定整数 $n$，判断是否存在 $q, k \ge 2$ 使得 $1 + q + q^2 + \cdots + q^k = n$。 $1 \le T \le {10^4}$，$1 \le n \le {10}^{18}$。 ### Solution 考虑弱化问题 ......

# Description 有 $n$ 个套娃，每个套娃都有外体积与内体积，内体积严格小于外体积。你可以把一个娃套到另一个内体积比它的外体积大的娃里面，并且需要套到不能再套为止。求出有多少种套娃方案。 题目链接：[JOI](https://www2.ioi-jp.org/camp/2012/2012 ......

# P4843题解 + [原题连接](https://www.luogu.com.cn/problem/P4843) ## 建模 一到比较裸的有源汇上下界最小流。每条边必走一次，要求求出最小的流量。由于比较裸，这里当作上下界流的例题讲。 ## 什么是有源汇上下界最小流 顾名思义，就是在最大流的基础上 ......

## [题目](https://tg.hszxoj.com/contest/759/problem/8)  ## 前言 出生镇楼 [![](https://cdn.luogu.com.cn/ ......

思路不错。 首先考虑把每个机器人转化为 $(a_i,b_i)$ 两个参数。 表示向左 $a_i$ 步会进入左边的出口，向右 $b_i$ 会进入右边的出口。 > 注：此时其他只能进入唯一的出口的机器人不影响答案，不考虑。 记 $c_i=0/1$ 表示 $i$ 号机器人是进入左边还是右边出口。 然后考虑 ......

先说思路： 因为我们是比对较短的$B$与较长的$A$的子串，所以我们求不变的$B$的$next$ 对于这道题我们可以使用树状数组查询前缀和维护数的排名。 对于相同的数我们查询的排名是有误的，因此不仅要比对小于等于该数的前缀和，也要比对小于该数的前缀和。 如:对于$A=2$ $2$,$B=1$ $2$ ......

## [牛客小白赛 65](https://ac.nowcoder.com/acm/contest/62008 "模拟赛 2 题解") ## [A. 牛牛去购物](https://ac.nowcoder.com/acm/contest/62008/A "A 牛牛去购物") ### 标签 `统计类 D ......

首先如果一开始 $A$ 和 $B$ 相同，可以直接输出 $0$。 否则 $O(n^2)$ 枚举一个被操作的叶子 $x$，和 $x$ 接到了的 $y$ 点，此时 $x$ 不能再被操作，所以将其当作新树 $A'$ 和 $B$ 的根节点。 由于操作是作用于叶子的，所以一个非叶节点想要被操作，当且仅当其所有 ......

考虑先手操作完后得到的序列为 $b_i$，后手如何操作得到最大答案。 由于不互质的数不能交换，所以任意一对 $i<j,\text{gcd}(b_i,b_i)\neq 1$，后手操作后相对顺序不变。 所以可以枚举每对不互质的数，编号小的往大的连边，然后用优先队列跑最大拓扑序。 再考虑先手如何操作。 容 ......

神仙题。 由于时间限制 $5\text s$，我们可以整点怪的，比如根号分解质因子。 但是直接分解是 $O(n\sqrt w)$ 的，值域为 $w$ 即 $10^{10}$，肯定会炸。 毛估估一下，如果需要分解质因数，大概只能分解到 $O(\sqrt[3]{w})$ 的质数。 我们把小于 $\sqr ......

这种点对移动互相感染的题，一般可以建笛卡尔坐标系。每个点 $i$ 坐标为 $(V_i,X_i)$，若有两个点 $a,b$ 的相遇时间为 $\dfrac{X_a-X_b}{V_b-V_a}$，即 $-k_{ab}$。 所以当且仅当两个点连接直线的斜率为负数时，两个点会在时间 $t_{ab}=-k_{a ......

经典题。 考虑 dp，然后发现你根本 d 不动。 冷静思考，发现原因在于，无法在较小的复杂度内确定选数的状态。 遇到这种情况可以考虑容斥。设 $f(i)$ 表示强制选 $i$ 个位置满足 $|p_j-j|=k$。 显然 $\text{ans}=\sum\limits_{i=0}^n(-1)^if(i ......

sweet tea. 手玩一下发现「交换」的性质是具有传递性的，所以考虑一个 $O(n^2)$ 做法： 枚举每个点对，如果满足交换条件，则连双向边。显然一个连通块内的点可以互相交换，而不同连通块之间互相独立。答案就是 $\prod\limits_{i=1}^m\dbinom{size_i}{s_{i ......

## 格雷码 && CF1848F. Vika and Wiki 题解 本来有个GitHub上的Hexo博客的，但是我用起来不太熟练……先在博客园里写了后到时候转移过去吧。 ### 前置知识：格雷码（了解的读者可以跳过） 格雷码是所有k-bit（含k个二进制位）的数的一个排列，使得两个循环相邻（即两 ......

```c++ #include using namespace std; /* LingHusama题解 （atcoder bushigeshizhenpi） 1.背景：老师说做做复习下最短路 我：有最短路吗？不是模拟吗？ 2.解题思路： 我的题解稍微用到了最短路的思想，但代码与其完全没关系 模拟+ ......