20260910 每日 2.0 2.5 5.0
No.1623 三角形的制作 2.0$
https://yukicoder.me/problems/no/1623
Note
红色，绿色，蓝色棒子各 $N$ 根，第 $i$ 根长度为 $r_i, g_i, b_i$
求使用第 $i$ 个红棒，第 $j$ 个绿棒，第 $k$ 个蓝棒制作三角形且满足，$r_i=max(r_i, g_i, b_k)$ 的整数对数量
- $1 \le N \le 2 \times 10^5$ $1 \le r_i,g_i,b_i \le 3 \times 10^3$
显然枚举两组然后二分第三组是不能通过的，于是考虑值域
看到了值域可以满足平方复杂度，于是考虑枚举绿和蓝的数量，然后对红棒前缀和，直接相减后统计计数即可。
namespace XK {
const int MAXN = 3e3 + 1;
void solve() {
int N; in(N);
V<int> A(MAXN + 1), B(MAXN + 1), C(MAXN + 1);
rep(i, N) {int x; in(x); A[x] ++;}
rep(i, N) {int x; in(x); B[x] ++;}
rep(i, N) {int x; in(x); C[x] ++;}
V<int> pre(MAXN + 1);
rep(i, MAXN) pre[i + 1] = pre[i] + A[i];
ll ans = 0;
rep(i, MAXN + 1) rep(j, MAXN + 1) {
if(i == 0 && j == 0) continue;
int cnta = pre[min(i + j + 1, MAXN + 1) - 1] - pre[max(i, j)];
ans += cnta * B[i] * C[j];
}
out(ans);
}
};No.2462 七人卡农 2.5$
https://yukicoder.me/problems/no/2462
Note
一共有 $N$ 个演奏者，给出 $Q$ 个三元组 $(I_i,S_i,T_i)$ 表示第 $I_i$ 个演奏者在 $[S_i, T_i]$ 时间内演奏。
如果在第 $T$ 秒的时候有 $X$ 个人演奏，那么演奏中的每个人都会在这一秒获得 $\frac{1}{X}$ 的醒目度，求每个人的醒目度之和。
- 保证给出的三元组满足 $I_i = I_j$ 时，$[S_i,T_i]$ 区间与 $[S_j,T_j]$ 区间不交
- $1 \le I_i \le N, Q \le 10^5$
- $0 \le S_i \lt T_i \le 10^5$
可以尝试预处理出每一秒的时候，如果在演奏的话，贡献是多少，因为这个部分是不变量，如果可以预处理出每一秒的 $val_i$ 的话，那么每个人的贡献就可以写成：
$$
\sum_{t=0}^{10^5} val_i [vis_t = 1]
$$
而这一部分可以直接暴力，因为总区间数最大是 $10^5$ 的，可以前缀和搞定。
因为要做两次前缀和，注意下标即可，复杂度 $O(N + Q + \text{max}(T))$
namespace XK {
const int MAXT = 1e5;
void solve() {
int N, Q; in(N, Q);
V<double> val(MAXT + 1, 0);
V<V<pair<int, int>>> Seg(N);
rep(_, Q) {
int I, S, T; in(I, S, T); I --;
Seg[I].pb({S, T});
val[S] ++, val[T] --;
}
rep(i, MAXT) val[i + 1] += val[i];
rep(i, MAXT + 1) if(val[i]) val[i] = 1.0f / val[i];
rep(i, MAXT) val[i + 1] += val[i];
rep(i, N) {
double ans = 0.0f;
for(auto [x, y] : Seg[i]) {
ans += val[y - 1] - (x > 0 ? val[x - 1] : 0.0f);
}
out(ans);
}
}
};No.981 一般幂乘根 5.0$
https://yukicoder.me/problems/no/981
Note
设 $p$ 是质数，求 $x^k \equiv a \pmod p$ 的一个解，如果不存在，输出 $-1$
题解我真的看不懂，ごめなさい~