A. I'm bored with life
水。給定兩個(gè)整數(shù)A,B宾娜，保證其中較小的一個(gè)不超過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
水。給定兩個(gè)字符串s和t前塔，長度分別為n,m, 1<=n<=m<=1000，求至少把s中多少個(gè)字符替換成通配符食零，使得s成為t的子串顶燕。枚舉即可，復(fù)雜度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個(gè)區(qū)間恳谎，每個(gè)區(qū)間有一個(gè)左端點(diǎn)l岸更，右端點(diǎn)r谭企，代價(jià)值c。區(qū)間長度定義為r-l+1盹廷，要求取兩個(gè)不相交的區(qū)間（端點(diǎn)重合也算相交），使得兩個(gè)區(qū)間的長度和為x颠放，且代價(jià)之和最小。其中1<=n欲低，l，r<=200000
直接枚舉的話腊瑟，O(n*n)肯定是過不了的，但是l,r的范圍給我們提供了一些思路瘪贱。一種可行的做法是先枚舉一個(gè)區(qū)間，這個(gè)區(qū)間的長度為len球昨，再找出長度為x-len的所有不相交區(qū)間中的最小代價(jià)。因此我們維護(hù)一個(gè)數(shù)組best，best[i]代表長度為x-len的所有與當(dāng)前區(qū)間不相交的區(qū)間的最小代價(jià)。要保證不相交沙庐，只需要事先分別按照左端點(diǎn)和右段點(diǎn)對(duì)區(qū)間排序就可以了棉安。時(shí)間復(fù)雜度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
核心是要求解決下面一個(gè)問題：有n位選手參加一次比賽，比賽分多輪進(jìn)行，每一輪會(huì)把當(dāng)前所有選手分為幾組若皱，每組人數(shù)均為k晦譬，每個(gè)小組內(nèi)要進(jìn)行k(k-1)/2次比較并出現(xiàn)1位選手，這樣算作一輪結(jié)束迎瞧。出現(xiàn)的選手再進(jìn)行下一輪足绅，知道只剩一個(gè)選手。問整個(gè)比賽至少需要多少次比較首量。
設(shè)f(n)表示n位選手參加比賽的話需要的最少比較次數(shù)。如果n=ab拣宏，很顯然有f(n)=b*f(a)+f(b)，關(guān)鍵是確定第i輪比賽中一個(gè)小組的人數(shù)d_i。可以證明d_i必須滿足兩個(gè)性質(zhì)：(1)d_i是素?cá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;
}
