当前位置：首页 > news >正文

2026/05/04 模拟赛总结

news 2026/5/4 17:12:35

NOIP模拟赛。排名：\(35+55+20+77=187\)，\(rk 1/7\)。

（为什么 T1 老是拿不到满分）

~~还有就是这个排名没有什么参考性，因为大佬都没来~~

T1

题目大意：

你有 \(n\) 张卡牌，每张卡牌每轮会对国王造成 \(att_i\) 点伤害，生命值为 \(hp_i\)，有一个国王，它有 \(m\) 个等级，第 \(i\) 等级的生命值为 \(Hp_i\)，每轮会对你的卡牌造成 \(Att_i\) 点伤害，保证 \(Hp\) 数组和 \(Att\) 数组单调不降。如果你必须顺序出牌，问第 \(i\) 等级你至少需要使用多少张卡牌。另外，除 \(Hp\) 数组外所有输入的值域均在 \((0,V]\) 之间。

\(n,m,V \le 3 \times 10^5,Hp_i \le 10^9\)

思路分析：

赛事想到了一个 \(\mathcal{O}(n \sqrt{n} \log n)\) 做法，然后这死评测机导致我 \(n = 10^5\) 都 T 飞从而得到 \(35\) 分的好成绩，比暴力分高了 \(5\) 分。

我的做法是：发现每张卡牌对国王的攻击次数只有 \(\mathcal{O}(\sqrt{V})\) 量级种可能（用整除分块可以证明），而且相同的攻击次数必定会形成一段连续的区间，所以直接用树状数组区间维护它造成的贡献就可以了。而且注意到答案也是单调不降的，所以双指针来维护第 \(i\) 等级在树状数组上是否超过它的 \(Hp\) 值，如果超过，那么它就被 out 了，把答案更新即可。

但是本题存在一个 \(\mathcal{O}(V \log^2 V)\) 的做法，时间复杂度的证明也是很巧妙。

我们换一个角度思考，枚举第 \(i\) 等级的国王，累加之前卡牌对国王造成的伤害，并双指针维护新加的卡牌对国王造成的伤害。我们分两种情况讨论。

第一种，第 \(i\) 等级的国王攻击力和第 \(i - 1\) 等级的国王攻击力相等。这个就可以搬原来的答案了，直接算新添加的卡牌对国王造成的伤害就行了。
第二种，第 \(i\) 等级的国王攻击力比第 \(i - 1\) 等级的国王攻击力强。这以前的答案偏差就比较大了，迫不得已我们只能放弃原来的答案。

那这样不就又 \(\mathcal{O}(n^2)\) 了吗？我们有一个很神奇的技巧。将之前的卡牌以 \(hp\) 值为下标存进树状数组，不难发现 \(query_{(a + 1)k} - query_{ak}\) 的所有贡献，都能恰好攻击国王 \(a + 1\) 次。所以我们直接依次查询所有结果累加起来，就有更新之后前面卡牌的贡献了。

那么这个复杂度怎么来的？注意到只有攻击力变了的情况下才会进行上述操作，那么跑满的情况下复杂度就是 \((\dfrac{V}{1} + \dfrac{V}{2} + \dfrac{V}{3} + ... + \dfrac{V}{V}) \times \log V\)（后面为树状数组查询复杂度）。

然后注意到 \((\dfrac{1}{1} + \dfrac{1}{2} + \dfrac{1}{3} + ... + \dfrac{1}{V}) > 15\) 最小的 \(V\) 已经是 \(1835421\) 了，差不多就是 \(e^{15}\)。所以它的复杂度近似于 \(\ln V\)，完全可过。~~不信邪的去 P1035 跑一遍程序吧~~

Code

#include <iostream>
#include <cmath>
#define int long long
#define lowbit(k) k&(-k)
using namespace std;
int n,m,v,zhi,ans,yatk[300005],yhp[300005],datk[300005],dhp[300005];
int tr[300005];
void add(int x,int k)
{while(x <= v)tr[x] += k,x += lowbit(x);
}
int query(int x)
{int su = 0;while(x)su += tr[x],x -= lowbit(x);return su;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);freopen("card.in","r",stdin);freopen("card.out","w",stdout);cin >> n >> m >> v;for(int i = 1;i <= n;i ++)cin >> yatk[i] >> yhp[i];//我方卡牌for(int i = 1;i <= m;i ++)cin >> datk[i] >> dhp[i];//国王等级for(int i = 1;i <= m;i ++){if(zhi > n){cout << "-1\n";continue ;}if(datk[i] != datk[i - 1]){int p = 1;ans = 0;while(p <= v)ans += (query(min(p + datk[i] - 1,v)) - query(p - 1)) * (p / datk[i] + 1),p += datk[i];}while(zhi <= n && ans < dhp[i]){zhi ++;if(zhi > n)break ;add(yhp[zhi],yatk[zhi]),ans += ceil(yhp[zhi] / (double)(datk[i])) * yatk[zhi];	}if(zhi > n){cout << "-1\n";continue ;}cout << zhi << '\n';}
}

T2

题目大意：

给定正整数 \(n,m\) 和 \(m\) 个要求和一个数列 \(a\)，第 \(i\) 个要求是 \(a_l,a_{l+1},...,a_r\) 的按位与（AND）必须等于 \(x\)。

现在你想知道对于每个要求 \(i\)，是否存在长度为 \(n\) 的序列 \(a\) 能满足除了该要求之外的所有要求（也就是其他要求必须满足，但要求 \(i\) 可以不满足）

\(n,m \le 10^6,x \le 10^{18}\)。

思路分析：

我的 \(55\) 分做法：\(\mathcal{O}(n^2 \log n)\)。

我们先枚举要求 \(i\)。

先让其他所有的要求全部满足，即将 \(a_{l_j},a_{l_{j + 1}},...,a_{r_j}\) 全部或（OR）上 \(x_j\)，\(i \neq j\)。

然后直接判断修改完后要求是否仍然被满足即可。

但注意到这是 \(\mathcal{O}(n^3)\) 的，所以我们可以使用线段树优化，线段树维护每个区间的与，那么就变成了区间按位或，区间查询按位与。显然这是容易做的，把区间按位或拆成子区间即可。

正解：

我们先考虑 \(x = 0/1\) 的情况。

这就相当于当 \(x=1\) 时做一遍区间覆盖（\(l \sim r\) 必须全部为 \(1\)），否则这个区间至少有一个为 \(0\)，我们不妨叫做区间询问。

首先看能不能删去区间询问。不难发现必须其他的区间询问都得满足至少一个为 \(0\)，否则删去这个仍然会有不合法的情况。否则就可以删去，那么删去这个区间就是合法的。这个很容易维护，先预处理不合法的区间询问就行了。

然后看能不能删去区间覆盖。我们发现，它能删去当且仅当删去了之后不合法的区间询问能变为合法。那么就说明，不合法的区间得存在一个位置，它只被区间覆盖覆盖到了一次。

因此我们对不合法的区间询问进行遍历，将预处理过的只被区间覆盖到了一次的位置全部算上贡献。最后将位置统计，如果统计到了全部的不合法的区间询问就说明删去该区间覆盖可行。

但是 \(x \le 10^{18}\)，我们直接拆成若干个进制位即可，最后的答案要进行按位与，表示所有进制位都得满足。

复杂度 \(\mathcal{O}(n \log 10^{18})\)。

T3

题目大意：

有一个 \(p\) 个结点的图，点从 \(0 \sim p - 1\) 标号，给定系数 \(k\)，对于 \(∀\,0 ⩽ x < p, 0 ⩽ i < k\)，存在一条 \(x\) 到 \((kx + i)\!\!\mod p\) 的边权为 i 的有向边。然后有 \(q\) 次询问求 \(u\) 到 \(v\) 的最短路。

\(p \le 10^6,k < p\)

思路分析：

只会 \(60\) 分的 \(\mathcal{O}(p^2 \log p)\) 做法，结果 \(\text{vector}\) 还未清空直接挂成 \(20\) 了。

显然直接跑全源最短路就行了。

但注意到边数很多，直接跑会是 \(\mathcal{O}(p^3 \log p)\)，但我们首先把边权为 \(0\) 的边连接的点权并起来，然后只连接边权位 \(1\) 的边在两个联通块之间就行了。边权为 \(2\) 的边都没必要，因为根据同余的性质可以拆成依次走两个边权为 \(1\) 的边。

所以边的数量降到了 \(p\) 条，直接跑最短路即可。