JSOI

思路 每次询问 \(u,v\) 的简单路径上有多少个字符串以 \(s\) 为前缀，不难想到用 trie 树去维护。而普通的 trie 只能查询所有字符串中产生的答案，对于这类区间询问，就要用到可持久化 trie 树了。不会右转可持久化 trie 树模板题。 \(u,v\) 的简单路径上编号不连续，非 ......

题面传送门 本来以为 \(m\) 这么小是 \(m\sum k_i\log k\) 的 NTT 的，写完发现一点不用（ 首先我们发现，这样的图上面的一个哈密顿回路可以表示成原森林若干条链，每个点都在其中一条链上，且相邻两条链不在同一棵树上。 先跑一个 DP 把 \(f_{i,j}\) 表示用 \(j ......

P8061 [JSOI2016] 炸弹攻击1 - 数据加强版 第一种情况现有的题解讲的很详细，这里只讨论第二种情况 也就是求 与两圆相切 且 过定点的圆 的方法 并且似乎现有的二分思路不严谨？ 先来考虑正常二分的思路 选定 一个点 和 一个圆，二分 增加半径，求出扩张后 新的圆交点，然后与 判断与第 ......

本篇题解参考 @djwj223，但是本人太弱了，对着代码看了 INF 年才看懂。因此写一篇具体讲解实现方面的题解。在此先表示感谢。 思路 考虑最终的答案圆会是怎样的。第一种是半径达到了 \(R\) 的上界，不能继续扩充。显然这种情况可以把圆移动一下使某个点在圆上，以此进行计算。第二种是楼上所说的与两 ......

20230921 P4037 [JSOI2008] 魔兽地图 sol 前言 历经千辛万苦终于调出来了， 细节不是有点多吧~ 还参考了题解…… Statement 有 \(n\) 种装备，你有 \(m\) 块钱。装备的合成路线形成一棵树。叶子节点的装备需要用钱买，非叶子节点需要用它的儿子合成（对于一个 ......

problem 给你两个平面凸多边形 \(A,B\)，\(Q\) 次询问，每次询问是一个向量 \(\vec v\)，回答 \(A\) 与 \(B + \vec v\) 是否有交。\(n,Q \leq 10^5\)。 solution 观察闵可夫斯基和（Minkowsky sum）的定义，若将这个运算 ......

原题 题解里大部分做法要做两次二项式反演，不知为何有点喜感 老规矩，先说我的做法： 方法1： 我一开始也想到了要做两次二项式反演，但感觉好麻烦，于是把一个二项式反演换成了\(dp\)，复杂度就差了一些 首先我们发现行列的限制不好容斥，因此我们考虑容斥颜色的限制。具体的，设\(f_i\)表示有至少\( ......

原题 还是二项式反演，主要问题是怎么发现他是这个关系 因为我们发现我们钦定\(T,P \subseteq S,|T|=|P|\)时，我们假设里面有一个元素\(x,y\)不相同，则他们会计算两次 因此是二项式反演 ......

[原题](https://www.luogu.com.cn/problem/P4042) 非常好的一道题，用到了一个重要的思路：消除$dp$的后效性 不要觉得这个东西很恐怖，其实这个东西并不复杂，只是名字有点吓人 我们容易想到对把原题抽象成一个图，我们容易想到如果该图为$DAG$我们要怎么做，直接拓 ......

[link](https://www.luogu.com.cn/problem/P4306) 洛谷上的题解的做法似乎有点麻烦。（不得不说时限 300 ms ） 这里我们看了题后我们可以选择传递闭包做法。 但是时限太短，我们可以利用 bitset 优化。 明显会被 hack ，但是都 2023 了，N ......

[题目链接](https://ac.nowcoder.com/acm/problem/20189) # 题目 **题目描述** JYY 带队参加了若干场ACM/ICPC 比赛，带回了许多土特产，要分给实验室的同学们。 JYY 想知道，把这些特产分给N 个同学，一共有多少种不同的分法？ 当然，JYY ......

# [题目描述](https://www.luogu.com.cn/problem/P4516) 外星人又双叒叕要攻打地球了，外星母舰已经向地球航行！这一次，``JYY`` 已经联系好了黄金舰队，打算联合所有 ``JSOIer`` 抵御外星人的进攻。 在黄金舰队就位之前，``JYY`` 打算事先了解 ......

> 题外话，以后正经题解放洛谷上，贺题记录这种放博客园吧。 学习自 AThousandSuns 大佬的[博客](https://www.luogu.com.cn/blog/1000suns/solution-p5503 "博客")。 # 题意 给定长度为 $n$ 的数组 $h$ ，对于每一个 $i$ ......

### Description [Problem](https://www.luogu.com.cn/problem/P4306) ~~由于题目太短我直接上图罢~~ ![image](https://img2023.cnblogs.com/blog/3195128/202308/3195128-20 ......

### 简要题意 现在给出了一个简单无向加权图。你希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。输出方案数对$31011$取模。 ### SOLUTION 这个题求最小生成树的方案 所以我们从最小生成树入手 （根据kruskal的思 ......

一、题目描述： 给你一颗 $n$ 个节点的有根树。节点 $i$ 的价值为 $v_i$，费用为 $w_i$。 你需要选择 $k$ 个节点，使得 $\frac{\sum_{i=1}^nv_i}{\sum_{i=1}^nw_i}$ 最大。 约束：选择一个节点之前，必须先选择它的父亲节点。（根节点除外） 输 ......

第一道 AC 自动机 + DP 题。 题目链接：[P4052 [JSOI2007] 文本生成器 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P4052) 利用容斥原理的思想，答案就是所有串的数量减去不可读的串的 ......

# Day -15 开坑，但愿能进决赛 # Day -10 组了个MOer，希望能帮忙做点数学题 # Day 1 A做了好久，还是要多练脑子 B推出来了不敢做，怕罚时(怕个P 同余最短路没调出来，晚上去补 签到签得太慢(虽然不是我写的 寄，如果有强一点的队友可以过个六题左右吧 现实是一轮游了 题解写 ......

[P4322 [JSOI2016]最佳团体](https://www.luogu.com.cn/problem/P4322) 分数规划+树形背包。 可以根据推荐关系建出一颗树，然后如果选了一点，则该点到根上的所有点都必须选。 二分 $mid$，定义每个结点的权值，然后判断选 $k+1$ 个节点的最大 ......

## Description 在这个游戏中，JYY 一共有两种攻击方式，一种是普通攻击，一种是法术攻击。两种攻击方式都会消耗 JYY 一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则 ......

## Description JYY 最近迷上了拼图游戏。作为一个计算机科学家，JYY 有一套黑白色的拼图，他希望通过合理的拼接，使得拼出的最终图案中，能包含面积最大的全白色子矩形。JYY 一共有 $S$ 块拼图，并且由 $1$ 到 $S$ 编号。编号为 $i$ 的拼图是一个 $N$ 行的方格矩形， ......

# [AHOI2014/JSOI2014] 骑士游戏 观察性质： 1. 对于一类怪兽，要么全部使用普通攻击，要么全部使用魔法攻击。 2. 若对怪兽 $i$ 满足 $s_i > k_i$，则必使用魔法攻击。 3. 若按照怪兽的生成关系连有向边建图，则一个环内 $k$ 值最小的怪兽必使用魔法攻击。 注意 ......

20230707 ~~不想做题于是随机跳题~~ [传送门](https://www.luogu.com.cn/problem/P6093 "传送门") 我们考虑每个套娃$i$套到另一个套娃$j$里面的价值 很明显可以知道，这样可以减少$b[j]* out[i]$ 为了让答案尽可能小 我们就要让每一个 ......

[TOC] ## 潜入行动 一眼直接 DP。 设 $f_{i,j,0/1,0/1}$ 表示 $i$ 子树内放了 $j$ 个监听设备，$i$ 是否被子结点覆盖，$i$ 是否放了监听设备，$i$ 子树内除了 $i$ 都被覆盖的方案数。 转移是一个树形背包，时间复杂度 $\mathcal{O}(nk)$， ......

# P5333 [JSOI2019]神经网络 ## Solution `EGF` 表示有标号排列。 对每棵树分别算出划分成 $i$ 条链的方案数，记为 $f_i$。 > 具体地：设 $dp[u][i][0/1/2]$ 表示在 $u$ 子树内拆分成 $i$ 条已结束的链， > > $0$: 已拼完，无 ......

##暴力水过了wwwwwwwwwwwwwww ``` #include // //#define LOCAL FLANDRE KAWAII #ifndef LOCAL constexpr int SIZE(1'9';ch=getchar()) f^=ch=='-'; for(;ch>='0'&&ch ......

# 闵可夫斯基和 ## 前言 入门建议看吉老师（吉如一）的[计算几何入门到放弃](https://www.bilibili.com/video/BV1Bt411j7bs/?spm_id_from=333.337.search-card.all.click&vd_source=f401181639ee ......

[[JSOI2007]建筑抢修](https://ac.nowcoder.com/acm/problem/20154) 跟经典题poj1456非常像。 首先如果两个都被选入那么截至时间T2小的放前面肯定更优，所以我们先按T2排序。然后逐个遍历建筑，建立一个维修时间为关键字的大根堆，如果前面花费的总时 ......

题目链接 题目 题目描述 现在请求你维护一个数列，要求提供以下两种操作： 1、 查询操作。语法：Q L 功能：查询当前数列中末尾L 个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。 2、 插入操作。语法：A n 功能：将n加 上t，其中t是最近一次查询操作的答案（如果还未执行过查询 ......

P6134 [JSOI2015]最小表示 思: 有向无环图，想到拓扑排序。 逆序枚举，因为排序后下标小的点用到它前面的点的联通性。 对其连接的点按照拓扑序由小到大进行排序(靠前的点可以连接的点多，那么可以删的边数也变多。 其余套路与可达性统计类似，注意代码细节。 #include <bits/std ......