【AtCoder Beginner Contest 099】Solution / Editorial / 题解

【AtCoder Beginner Contest 099】Solution / Editorial / 题解

比赛地址

A、B 过水,不讲。

C – Strange Bank

Statement

To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:

1 yen (the currency of Japan)

6 yen, 62(=36) yen, 63(=216) yen, …

9 yen, 92(=81) yen, 93(=729) yen, …

At least how many operations are required to withdraw exactly N yen in total?

It is not allowed to re-deposit the money you withdrew.

Idea

题目中$N$最大为 $1000000$,发现只有14种小于$N$的面额,完全背包即可。

Code

伪的,不能A。

    cin>>n;
    for (int i=1;i<=n;i++) f[i]=i;
    t=1;while(t<=n){t*=6;c[++cnt]=t;}
    t=1;while(t<=n){t*=9;c[++cnt]=t;}
    for(int i=1;i<=cnt;i++)
        for(int j=c[i];j<=n;j++)
            if(c[i]<j) f[j]=min(f[j],f[j-c[i]]+1);
    cout<<f[n]<<endl;

D – Good Grid

Statement

There is a grid with N rows and N columns of squares. Let (i,j) be the square at the i-th row from the top and the j-th column from the left.

These squares have to be painted in one of the C colors from Color 1 to Color C. Initially, (i,j) is painted in Color ci,j.

We say the grid is a good grid when the following condition is met for all i,j,x,y satisfying 1≤i,j,x,y≤N:

If (i+j)%3=(x+y)%3, the color of (i,j) and the color of (x,y) are the same.
If (i+j)%3≠(x+y)%3, the color of (i,j) and the color of (x,y) are different.
Here, X%Y represents X modulo Y.

We will repaint zero or more squares so that the grid will be a good grid.

For a square, the wrongness when the color of the square is X before repainting and Y after repainting, is DX,Y.

Find the minimum possible sum of the wrongness of all the squares.

Idea

发现只选择三种不同颜色填在三个部分,预处理每个部分每种颜色的代价,然后枚举,两个三重循环搞定。

Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int D[40][40],C[600][600],n,c,P[3][40],ans=2147483647;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>c;
    for (int i=1;i<=c;i++)
        for (int j=1;j<=c;j++)
            cin>>D[i][j];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cin>>C[i][j];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            for (int k=1;k<=c;k++)
                P[(i+j)%3][k]+=D[C[i][j]][k];
    for (int i=1;i<=c;i++)
        for (int j=1;j<=c;j++)
            for (int k=1;k<=c;k++)
                if (i!=j&&i!=k&&j!=k)
                    ans=min(ans,P[0][i]+P[1][j]+P[2][k]);
    cout<<ans<<endl;
    return 0;
}

Summary

很水的ABC,竟然花了一个小时才AK,其中还WA了六发。。。

这么水的比赛写题解的原因当然是给博客加内容啦(

Show Comments