【杭电多校比赛记录】2025“钉耙编程”中国大学生算法设计春季联赛（1）

比赛链接
博客园原文链接（防盗）
开题 + 补题情况

还是很吃教训的一场比赛，被博弈论硬控两小时（很好的一个博弈论题），dijkstra被卡map，最终三题。

总结

上百通过的题已补完，还是学到了很多东西，其实这些题目也不是自己不会，往往是题目信息转化的能力不足（1002 和 1004），或是赛时被卡题没有及时换题导致会的题没有开出（1009），又或是复杂度分析能力不足（1004被卡常），补完题还是学到了很多东西，有很多之前自己没有注意过的地方吃了教训。
自己不会的东西还是太多了，还得多多练习多多长见识，革命尚未结束，加油！
1001 - 签到

题如其名，签到题，问给出的字符串第一次出现的位置。
点击查看代码

1. #define int long long
3. void solve()
4. {
5.     int n;cin >> n;
6.     string s;cin >> s;
8.     bool ck = false;
9.     for(int i = 1;i <= n;i ++) {
10.         string t;cin >> t;
11.         if(s == t) {
12.             cout << i << '\n';
13.             ck = true;
14.         }
15.     }
17.     if(!ck)cout << -1 << '\n';
18. }

复制代码

1004 - 海浪（补题）

题目对于海浪的定义是，在一个区间内，存在一个海面实数高度，使得区间内任何两个相邻海面，一个高于该高度，一个低于该高度。
比如，\(1,2,1\) 是符合题目要求的海浪，而 \(1,2,3\) 就不是题目要求的海浪。
可以看出相邻两个海面的下标，一个是奇数，一个是偶数，并且一定是奇偶相间的，除了边界外，一个奇数会匹配两个偶数，一个偶数会匹配两个奇数。
要让一个区间是海浪，若 \(a_i < a_{i + 1}\)，则 \(a_{i + 2} < a_{i + 1}\)，则 \(a_{i + 3} > a_{i + 2}\)，并且 \(a_{i + 3} > a_{i}\)，由此推下去可以发现，从这个起始条件出发，可以得出结论，要让一个区间是海浪，则这个区间偶数位置的最小值，要大于这个区间奇数位置的最大值。
若起始条件相反，\(a_i > a_{i + 1}\)，也可以得出相应的结论，要让一个区间是海浪，则这个区间偶数位置的最大值，要小于这个区间奇数位置的最小值。
我们对第一种情况进行考虑，对于第二种情况，我们只需要把所有海面高度取反，就转化为了第一种情况。
由于一个海浪区间是连续的，因此我们可以使用双指针算法来寻找每一个左端点对应的海浪最远右端点，用两个优先队列，一个大根堆存储奇数下标，一个小根堆存储偶数下标，在添加的过程中，只需要根据新加进来的位置是奇数还是偶数从而和偶数最小值还是奇数最大值进行比较看能不能加进来即可，并用滑动窗口的手法移除掉不合法的堆顶元素。
处理好了每一个下标对应的海浪最远右端点后，我们再用一个 ST 表来存储区间内的左端点的最大海浪宽度。
然后就可以处理查询了，对于每一个查询 \([x, y]\)，由于我们存储的所有信息都是对于左端点来记录的，所以我们对右端点进行分类讨论：

• 当右端点 \(> y\)，这种情况对应的左端点一定是有单调性的，因为海浪是连续的，一旦有一个左端点不满足对应的右端点 \(> y\)，那么它左边的其他点也都不满足。
  
• 当 \(x \leq\) 右端点 \(\leq y\)，此时我们已经把上述 \(> y\) 的情况剖除掉了，假设上面的情况最左端点为 \(e\)，则对于 \([x, e - 1]\)，他们的海浪区间一定都在 \([x, y]\) 内，此时只需要在 \([x, e - 1]\) 中查询 ST 表的最大值即可。
  

对这两种情况找到的最大值再取一个最大值，就是这个查询区间的最大值了。
时间复杂度：\(O((n + q) \log n)\)
点击查看代码[code]#define int long longconst int N = 1e5 + 9, M = 1e9 + 7;int a[N];int r[N];int st[N][20];int ans[N];int log_2[N];int n, q;struct myoddpq {    bool operator () (const int &u, const int &v) const {        return a < a[v];    }};struct myevenpq {    bool operator () (const int &u, const int &v) const {        return a > a[v];    }};void getr() {    std::priority_queue odd;    std::priority_queue eve;    for(int i = 1, j = 0;i  1;            if(r[mid] > y)e = mid;            else s = mid;        }        ans = std::max(ans, y - e + 1);        ans = std::max(ans, query(x, e - 1));    }    int res = 0;    for(int i = 1;i  k) & 1);                if(l[now ^ 1][k] > s && l[now ^ 1][k] > k) & 1);                if(l[now ^ 1][k] == s) {                    tmp |= (1 > j) & 1][j] = i;        }    }    std::cout