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;
}
