模拟赛

- 赛时想了 1.5h 没想出来做法，然后写了个随机化乱搞过了，有点侥幸。 ### 思路 赛时想到： - 答案上界为 $n$。 需要进阶： - 变化超过 $1$ 的数的个数 $\le \lfloor\frac{n}{2}\rfloor$。 - 所以随机一个数，这个数变化不超过 $1$ 的概率 $\g ......

首先是~~伟大的~~题面  然后是数据范围 ![image](https://img2023.cnblo ......

赛时想写 60pts，结果 cxr 似乎少算了一点空间，导致我一直没把空间卡过去QWQ。 当时不会 dfs 求拓扑序，这里讲一下。 枚举所有非访问过的点依次 dfs，每次进行下列操作： - 找出 $v$ 的一个未访问过的入点 $u$，调用 `dfs(u)`； - 找不到 $u$ 的时候，把 $v$ ......

# 07.06&07.11模拟赛总结 > 前言：\ > 之前学了些新东西，所以只比了两场模拟赛，一场`Atcoder`，一场`USACO`。\ > 改完题了，趁有空总结一下。 # 07.06——Day 1 ## T1 [[ABC218D] Rectangles ](https://www.luogu ......

# summarization 给定一个 $n$ 个节点的树，定义 $x_1,x_2,\cdots,x_k$ 生成的子树为树中*边数最少*的包含 $x_1,x_2,\cdots,x_k$ 的连通块。 对所有可能的 $x_1,x_2,\cdots,x_k\quad(1\le x_1>= 1, x = ......

## 2023.7.10 ### T1 题面 在一个迷宫中有一个蛋糕。作为一个吃货，Luna 非常想吃到这块蛋糕。现在Luna 手里有这个迷宫的地图，该地图是一个r 行c 列的网格图，每个格子包含了下述4 种字符中的一种： “#”表示这里是墙砖，不能通过； “.”表示这里是空地，可以通过； “S”表 ......

# 7.10 冲刺国赛模拟 33 ## T1 染色 点分树模板。 另一做法是考虑差分，关键是求 $\mathrm{LCA}$ 到跟距离的和，可以每次染色后使得到根的路径上 $+1$，这样查询时也查询到根的路径上权值和。 点击查看代码 ```cpp int n,m; struct edge{ int ......

20230707 ## T1.信号传输（signal） #### 考场思路 先把这$n+k+1$个点都转化到平面直角坐标系上面 又是没有想清楚就开始打代码（但至少比昨天好，懂得放弃） 本来想的是按照x轴从左到右扫一遍 每一次处理这一列上的每个点 复杂度是$O(n)$ 但是后面想到有可能信号是从后面的 ......

## 题目大意 [原题](http://211.140.156.254:2333/problem/1216) 有一个 $n+1\times m+1$ 的网格。对于每一行 $i$，都要将左侧的一些格子 $(i,1),(i,2),\ldots,(i,x)$ 涂黑，其中 $x = k$ 的概率为 $a_{ ......

20230706 ## T1.骰子游戏（dice） #### 题目大意 给你两个正整数 $n$ 和 $d$，你需要构造 $n$ 组数据，每组6个整数 满足整数都在 $[0, 10^6]$ 范围内，每组数据中两两不同， 在每组数据中分别随机选一个数所得到的异或和为$d$的倍数 如果能构造出这样的 $n ......

# 2023.7月初模拟赛总结 > 前言：\ > 近期（约）3天比了3场模拟赛，都源于USACO。但是这3场我的成绩都很低，赛后一看题解被自己的智商哭死，实在看不下去了，决定要写一篇总结 # Day 1 ## T1 [P3132 [USACO16JAN] Angry Cows G ](https:/ ......

> 本题转化为梯形面积就已经不是很好想了（赛时切掉，开心！） 进阶为静态区间查询。 使用不删除莫队+凸包合并 - 凸包合并就是把散块和整块的凸包合并 - 注意这里两个凸包的横坐标值域是无交的 - 于是可以使用二分套二分解决此问题 > 代码咕着，感觉非常难写 ......

> 引用：这是一道非常棒的思维题，可以说没有用到任何高深的知识点，却极大地考验了做题人的思维能力和创造性。 本题分为两步。 - 根据线性规划对偶或贪心，转化题意。 - 对 $m$ 根号分治，然后分别进行分治。 > $m\le \sqrt{n}$分治比较好想，$m>\sqrt{n}$ 的根号分治比较难 ......

未完待续 A.方格填数 2 这里提供一种可以用来蒙结论的方法：以大见小，由浅入深的暴力找规律。 之前模拟赛里出过本题的简易版，其中 m 固定为 3。那个题根据爆搜可以得到：当 n 为奇数时答案是 2 ^ n - 2，当 n 为偶数时答案是 2 ^ n + 2，特判 1。然后发现今天这个题和那天的挺像 ......

# [总结]2023-7-6A组模拟赛 ## P1 心路历程 看完题之后发现：**唉，好像简单了一点。** 然后就开始想T1。一开始以为是DP，发现不好转移。不知道为什么脑子里面一直在想二维偏序，之后就往数据结构方面想。 我发现：一个点，绝对不可能从后面走回来。类似于这样： ![image](htt ......

# summarization  # solution 考虑倒着走，那么从 $u$ 走到 $v$ 条件就变为 $r ......

# summarization  # solution 首先发现，范围小的工具在删除某一数字时将更大数字包括进来的可 ......

# summarization 有一个长度为 $n$ 的序列 $p$，将其中若干个数标记。对于序列中的每一个位置 $i$，其贡献为其左边与右边离它最近的被标记的数的数值的和。求出最大的贡献总和。（$1\le n\le2\times10^6$） # solution 首先显然，$p_1, p_n$ 一 ......

## 题目大意 [原题](http://211.140.156.254:2333/problem/1212) 给定长为 $n$ 的序列 $a$，现在要标记其中的若干个数，记每个数左右两边（不包括本身）第一个被标记的数之和为这个数的满意度，求所有数满意度之和的最大值。$n\le 2\times 10^ ......

爆零模拟赛。  ## T1 [Gym 101078](https://codeforce ......

A.方格填数 4 - 填错了 n 个格子，一排，能填 1 ~ m，求填数时左右相邻的格子出现相同数的方案数。 正难则反，补集转换。容易想到所有方案数减去相邻格子没有出现相同数的方案数。 那么没填错的方案数：$m \times (n - 1) ^ {m - 1}$。即第一个格子有 m 种选法，后 n ......

[**原题链接**](https://local.cwoi.com.cn:8443/contest/C0281) ## 前言 挂分最多的一场。 考虑到之前都无分可挂，这场算是最近很简单的了。 > T1 不排序（按理说我的做法不需要排，但挂了），100->40。 > > T2 二分某个边界时单调性判错 ......

# [总结]2023-7-4A组模拟赛 ## P1 心路历程 开题看到T1大概是个结论、T2似乎是倒序而且暴力可以拿很多分、T3不会、T4没想法。 先想T1，以为是一个结论题。想了很久，没有结果，然后就在怀疑自己是否能做出来这种结论题。之后就弃疗了。 看到T2，40%的很好拿，50%不妨考虑离线之后 ......

[link](http://211.140.156.254:2333/contest/387) ### T1 转化为 $(b_i,a_i)$ 与 $(b_j,a_j)$ 之间的斜率。 发现性质（省略），只需要计算相邻两个点之间的答案即可，用 set 就行了。 ### T2 先找性质，发现即为 $a, ......

# [Contest2043 - NOIP2023模拟测试赛（三）](http://xsy.gdgzez.com.cn/JudgeOnline/contest.php?cid=2043) ## [Problem B: 上升子序列（sequence）](https://codeforc.es/cont ......

##前言 时间分配和做题顺序只是大致，因为时间原因记得不太清晰了。 关于失误的定义：能拿但没拿到的分。 题解均待续。 ##0626 ###复盘 0+0+10+26 ####时间分配&做题顺序： 先把所有题通看了一遍，没有特别明显的简单题，就从前往后做。T1、T2都没打暴力（所以寄得很惨），过了样例之 ......

# 7.2 冲刺国赛自测 9 ## T1 字符串 一个合法位置 $[l,r]$ 代表 $[1,x]$ 与 $[l,l+x-1]$ 相同，$[y,n]$ 与 $[r-y+1,r]$ 相同，类似 $x\in \mathrm{Border}(l+x-1)$。 对正反串做 KMP，建失配树，类似要求 $x$ ......

大脑宕机了！错误已更正，感谢提醒！ [更好的阅读体验？]() A.木棍切割 1 我现在很难解释我的做法，只能说 n^3 大标之后就很容易推出柿子了。现在还不知道怎么证明正确性qwq 以及如果模拟赛你去洛谷找原，找到的不是这个，是木棍切割 2，如果看看题面的话就不会掉进坑里。 ```cpp#inclu ......

[**原题链接**](https://local.cwoi.com.cn:8443/contest/C0276) ## 前言 隔天考试食不食油饼。 感受： > 难度还是佛如 C 组。 > > T1 用 1.5 h 想出正解，是道比较好想的博弈论。 > > T2 一开始居然想的树剖（脑子抽了），实际可 ......

A.生成字符串 (syoj.1761) 洛谷 P6191 [USACO09FEB] Bulls And Cows S 首先单独统计只有 0 - 1 个 1 的答案； 另所求序列由 "1000" 这样的形式再加一个 1 构成，设当前统计的有 i 个 1，此时序列长度 j 为 (k + 1) * (i ......