cf 422 div.2题解

A. I'm bored with life

水。给定两个整数A,B，保证其中较小的一个不超过12.求A!和B!的最大公约数。

AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
    int a, b, ans = 1;
    scanf("%d%d", &a, &b);
    if(b < a) swap(a, b);
    for(int i = 1; i <= a; i++) ans = ans *i;
    printf("%d\n", ans);
    return 0;
}

B. Crossword solving

水。给定两个字符串s和t，长度分别为n,m, 1<=n<=m<=1000，求至少把s中多少个字符替换成通配符，使得s成为t的子串。枚举即可，复杂度O(mn)

AC代码：

#include<cstdio>
#include<vector>
using namespace std;

int main() {
    int n, m;
    char s[1005], t[1005];
    vector<int> ans;
    scanf("%d%d%s%s", &n, &m, s, t);
    ans.resize(n + 1);
    for(int i = 0; i <= m - n; i++) {
        vector<int> tmp;
        for(int j = 0; j < n; j++) {
            if(s[j] != t[i + j]) tmp.push_back(j + 1);
        }
        if(tmp.size() < ans.size()) ans = tmp;
    }
    printf("%d\n", ans.size());
    for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
    return 0;
}

C. Hacker, pack your bags!

给定n个区间，每个区间有一个左端点l，右端点r，代价值c。区间长度定义为r-l+1，要求取两个不相交的区间（端点重合也算相交），使得两个区间的长度和为x，且代价之和最小。其中1<=n，l，r<=200000

直接枚举的话，O(n*n)肯定是过不了的，但是l,r的范围给我们提供了一些思路。一种可行的做法是先枚举一个区间，这个区间的长度为len，再找出长度为x-len的所有不相交区间中的最小代价。因此我们维护一个数组best，best[i]代表长度为x-len的所有与当前区间不相交的区间的最小代价。要保证不相交，只需要事先分别按照左端点和右段点对区间排序就可以了。时间复杂度O(nlogn)

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX = 2e5 + 10;
const int INF = 2e9 + 10;

int n, x;
int best[MAX];
int ans = INF;

struct Node {
    int l, r, len, cost;
}a[MAX], b[MAX];

struct cmp1 {
    bool operator () (const Node &n1, const Node &n2) const {
        return n1.l < n2.l;
    }
};

struct cmp2 {
    bool operator () (const Node &n1, const Node &n2) const {
        return n1.r < n2.r;
    }
};
int main() {
    scanf("%d%d", &n, &x);
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].cost);
        a[i].len = a[i].r - a[i].l + 1;
    }
    memcpy(b, a, sizeof(a));
    sort(a, a + n, cmp1());
    sort(b, b + n, cmp2());
    for(int i = 0; i < MAX; i++) best[i] = INF;
    int i, j = -1;
    for(int i = 0; i < n; i++) {
        while(b[++j].r < a[i].l) {
            best[b[j].len] = min(b[j].cost, best[b[j].len]);
        }
        j--;
        if(x - a[i].len <= 0) continue;
        if(best[x - a[i].len] == INF) continue;
        ans = min(ans, best[x - a[i].len] + a[i].cost);
    }
    if(ans != INF) printf("%d\n", ans); else printf("-1\n");
    return 0;
}

D. My pretty girl Noora

核心是要求解决下面一个问题：有n位选手参加一次比赛，比赛分多轮进行，每一轮会把当前所有选手分为几组，每组人数均为k，每个小组内要进行k(k-1)/2次比较并出现1位选手，这样算作一轮结束。出现的选手再进行下一轮，知道只剩一个选手。问整个比赛至少需要多少次比较。

设f(n)表示n位选手参加比赛的话需要的最少比较次数。如果n=ab，很显然有f(n)=b*f(a)+f(b)，关键是确定第i轮比赛中一个小组的人数d_i。可以证明d_i必须满足两个性质：(1)d_i是素数；（2）d_i < d_i+1

AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;

const int MAX = 5e6 + 10;
const int MOD = 1e9 + 7;

int t, l, r;
int min_prime[MAX];
long long ans, dp[MAX];

inline void init_prime_list() {
    for(int i = 2; i < MAX; i++)
        min_prime[i] = i;
    for(int i = 2; i * i < MAX; i++) {
        if(min_prime[i] != i) continue;
        for(long long j = i * i; j < MAX; j += i)
            min_prime[j] = min(i, min_prime[j]);
    }
}

int main() {
    scanf("%d%d%d", &t, &l, &r);
    init_prime_list();
    for(long long i = 2; i <= r; i++) {
        if(min_prime[i] == i)
            dp[i] = (i * (i - 1) / 2) % MOD;
        else {
            int groups = i / min_prime[i];
            dp[i] = (dp[min_prime[i]] * groups + dp[groups]) % MOD;
        }
    }
    long long t_pow = 1;
    for(int i = l; i <= r; i++) {
        ans += (t_pow * dp[i]) % MOD;
        ans = ans % MOD;
        t_pow = (t_pow * t) % MOD;
    }
    printf("%I64d\n", ans);
    return 0;
}