Codeforces Round #419 (Div. 2) 题解

题目链接：http://codeforces.com/contest/816/problem/A

A. Karen and Morning
题意：给了一个时间ab:cd的方式，问多少分钟后时间变成回文的。
解法：模拟。

#include <bits/stdc++.h>
using namespace std;
char s[5];
int main()
{
    int h, m, ans=0;
    scanf("%d:%d",&h,&m);
    while(1){
        sprintf(s,"%02d%02d",h,m);
        if(s[0]==s[3]&&s[1]==s[2]){
            printf("%d\n", ans);
            return 0;
        }
        ++ans;
        ++m;
        h+=m/60;
        m%=60;
        h%=24;
    }
}

B - Karen and Coffee
题意：有N个区间，Q个询问，每次输入一个区间。问在这个询问的区间中，有多少个整数在那N个区间中至少出现了K次。
解法：前缀和的经典运用。要想使某个区间同时加上一个数，不需要把每个都加，只需要像lazy tag一样在起点加上这个数，终点的下一个减去这个数。最后求一遍前缀和就一次性的把前面的全部区间都更新了。所以这题，先利用上面的方法得到每个点的出现次数，再用一个前缀和就可以O（1）的得到某一个区间满足条件的点的数目。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n, k, q, sum[maxn], ans[maxn];

int main()
{
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<=n; i++){
        int l, r;
        scanf("%d %d", &l,&r);
        sum[l]++;
        sum[r+1]--;
    }
    for(int i=1; i<=200000; i++) sum[i]+=sum[i-1];
    for(int i=1; i<=200000; i++){
        if(sum[i]>=k){
            ans[i]++;
        }
        ans[i]+=ans[i-1];
    }
    while(q--){
        int l, r;
        scanf("%d %d", &l,&r);
        printf("%d\n", ans[r]-ans[l-1]);
    }
    return 0;
}

C. Karen and Game
题意：每次操作可以选择一行或者一列进行整体+1的操作，问最少步数，使得一开始的全0矩阵变成输入进来的N*M的矩阵。
解法：直接模拟，先行后列的去做，每行取最小值，以及每列取最小值，那么就是这一行和这一列的操作数量。对应模拟出来就行了。因为是要最小步数，所以有可能要先列后行的去做，那么我们两种情况都做以下然后比较操作数量即可。

#include <bits/stdc++.h>
using namespace std;
struct node{
    string s;
    int x;
};
queue<node>s;
int n,m,a[110][110];
int main()
{
    scanf("%d %d", &n,&m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            scanf("%d", &a[i][j]);
    int T = 1000;
    bool *** = 0;
    while(T--){
        bool flag = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(a[i][j]!=0)
                    flag = 1;
        if(flag==0) break;
        int mx=0,r,c;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(a[i][j]>mx){
                    mx=a[i][j];
                    r=i;
                    c=j;
                }
            }
        }
        int mi1=600,mi2=600;
        for(int i=1; i<=n; i++){
            mi1=min(mi1,a[i][c]);
        }
        for(int i=1; i<=m; i++){
            mi2=min(mi2,a[r][i]);
        }
        if(mi1==0&&mi2==0){
            *** = 1;
            break;
        }
        else if(mi1==mi2&&n<m){
            for(int i=1; i<=mi2; i++) s.push(node{"row", r});
            for(int i=1; i<=m; i++){
                a[r][i]-=mi2;
            }
        }
        else if(mi1==mi2&&n>m){
            for(int i=1; i<=mi1; i++) s.push(node{"col", c});
            for(int i=1; i<=n; i++){
                a[i][c]-=mi1;
            }
        }
        else if(mi1>0&&mi2>0){
            if(n>m){
                for(int i=1; i<=mi1; i++) s.push(node{"col", c});
                for(int i=1; i<=n; i++){
                    a[i][c]-=mi1;
                }
            }
            else{
                for(int i=1; i<=mi2; i++) s.push(node{"row", r});
                for(int i=1; i<=m; i++){
                    a[r][i]-=mi2;
                }
            }
        }
        else if(mi1){
            for(int i=1; i<=mi1; i++) s.push(node{"col", c});
            for(int i=1; i<=n; i++){
                a[i][c]-=mi1;
            }
        }
        else if(mi2){
            for(int i=1; i<=mi2; i++) s.push(node{"row", r});
            for(int i=1; i<=m; i++){
                a[r][i]-=mi2;
            }
        }
    }
    if(***==1){
        puts("-1");
    }
    else{
        printf("%d\n", s.size());
        while(!s.empty()){
            cout<<s.front().s<<" "<<s.front().x<<endl;
            s.pop();
        }
    }
}

D. Karen and Test

题意：按照规则求出最后的结果，就是对于相邻两个数的加和减的操作，如果这个操作是第奇数个操作的话就是加，反之为减。直到最后只剩最后一个数即为结果。
解法：打表后可以发现当n为偶数时，相间的偶数行是有规律的，即a[i][j] = a[i-2][j]+a[i-2][j+2]。所以最后的两个数a[n][0]和a[n][1]分别由最初行的奇数列和偶数列得到，最初行的每个值的贡献符合二项式展开，及杨辉三角。如果n%4==0的话，答案由最后两个数相减得到，否则由两个数相加得到。如果n为奇数，那么就先把n模拟一遍，变成偶数。具体证明在CF的BLOG上http://codeforces.com/blog/entry/52742

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+7;
const LL mod = 1e9+7;
LL a[maxn], b[maxn], fac[maxn];
LL qsm(LL a, LL n){
    LL res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
int main(){
    LL n;
    scanf("%lld", &n);
    for(LL i=0; i<n; i++) scanf("%lld", &a[i]), b[i] = a[i];
    if(n == 1){
        printf("%lld\n", a[0]);
        return 0;
    }
    if(n&1){
        n--;
        int flag=0;
        for(LL i=0; i<n; i++){
            if(!flag) a[i]=(b[i]+b[i+1])%mod;
            else a[i]=(b[i]-b[i+1]+mod)%mod;
            flag^=1;
        }
    }
    n=n/2-1;
    fac[0]=1;
    for(LL i=1; i<=n; i++) fac[i]=fac[i-1]*i%mod;
    LL ans1=0,ans2=0;
    for(LL i=0; i<=n; i++){
        LL xishu = (fac[n]*qsm(fac[i]*fac[n-i]%mod,mod-2))%mod;
        (ans1 += xishu*a[i*2]%mod) %= mod;
        (ans2 += xishu*a[i*2+1]%mod) %= mod;
    }
    if(n&1) ans1=(ans1-ans2+mod)%mod;
    else ans1=(ans1+ans2)%mod;
    printf("%lld\n", ans1);
}

E. Karen and Supermarket
题意：n件商品,每件有价格ci,优惠券di,对于i>=2,使用di的条件为:xi的优惠券需要被使用,问初始金钱为b时最多能买多少件商品? n<=5000,ci,di,b<=1e9
解法：树形背包。
把他看成一棵树，dp[i][j][k]是对于j点用不用优惠券（i）已选k个的最小花费。。。很明显对子树做一个分组背包即可。然而乍一看分组背包的复杂度不是n（n个点）*n*n（dp复杂度）是n^3次方吗？
这里有2种dp方式
1.dfs过程中处理u时初始siz[u]=1，搞完u的一棵子树v，花O(siz[u]*siz[v])dp，然后在siz[u]+=siz[v]，继续其他子树
2.先siz[u]+=siz[v]，然后再花O(siz[u]*siz[v])dp。
第一种是O（n^2）的，因为这就相当于求了一次任意两点的lca。
第二种在树是一条链的时候，是n^3的

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
struct edge{
    int v,next;
}E[maxn];
int n, b, dp[2][maxn][maxn]; //dp[i][j][k]表示是对于j点用不用优惠券（i）已选k个的最小花费
int c[maxn], d[maxn], siz[maxn];
int head[maxn], edgecnt;
void init(){
    edgecnt=0;
    memset(head,-1,sizeof(head));
}
void add(int u, int v){
    E[edgecnt].v=v,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
void dfs(int u){
    siz[u] = 1;
    dp[0][u][0] = 0;
    dp[0][u][1] = c[u];
    dp[1][u][1] = c[u]-d[u];
    for(int i=head[u]; ~i; i=E[i].next){
        int v = E[i].v;
        dfs(v);
        for(int j=siz[u]; j>=0; j--){
            for(int k=1; k<=siz[v]; k++){
                dp[0][u][j+k] = min(dp[0][u][j+k], dp[0][u][j]+dp[0][v][k]);
                dp[1][u][j+k] = min(dp[1][u][j+k], dp[1][u][j]+dp[0][v][k]);
                dp[1][u][j+k] = min(dp[1][u][j+k], dp[1][u][j]+dp[1][v][k]);
            }
        }
        siz[u]+=siz[v];
    }
}
int main(){
    while(~scanf("%d%d",&n,&b)){
        memset(dp, 0x3f, sizeof(dp));
        init();
        for(int i=1; i<=n; i++){
            int x;
            scanf("%d %d", &c[i],&d[i]);
            if(i!=1){
                scanf("%d", &x);
                add(x,i);
            }
        }
        dfs(1);
        int ans = 0;
        for(int i=n; i>=0; i--){
            if(dp[1][1][i]<=b || dp[0][1][i]<=b){
                ans=i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}