[Codeforces] #422 (Div. 2)

題目連結：http://codeforces.com/contest/822

#A
啦啦啦

#include <iostream>
using namespace std;
int f(int a){return a == 1 ? 1 : a*f(a-1);}
int main(){
    int a,b;cin >> a >> b;
    cout << f(min(a,b)) << endl;
}

#B
窮舉 t 的子字串然後比較看哪一段的差異最小，並記錄是哪一段，最後再重新跑一次那一段，並輸出不一樣的位置。

#include <iostream>
#include <string>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    string s1,s2;
    cin >> s1 >> s2;
    int ans = 21474836,ans2;
    for(int i = 0 ; i < (m-n+1) ; i++){
        int tmp = 0;
        for(int j = 0 ; j < n ; j++){
            if(s1[j] != s2[j+i])tmp++;
        }
        if(ans > tmp)ans = tmp,ans2 = i;
    }
    cout << ans << endl;
    for(int j = 0 ; j < n ; j++){
        if(s1[j] != s2[j+ans2]){
            cout << j+1 << ' ';;
        }
    }
    return 0;
}

#C
可以按照 r-l+1 的數值分組。
窮舉所有旅途，要找x-(r-l)+1那組中不重複的區間的花費的最小，但因為你會窮舉所有旅途，所以其實只要找在此區間的右邊或左邊即可。
排序一下每個組，二分搜找到第一個的左界大於該區間的右界，記錄個後輟最大值即可。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
//#define ll long long
#define PB push_back
#define F first
#define S second
#define INF 2147483647
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
using namespace std;
typedef pair<int,int> Pair;
struct Ken{
    int r,c,h;
} E[200005];
vector<Pair> v[200005];
int main(){jizz
    int n,x;cin >> n >> x;
    for(int i = 0 ; i < n ; i++){
        int ll,rr,cc;cin >> ll >> rr >> cc;
        v[rr-ll+1].PB({ll,cc});
        E[i] = (Ken){rr,cc,x - rr+ll-1};
    }
    for(int i = 0 ; i < 200001 ; i++)sort(v[i].begin(),v[i].end(),[](Pair x,Pair y){
        return x.F == y.F ? x.S < y.S : x.F < y.F;
    });
    for(int i = 0 ; i < 200001 ; i++){
        for(int j = v[i].size()-2; j >= 0 ; j--){
            v[i][j].S = min(v[i][j].S,v[i][j+1].S);
        }
    }
    int ans = INF;
    for(int i = 0 ; i < n ; i++){
        if(E[i].h <= 0 || !v[E[i].h].size())continue;
        int L = -1,R = v[E[i].h].size()-1;
        while(R-L > 1){
            int M = (R+L)/2;
            if(v[E[i].h][M].F > E[i].r){
                R = M;
            }
            else L = M;
        }
        if(v[E[i].h][R].F > E[i].r)ans = min(ans,v[E[i].h][R].S+E[i].c);
    }
    ans == INF ? cout << "-1\n" : cout << ans << '\n';
    return 0;
}

#D
不難發現當如果是x是質數時，f(x)便是x*(x-1)/2，那若x不為質數時，便要找x的因數k的 min(x/k+f(k)+f(x/k))。 又能發現k越小f(x)會越小，因此只要找k的質因數中最小的那個即可。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
#define N 5000000
#define MOD 1000000007
using namespace std;
typedef pair<int,int> Pair;
bitset<N+5> ok;
lld f[N+5];
vector<int> v;
void init(){
    for(int i = 2; i <= N ; i++){
        if(!ok[i]){
            v.PB(i);
            for(lld j = 1LL*i*i; j <= N ; j += i)ok[j] = 1;
        }
    }
    for(int i = 2; i <= N ; i++){
        if(!ok[i])f[i] = (1LL*i*(i-1)/2)%MOD;
        else{
            for(int j : v)if(i % j == 0){
                f[i] = (i/j*f[j]+f[i/j])%MOD;
                break;
            }
        }
    }
}
int main(){jizz
    init();
    lld t,l,r;cin >> t >> l >>r;
    lld ans = 0;
    for(lld i = l ,k = 1; i <= r; i++,k *= t,k%= MOD)ans += (f[i]*k)%MOD,ans %= MOD;
    cout << ans << endl;
    return 0;
}

#E
#F