Codeforces Round #422 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #422 (Div. 2)
过题数：2
排名：1873/13732

A. I'm bored with life

题意

求 $\gcd(A!,B!)$，其中 $x!=\prod_{i=1}^xi$。

输入

输入包含两个整数 $A,B~(1\leq A,B\leq10^9,\min(A,B)\leq12)$。

输出

输出 $A!$ 和 $B!$ 的最大公约数。

样例

题解

$\gcd(A!,B!)=\min(A,B)!$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 13;
int A, B;
LL fac[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    fac[0] = 1;
    for(int i = 1; i < maxn; ++i) {
        fac[i] = fac[i - 1] * i;
    }
    while(scanf("%d%d", &A, &B) != EOF) {
        printf("%I64d\n", fac[min(A, B)]);
    }
    return 0;
}

B. Crossword solving

题意

给定两个字符串 $s$ 和 $t$，可以将字符串 $s$ 任意位置上的字符改为 '?'，使 $s$ 能够匹配 $t$ 的某个子串，在匹配过程中，$s$ 串中的 '?' 可以匹配任意字符，问最少需要修改多少个字符为 '?' 才能使得 $s$ 可以匹配 $t$ 的某个子串。

输入

第一行包含两个整数 $n,m~(1\leq n\leq m\leq1000)$，分别表示字符串 $s$ 和 $t$ 的长度，第二行为字符串 $s$，第三行为字符串 $t$，字符串只包含小写字母。

输出

第一行为一个整数 $k$，表示最少需要修改的字符数，第二行为 $k$ 个整数，每个整数表示需要修改的字符在 $s$ 中的位置。如果有多解输出任意一组。

样例

题解

$O(n^2)$ 对于 $t$ 的每个长度为 $n$ 的子串计算与 $s$ 串的不同字符数的最小值，并将不同字符的位置记录下来，就是答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
int n, m, ans;
char s[maxn], t[maxn];
bool vis[maxn], visans[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        ans = n;
        for(int i = 1; i <= n; ++i) {
            visans[i] = true;
        }
        scanf("%s%s", s + 1, t + 1);
        for(int i = 1; i <= m - n + 1; ++i) {
            int tmp = 0;
            memset(vis, 0, sizeof(vis));
            for(int j = 0; j < n; ++j) {
                if(s[j + 1] != t[i + j]) {
                    vis[j + 1] = true;
                    ++tmp;
                }
            }
            if(tmp < ans) {
                ans = tmp;
                memcpy(visans, vis, sizeof(vis));
            }
        }
        bool flag = false;
        printf("%d\n", ans);
        for(int i = 1; i <= n; ++i) {
            if(visans[i]) {
                if(flag) {
                    printf(" ");
                }
                printf("%d", i);
                flag = true;
            }
        }
        printf("\n");
    }
    return 0;
}

C. Hacker, pack your bags!

题意

$Leha$ 的老板给她放了 $x$ 天的假，她从旅行社那里拿到了所有的行程表以及花费 $l_i,r_i,cost_i$，分别表示第 $i$ 个行程从第 $l_i$ 天出发，第 $r_i$ 天回来，需要花费 $cost_i$ 元，期间经过 $r_i-l_i+1$ 天。$Leha$ 想要挑选两次不相交的行程，且这两次行程总的旅行天数和正好为 $x$ 天，两段行程不相交等价于 $r_i<l_j$ 或者 $r_j<l_i$，问在满足以上条件的情况下的最小花费。

输入

第一行包含两个整数 $n,x~(2\leq n,x\leq2\times10^5)$，接下去 $n$ 行每行三个整数 $l_i,r_i,cost_i~(1\leq l_i\leq r_i\leq2\times10^5,1\leq cost_i\leq10^9)$。

输出

如果无法找到两个不相交且天数和等于 $x$ 的行程，则输出 $-1$，否则输出最小花费。

样例

题解

先将所有行程按左端点排序，枚举每一个行程 $i$，将所有满足 $r_j<l_i$ 的行程记录下来，记录第 $j$ 个行程的天数所对应的最小花费，就可以 $O(1)$ 地查询出 $x-(r_i-l_i+1)$ 对应的天数的最小花费，对每一个行程取最小值就是答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
struct Node {
    int l, r;
    LL cost;
};
bool operator<(const Node &a, const Node &b) {
    return a.l < b.l;
}
bool cmp(const Node &a, const Node &b) {
    return a.r < b.r;
}
int n, x, day;
LL ans;
LL cost[maxn];
Node node[maxn], ntmp[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &x) != EOF) {
        ans = INT_MAX;
        memset(cost, 0x3f, sizeof(cost));
        for(int i = 0; i < n; ++i) {
            scanf("%d%d%I64d", &node[i].l, &node[i].r, &node[i].cost);
            ntmp[i] = node[i];
        }
        sort(node, node + n);
        sort(ntmp, ntmp + n, cmp);
        int Index = 0;
        for(int i = 0; i < n; ++i) {
            while(ntmp[Index].r < node[i].l) {
                day = ntmp[Index].r - ntmp[Index].l + 1;
                cost[day] = min(cost[day], ntmp[Index].cost);
                ++Index;
            }
            day = node[i].r - node[i].l + 1;
            if(day >= x) {
                continue;
            }
            ans = min(ans, node[i].cost + cost[x - day]);
        }
        if(ans == INT_MAX) {
            printf("-1\n");
        } else {
            printf("%I64d\n", ans);
        }
    }
    return 0;
}

D. My pretty girl Noora

题意

在一次选美大赛中，有 $n$ 个小姐姐参加比赛，比赛规则为：将 $n$ 个小姐姐分到各个组里，每组 $x$ 人，在每组之间先两两进行比较选出小组的优胜者，每组内的比较次数为 $\frac{x(x-1)}{2}$，其中的 $\frac{n}{x}$ 名优胜者继续分组比赛，直到产生最后的优胜者。
设 $f(n)$ 为当比赛人数为 $n$ 时最小的比较次数，要求计算 $t^0\times f(l)+t^1\times f(l+1)+\cdots+t^{r-l}\times f(r)$ 对 $10^9+7$ 取模的结果。

输入

输入包含三个整数 $t,l,r~(1\leq t\leq10^9+7,2\leq l\leq r\leq5\times10^6)$。

输出

输出答案。

样例

题解

由题可知，组内比较次数随着组内人数的增加平方级地增长，所以应该将每一轮的分组尽可能地多，每组人数尽可能少，才能使 $f(n)$ 最优，如果 $n$ 为质数，则 $f(n)=\frac{n\times(n-1)}{2}$，否则 $f(n)=f(p)\times\frac{n}{p}+f(\frac{n}{p})$，其中 $p$ 为 $n$ 的最小的质因数，公式的其他部分直接 $O(n)$ 求解即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 5000000 + 100;
const LL MOD = 1000000000 + 7;
int cnt;
LL t, l, r;
LL f[maxn], prime[maxn];
bool vis[maxn];
void Prime() {
    cnt = 0;
    for(LL i = 2; i < maxn; ++i) {
        if(!vis[i]) {
            prime[cnt++] = i;
        }
        for(LL j = 0; j < cnt && i * prime[j] < maxn; ++j) {
            LL k = i * prime[j];
            vis[k] = true;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}
LL get(LL x) {
    if(!vis[x]) {
        return x * (x - 1) / 2;
    }
    LL ret = 0;
    for(int i = 0; prime[i] * prime[i] <= x; ++i) {
        if(x % prime[i] == 0) {
            ret = f[prime[i]] * (x / prime[i]);
            x /= prime[i];
            break;
        }
    }
    ret %= MOD;
    ret += f[x];
    return ret;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    Prime();
    for(int i = 2; i < maxn; ++i) {
        f[i] = get(i) % MOD;
    }
    while(scanf("%I64d%I64d%I64d", &t, &l, &r) != EOF) {
        LL ans = 0;
        LL tt = 1;
        for(LL i = l; i <= r; ++i) {
            ans = (ans + (tt * f[i]) % MOD) % MOD;
            tt = (tt * t) % MOD;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}