## 思路 备战 ICPC 武汉站，但是因为三个人有事无法 vp，因此今天单挑 2024 杭州站。这道题差不多是一道银牌题，快速切掉可以有银牌，因此设置为蓝题很合理。但是我在赛时没能写出这题，因为单调栈错了。又有一道铜牌构造 H 题不会，遗憾打铁。 **算法：倍增，差分，单调栈。** 有的大佬用了笛卡尔树，但是我不会这…

在文章《记录第一次ICPC网络预选赛》发表评论：

运气比较好，有上海站和武汉站可以打

## 思路 昨天写了一下，为了准备区域赛，其实整套题做的很烂，写一下题解复盘。 这道题其实就是基本的拓扑排序，不难发现一个点如果被几个数字先后染色，只要保证最后一个染色数字不变就行，因此就说明最后的这个数字是前面数字的上级。同理，这样对每个位置都找到一个这样的顺序，就可以构成一个类似食物链的结构，就是拓扑图。因此只要拓…

这是**河边喝水的三只猫**的第二场网络预选赛，本次赛事复旦大学命题，图论考了不少。一下午的奋战，$A$ 了 $3$ 题，中规中矩。 赛前做了前两年的 $CCPC$ 预选赛题目，难度合理但是颇感怪异，因此赛前略有紧张。但是在机房快乐的氛围下，调整心态顺利开始比赛。 由于最初是队长机看题，所以我们都在思考 $A$ 题，但…

## 回顾 进入大学一年，从程序设计基础课开始，一直在学习编程算法。怀着一些兴趣，在暑假我加入了 $ICPC$ 校队。经过一假期的训练，能力有着明显的提升。因此我主动联络了两位同学，准备参加 $ICPC$ 网络预选赛。根据三个人的微信头像，取名为**河边喝水的三只猫**。 两位队友都有着各自的特点，$zmx$ 同学非常…

## 基本思路 首先我们应该都做过一种类型题，给定一个一维数组，求一段区间内的最小值；**同理我们不难想到另一种题目，求一个二维数组的矩形区域内最小值，洛谷有但是我忘了是哪题**。 因此这道题我们可以想到，**一个矩形被破坏的时间仅取决于最先碎掉的单元格**，因此我们对于存在的所有矩形可以做一个统计，统计每个矩形内最先…

这道题优先队列和贪心的综合应用，我是先排序，然后降序分配每个选手的组别。 优先队列里面存 $pair $,第一个变量存队末最小值，第二个存长度，用小根堆存。 每个点加入之前要判断队首是不是比自己大 $1$，如果是就加入，不是就单独站队。 **不过有时候比如有好几个人能力值一样，就需要先把可能加进去的队列都弹出，比如队列…

```cpp #include #include using namespace std; const int N = 100005; struct node { int l, r, lmax, rmax, smax, sum, lazy, l0max, r0max, s0max; }tr[N > 1; build(l…

## 一开始这样写 ```cpp get_root(1, 0); solve(root); ``` 成功的超时，90pts。 ## 后来意识到编号从0起 ```cpp get_root(0, -1); solve(root); ``` AC。。。

在讨论《建议升蓝》回复：

应该不至于，毕竟维护最大值是很显然的，但是因为有负数，所以应该也比较容易在过程中考虑最小值

在讨论《建议降绿，因为剪枝只有两步》回复：

@[Van_Helsing](luogu://user/1485399) mol(搜索也可以，感觉用搜索并不算难

在讨论《？？？暴力也行吗？》回复：

确实。。我也很震惊

## 转化利用树状数组！！！ 由于是排队问题，所以后进入队列的人拥有站在哪里的决定权，因此我们倒序处理进入队列的人。 因此每个人进入队列的时候，如果他的理想位置是 $x$ 的话,他显然没有任意挑选位置的自主权，必须在剩下的位置里面挑选一个最满意的。 由此可知我们整道题所要做的就是维护一个数组，来存储第 $k$ 个点以前…

在讨论《样例不过+WA0分，玄关求条，码风良好》回复：

码风真的很好@[HP_Serenity](luogu://user/1033086)

# 思路 作为经典的并查集问题，按照剪刀石头布分为三类，但是本题关键并不在于每个人属于哪一类，而是在于两个人的关系。这个关系我们可以用边权来记，由于规则分为平局和非平局，所以边权很容易用 $0、1$ 来表示。因此读入数据的时候我们把输赢统一为一种情况，赢者在后 ```cpp for (int i = 1; i > pl…

## 本人的代码在6和9两个点出错，但是换了最后一步的统计答案方法就对了，不懂原方法错在哪里，以下是原始代码（80分） ```cpp #include #include #include using namespace std; const int N = 1000006; int v[N];//存储美丽值 long…

## 虽然是绿题，在洛谷上跑得很快，但是本人在awcing上提交会T，提供一组数据自测 **aaaaaaaa bbbbbbbb** **aa ba** **aaa bab** **ba aba** **abab bbab** **ab bab** **aa bbb**

在讨论《建议升绿》回复：

@[YBJ1006](luogu://user/1039172)同意

在讨论《建议降绿，因为剪枝只有两步》回复：

@[SuperAlex4](luogu://user/179187)谢谢

## 本人最开始一直超时，后来无意间发现启发函数写错，希望警示后人(大悲) ### 最初的错误版 ```cpp inline int f(string str) { int cnt = 0; for (int i = 0; i < str.length(); i++) { cnt += (str[i] - '1');…

# 本题确实有辱蓝题，应该降绿 仅需要三个剪枝就能把 O（26！）的复杂度过掉，确实令人惊讶,所以除非数据加强，不然应该降绿，并备注数据的强度，以免过度思考 ## 剪枝1 从算式的低位到高位计算，不是说这样多优越，是反向太容易较晚引发矛盾，从而产生不必要的搜索 ## 剪枝2 每次检查算式三个字符串都被赋值的位是不是成立…

在讨论《可以加强的数据》回复：

最后的数据比较强

# 探讨一下超时问题（注意并不是题解，因为在acwing不是满分，有一个测试点超时） ### 本人用的双向广度搜索，在洛谷AC，但是在acwing会超时（可能是acwing把他归在了IDA*，需要启发函数），希望大家讨论一下如何优化BFS，过不了的数据在下面大家可以自测。下面是我的双向广度搜索函数 ```cpp int…

在讨论《想问一下这题二分是否可做？》回复：

可做，但是答案显然更巧妙（本人也是二分答案）

在讨论《runtime error从何而来》回复：

@[Poole_tea](luogu://user/668379) 十分感谢

在讨论《runtime error从何而来》回复：

@[qiminghaonan](luogu://user/371143) 十分感谢

在讨论《runtime error从何而来》回复：

@[libu2333](luogu://user/1475943) 这个好像没太大问题，毕竟我另一个AC代码也这样写的，不过还是真心感谢您

码风一般，已经尽量写了注释，希望大家尽量帮我看一下 ```cpp #include #include #include using namespace std; stack enter;//入栈序列 queue left;//出栈序列 int main(void) { int n = 0; int a[100005]…

```cpp #include #include #include using namespace std; struct word { char s[500] = {}; int count[25] = {}; int okk = 0; };//储存每个接龙结果 word beg[25] = {}; queue Q;…