记录一下我出的几道题的题解。个人感觉E和J比较有意思。
C、Lecxcy与蚂蚁
容易发现这个过程是高度对称的,那么在任一时刻这$n$只蚂蚁都组成正$n$边形,因此每只蚂蚁的速度在向心方向上的速度都不变,为$v\sin\frac{\pi}{n}$。那么时间就是半径除速度,答案为$\frac{r}{v\sin\frac{\pi}{n}}$。
好像有同学反映卡精度?
#include <bits/stdc++.h>
typedef long long ll;
const double PI = std::acos(-1);
int main() {
int t; scanf("%d", &t);
while (t--) {
int n, r, v;
scanf("%d%d%d", &n, &r, &v);
printf("%.3lf\n", 1.0 * r / v / std::sin(PI / n));
}
return 0;
}
D、异或数对
验题的时候觉得这肯定是全场最简单的题,没想到最终通过率只有7.5%,不知道哪里出了问题。
需要知道性质$a\oplus b=0\Leftrightarrow a=b$,那么统计一下每个数的出现次数后组合数加起来即可。
#include <bits/stdc++.h>
typedef long long ll;
const int MAXN = 2e6 + 10;
int cnt[MAXN];
int main() {
int n, maxi = 0; scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int t; scanf("%d", &t);
cnt[t]++; maxi = std::max(maxi, t);
}
ll ans = 0;
for (int i = 0; i <= maxi; ++i)
ans += 1ll * cnt[i] * (cnt[i] - 1) >> 1;
printf("%lld\n", ans);
return 0;
}
E、模与和
首先要观察出性质$y\le x< 2y$。
若$x<y$,那么$x\bmod y=x=x\oplus y\Rightarrow y=0$,不可能,舍去;
而$0\le x\bmod y<y$,那么$x=y\oplus(x\bmod y)<2y$,因此$y\le x<2y$。
那么原题中式子就可以简化为$x-y=x\oplus y$。变为此式后考虑二进制表示中每一位上$x,y$可能的取值,容易发现此时不能出现某一位$x=0,y=1$,否则$x-y$需要借位,则不满足位运算独立性。
那么反过来考虑,当某一位上$y=1$时意味着这一位上$x$一定等于$1$,否则当$y=0$时$x$取$0,1$均可。那么不考虑$x$的取值范围的话由上述两条性质可以得出:对于任意的$y$,设其二进制表示中的$0$有$k$个,满足条件的$x$的个数就是$2^k$。
再进一步,我们观察到由于$y=0$的每一位$x$都对应只有$0,1$两种取值,那么我们把$y$中所有为$0$的位取出来,从高到低拼成一个新的二进制数$\text{cnt}$,此时$x$的个数应该和$\text{cnt}$密切相关。如果$\text{cnt}$最大只能取到$u$,那么具有上限$y|u$的$x$的个数应该为$u+1$。
所以我们把$x$的下限弄掉,对于特定的$y$,我们计算$0\sim r_x$中满足条件的个数$x_r$,再计算$0\sim l_x-1$中满足条件的个数$x_{l-1}$,那么在$l_x\sim r_x$中满足条件的个数即为$x_r-x_{l-1}$。设$x$的上界为$x_{upper}$,我们枚举$y$,接下来只需要考虑此时的$y$怎么取到最大的$\text{cnt}$。从高位往低位考虑,设此时枚举到$y$的第$i$位;若$y_i=1$则不考虑;若$y_i=0$,那么这一位一定在$\text{cnt}$中;如果$2^i\le x_{upper}$,那么根据贪心选择性质,这一位取$1$更优,$\text{cnt}$中对应位置$1$,$x_{upper}-=2^i$;否则置$0$。
#include <bits/stdc++.h>
typedef long long ll;
int query(int x, int rx) {
rx -= x;
if (rx < 0) return 0;
int r = 0;
for (int i = 22; ~i; --i)
if (!(x >> i & 1) && 1 << i < x)
if (rx >= 1 << i)
r = r << 1 | 1, rx -= 1 << i;
else r <<= 1;
return r + 1;
}
int main() {
int lx, rx, ly, ry; scanf("%d%d%d%d", &lx, &rx, &ly, &ry);
ll ans = 0;
for (int i = ly; i <= ry; ++i)
ans += query(i, rx) - query(i, lx - 1);
printf("%lld\n", ans);
return 0;
}
F、数对统计
发现直接计算并不好计算。那么设$X$为合法数对的个数,我们考虑计算$\mathcal{E}[X]$。
考虑任意三个数$a_i,a_j,a_k$对$\mathcal{E}[X]$的贡献。只有当$a_j$是最大数的情况下这对数才会对答案有贡献。我们只考虑$a_j>a_i$且$a_j>a_k$的情况。之后再分两种情况:若$a_i=a_k$,那么$a_j$有三种摆放位置:$(a_j,a_i,a_k),(a_i,a_j,a_k),(a_i,a_k,a_j)$,此时只有第二种对答案有贡献,而三种排列等概率出现,那么此时贡献为$\frac{1}{3}$;若$a_i\not=a_k$,那么$a_j$有六种摆放位置:$(a_j,a_i,a_k),(a_i,a_j,a_k),(a_i,a_k,a_j),(a_j,a_k,a_i),(a_k,a_j,a_i),(a_k,a_i,a_j)$,其中只有第二种和第五种对答案有贡献,而六种排列等概率出现,那么此时贡献同样为$\frac{2}{6}=\frac{1}{3}$。
所以对原数组排序,排序后枚举最大数$a_j$,双指针计算出此时$a_i,a_k$有多少种取法并全部求和,之后除三就是$\mathcal{E}[X]$的值。
之后原问题就转化为如何求出所有排列个数。若没有重复的数则为$n!$,如果$x$重复了$\text{cnt}$次那么就需要除$\text{cnt}!$。求出个数后两者相乘即可。
#include <bits/stdc++.h>
typedef long long ll;
const int MAXN = 2e5 + 10;
const int MOD = 998244353;
ll a[MAXN], fac[MAXN], inv[MAXN];
std::unordered_map < ll, int > mp;
ll qpow(ll a, ll b) {
ll res = 1; a %= MOD;
while (b)
{
if (b & 1) res = res * a % MOD;
a = a * a % MOD; b >>= 1;
}
return res;
}
int main() {
int n; scanf("%d", &n);
fac[0] = 1; inv[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = qpow(fac[i], MOD - 2);
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
++mp[a[i]];
}
std::sort(a + 1, a + 1 + n);
ll ans = 0;
for (int i = 3, j = 0; i <= n; ++i) {
while (a[j + 1] < a[i]) ++j;
ans = (ans + (1ll * j * (j - 1) / 2)) % MOD;
}
ans = ans * qpow(3, MOD - 2) % MOD * fac[n] % MOD;
for (auto &[u, v]: mp) ans = ans * inv[v] % MOD;
printf("%lld\n", ans);
return 0;
}
J、Stable Diffusion
首先我们把属性$q$全部取相反数,方便计算。
设物品$1$的两个属性为$p_1,q_1$,物品$2$的两个属性为$p_2,q_2$。考虑邻项交换,如果物品$1$放在正面栏里、物品$2$放在负面栏里比两者交换顺序更优,那么有$p_1+q_2>p_2+q_1$,得到$p_1-q_1>p_2-q_2$。所以对所有物品按$p-q$排序,枚举分界线$k$,那么在$k$之前的物品一定放在正面栏中更优。
于是问题转化为从前面$k$个物品中最多取$a$个数,从后面$n-k$个物品中最多取$b$个数,要求使得和最大。用三个multiset维护一下即可。
需要注意的是有可能出现贡献为负数的情况,要特殊处理成$0$。
#include <bits/stdc++.h>
typedef long long ll;
const int MAXN = 2e5 + 10;
struct node {
int p, q;
} arr[MAXN];
int main() {
int n, a, b; scanf("%d%d%d", &n, &a, &b);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &arr[i].p, &arr[i].q);
arr[i].p = std::max(arr[i].p, 0);
arr[i].q = std::max(-arr[i].q, 0);
}
std::sort(arr + 1, arr + 1 + n, [](node a, node b) {
return a.p - a.q > b.p - b.q;
});
std::multiset < int > l, r, tot;
ll ans = 0, lsum = 0, rsum = 0;
for (int i = 1; i <= n; ++i)
tot.insert(arr[i].q);
while (r.size() < b && !tot.empty()) {
auto it = tot.end(); --it;
r.insert(*it); rsum += *it;
tot.erase(it);
}
ans = std::max(ans, lsum + rsum);
for (int i = 1; i <= n; ++i) {
auto it = tot.find(arr[i].q);
if (it != tot.end()) tot.erase(it);
else {
rsum -= arr[i].q;
r.erase(r.find(arr[i].q));
if (!tot.empty()) {
auto it = tot.end(); --it;
r.insert(*it); rsum += *it;
tot.erase(it);
}
}
lsum += arr[i].p;
l.insert(arr[i].p);
while (l.size() > a) {
lsum -= *l.begin();
l.erase(l.begin());
}
ans = std::max(ans, lsum + rsum);
}
printf("%lld\n", ans);
return 0;
}
orz