题解

NOIP半年集训day4

A.和

数学题。
根据等差数列求和公式,有:
$$\sum_{i=l}^{r}i=\frac{(l+r) \times (r – l + 1)}{2}$$
则有
$$n = \frac{(l+r) \times (r – l + 1)}{2}$$
$$2n = (l+r) \times (r – l + 1)$$
设 $len = r – l + 1$
则有 $r = l + len – 1$
那么所有合法的 $len$ 一定是 $2n$ 的因子。
一个数的因子是很少的,那么我们枚举 $len$ ,就可以得出 $l,r$ 了,判断下是否合法就可以了。
$$l = {{{2n \over len} + 1 – len} \over 2}$$
时间复杂度:$O(\sqrt{n})$

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
typedef long long ll;
ll p[100000], tail;
int main(int argc, char *argv[]) {
    ll n;
    scanf("%lld", &n);
    for (ll i = 2; i <= sqrt(2 * n); i++) {
        ll j = 2 * n / i;
        if (i * j == 2 * n) {
            if (i <= n / 2) p[++tail] = i;
            if (i == j) continue;
            if (j <= n / 2) p[++tail] = j;
        }
    }
    for (int i = tail; i >= 1; i--) {
        ll len = p[i];
        ll l = (2 * n / len + 1 - len) / 2;
        ll r = l + len - 1;
        if (l >= 1 && l < r && (l + r) * (r - l + 1) / 2 == n) {
            printf("%lld %lld\n", l, r);
        }
    }
    return 0;
}

B.串串

统计下两个串里每个字母的个数,因为保证有解,那么就在保证字典序最小的前提下大力分类讨论就好。
扫一遍就过去了,时间复杂度 $O(n)$

代码

#include <cstdio>
#include <cstring>
#include <climits>
const int MAXN = 5000 + 7;
char s1[MAXN], s2[MAXN];
int c1[4], c2[4], n;
int main(int argc, char *argv[]) {
    scanf("%d %s %s", &n, s2 + 1, s1 + 1);
    for (int i = 1; i <= n; i++) {
        c1[s1[i] - 'a' + 1]++;
        c2[s2[i] - 'a' + 1]++;
    }
    for (int i = 1; i <= n; i++) {
        if (s1[i] == 'a') {
            c1[1]--;
            if (c2[2] && c2[2] - 1 + c2[1] >= c1[3]) {printf("b"); c2[2]--;}
            else {printf("c"); c2[3]--;}
        } else if (s1[i] == 'b') {
            c1[2]--;
            if (c2[1] && c2[1] - 1 + c2[2] >= c1[3]) {printf("a"); c2[1]--;}
            else {printf("c"); c2[3]--;}
        } else {
            c1[3]--;
            if (c2[1] && c2[1] - 1 + c2[3] >= c1[2]) {printf("a"); c2[1]--;}
            else {printf("b"); c2[2]--;}
        }
    }
    puts("");
    return 0;
}

C.简单函数

我的做法是欧拉筛。
设 $sum[i] = \sum_{d|n,d \neq n}d$,$fac[i]$ 表示该数的最小质因子的乘积。
对于一个质数 $p$,$sum[p]=1,fac[p]=p$
对于一个合数,$sum[i \times pri[j]]=sum[i]+i+fac[i*pri[j]] \times sum[\frac{i \times pri[j]}{fac[i \times pri[j]]}]$.
求 $fac$ 也是基本操作了,看代码吧。

代码

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
typedef long long ll;
#define int long long
const int MAXN = 1e7 + 7;
int l, r;
ll sum[MAXN], pri[MAXN], tail, min[MAXN], qwq[MAXN], fac[MAXN], f[MAXN];
ll pre[MAXN];
bool vis[MAXN];
void solve(int n) {
    vis[1] = true;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            pri[++tail] = i;
            sum[i] = 1;
            fac[i] = i;
        }
        for (int j = 1; j <= tail && pri[j] * i <= n; j++) {
            vis[i * pri[j]] = true;
            min[i * pri[j]] = pri[j];
            if (i % pri[j] == 0) {
                fac[i * pri[j]] = pri[j] * fac[i];
                sum[i * pri[j]] = sum[i] + i + fac[i * pri[j]] * sum[i * pri[j] / fac[i * pri[j]]];
                break;
            } else {
                fac[i * pri[j]] = pri[j];
                sum[i * pri[j]] = sum[i] + i + fac[i * pri[j]] * sum[i * pri[j] / fac[i * pri[j]]];
            }
        }
    }
}
signed main() {
    scanf("%lld %lld", &l, &r);
    for (int i = 1; i <= r; i++) fac[i] = 1;
    solve(r);
    for (int i = 1; i <= r; i++) {
        f[i] = std::abs(i - sum[i]);
        sum[i] = sum[i - 1] + f[i];
    }
    printf("%lld\n", sum[r] - sum[l - 1]);
    return 0;
}

D.简单MST

留坑待填


Update
首先最暴力的三十分,就是无脑最小生成树。
想一想这个算法的瓶颈在哪里?
边数对吧,要是把所有的边权都算出来,就已经T上天了。
那既然这个题能做,就说明有很多边可以删掉,是没有意义的。
最直观的,如果有若干点权值相同,那么根据边权的规则,他们可以无消耗地合在一起。
然而这是个小优化,还远远不够。
我们结合一下MST和同余的性质。
如果有三个点 $a,b,c$。
若 $(a,c)>(a,b)+(b,c)$ ,那么我们无论如何是没有理由把 $(a,c)$ 这条边加到最小生成树里面的。
那根据边权的定义,什么时候会发生这种情况呢?
我们考虑对于一个点 $x$ 的点,讨论两个点$a,b$,满足$p_a,p_b>p_x, p_a < p_b$,并且 $kp_x \leq p_b, p_b \leq k(p_x+1)$。
(自己画一条数轴会更直观一点。)
那么单纯对于点这个点,是绝对没有理由连边 $(x,b)$ 的,因为无论如何 $(x,a) + (a,b) <= (x,b)$
那么我们对于每个点枚举倍数就可以了。
因为点权最大值为 $10^7$,再每个点枚举倍数,那时间复杂度就是喜闻乐见的调和级数,数量级是 $n \log2(n)$ 的。
然后时限也很宽松,五秒,并查集再把按秩合并和路径压缩都弄上,实际上就跑得飞快了。
注意加边的时候别越界,写好特判,不然会RE

代码

#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
const int MAXN = 1e7 + 5;
int p[MAXN], f[MAXN], pos[MAXN];
int up[MAXN], h[MAXN];
int cnt[MAXN];
std::vector<std::pair<int,int> > v[MAXN];
int n;
inline int find(int x) {
    if (f[x] == -1) return x;
    return f[x] = find(f[x]);
}
void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    if (h[u] < h[v]) f[u] = v;
    else if (h[u] > h[v]) f[v] = u;
    else {
        f[u] = v;
        h[u]++;
    }
}
int main(int argc, char *argv[]) {
    scanf("%d", &n);
    memset(pos, -1, sizeof pos);
    for (int i = 1; i <= n; i++) {
        scanf("%d", p + i);
        up[p[i]] = p[i];
        if (pos[p[i]] == -1) pos[p[i]] = i;
    }
    for (int i = MAXN - 2; i >= 0; i--)
        if (!up[i]) up[i] = up[i + 1];
    for (int i = 1; i <= n; i++) {
        if (cnt[p[i]]++) continue;
        if (up[p[i] + 1]) {
            if (p[i] * 2 >= MAXN || up[p[i] + 1] != up[2 * p[i]]) {
                v[up[p[i] + 1] - up[p[i]]].push_back(std::make_pair(i, pos[up[p[i] + 1]]));
            }
        }
        for (int j = 2 * p[i]; j < MAXN && up[j]; j += p[i]) {
            if (j + p[i] >= MAXN || up[j + p[i]] != up[j]) {
                v[up[j] - j].push_back(std::make_pair(i, pos[up[j]]));
            }
        }
    }
    memset(f, -1, sizeof f);
    long long ans = 0;
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < (int)v[i].size(); j++) {
            if (find(v[i][j].first) != find(v[i][j].second)) {
                merge(v[i][j].first, v[i][j].second);
                ans += i;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注