2017年西南民族大学程序设计竞赛-网络同步赛 简要题解

题目链接https://www.nowcoder.com/acm/contest/64#question

  • 题目好像很水,就随便写写。

A:维护黑洞个数的二维前缀和,每次查询的时候用区间加加减减把我们要的区间减出来判断一下就好了。

int n,m,q;
int cnt[maxn][maxn];
char maze[1005][1005];
int main(){
    read(n),read(m),read(q);
    for (int i=1;i<=n;i++){
        scanf("%s",maze[i]+1);
        for (int j=1;j<=m;j++){
            if (maze[i][j]=='#') cnt[i][j]++;
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cnt[i][j]+=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1];
        }
    }
    for (;q--;){
        int i,j;char op[2];scanf("%d%d%s",&i,&j,op);
        int ans=0;
        if (op[0]=='L'){
            ans+=cnt[i][j]-cnt[i-1][j];
        }
        else if (op[0]=='R'){
            ans+=cnt[i][m]-cnt[i-1][m]-cnt[i][j-1]+cnt[i-1][j-1];
        }
        else if (op[0]=='U'){
            ans+=cnt[i][j]-cnt[i][j-1];
        }
        else ans+=cnt[n][j]-cnt[n][j-1]-cnt[i-1][j]+cnt[i-1][j-1];
        if (ans==0) puts("YES");
        else puts("NO");
    }
    return 0;
}

B

int cnt[10];
char s[maxn];
int main(){
    scanf("%s",s);
    int len=strlen(s);
    for (int i=0;i<len;i++){
        cnt[s[i]-'0']++;
    }
    int x=0;
    for (int i=0;i<10;i++){
        if (cnt[i]) x++;
    }
    if (x==1) puts("YES");
    else puts("NO");
    return 0;
}

C:以b-aa-b为关键字分别排序两次,然后贪心的选择,输出答案的较大者即可,因为当他们差值越大的时候我们选择其中一个才能获得最大利益,如此即可。

struct Node{
    int a,b;
}can[100005];
inline bool cmp1(Node&a,Node&b){
    if (a.a-a.b==b.a-b.b) return a.b<b.b;
    return a.a-a.b>b.a-b.b;
}
inline bool cmp2(Node&a,Node&b){
    if (a.b-a.a==b.b-b.a) return a.a<b.a;
    return a.b-a.a>b.b-b.a;
}
int main(){
    int n,k;
    while (~scanf("%d%d",&n,&k)){
        for (int i=1;i<=n;i++) read(can[i].a);
        for (int i=1;i<=n;i++) read(can[i].b);
        sort(can+1,can+1+n,cmp1);
        ll ans=0,ans2=0;
        for (int i=1;i<=k;i++){
            ans+=can[i].a*1LL;
        }
        for (int i=k+1;i<=n;i++){
            ans+=can[i].b*1LL;
        }
        sort(can+1,can+1+n,cmp2);
        for (int i=1;i<=n-k;i++){
            ans2+=can[i].b*1LL;
        }
        for (int i=n-k+1;i<=n;i++){
            ans2+=can[i].a*1LL;
        }
        cout<<max(ans,ans2)<<endl;
    }
    return 0;
}

D:维护前缀和,贪心即可

const int N=10005;
int n;
ll w[N];
int main(){
    while (~scanf("%d",&n)){
        for (int i=1;i<=n;i++) read(w[i]),w[i]+=w[i-1];
        int m,L,R;
        ll ans=0;
        for (read(m);m--;){
            read(L),read(R);
            ans+=max(0LL,w[R]-w[L-1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

E:补集的思想,所有的方案数是m^n,所有不相邻的方案数就是m\*(m-1)^{n-1},就是第一个格子可以放m个颜色,之后的所有格子都只能放m-1个颜色,相减即可。

const ll MOD=1000000007LL;
ll n,m;
ll ksm(ll a,ll n){
    if (a<0) a+=P;
    if (n<0) n+=P;
    ll res=1LL;
    while (n){
        if (n&1) res=res*a%P;
        a=(a*a)%P;
        n>>=1;
    }
    return res;
}
int main(){
    read(n),read(m);
    m%=MOD;
    cout<<((ksm(m,n)-m*ksm(m-1,n-1)%P)%P+P)%P<<endl;
    return 0;
}

F:模拟题意即可

int n;
int cnt[13][13]={1,1,1,1,1,1,1,1,1,1,1,1,1,
                 1,2,2,2,2,2,2,2,2,2,2,2,1,
                 1,2,2,2,2,2,2,2,2,2,2,2,1,
                 1,2,2,3,3,3,3,3,3,3,2,2,1,
                 1,2,2,3,3,3,3,3,3,3,2,2,1,
                 1,2,2,3,3,4,4,4,3,3,2,2,1,
                 1,2,2,3,3,4,4,4,3,3,2,2,1,
                 1,2,2,3,3,4,4,4,3,3,2,2,1,
                 1,2,2,3,3,3,3,3,3,3,2,2,1,
                 1,2,2,3,3,3,3,3,3,3,2,2,1,
                 1,2,2,2,2,2,2,2,2,2,2,2,1,
                 1,2,2,2,2,2,2,2,2,2,2,2,1,
                 1,1,1,1,1,1,1,1,1,1,1,1,1};
char s[14][14];
int main(){
    while (~scanf("%d",&n) && n){
        double ans=0;
        for (int i=0;i<13;i++){
            scanf("%s",s[i]);
            for (int j=0;j<13;j++){
                ans+=(s[i][j]=='#'?cnt[i][j]*1.0:0);
            }
        }
        printf("%.2lf\n",ans/n);
    }
    return 0;
}

G:模拟题意即可

int n;
char x[20],y[20];
int main(){
    while (~scanf("%d",&n)){
        int a=0,b=0;
        for (int i=1;i<=n;i++){
            scanf("%s%s",x,y);
            if (x[0]=='J' && y[0]=='M') a+=3;
            else if (x[0]=='M' && y[0]=='T') a+=3;
            else if (x[0]=='T' && y[0]=='S') a+=3;
            else if (x[0]=='S' && y[0]=='H') a+=3;
            else if (x[0]=='H' && y[0]=='J') a+=3;
            else if (y[0]=='J' && x[0]=='M') b+=3;
            else if (y[0]=='M' && x[0]=='T') b+=3;
            else if (y[0]=='T' && x[0]=='S') b+=3;
            else if (y[0]=='S' && x[0]=='H') b+=3;
            else if (y[0]=='H' && x[0]=='J') b+=3;
            else a++,b++;
        }
        if (a>b) puts("Alice");
        else if (a==b) puts("Draw");
        else puts("Bob");
    }
    return 0;
}

H

string s="gu...";
string t="The story is so boring. And I am so hungry!" ;
int main(){
    int n;
    while (~scanf("%d",&n)){
        for (int i=1;i<=n;i++) cout<<s;
        cout<<endl;
        cout<<t<<endl;
    }
    return 0;
}

Idp[i][j]为到i位置为止结尾为01的方案数,转移显然。

ll dp[22][2];
int main(){
    dp[1][0]=1;
    dp[1][1]=1;
    for (int i=2;i<=20;i++){
        dp[i][0]=dp[i-1][1];
        dp[i][1]=dp[i-1][0]+dp[i-1][1];
    }
    int n;
    while (~scanf("%d",&n)){
        cout<<dp[n][0]+dp[n][1]<<endl;
    }
    return 0;
}

J:模拟题意即可

int m,pos[26],pos2[26];
char x[2],y[2];
char s[maxn];
int main(){
    while (~scanf("%s",s)){
        int len=strlen(s);
        for (int i=0;i<26;i++) pos[i]=i,pos2[i]=i;
        for (read(m);m--;){
            scanf("%s%s",x,y);
            int xxx=pos2[x[0]-'a'],yyy=pos2[y[0]-'a'];
            pos2[x[0]-'a']=yyy,pos2[y[0]-'a']=xxx;
        }
        for (int i=0;i<len;i++){
            putchar(pos[pos2[s[i]-'a']]+'a');
        }
        puts("");
    }
    return 0;
}

K:经典区间打标记题

int n,m,cnt[maxn];
int main(){
    while (~scanf("%d%d",&n,&m)){
        memset(cnt,0,sizeof(cnt));
        int mx=0;
        for (int i=1;i<=n;i++){
            int l,r;read(l),read(r);
            cnt[l]++,cnt[r+1]--;
        }
        for (int i=1;i<=5000;i++) mx=max(mx,cnt[i]+=cnt[i-1]);
        printf("%d\n",mx/m+(mx%m==0?0:1));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注