A. I'm bored with life

水。給定兩個整數(shù)A,B，保證其中較小的一個不超過12.求A!和B!的最大公約數(shù)。

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個區(qū)間，每個區(qū)間有一個左端點l，右端點r，代價值c。區(qū)間長度定義為r-l+1，要求取兩個不相交的區(qū)間（端點重合也算相交），使得兩個區(qū)間的長度和為x，且代價之和最小。其中1<=n，l，r<=200000

直接枚舉的話，O(n*n)肯定是過不了的，但是l,r的范圍給我們提供了一些思路。一種可行的做法是先枚舉一個區(qū)間，這個區(qū)間的長度為len，再找出長度為x-len的所有不相交區(qū)間中的最小代價。因此我們維護一個數(shù)組best，best[i]代表長度為x-len的所有與當前區(qū)間不相交的區(qū)間的最小代價。要保證不相交，只需要事先分別按照左端點和右段點對區(qū)間排序就可以了。時間復雜度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位選手參加一次比賽，比賽分多輪進行，每一輪會把當前所有選手分為幾組，每組人數(shù)均為k，每個小組內要進行k(k-1)/2次比較并出現(xiàn)1位選手，這樣算作一輪結束。出現(xiàn)的選手再進行下一輪，知道只剩一個選手。問整個比賽至少需要多少次比較。

設f(n)表示n位選手參加比賽的話需要的最少比較次數(shù)。如果n=ab，很顯然有f(n)=b*f(a)+f(b)，關鍵是確定第i輪比賽中一個小組的人數(shù)d_i。可以證明d_i必須滿足兩個性質：(1)d_i是素數(shù)；（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;
}