蓝桥 题解2017

#### [原题传送门](https://atcoder.jp/contests/abc306/tasks/abc306_e) 题意：带修维护序列前k大的和 首先性质：1、只关心值；2、k不变 一眼ds，且是排序类的。修改可以拆成插入和删除。一眼Treap。 然后再考虑k不变。我们发现每次修改我们在 ......

~~晚自习。不想做题了，来写篇题解消遣一下（~~ **[原题传送门](https://atcoder.jp/contests/abc242/tasks/abc242_f)** 题意：挺简洁的，懒得说了。鸽。 刚看到这题的时候没有一点头绪，乱想了状压啥的。但现在看来，其实是因为没有抓住重点。 首先此题 ......

### **[原题传送门](https://atcoder.jp/contests/agc002/tasks/agc002_e)** 题意：给一个正整数序列 $a$，两人轮流操作直到不能再进行任何操作，每次操作可以将序列中的一个最大的数变为 $0$，或者将序列中所有正整数减去 $1$。当序列中所有数 ......

原文：VS2019 C++ 调用python函数/类对象的方法_ 蜗牛在听雨的博客-CSDN博客_c++调用python函数 1、c++调用python类（传图像参数） ，编译出错，解决方法： 因为需要转换图像格式，从opencv的Mat格式转为python的PIL格式，需要用到numpy的C++接 ......

题目链接：[【LuoguP3306】](https://www.luogu.com.cn/problem/P3306)。 ## 前置知识 OI-Wiki：[快速幂](https://oi-wiki.org//math/binary-exponentiation/)，[扩展欧几里得算法（exgcd）] ......

# HDU 多校 Round #6 题解 $\text{By DaiRuiChen007}$ ## A. Count [Problem Link](https://acm.hdu.edu.cn/showproblem.php?pid=7336) **题目大意** > 求有多少个长度为 $n$，字符集 ......

## problem You are given an integer sequence $A_1,A_2,\ldots,A_N$. You'll make a rooted tree with $N$ vertices numbered from $1$ through $N$. The vert ......

给定 $01$ 矩阵 $C$，求有多少个 $01$ 矩阵的有序对 $(A,B)$ 满足 $A \times B \equiv C \pmod 2$。 $n \leq 2 \times 10^3$。 先考虑如果知道了 $A$ 怎么做。考虑把 $C$ 和 $A$ 写成若干行向量的组合 $c_1 \sim ......

给定 $n$ 个物品，第 $i$ 个物品有体积 $c_i$，价值 $v_i$。给定 $K$，对 $1 \sim K$ 的所有 $i$ 求大小为 $i$ 的背包的最大价值。 $n \leq 10^6$，$K \leq 5 \times 10^4$，$c_i \leq 300$，$0 \leq v_i ......

题目链接 Royal Questions - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 分析 每个公主会选择两个王子，考虑将每个公主所选择的两个王子连边，边权为该公主的嫁妆 选择该边即为选择该公主 那么结果图是什么呢？ 由于每个王子最多只能选择一个公主即每个点最多有1个出边（也可 ......

## A.New Palindrome ### 题目描述： 给你一个由小写字母组成的回文字符串，问你是否能在重排其之后构造出另一个与原串不同的回文字符串。 多测，$t \le 1000,2 \le |s| \le 50$ ### 题目分析： 考虑其实就是前 $\lfloor \frac{n}{2} ......

~~好像并没有**矩阵快速幂**的题解，那我来写一篇~~ ## 题目分析 ### 对于每两盏灯，只考虑右灯变化，分为四种情况： 左灯为 $1$，右灯为 $1$，右灯变为 $0$； 左灯为 $0$，右灯为 $0$，右灯不变，为 $0$； 左灯为 $1$，右灯为 $0$，右灯变为 $1$； 左灯为 $0 ......

思路前几篇题解都介绍了，这里着重介绍一个状态设计的小技巧。 在设计状态时，我们可能会碰到**状态数值过大，而dp数组内存的值较小**的情况。 例如在该题用 $dp_{l,r,t,0/1}$ 表示逆时针经过 $l$ 个，顺时针经过 $r$ 个，已经花费 $t$ 秒，所拿到的雕像个数，$0$ 表示当前在 ......

模拟赛做到的题，赛后看了 Y2hlbnlpa2Fp 的题解，感觉没讲清楚，这里做下补充，提供自己的理解。 ### 基本思路： 对每个 $A_i$ 的答案进行预处理，对于每个询问，只需要找到第一个到达的景点即可。 那么如何预处理每个点的答案呢？有一条很重要的性质：**最多转向 $\log{X}$ 次* ......

~~模拟赛做到的题，场上写贪心爆栈了qwq~~ 首先在首尾加上两个 $1$ 表示进出，将两段路中间的间隔作为传送门，恰好有 $2 \times N$ 个传送门，根据两段路的经过情况给传送门分类别： `00`：用 $N$ 表示，称为无用点，不到达该点。 `10`：用 $S$ 表示，称为起点，需要通过向 ......

## 前言 昨天考试考到过了，顺便叫发题解，我的做法有两个，一个 $O(n)$，一个 $O(n\log n)$。 ### $O(n\log mn)$ 的方法——三分 当时考试时就想到了，因为这次的答案是单谷函数，可以使用三分，跟二分差不多，就是找向左走上升还是向右走更优，然后 $O(n)$ 统计一下 ......

准备安装QT，参考教程： 安装CUDA11.3 配置环境 与在VS2017中的配置不同，VS2017可以在选项卡中对CUDA的编译调试环境进行配置，而在QT中，这都需要在工程文件.pro中，通过代码来实现。下面介绍如何新建一个可运行CUDA代码的QT工程。 （1）新建一个QT Console App ......

准备 安装好VS2017和CUDA11.3，这两个软件的安装都很简单，网上也有很多的教程，对于对应的系统环境变量的配置，一般安装成功后，都会自动添加好，只需要按照网上的教程检查一下即可，下面我会给出我个人感觉不错的安装教程。 VS2017安装 CUDA安装 CUDA自带例程（1）首先测试CUDA安装 ......

# 23 暑假友谊赛 No.4(UKIEPC 2017) ## Problem A Alien Sunset ~~hh,开始一眼差分,但是写寄了qwq~~,后来换枚举过了(Orz,但是看学长差分是能做的,我就说嘛,差分肯定能做( **说下枚举思路吧,就是把每个区间都存起来,选出自转周期的最大值为$m ......

# A-Alien Sunset 这到题，用一个数组表示当前时间有多少个星球是夜晚，这样就转换成了区间修改单点查询。因为只查询一次，所以用差分即可。 ```cpp #include using namespace std; #define int long long const int m = 18 ......

**[原题传送门](https://atcoder.jp/contests/abc262/tasks/abc262_e)** 感觉是一道不是很难想到但还是比较不错的题。 题目要求将k个点染成红色，那么我们不妨首先将所有点视为蓝色，然后一个一个地将红点加进去。 那么就从简单的入手，考虑最初只加入一个红 ......

测试小姐姐给了我一个活，因为他懒得一个个根据表输入名字，所以要实现输入姓氏，然后出现下拉框，其中展示所有含该姓氏的人名，基础模板如下 ![](https://img2023.cnblogs.com/blog/3078120/202308/3078120-20230810091312593-11617 ......

# [ABC311] D~G 题解 ## D - Grid Ice Floor 搜索 题目的意思实际上是要求出所有可能到达的点，也就是说所有路径可达点的并。 基本上看清题目就会了，直接搜索每个点，每次枚举四个方向的时候直接冲到底，需要用数组去重贡献。 ```cpp void dfs(int x, i ......

[题目链接](https://www.luogu.com.cn/problem/P2149) 题意简述：求两条给定起点终点最短路的最长公共路径。 首先最长公共路径一定是两条最短路的公共最长链的部分。至少一定在两条最短路上。 考虑如何求出一条路径是否包含于一条最短路，只要路径 $x\rightarro ......

妙妙题。 ### 题意 给定 $F_0(x)=a_{(x-1)\bmod n +1}$。 $$ F_k(x)=F_{k-1}(x)-\sum\limits_{i=2}^n F_k(\lfloor\frac{n}{i}\rfloor) $$ 求 $F_k(m)$。 $1\le n\le 10^4,1\ ......

集体被大样例薄纱了。 ## T1 P1292 > 有两个容量分别为 $a$ 与 $b$ 的酒杯与一个容量无限的酒桶，有以下几种操作： > 1. 用酒桶将 $a$ 倒满； > 2. 将 $b$ 中的酒全部倒入酒桶； > 3. 将 $b$ 中的酒倒入 $a$，直到 $a$ 被装满或 $b$ 被倒空。 > ......

一个非常显然的事情是：总方案数即为每条边方案数之积。 树边已经确定，考察每条非树边 $(u,v)$ 可以怎么取。给定的树 $T$ 是唯一最小生成树，这意味着非树边 $(u,v)$ 要么不存在，要么权值大于 $T$ 上 $(u,v)$ 之间任意一条边的权值。设 $T$ 上 $(u,v)$ 间的最大边权 ......

打算只写点有意思的题。 ### D1J Easy problem I 注意到 $x_i$ 单增，所以一个数被减到负数之后，所有的操作都会将它减到负数，也就等价于乘 $-1$ 再相加。 使用一棵线段树维护所有数，将这些数分为两种，一种如上，一种是区间减。 最终所有数都会变为需要乘 $-1$ 再相加的数 ......

[Lnk](https://www.luogu.com.cn/problem/P4069) 首先树剖，然后变成在 $\text{dfn}$ 区间上插一个关于 $\text{dis}$ 的一次函数。这个很神奇，一般的李超树是，在 $x$ 轴区间上插入关于 $x$ 的一次函数。然而这里，$\text{d ......

[TOC] # 题目 [题目链接](https://www.luogu.com.cn/problem/P4200) # 解题思路 首先，此题有明显的插入、删除、查找，所以必须要使用平衡树。 考虑如何使用平衡树维护每个鸟的状态。发现很不方便，因为鸟的位置改变，整个平衡树的值都要修改。 考虑针对每个节点 ......