比赛地址
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了六发。。。
这么水的比赛写题解的原因当然是给博客加内容啦（