[Codeforces] #420 (Div. 2)

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

#A
照著敘述做就好。

#include <iostream>
using namespace std;
int a[60][60];
int main(){
    int n;cin >> n;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0; j < n ; j++)
            cin >> a[i][j];
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            if(a[i][j] != 1){
                bool flag = 0;
                for(int s = 0 ; s < n ; s++)
                    for(int p = 0 ; p < n ; p++)
                        if(a[i][s] + a[p][j] == a[i][j])
                            flag = 1;
                if(!flag){
                    puts("No");
                    return 0;
                }
            }
        }
    }
    puts("Yes");
    return 0;
}

#B
枚舉所有Y點，然後O(1)判斷那個點可以拿幾根香蕉。

#include <iostream>
#include <cmath>
using namespace std;
long long m,b;
long long a(long long y){return (y-b)*-m;}
long long check(long long x,long long y){
    x = abs(x);
    y = abs(y);
    return y*(y+1)/2*(x+1) + x*(x+1)/2*(y+1);
}
int main(){
    cin >> m >> b;
    long long ans = 0;
    for(int i = 0 ; i <= b ; i++)
        ans = max(ans,check(a(i),i));
    cout << ans << endl;
    return 0;
} 

#C
保證結果是hao的的解法是一發現stack的top不是那個時候該丟掉的就把stack排序，但這樣顯然TLE。
可以發現reorder之後，那些reorder之前進來的箱子要丟掉並不會再造成stack的頂端不是應該丟出去的箱子，所以其實可以遇到要reorder的時候就直接把stack清空。

#include <iostream>
#include <string>
using namespace std;
int n,t = 1;
int ST[300005];
int main(){
    cin >> n;
    n *= 2;
    int top = -1,ans = 0;
    while(n--){
        string s;cin >> s;
        if(s[0] == 'a')cin >> ST[++top];
        else{
            if(ST[top] == t)top--;
            else if(ST[top] != t && top != -1)ans++,top = -1;
            t++; 
        }
    }
    cout << ans << endl;
    return 0;
}

#D
我一開始還把題意搞錯ＱＱ
如果目前在點亮的那一格上，那你可以走去x座標差及y座標差 <= 2一開始就被點亮或x座標差及y座標差 <= 1一開始未被點亮的位置。因此可以想成最短路徑問題，只要多特判一開始終點是不是被點亮的即可。

#include <iostream>
#include <queue>
#include <bitset>
#define INF 2147483647
#define N 10010
#define F first
#define S second
using namespace std;
typedef pair<int,int> pi;
bitset <N> in;
pi d[N];
int dis[N];
int n,m,k,t;
bool flag;
int main(){
    cin >> n >> m >> k;
    for(int i = 0 ; i < k ; i++){
        cin >> d[i].F >> d[i].S;
        if(d[i].F == n && d[i].S == m)flag = 1,t = i;
    }if(!flag)d[k].F = n,d[k].S = m,t = k,k++;
    priority_queue< pi,vector<pi>,greater<pi> > pq;
    fill(dis,dis+N,INF);
    dis[0] = 0;
    pq.push({0,0});
    while(!pq.empty()){
        int now = pq.top().S;pq.pop();
        if(in[now])continue;
        in[now] = 1;
        for(int i = 0 ; i < k ; i++){
            if(now == i)continue;
            int x = abs(d[i].F-d[now].F),y = abs(d[i].S-d[now].S);
            if(i == t && !flag && (x <= 1 || y <= 1) && dis[i] > dis[now]+1){
                dis[i] = dis[now]+1;
                pq.push({dis[i],i});
            }
            else if(x+y == 1 && dis[i] > dis[now]){
                if(i == t && !flag)continue;
                dis[i] = dis[now];
                pq.push({dis[i],i});
            }else if((x <= 2 || y <= 2) && dis[i] > dis[now]+1){
                if(i == t && !flag)continue;
                dis[i] = dis[now]+1;
                pq.push({dis[i],i});
            }
        }
    }
    if(dis[t] == INF)puts("-1");
    else cout << dis[t] << endl;
    return 0;
}

#E
如果k沒有那麼大的話，其實可以掃過去dp一下即可。
但如果k很大的話怎麼辦呢，那就用矩陣快速冪拉！
對於每一條橫線都構造出其矩陣，利用快速冪算min(k,b)-a次方然後乘上到a時的dp矩陣。
這邊要小心是當a == k時會造成min(k,b)-a = 0，因此要特判一下，還有記得開long long。

#include <iostream>
#define MOD 1000000007
using namespace std;
struct Matrix{
    int n,m;
    long long d[16][16];
    Matrix(int _n,int _m){
        fill(&d[0][0],&d[15][15]+1,0);  
        n = _n,m = _m;
    }
    void se(int x){
        fill(&d[0][0],&d[15][15]+1,0);
        n = m = x+1;
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                if(j == i-1 || j == i || j == i+1)d[i][j] = 1;
                else d[i][j] = 0;
            }
        }
    }
};
Matrix dp = Matrix(16,1);
Matrix mul(Matrix x,Matrix y){
    Matrix tmp = Matrix(x.n,y.m);
    for(int i = 0 ; i < x.n ; i++){
        for(int j = 0 ; j < y.m; j++){
            for(int k = 0 ; k < x.m; k++){
                tmp.d[i][j] += x.d[i][k]*y.d[k][j]; 
                tmp.d[i][j] %= MOD;
            }
        }
    }
    return tmp;
}
Matrix fast(Matrix x,long long y){
    if(y == 1)return x;
    if(y&1)return mul(fast(x,y-1),x);
    Matrix tmp = fast(x,y/2);
    return mul(tmp,tmp);
}
int main(){
    long long n,k;cin >> n >> k;
    dp.d[0][0] = 1;
    Matrix w = Matrix(16,16);
    while(n--){
        long long a,b,c;cin >> a >> b >> c;
        if(a == k)continue;
        w.se(c);
        w = fast(w,min(k,b)-a);
        dp.n = c+1;
        dp = mul(w,dp);
    }
    cout << dp.d[0][0]% MOD << endl;
    return 0;
}

不負責任小總結：
pC挺有趣的，pD題敘難懂，pE是個練習矩陣快速冪的好題目。