小白月赛 60

A

说妈妈的年龄是小竹的 $aa$ 倍还要多 $bb$ 岁！

那妈妈是 $xx$，小竹就是 $\frac{x-b}{a}\backslash frac\; \{x\; -\; b\}\; a$。

fin >> a >> b >> x;
cout << (x - b) / a << endl;

但是看错题 WA 了一发/ll/ll，我的 rank2 啊

B

也就是每次询问有个房间被 ban 掉，那每次的答案就是总和减去被 ban 的房间的和。

用 cnt 记录一下每个房间的边数。

fin >> n >> m >> q;
for (int i = 1; i <= n; i++) fin >> a[i], cnt[a[i]]++;
while (q--) {
  int x;
  fin >> x;
  printf ("%lld\n", n - cnt[x]);
}

C

很典的 dp，可以前缀优化到 $O(N)O(N)$，但是写的 $O(N^2)O(N^2)$。

设 $f_{i}f\_i$ 为取了前 $ii$ 个数其中 $ii$ 必选的方案数，那么有：

$f_i={}_{j=0}^{i-k-1}{f}_j+a_{i}f\_i\; =\; \backslash max\_\{j\; =\; 0\}^\{i\; -\; k\; -\; 1\}\; f\_j\; +\; a\_i$

答案是 $\max f\backslash max\; f$，优化用前缀和记录下 $s_i={}_{j=0}^i{f}_{j}s\_i\; =\; \backslash max\_\{j\; =\; 0\}^i\; f\_j$ 就行了。

fin >> n >> m;
for (int i = 1; i <= n; i++) fin >> a[i];
for (int i = 1; i <= n; i++) {
  f[i] = 0;
  for (int j = 0; j < i; j++)
    if (i - j > m) f[i] = max (f[i], f[j]);
  res = max (res, f[i] += a[i]);
}
cout << res << endl;

D

我写了个分层图最短路，但是不用这么麻烦，从起点终点分别来个 bfs，然后枚举每个刺激度大于 $xx$ 的点看下两个点到这个点的距离和就行，取最小值，代码放分层图的：

int dis[maxn][maxn][2];
struct WER {
    int x, y, p, dis;
    bool operator < (WER T) const {
        return dis > T.dis;
    }
} now;
priority_queue < WER > que;
 
void Dijkstra () {
    while (!que.empty ()) que.pop ();
    memset (dis, 127, sizeof dis);
    que.push ((WER) { sx, sy, 0, dis[sx][sy][0] = 0 });
    while (!que.empty ()) {
        now = que.top (); que.pop ();
        if (dis[now.x][now.y][now.p] != now.dis) continue ;
        for (int i = 0; i < 4; i++) {
            int nx = now.x + W[i][0], ny = now.y + W[i][1];
            if (nx < 1 || ny < 1 || nx > n || ny > m) continue ;
            if (a[nx][ny] == -1) continue ;
            if (!now.p) {
                if (dis[nx][ny][0] > now.dis + 1)
                    que.push ((WER) { nx, ny, 0, dis[nx][ny][0] = now.dis + 1 });
            }
            if (now.p || a[nx][ny] > x) {
                if (dis[nx][ny][1] > now.dis + 1)
                    que.push ((WER) { nx, ny, 1, dis[nx][ny][1] = now.dis + 1 });
            }
        }
    }
    return ;
}
 
wheneveright () {
    fin >> n >> m >> x;
    fin >> sx >> sy >> tx >> ty;
     
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) fin >> a[i][j];
     
    Dijkstra ();
     
    printf ("%lld\n", dis[tx][ty][1] < dis[0][0][0] ? dis[tx][ty][1] : -1);
    return 0;
}

E

加边！加边！加边！加边！加边！然后并查集查询！

对于每条边，其实只要考虑 $\gcd (a_x,a_y)\backslash gcd\; (a\_x,\; a\_y)$ 的质因数的个数就行了。

我们先把质数筛出来，然后用类似埃氏筛的方法判断值域内每个数的质因数个数，可以用线性筛，但是没必要。

int n, a[maxn], res;
int x, y, fat[maxn], siz[maxn];
int getfa (int id) { return id == fat[id] ? id : fat[id] = getfa (fat[id]); }
void merge (int x, int y) { fat[getfa (x)] = getfa (y); }
 
bool isp[maxm];
int pri[maxm], num[maxm], cnt;
void Prime (int n = 5000000) {
    for (int i = 2; i <= n; i++) {
        if (!isp[i]) pri[++cnt] = i;
        for (int j = 1; j <= cnt && i * pri[j] <= n; j++) {
            isp[i * pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
    for (int i = 1; i <= cnt; i++)
        for (int j = pri[i]; j <= n; j += pri[i])
            num[j]++;
    return ;
}
 
 
wheneveright () {
    fin >> n; Prime ();
    for (int i = 1; i <= n; i++) fin >> a[i], fat[i] = i;
     
    for (int i = 2; i <= n; i++) {
        fin >> x >> y;
        if (num[__gcd (a[x], a[y])] >= 2) merge (x, y);
    }
     
    for (int i = 1; i <= n; i++) res = max (res, ++siz[getfa (i)]);
     
    cout << res << endl;
    return 0;
}

F

先推下柿子

${\sum }_{x=1}^n{\sum }_{i=1}^x{\sum }_{j=x}^{n}F(p,i,j,x)\backslash sum\_\{x=1\}^n\backslash sum\_\{i=1\}^x\backslash sum\_\{j=x\}^n\; F(p,i,j,x)$

${\sum }_{x=1}^n{\sum }_{i=1}^x{\sum }_{j=x}^n{\sum }_{k=i}^j[p_x\le p_k]\backslash sum\_\{x=1\}^n\backslash sum\_\{i=1\}^x\backslash sum\_\{j=x\}^n\; \backslash sum\_\{k\; =\; i\}^j\; [p\_x\backslash le\; p\_k]$

考虑一个转换枚举方式，枚举两个数然后数贡献的区间个数，三项分别是 的情况，$kk$ 的含义见上试。

${\sum }_{i=1}^n{\sum }_{j=i+1}^n[p_i\le p_j]i(n-j+1)+{\sum }_{i=1}^n{\sum }_{j=i+1}^n[p_j\le p_i]i(n-j+1)+{\sum }_{i=1}^{n}i(n-i+1)\backslash sum\_\{i=1\}^n\backslash sum\_\{j=i+1\}^n[p\_i\; \backslash le\; p\_j]\; i\; (n\; -\; j\; +\; 1)\; +\; \backslash sum\_\{i=1\}^n\backslash sum\_\{j=i+1\}^n[p\_j\; \backslash le\; p\_i]\; i\; (n\; -\; j\; +\; 1)\; +\; \backslash sum\_\{i\; =\; 1\}^n\; i(n-i+1)$

发现前两项可以合并（互斥事件），然后就是：

${\sum }_{i=1}^n{\sum }_{j=i+1}^{n}i(n-j+1)+{\sum }_{i=1}^{n}i(n-i+1)\backslash sum\_\{i\; =\; 1\}^n\; \backslash sum\_\{j\; =\; i\; +\; 1\}^n\; i\; (n\; -\; j\; +\; 1)\; +\; \backslash sum\_\{i\; =\; 1\}\; ^\; n\; i\; (n\; -\; i\; +\; 1)$

合并进去。

${\sum }_{i=1}^n{\sum }_{j=i}^{n}i(n-j+1)\backslash sum\_\{i\; =\; 1\}^n\; \backslash sum\_\{j\; =\; i\}^n\; i\; (n\; -\; j\; +\; 1)$

发现题目要求 $O(N)O(N)$ 就行，那么枚举 $ii$，有等差数列求和公式：

${\sum }_{i=1}^n\frac{i(n-i+1)(n-i+2)}{2}\backslash sum\_\{i=1\}^n\; \backslash frac\{i(n-i+1)(n-i+2)\}2$

其实拆开可以做到 $O(1)O(1)$。

这边算完了，考虑 $inv(p)inv(p)$，有一个经典的公式

$inv(p)=\frac{n!n(n-1)}{4}inv(p)\; =\; \backslash frac\{n!n(n-1)\}4$

也很好想，对于 $n!n!$ 个排列，对于每个 ，有一半的排列 $p_i>p_{j}p\_i>p\_j$。

所以就是 $\frac{n!}{2}\times \frac{n(n-1)}{2}\backslash frac\{n!\}2\; \backslash times\; \backslash frac\{n(n-1)\}2$，后面的是有序对 $(i,j)(i,j)$ 的个数。

然后就做完了。代码：

fac[0] = 1;
for (int i = 1; i <= 100000; i++)
  fac[i] = fac[i - 1] * i % mod;
for (int i = 1; i <= 100000; i++)
  fac[i] = fac[i] * i % mod * (i - 1) % mod * inv4 % mod;
// inv4 = 250000002, 就是模 1000000007 下 1/4 的逆元
fin >> T;
while (T--) {
  fin >> n; res = 0;
  for (int i = 1; i <= n; i++)
    res = (res + i * (((n - i + 1) * (n - i + 2) / 2) % mod) % mod) % mod;
  res = (res % mod + mod) % mod;
  printf ("%lld\n", res * fac[n] % mod);
}

终于写完了。