[Codeforces] #419 (Div. 2)

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

#A
就勇敢的給他暴力做下去～
'9' + 1 會變成 ':'。

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;cin >> s;
    int ans = 0;
    while(1){
        if(s[0] == s[4] && s[1] == s[3])break;
        s[4]++;
        if(s[4] == ':')s[4] = '0',s[3]++;
        if(s[3] == '6')s[3] = '0',s[1]++;
        if(s[1] == '4' && s[0] == '2')s[1] = s[0] = '0';
        if(s[1] == ':')s[1] = '0',s[0]++;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

#B
感覺就有很多人會寫線段樹區間加值ＸＤ
但只要記每個區間的左界、右界，然後掃過去每個點被覆蓋的次數就是在這之前出現的左界數 - 右界數。詢問就用前綴和即可。

#include <iostream>
#define N 200005
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
using namespace std;
int l[N],r[N],tmp,c[N],a,b;
int main(){jizz
    int n,k,q;cin >> n >> k >> q;
    for(int i = 0 ; i < n ; i++){
        cin >> a >> b;
        l[a]++,r[b+1]++;
    }for(int i = 1; i < N-4 ; i++){
        tmp = tmp+l[i]-r[i];
        if(tmp >= k)c[i] = 1;
        c[i] += c[i-1];
    }while(q--){
        cin >> a >> b;
        cout << c[b]-c[a-1] << endl;
    }
    return 0;
}

#C
對於隨便某一行一定可以至少做那一行的最小值次move，列也亦同。
所以可以先掃過所有列，讓每一列都先move那一列的最小值次，然後接著掃行，看每一行剩的數字是不是都一樣，有不一樣的就是不hao的，不然就move那一行的數值的次數。
但是因為他是要求移動次數的最小值，所以就做兩次，分別先做行或列，然後比大小。

#include <iostream>
#include <vector>
#include <string> 
#define endl '\n'
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair <string ,int> pi;
vector<pi> v;
vector<pi> q;
int a[105][105],b[105];
int main(){jizz
    int n,m;cin >> n >> m;
    for(int i = 1 ; i <= n ; i++){
        int mn = 7122;
        for(int j = 1 ; j <= m ; j++){
            cin >> a[i][j];
            mn = min(a[i][j],mn);
        }
        for(int k = 0 ; k < mn ; k++)v.pb(mp("row",i));
        b[i] = mn;
    }
    for(int i = 1; i <= m ; i++){
        int mn = 7122,mx = -1;
        for(int j = 1; j <= n ; j++){
            mn = min(a[j][i]-b[j],mn);
            mx = max(a[j][i]-b[j],mx);
        }
        if(mx != mn){
            cout << "-1" << endl;
            return 0;
        }
        for(int k = 0 ; k < mn ; k++)v.pb(mp("col",i));
    }
    fill(b,b+105,0);
    for(int i = 1 ; i <= m ; i++){
        int mn = 7122;
        for(int j = 1 ; j <= n ; j++)mn = min(a[j][i],mn);
        for(int k = 0 ; k < mn ; k++)q.pb(mp("col",i));
        b[i] = mn;
    }
    for(int i = 1; i <= n ; i++){
        int mn = 7122,mx = -1;
        for(int j = 1; j <= m ; j++){
            mn = min(a[i][j]-b[j],mn);
            mx = max(a[i][j]-b[j],mx);
        }
        if(mx != mn){
            cout << "-1" << endl;
            return 0;
        }
        for(int k = 0 ; k < mn ; k++)q.pb(mp("row",i));
    }
    if(v.size() < q.size()){
        cout << v.size() << endl;
        for(pi i : v)cout << i.first << ' ' << i.second << endl;
    }else{
        cout << q.size() << endl;
        for(pi i : q)cout << i.first << ' ' << i.second << endl;
    }
    return 0;
}

#D
觀察一下會發現n是偶數時有規律：
當n = 4時，第3層左邊那個數會等於a1+a3，右邊那個數會等於a2+a4，答案會等於a1-a2+a3-a4。
當n = 6時 第5層左邊那個數會等於a1+2a3+a5，右邊那個數會等於a2+2a4+a6，答案會等於a1+a2+2a3+2a4+a5+a6。
不難發現有點像巴斯卡三角形，只是一次跳兩層，以及n是4的倍數時倒數第二層的符號會是減。
執於如果n是奇數，那就做一遍讓他變偶數就好。
因此只要實作1!~n!的模逆元即可好好的求出C(a,b)%MOD。
根據費馬小定理，當MOD是質數時，則x的模逆元為x的p-2次方。
至於1!~n!的模逆元有個很簡單的遞迴關係：
inv[I] = inv[i+1]*i+1
可以自己推推看～

#include <iostream>
#define N 200005
#define ll long long
#define MOD 1000000007
using namespace std;
ll f[N],a[N],inv[N];
ll C(int x,int y){return f[x]*inv[x-y]%MOD*inv[y]%MOD;}
ll fast(int x,int y){
    if(y == 0)return 1;
    if(y & 1)return fast(x,y-1)*x%MOD;
    ll tmp = fast(x,y/2);
    return tmp*tmp%MOD;
}
int main(){
    f[1] = f[0] = 1;
    inv[0] = inv[1] = 1;
    for(int i = 2; i < N ; i++)f[i]=f[i-1]*i%MOD;
    inv[N-1] = fast(f[N-1],MOD-2);
    for(int i = N-2; i >= 2; i--)inv[i] = inv[i+1]*(i+1)%MOD;
    int n;cin >> n;
    for(int i = 1 ; i <= n ; i++)cin >> a[i];
    if(n == 1){cout << a[1] << endl;return 0;}
    if(n & 1 && --n)
        for(int i = 1,p = 1; i <= n; i++,p>0?p-=2:p+=2)
            a[i] = (a[i]+p*a[i+1]+MOD)%MOD;
    ll ans1 = 0,ans2 = 0;
    for(int i = 1; i <= n ; i += 2)
        ans1 =((ans1+C(n/2-1,i/2)*a[i]+MOD)%MOD),ans2 = ((ans2+C(n/2-1,i/2)*a[i+1]+MOD)%MOD);
    cout <<((n%4 ? ans1+ans2 : ans1-ans2)+MOD)%MOD << endl;
    return 0;
}

#E
待編輯