2016 ACM Amman Collegiate Programming Contest 训练赛部分题解

【题目】题目可以在这里看：http://codeforces.com/gym/101102/problem/A

【A】Coins

【题意】在A,B两个大集合里面选子集使得他们的和为W,并且两个子集的和的差<=K。

【解题方法】背包问题计算方案数，注意要考虑空集。

【代码君】

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N =15000;
const int mod=1e9+7;
int a[200],b[200];
LL dp1[200][16000],dp2[200][16000];
int main()
{
    int T,n,m,k,w;
    scanf("%d",&T);
    while(T--){
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        scanf("%d%d%d%d",&n,&m,&k,&w);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=0;i<m;i++){
            scanf("%d",&b[i]);
        }
        dp1[0][a[0]]=1;
        dp1[0][0]=1;
        for(int i=1;i<n;i++){
            for(int j=0;j<=N;j++){
                dp1[i][j]+=dp1[i-1][j];
                if(j-a[i]>=0) dp1[i][j]=(dp1[i][j]+dp1[i-1][j-a[i]])%mod;
            }
        }
        dp2[0][b[0]]=1;
        dp2[0][0]=1;
        for(int i=1;i<m;i++){
            for(int j=0;j<=N;j++){
                dp2[i][j]+=dp2[i-1][j];
                if(j-b[i]>=0) dp2[i][j]=(dp2[i][j]+dp2[i-1][j-b[i]])%mod;
            }
        }
        LL ans=0;
        for(int i=0;i<=w;i++){
            if(abs(w-i-i)<=k) ans=(ans+dp1[n-1][i]*dp2[m-1][w-i])%mod;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

【B】

【题意】用已经有的火柴去拼成更大的数字，问这个最大数字。

【解题方法】只需要考虑拼火柴的上下界，然后贪心即可。

【AC 代码】

//
//Created by just_sort 2016/9/30 19:27
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int f[10]={6,2,5,5,4,5,6,3,7,6};
char s[100010];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%s",&n,s);
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += f[s[i]-'0'];
        }
        for(int i = 1; i < n; i++){
            for(int j = 9; j >= 0; j--){
                int temp = sum - f[j];
                if(temp <= (n-i)*7 && temp >= (n-i)*2){
                    printf("%d",j);
                    sum -= f[j];
                    break;
                }
            }
        }
        for(int i = 9; i >= 0; i--){
            if(sum == f[i]){
                printf("%d",i);
                break;
            }
        }
        printf("\n");
    }
    return 0;
}

【C】

【题意】给了一些人比赛的得分，问从哪个位置开始，这个比赛的冠军就确定了。

【解题方法】我们可以考虑记录最大值的位置，然后倒着扫描一遍，那么第一个不等于最后一次操作确定的最大值，就是这个位置了。

【代码君】

//
//Created by just_sort 2016/9/30 15:32
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6+10;
struct node{
    int l,r;
    int maxv,id;
}Tree[maxn*4];
int ans[maxn];
void pushup(int rt){
    Tree[rt].maxv = max(Tree[rt*2].maxv,Tree[rt*2+1].maxv);
    if(Tree[rt*2].maxv >= Tree[rt*2+1].maxv){
        Tree[rt].id = Tree[rt*2].id;
    }
    else{
        Tree[rt].id = Tree[rt*2+1].id;
    }
}
void Build(int l,int r,int rt)
{
    Tree[rt].l = l,Tree[rt].r = r;
    if(l == r){
        Tree[rt].maxv = 0;
        Tree[rt].id = l;
        return ;
    }
    int mid = (l + r)/2;
    Build(l,mid,rt*2);
    Build(mid+1,r,rt*2+1);
    pushup(rt);
}
void update(int pos,int v,int rt){
    if(Tree[rt].l == Tree[rt].r){
        Tree[rt].maxv += v;
        return ;
    }
    int mid = (Tree[rt].l + Tree[rt].r)/2;
    if(pos <= mid) update(pos,v,rt*2);
    else update(pos,v,rt*2+1);
    pushup(rt);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,q;
        //memset(ans,0,sizeof(ans));
        scanf("%d%d",&n,&q);
        Build(1,n,1);
        for(int i = 1; i <= q; i++){
            int id,val;
            scanf("%d%d",&id,&val);
            update(id,val,1);
            ans[i] = Tree[1].id;
        }
        int pos;
        for(int i = q; i > 0; i--){
            if(ans[i] != ans[q]){
                break;
            }
            pos = i;
        }
        if(pos == 1 && ans[pos] == 1){
            printf("0\n");
        }
        else{
            printf("%d\n",pos);
        }
    }
    return 0;
}

【D】

【题意】问一个大的矩阵里面有多少个子矩阵，满足每个子矩阵的每一个元素想等。

【解题方法】特别感谢 qwb 大牛替我解答这一个问题。单调栈的经典题目了，不会单调栈可以去学一下。直接放代码了。

【代码君】

//
//Created by just_sort 2016/9/30 15:32
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1002;
int S[maxn][maxn],TOP[maxn][maxn];
int A[maxn],B[maxn],sz,sum;
int n,m;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                scanf("%d",&S[i][j]);
            }
        }
        long long ans = 0;
        for(int i = 1; i <= n; i++){
            sz = sum = 0;
            for(int j = 1; j <= m; j++){
                int h = (S[i][j] == S[i-1][j] ? TOP[i-1][j] + 1 : 1);
                int w = 1;
                TOP[i][j] = h;
                if(S[i][j] != S[i][j-1]) sum = sz = 0;
                while(sz && h <= A[sz]){
                    sum -= A[sz] * B[sz];
                    w += B[sz--];
                }
                A[++sz] = h;B[sz] = w;
                sum += A[sz] * B[sz];
                ans += sum;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

【E】水题，输出(n+4)/5即可。

【F】

【题意】问经过最多一次替换，原串可以得到的字典序最小的串是什么？

【解题方法】简单贪心即可。

【AC 代码】

#include<bits/stdc++.h>
using namespace std;
char s[200000];
int flag[26],f[26];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        memset(flag,0,sizeof(flag));
        memset(f,0,sizeof(f));
        scanf("%s",s);
        for(int i=0;s[i];i++){
            flag[s[i]-'a']=1;
        }
        int ans1=-1,ans2=-1,ff=0;
        for(int i=0;s[i];i++){
            f[s[i]-'a']=1;
            for(int j=0;j<s[i]-'a';j++){
                if(flag[j]&&f[j]==0){
                    ans1=s[i]-'a';
                    ans2=j;
                    ff=1;
                    break;
                }
            }
            if(ff==1) break;
        }
        if(ans1!=-1){
            for(int i=0;s[i];i++){
                if(s[i]-'a'==ans1){
                    s[i]='a'+ans2;
                }
                else if(s[i]-'a'==ans2){
                    s[i]='a'+ans1;
                }
            }
        }
        printf("%s\n",s);
    }
    return 0;
}

【H】水题，判断相邻空位是否>=(m+1)即可。

【I】

【题意】给了一个矩形，大小R*C,然后给了一个机器人的一串指令，现在机器人的初始位置不定，如果机器人执行当前指令，它会走出r*c的区域的话，那么当前指令会被跳过，问最少有多少条指令会被跳过。

【解题方法】一种好的方法是，我们分别来统计横着走和上下走的对答案的贡献。所以我们分别拿出横的和竖的走法，分别统计就行了。

【代码君】

//
//Created by just_sort 2016/9/30 20:23
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5+10;
char str[maxn];
int X[maxn],Y[maxn],cntx,cnty;
int ans,maxx,minn,pos,sum;
bool flag;

int main()
{
    int T,r,c;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%s",&r,&c,str);
        int len = strlen(str);
        cntx = 0;
        cnty = 0;
        memset(X,0,sizeof(X));
        memset(Y,0,sizeof(Y));
        for(int i = 0; i < len; i++){
            if(str[i] == '>') X[cntx++] = 1;
            else if(str[i] == '<') X[cntx++] = -1;
            else if(str[i] == '^') Y[cnty++] = -1;
            else if(str[i] == 'v') Y[cnty++] = 1;
        }
        sum = 0;
        flag = 0;
        ans = minn = maxx = pos = 0;
        for(int i = 0; i <cntx; i++){
            pos += X[i];
            if(flag){
                if(pos >= c){
                    ans++;
                    pos = c - 1;
                }
                else if(pos < 0){
                    ans++;
                    pos = 0;
                }
            }
            else{
                minn = min(minn,pos);
                maxx = max(maxx,pos);
                if(maxx - minn >= c){
                    flag = 1;
                    ans++;
                    if(pos == minn){
                        pos = 0;
                    }
                    else{
                        pos = c - 1;
                    }
                }
            }
        }
        sum += ans;
        flag = 0;
        ans = minn = maxx = pos = 0;
        for(int i = 0; i <cnty; i++){
            pos += Y[i];
            if(flag){
                if(pos >= r){
                    ans++;
                    pos = r - 1;
                }
                else if(pos < 0){
                    ans++;
                    pos = 0;
                }
            }
            else{
                minn = min(minn,pos);
                maxx = max(maxx,pos);
                if(maxx - minn >= r){
                    flag = 1;
                    ans++;
                    if(pos == minn){
                        pos = 0;
                    }
                    else{
                        pos = r - 1;
                    }
                }
            }
        }
        sum += ans;
        printf("%d\n",sum);
    }
    return 0;
}