BJOI

由于大家的做法需要大量分类讨论和代码量，这里提供一种不怎么分类的，容易实现的做法。 首先，由于墙体会随时变化，所以直接对墙体本身维护不是很方便。 我们可以牺牲一点常数，对 \((i,j)\) 建立四个点 \(UL_{i,j},UR_{i,j},DL_{i,j},DR_{i,j}\) 分别表示 \(( ......

题面传送门 这么牛的结论题！ 分别考虑每个联通块，不断去掉一度点显然不影响，我们依次给出几个手玩的结论： 性质 1：如果有奇环，那么无解。 只需要给奇环上的集合全部赋值 \(\{0,1\}\) 即可。 性质 2：若存在两个环的边不相交，那么无解。 考虑一个环，取其对称的两个点，分别记为 \(p,q\ ......

先考虑这个权值 \(\sqrt[c]{\prod\limits_{i = 1}^c V_i}\)。 感觉找不到好的方法算出精确值，但是能发现只用比大小。 于是考虑取个对数成 \(\frac{1}{c}\times \ln(\prod\limits_{i = 1}^c V_i) = \frac{1}{ ......

P3713 机动训练 关键在于 trick：\(\sum a_i^2\) 可以视为两个人走了相同的路径的方案数，证明是容易的：对不同的机动路径求相同的方案数，每种个数为 \(a_i\) 的机动路径会产生 \(a_i^2\) 种本质相同的走法。 如果令 \(dp[x][y][a][b]\) 为两个人分 ......

P4427 [BJOI2018] 求和 谔谔题。这个问题看上去很不可维护，而且让我想到了 P5305 旧词。结果发现怎么 \(k\le50\)，那我直接跑 \(50\) 遍不就好了？ P4429 [BJOI2018] 染色 神仙题。考虑先用一些比较简单的情况搞到一些性质继续研究。那我们不妨只对原图黑 ......

P5319 [BJOI2019] 奥术神杖 数学题。搞掉几何平均数的方法是左右取对数，然后变成一个经典的 \(0/1\) 分数规划问题。解决方法是二分答案后 AC 自动机 + DP。 P5322 [BJOI2019] 排兵布阵 简单题。随便 DP 即可，五分钟之内没想出这道题的赶快去加训。 P532 ......

题面 提供一种不需要多项式/生成函数的做法。 方便起见，记 \(P(G)=0/1\) 表示 \(G\) 是否不存在非平凡自同构。 首先发现对于图 \(G\) 的补图 \(G'\)，显然 \(P(G)=P(G')\)。 那么边数的最大值 \(=\frac{n(n-1)}{2}-\) 边数的最小值。 显 ......

P5322 BJOI2019 排兵布阵 基本思路 一眼背包，然后无脑套01，样例也过了，直接提交，40pts。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace ......

P5323 [BJOI2019] 光线 题目描述 当一束光打到一层玻璃上时，有一定比例的光会穿过这层玻璃，一定比例的光会被反射回去，剩下的光被玻璃吸收。 设对于任意 \(x\)，有 \(x \times a_i\%\) 单位的光会穿过它，有 \(x \times b_i\%\) 的会被反射回去。 现 ......

机动训练 这题的瓶颈，在于把 \(a_i^2\) 看作 \(\sum\limits_{i=1}^{a_i}\sum\limits_{j=1}^{a_i}1\)，然后我们就可以看成“两两相同的机动路径都能贡献 1”。于是我们设 \(f_{x1,y1,x2,y2}\) 表示两条起点为 \((x1,y1) ......

P4133 双倍经验 发现斐波那契数列增长极快，不到 \(100\) 项就超过了 \(10^{18}\)，搜索树也极为稀疏，可以考虑搜索。 爆搜肯定会超时，考虑优化： 可行性剪枝。 记忆化，去除重复的计算。 改变搜索的顺序，因为先考虑小元素的话，会有较多的无用的搜索，且小元素较灵活，更容易凑到 \( ......

P4427 [BJOI2018] 求和 树链剖分+树上前缀和 说来有趣，中午刚学完树上前缀和，立马就在这用上了 注意这里是点的前缀和，算出每个点的前缀和后，会发现有不少重复的，减去重复的点权和，就可以了。 利用mi[j]，数组记录每个深度的第j次方，s[v][j]记录根节点到v点j次方的前缀和。 代 ......

[题目链接](https://www.luogu.com.cn/problem/P4219) 可以发现，一条边 $(x,y)$ 的答案，就是 $x$ 不经过该边可达的点的数量（记作 $cnt_x$） $\times$ $y$ 不经过该边可达的点的数量（记作 $cnt_y$）。 尝试将这个式子转化，若 ......

# [BJOI2019] 排兵布阵 ## 题目描述 小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。 如果一名玩家向第 $i$ 座城 ......

### 题目大意 设对于任意 $x$，有 $x \times a_i\%$ 单位的光会穿过它，有 $x \times b_i\%$ 的会被反射回去。 现在 $n$ 层玻璃叠在一起，有 $1$ 单位的光打到第 $1$ 层玻璃上，那么有多少单位的光能穿过**所有** $n$ 层玻璃呢？ ### 思路 记 ......

[原题](https://www.luogu.com.cn/problem/P5319) 虽然不会AC自动机，但这题的前半部分解法让我小小的震撼了 由于本人水平有限，所以这里只说前半部分思路 我们发现答案$ans=\sqrt[c]{\prod_{i=1}^{c}{w_i}}$，其中这个$\sqrt[ ......

[Problem](https://www.luogu.com.cn/problem/P5322) ### Description 共有$n$种物品，每种物品都有$t$个，每种物品的重量是$a_i\times 2+1$,价值为$i$,现在你有一个重量为$m$的背包，请问你的价值最大是多少？ ### ......

题意描述比较迷惑，剩下 $m$ 个数是无穷的意思是任意操作对它们不产生影响，操作影响的，或者说影响选哪个数进行操作的，只有第一个数，所以当前的状态可以用第一个数的值来表示。 设 $dp_i$ 表示第一个数为 $i$ 时把它变为 $0$ 的期望步数，可得： $$ \begin{aligned} &dp ......

## 题目大意 有s名对手，n座城堡，你有m名士兵 如果一名玩家向第 $i$ 座城堡派遣的士兵数**严格**大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 $i$ 分。 求最大得分 ## 数据范围 对于 $10\%$ 的数据： $s=1,n \le 3,m \le 10$ 对于 $20 ......

[TOC] ### [题目链接](https://www.luogu.com.cn/problem/P4219 "题目链接") ### 题目描述： [BJOI2014]大融合 题目描述 小强要在 $N$ 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 $N$ 个点的一个树。 这个树的边是一条 ......

# [BJOI2014]大融合 ## 题目描述 小强要在 $N$ 个孤立的星球上建立起一套通信系统。这套通信系统就是连接 $N$ 个点的一个树。 这个树的边是一条一条添加上去的。 在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。 ![](https://cdn.luog ......

[题面传送门](https://www.luogu.com.cn/problem/P4581) 好牛逼的题目！ 首先直接 bitset 啥的看看就不太行，考虑随机化啥的。 考虑给每个想法赋一个权值，并求出每个点所能走到的想法的最小值。我们知道，$k$ 个 $[1,RANDMAX]$ 范围内的最小值的 ......

# 「BJOI2017」树的难题 TJ+卡题 ## 题目大意 - 给定一棵 $n$ 个点的树，每条边有颜色，第 $i$ 种颜色权值为 $v_i$，共 $m$ 种颜色。 - 对于树上一条路径，其权值定义为：经过边的颜色依次组成序列，每个相同颜色段的颜色权值之和。 - 如：颜色序列 $1,2,2,1,1 ......

P5322 BJOI2019 排兵布阵 本题主要考察对模型的转化能力。 首先要察觉两条性质： 对于一个城堡，想打败一个玩家的同时用最少的士兵，肯定是正好派出这个玩家在这个城堡派出的士兵数量的二倍加一名士兵。 在一个城堡上，打败了一个在这个城堡派出士兵数量为 $x$ 的玩家，就可以顺便打败所有在这个城 ......