比赛链接: https://acm.ayit.edu.cn/contest/5

A: 简单的签到题, 直接统计4种字符串的个数就行了

标算代码: https://acm.ayit.edu.cn/submission/516

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int n,A[4];
char s[9];

int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%s",s);
        if(s[0]=='N')++A[0];
        else if(s[0]=='R')++A[1];
        else if(s[1]=='R')++A[2];
        else ++A[3];
    }
    printf("N: %d\n",A[0]);
    printf("R: %d\n",A[1]);
    printf("SR: %d\n",A[2]);
    printf("SSR: %d\n",A[3]);
    return 0;
}

B: 很容易发现OFF的位置类似累加, 所以直接检查n是否能表示为$ \frac{x(x+1)}{2}-2 $就对了

做法可以二分或者sqrtl((long double)n).

标算代码: https://acm.ayit.edu.cn/submission/518

全贴太长就不一一贴出来了

C: 样例解释是个烟雾弹, 实际上正确的贪心策略是每次吃甜蜜度最高的桃子

因为所有桃子的甜蜜度每天总是都会-1, 所以先吃低的也不能避免其他桃子的损失

举例: 9 3 2 1: 先吃低的是1+1+1+6=9, 先吃高的是9+2=11

所以我们用一个堆维护每种甜蜜度的桃子的剩余数量即可

这里还有个小技巧, 入堆时加上入堆时间, 出堆时再减去出堆时间就能得到实际甜蜜度了

标算代码: https://acm.ayit.edu.cn/submission/520

D: 首先对所有线段按右端点排序

我们用 $F_i$ 表示仅用前 $i$ 个线段时能拼出的不相交的总长度

那么显然有 $F_i$ >= $F_{i-1}$ , 然后我们二分出与当前线段不相交的右端点最大的线段 $j$

那么显然 $ F_i = max( F_i , F_j + L_j ) $ { $L_i$ 为第i个线段的长度}

标算代码: https://acm.ayit.edu.cn/submission/522

E: 首先不难发现这个覆盖范围只和点与原点的距离有关

所以我们可以二分覆盖范围然后判定方案合不合法

然后不难发现可以设以某个点为扇形一边然后判有多少个点能被覆盖就好了

用一个队列来维护可以使判断的复杂度降到 $O(n)$

总体复杂度 $O(n \log{m})$ , 离散化一下距离可以降到 $O(n \log{n})$ (虽然也就是快了一倍2333)

PS: 这题是可以全整数运算的, 虽然开long double的话似乎精度也够用emmm

标算代码: https://acm.ayit.edu.cn/submission/525

F: 这题的本质就是求X的所有质因子个数, 设质因子i的个数为 $num_i$ , 则 $ans = \prod _{i是素数} \quad {num}_{i}+1$

直接miller_robin+pollard_rho是 $O(nx^{\frac{1}{4}}*log(x))$ ,在构造的 $X=P_1*P_2$ 的情况下会因为gcd的log超时

但实际上复杂度主要来自于 pollard_rho, 而且我们要求的是因子的个数而不是具体因子

考虑舍弃pollard_rho, 首先 $ x <= 10^{18}$ , 我们筛出 $10^6$ 以内的质数并且筛掉x的所有 $10^6$ 以内的质因子并计数, 复杂度 $O(n \frac{10^6}{\ln(10^6)})$

接下来剩余的 $X$ 只有三种情况: $X=1$, $X=P_1*P_2$(两个质数 $P_1,P_2$的乘积,$P_1,P_2>10^6$), X是质数

对于 $X=1$ 显然可以直接抛弃, 然后我们验证 $X$ 是否为质数, 如果 $X$ 是质数那么直接计数

对于剩下的 $X=P_1*P_2$ , 我们判断他们两两之间的gcd, 如果有公因子那么我们可以直接把这两个数拆分成4个素数并计数

然后我们找所有已经计数的素数并且判断剩下的没有gcd的 $X$ 是否有这些素数为因子, 是的话继续拆分

对于再剩下的 $X$ , 显然他们是由两个独占的素数 $P_1,P_2$ 组成的, 所以直接计成两个单独的素数对答案的贡献即可

最后还有一点要注意: 不要忘记特判 $X=P_1*P_1$ (平方数)的情况, 这时 $X$ 的贡献为两个相同的素数而不是2个不同素数

总体复杂度: $O(n \log(x)S + n^2 \log(x) + n \frac{(\sqrt[3]{x})}{\ln(\sqrt[3]{x})} )$ (S是miller_robin的验证次数)

标算代码: https://acm.ayit.edu.cn/submission/832