集训队 普罗2015

## Day1比赛 ### T1 #### [方差](https://noip.ac/rs/show_problem/4063 "方差") 求和可以用前缀和。 求平均值时，特判是否整除而输出结果。 求方差，我们直接用他给的公式以分数形式算出结果，维护两个分子和分母，通分相减后特判输出。 注意要输出最 ......

## 7.16 ### [USACO20DEC] Sleeping Cows P 确定dp顺序 ### P8863 「KDOI-03」构造数组 转化模型易于理解 ### CF1363F 转化概念 区间右移变为右端点左移，便于转移 ### CF1188C dp不一定要直接求出答案；使得答案为min(i ......

好像没做过 DAG 计数的题。 首先看到数据范围，考虑状压。 方便起见，记 $cnt_{S,T}=\sum\limits_{(u,v)\in E}[u\in S \and v \in T]$。 设 $f_S$ 表示 $S$ 为强连通分量的选边方案数，由于正面很难算。 考虑反面： $$ f_S=2^{ ......

咕咕咕了一天。集训的时候也没写。只把自己印象比较深的记下来罢。 ### 机房里的事情 1. 去之前知道自己的组别（普转提）里头有很多比自己年龄小的选手，成天调侃自己。去了之后发现有很多看着像高中生的。有点庆幸。结果后来才知道他们要么是初中生要么是新高一。（大悲）模拟赛被薄纱乐好几回。 2. 来这第5 ......

# P5933 [清华集训2012] 串珠子 题解 [Link](https://www.luogu.com.cn/problem/P5933) 非常好的一道状压题目（为啥自己总是想不到呢……）。 首先我们发现 $n$ 很小，于是考虑状压。我们一开始肯定会设 $dp_s$ 为集合 $s$ 内的点相互 ......

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

# T1 似乎想复杂了。搓了一个 $O(Q\sqrt{n\log n})$ 的做法，成功跳过正解。结果考后发现普通分块就可以 $O(Q\sqrt n)$。而且似乎还 WA 了一些点。 根据题意可以发现 $b_i$ 为 $1$ 当且仅当 $i$ 在二进制下有奇数个 $1$。这个可以用来快速求 $b_i ......

- 7.13 今天上午主要是把cdq和treap复习了一下，顺便写了两个博客来记录。 下午一直在学斜率优化，先是学了单调队列优化，写了 【P4954 [USACO09OPEN] Tower of Hay G】 【P2254 [NOI2005] 瑰丽华尔兹】 然后就开始学斜率优化，学完之后写了【P36 ......

刚从svn上chenk out 的项目，打开一直有个蓝色的锁，可以生成，可以运行，正常的页面修改了也有蓝色的锁，还是第一次遇到。 原因不清楚，后来通过单个项目重新拿文件就好了。整个文件夹checkout会出现这个问题。在此记录下。 ......

[UOJ 传送门](https://uoj.ac/problem/450 "UOJ 传送门") $d = 1$ 时答案显然为 $k^n$。 下面只讨论 $d = 3$ 的情况，$d = 2$ 类似。 设每个人的指数型生成函数（EGF）为 $G(x) = \sum\limits_{i = 0}^{+\ ......

Hint 是 $n$ 个 $[0,1]$ 之间均匀随机分布的数的第 $k$ 小值的期望为 $\frac{k}{n+1}$，证明可见[这篇博客](https://www.cnblogs.com/penth/p/9743303.html)。 考虑 Kruskal 求最小生成树的过程。从小到大加入每条边， ......

link：[[HEOI2015] 小 Z 的房间](https://www.luogu.com.cn/problem/P4111) ## 题意 你突然有了一个大房子，房子里面有一些房间。事实上，你的房子可以看做是一个包含 $n\times m$ 个格子的格状矩形，每个格子是一个房间或者是一个柱子。在 ......

# 七月份集训总结 ## 前言 今天被拉到办公室里头一个个总结了一下集训的收获和感想。emm，是该总结总结了。 ## 感想 自己马上就要从准高二成为真正的高二学生了，时间真的蛮快的。不知道去年的霜木看到今天的自己，还会不会选择竞赛呢？ ## 收获&不足 * 平衡树的一些应用 * KD-Tree (目 ......

本场比赛难度还可以，T1和T2还是比较可做。但是题目编排三道计数我真服了。 ## T3 [JOISC2018] 修行 ### 题目描述 求有多少个长度为 $n$ 的排列恰好有 $k$ 个位置满足 $a_{i}>a_{i+1}$ 。 对于 $49 \%$ 的数据， $n \leqslant 3\tim ......

## 搬题人：$\text{D}\color{red}\text{eaphetS}$ ### [#A. [NOI Online #1 提高组] 序列](https://oj.hailiangedu.com/d/hlxly2022/p/951?tid=64b8207e877c60817233a1d3) ......

# 2023 夏季集训 D1 贪心二分 ## 0x00 前言 24OI FXJ 大佬来给我们讲课 Orz Orz. 讲课好难 TAT. ## 0x10 贪心 ### 0x11 经典贪心 写了 [Best Cow Line G/S](https://www.luogu.com.cn/problem/P ......

#P4514 上帝造题的七分钟 ##题意 维护对二维平面上的矩形区域各元素进行加法以及对矩形区域求和 链接：https://www.luogu.com.cn/problem/P4514 ##思路 通过二维树状数组维护的二维前缀和利用差分实现矩形区域的区间加法与区间求和。 具体而言，二维的前缀和可以仿 ......

# T1 赛时打了一个 $O(n^3)$ $16pts$ 暴力和一个似乎可以过一个 $20pts$ 特殊性质但其余无正确性的贪心。结果出来发现特殊性质挂了一个点，另一个地方还莫名其妙对了。说明特殊性质挂掉了，如果运气不好可能就挂到 $16pts$ 了。考后看题解发现 $O(n^2)$ 其实也是不难想 ......

# 最小生成树 MST ### [P5994 [PA2014] Kuglarz](https://www.luogu.com.cn/problem/P5994) 考虑连边 $i,j$ 表示花费代价知道区间 $[i,j)$ 的奇偶性． 容易发现 $i,j$ 联通就可以发现表示出 $[i,j)$． 考虑 ......

## [目前进度——动态规划1：线性dp、背包问题，区间](https://ac.nowcoder.com/acm/contest/24213 "目前进度——动态规划1：线性dp、背包问题，区间") ## 好题 ### [1026 合并回文子串](https://ac.nowcoder.com/ac ......

# T1 做了 $3h$，时间复杂度不对，小样例都还有一个没过。 考虑容斥，不连通的情况枚举 $1$ 号点所在连通块。 设 $f_{S, i}$ 表示 $S$ 连通且选了 $i$ 条边的方案数。 设 $inb_s$ 表示 $S$ 内部的边数。 那么有转移： $$ f_{S,i}=\binom{inb ......

# [CTSC2015] 日程管理 ## 题意 幽香是幻想乡中一个非常有地位的人。她日理万机，事务繁多，反倒自己已经快管理不过来了。于是他决定开发一个日程管理软件来帮助自己管理任务。 对于每个任务$i$有一个对应的截止日期$t_i$以及收益$p_i$，表示若幽香能在不晚于第$t_i$天完成这个任务， ......

## 出/搬题人：$\text{D}\color{red}\text{eaphetS}$ ### [#A. [NOI Online #1 入门组] 跑步](https://oj.hailiangedu.com/d/hlxly2022/p/896?tid=64b56b26434bdea01161b69 ......

[P8026 ONTAK2015 Bajtocja](https://www.luogu.com.cn/problem/P8026) 题目只考察连通性，不考察图更具体的结构，所以可以用 $d$ 个并查集维护。然后就不会了。 ~~观察题解后不难想到，~~两个点 $u$ 和 $v$ 在图 $i$ 上连通 ......

[Problem Link](https://loj.ac/p/3629) 有一个长为 $n$ 的未知序列，给定 $m$ 个限制，每个限制形如给定 $i,j,k,x$，要求 $a_i,a_j,a_k$ 的中位数为 $x$。构造一个符合条件的序列或输出无解。 $n,m\le 10^5$。 首先这是一个 ......

[toc] ## Day0 2023.7.16 ## Day1 2023.7.17 讲了单调栈、单调队列和并查集。 模拟赛因``INF=0x3f3f3f3f`` 导致 $100->50$ ，警钟长鸣。以后写``INF=9223372036854775807``了。 ......

今天的模拟赛太逆天了。 $\text{NOIP}$ 模拟赛一紫三黑。 得分： $100+14+0+14=128$ ,被吊打。 ## T1 珠宝 ### 题目描述 有 $n$ 个物品，每一个物品有一个空间 $w_i$ 和一个价值 $v_i$ 。 你有一个空间为 $i$ 的背包，问最多可以装下多少价值的 ......

## [目前进度——动态规划1：线性dp、背包问题，区间](https://ac.nowcoder.com/acm/contest/24213 "动态规划1：线性dp、背包问题，区间") ## 好题 ### [1012 [NOIP1999]拦截导弹](https://ac.nowcoder.com/ ......

## Day5 ### T1 ### 简要题意 有两个正整数 $a 先给出 $O(n)$ 找的代码 ```cpp #include #define LL long long #define LD long double #define int LL #define fr(x) freopen(#x" ......

## [模拟赛 1 题解](https://ac.nowcoder.com/acm/contest/61579 "模拟赛 1 题解") ### [A 上班](https://ac.nowcoder.com/acm/contest/61579/A "A 上班") #### 代码 点击查看代码 ``` ......