集训队 普罗2015

## Problem 一个长度为 $n$ 的序列 $a$，设其排过序之后为 $b$，其中位数定义为 $b_{n/2}$，其中 $a,b$ 从 $0$ 开始标号，除法下取整。 给你一个长度为 $n$ 的序列 $s$。 回答 $Q$ 个这样的询问：$s$ 的左端点在 $[a,b]$ 之间，右端点在 $[ ......

## [NOI2014]动物园 ### 题目描述 我们给定一个字符串 $S$ ，定义 $num[i]$ 表示 $S$ 的前 $i$ 个字符组成的字符串中，长度小于等于 $\lfloor\dfrac{i}{2} \rfloor$ 的 $border$ 数量。求 $\sum (num[i]+1) $ 。 ......

# Day2 ### P7154 [USACO20DEC] Sleeping Cows P 将奶牛和牛棚放到一起从大到小排序然后 dp．考虑提前确定一只奶牛是否被空余出．记 $F_{i,j,0}$ 表示前 $i$ 个东西， ### P8863 「KDOI-03」构造数组 考虑按序列顺序 dp，记 $ ......

## 简要题意 有两个正整数 $a<b\le 10^9$，给出 $\dfrac{a}{b}$ 的小数点后 $19$ 位，要求还原 $a,b$，保证有解。 ## solution 一个科技：$\texttt{Stern-Brocot tree}(SBT)$，可以参考[这个博客](https://www ......

刚开始你有一个数字 $0$，每一秒钟你会随机选择一个 $[0,2^n-1]$ 的数字，与你手上的数字进行或（C++,C 的 `|`，pascal 的 `or`）操作。选择数字 $i$ 的概率是 $p_i$。保证 $0\leq p_i \leq 1$，$\sum p_i=1$ 。问期望多少秒后，你手上... ......

# Day 2 ## A.sequence ### 题目描述： ### 题目分析： 考虑一个很简单的 $dp$ 就是设 $f[i]$ 表示考虑了前 $i$ 个位置最多可以划分为多少个序列。 转移就是可以直接从 $f[i-1]$ 继承，或者从 $j$ 满足 $\sum_{k=j+1}^{i} c_i ......

# 2023暑假集训杂题解题报告 ## UOJ NOI Round #7 Day1 那些你不要的 [题目链接](https://uoj.ac/contest/84/problem/809) ### 题目描述 给定长度为 $n$ 的序列 $A$，保证 $n$ 为奇数，你是先手，每次先手与后手分别取相邻 ......

## [目前进度——动态规划1：线性dp、背包问题，区间](https://ac.nowcoder.com/acm/contest/24213#question "目前进度——动态规划1：线性dp、背包问题，区间") ## 好题 ### [1003 可爱の星空](https://ac.nowcode ......

在可能泄漏的文件头部加入下面几行（保证malloc和new的泄漏都可以检测到） #define _CRTDBG_MAP_ALLOC #include <crtdbg.h> #ifdef _DEBUG //重载new运算符 #define new new(_NORMAL_BLOCK, __FILE__ ......

 ## solution 首先，随机化、退火、贪心找规律等乱搞我们在考场上拿了 $[50,60]$ 的分，还是很高的。 考虑观察到一件事情：我们只需对于所有素数 $p$，确定 $a_p$ 即可确定所有 $a_ ......

[洛谷传送门](https://www.luogu.com.cn/problem/P6667 "洛谷传送门") 点值不好搞。考虑把它搞成系数一类的东西。 由二项式反演，$f(x) = \sum\limits_{i = 0}^x \binom{x}{i} b_i \Leftrightarrow b_i ......

# 页面布局 ## **1.盒子模型**  ![image](https://img2023.cnblogs ......

 # 1.**标题** **标题的排版** ![image](https://img2023.cnblogs ......

## 题目背景 一年一度的“跳石头”比赛又要开始了! ## 题目描述 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到 ......

## 出题人：$\text{D}\color{red}\text{eaphetS}$ ## [#A. [NOIP2012 提高组] 开车旅行](https://oj.hailiangedu.com/d/hlxly2022/p/P1081?tid=64b026672723396d9906d050) 倍 ......

### 质数和约数 > 质数是指除了 $1$ 和它本身之外没有其他因数的自然数。 #### 质数判定 判定单个自然数是否为质数，可以使用试除法，在这里不多描述。 ```cpp bool is_prime(int n){ if(n 练习1：Prime Distance [$\texttt {Prime ......

**滚动数组代码** 点击查看代码 ``` //滚动数组代码 //时间复杂度：O(nm) #include using namespace std; int f[maxn][maxn],v[maxn],w[maxn],m,n;//f[i][j] 代表前 i 个物品已经考虑完，用掉了 j 的体积所能获 ......

[题目链接](https://www.luogu.com.cn/problem/P2680) 闲话：虽说是紫题，但慢慢想还是完全没有问题的。 由于 $m$ 个运输计划同时开始，所以耗费时间就是最慢的飞船耗费的时间（即最长时间）。考虑到题目让求最短时间，也就是最长的最短，可以二分。 考虑二分最长时间（ ......

title: 2022 省队二轮集训培训日记 Day1 mathjax: true date: 2022-07-16 20:28:18 tags: - 培训日记 - 李超树 - DP - 线段树 - 树套树 - 凸包 feature: false categories: 做题记录 cover: ht ......

title: 2022 省队二轮集训培训日记 Day4 mathjax: true date: 2022-07-19 20:58:09 tags: - 培训日记 - 计算几何杂项 - 生成树 - DP feature: false categories: 做题记录 cover: https://pi ......

title: 2022 省队二轮集训培训日记 Day5 mathjax: true date: 2022-07-20 19:09:05 tags: - 培训日记 - 欧拉路径 - 数论 feature: false categories: 做题记录 cover: https://pic.imgdb. ......

title: 2022 省队二轮集训培训日记 Day7 mathjax: true date: 2022-07-24 08:35:06 tags: - 培训日记 - DP - 凸包 - 网络流 feature: false categories: 做题记录 cover: https://pic.im ......

# [BalticOI 2015] Tug of War ## 题意 拔河（*Tug of War*）在 Byteland 是十分受欢迎的运动。规则十分简单：两队以相反方向拉绳子。一年一度的 Byteland 拔河比赛将要进行，并且许多选手都报名参加了。作为公平竞赛专员，你的工作是把选手们划分为两个 ......

# T1 前 $20pts$ 打的暴力，然后打了 $30pts$ 的特殊性质，测样例的时候把暴力的判断关掉了，样例过了又忘了打开。结果写对的暴力没运行，特殊性质还写挂了。 树形 dp + 分讨。其实转移很好想，但是状态表示不好设计。$dp_{u,i}$ 表示从 $u$ 的祖先掉下 $i$ 个球的方案 ......

> 太阳🔆未起床，我去上集训~ > > 坐着车🚗，到门口🚪，迷迷糊糊坐在电脑💻前~ > > 看一看题目，全都不会😭做！ > > 摸电线:zap:，开电闸，滋滋滋滋到阎王👼面前~ #### 闲聊一阵 emm，今天我被各种东西虐惨了！ Why？ 早上 $\texttt {6:00}$ 起床， ......

**匈牙利算法** 点击查看代码 ``` //匈牙利算法代码 //匈牙利算法可用邻接矩阵和编表，优化用编表，不优化用邻接矩阵 //时间复杂度：O(n^3) #include using namespace std; bool z[maxn][maxn],vis[maxn];//z[i][j]代表左边 ......

### 20230710 #### [ I - Visiting Friend(点双/圆方树)](https://codeforces.com/gym/104427/problem/I) 题意 多次询问两个点之间所有路径可能经过的点数，路径只需要满足起点和终点不重复经过。 $N,M,Q ≤ 5\ti ......

次小生成树：第二小的生成树。 次小生成树：删掉一条边，再加上一条边，使得差值尽量小，并且要是一个树。 次小生成树：如果一条边在最小生成树上，我们就叫他树边，如果不在最小生成树上就叫他非树边。 次小生成树：删掉一条树边，加上一条非树边。 次小生成树：倍增 LCA 询问环上最大的值（章鱼图）。 从一张 ......

## 简要题意 有 $1\le T\le 10^6$ 次询问，每次询问正整数 $n$，问是否存在三个**正整数** $a,b,c$，满足 $ab+bc+ca=n$。有的话给出构造，否则输出 $-1$ 。 ## solution 首先我们有打表 ```cpp namespace DB { const ......

**倍增** 点击查看代码 ``` //最大值不支持减法操作 //倍增代码，求区间的最大值 #include using namespace std; int n,a[1000000],f[100000][20];//f的j次方开到20就可以达到1000000 int x[100010];//x[i ......