AtCoder Beginner Contest 099 解题报告
AtCoder Beginner Contest 099 解题报告
题目链接
https://abc099.contest.atcoder.jp/assignments
A题
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
cout << (n < 1000 ? "ABC" : "ABD") << endl;
return 0;
}B题
s1 = 1 s2 = 1 + 2 s3 = 1 + 2 + 3 sn = 1 + 2 + 3 + …… + n 对于相邻的两个塔来说，无论积雪多少米，b-a都是第2个塔的n。求出n之后，再根据求和公式s = n * (n + 1) / 2，即可求出塔高
#include <cstdio>
using namespace std;
int a,b,now;
int main()
{
scanf("%d%d",&a,&b);
now=b-a; //算出b等差数列的最后一项
printf("%d",(now+1)*now/2-b); //(now+1)*now/2为b塔的原始高度(等差数列求和公式)
return 0;
}C题
注意，本题不能使用贪心算法
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n;
cin >> n;
int res = n;
for(int i = 0; i <= n; i++)
{
int cnt = 0;
int tmp = i;
while(tmp > 0)
{
cnt += tmp % 6;
tmp /= 6;
}
tmp = n - i;
while(tmp > 0)
{
cnt += tmp % 9;
tmp /= 9;
}
if(res > cnt)
{
res = cnt;
}
}
cout << res << endl;
return 0;
}D题
对于二维网格C(i, j)，定义好网格： 若坐标%3的值相同，则颜色也相同。比如C(1, 2) = C(2, 1) 若坐标%3的值不相同，则颜色也不相同。比如C(1, 1) != C(1,2) != C(2,2)
D为代价值, 假如C(1, 2) = 2, 要调整为C(1, 2) = 3，则代价值为D(2, 3) 再比如C(2, 1) = 3，要调整为C(2, 1) = 2，则代价值为D(3, 2) 再比如C(1, 2) = 1, 要调整为C(1, 2) = 1，则代价值为D(1, 1)。这个其实不用调整，所以D(1, 1) = 0，同理D(x, x) = 0
用第1个例子来计算，
D =
0 1 1
1 0 1
1 4 0
C =
1 2
3 3这里C(1,1)的坐标模3等于(1 + 1) % 3 = 2 C(1, 2)的坐标模3等于(1 + 2) % 3 = 0 C(1, 2)的坐标模3等于(2 + 1) % 3 = 0 C(2, 2)的坐标模3等于(2 + 2) % 3 = 1 题目要求C(1, 2) = C(2, 1)，C(1,1)、C(2,1)和C(2,2)要两两互不相等。
可以用穷举法调整出6种好网格： （一） C(1, 1) = 1, D(1, 1) = 0 C(1, 2) = 2, D(2, 2) = 0 C(2, 1) = 2, D(3, 2) = 4 C(2, 2) = 3, D(3, 3) = 0 D = D(1, 1) + D(2, 2) + D(3, 2) + D(3, 3) = 4
（二） C(1, 1) = 1, D(1, 1) = 0 C(1, 2) = 3, D(2, 3) = 1 C(2, 1) = 3, D(3, 3) = 0 C(2, 2) = 2, D(3, 2) = 4 D = 0 + 1 + 0 + 4 = 5
（三） C(1, 1) = 2, D(1, 2) = 1 C(1, 2) = 1, D(2, 1) = 1 C(2, 1) = 1, D(3, 1) = 1 C(2, 2) = 3, D(3, 3) = 0 D = 1 + 1 + 1 = 3
（四） C(1, 1) = 2, D(1, 2) = 1 C(1, 2) = 3, D(3, 2) = 4 C(2, 1) = 3, D(3, 3) = 0 C(2, 2) = 1, D(3, 1) = 1 D = 6
（五） C(1, 1) = 3, D(3, 1) = 1 C(1, 2) = 1, D(2, 1) = 1 C(2, 1) = 1, D(3, 1) = 1 C(2, 2) = 2, D(3, 2) = 4 D = 7
（六） C(1, 1) = 3, D(3, 1) = 1 C(1, 2) = 2, D(2, 2) = 0 C(2, 1) = 2, D(3, 2) = 4 C(2, 2) = 1, D(3, 1) = 1 D = 6
这六种调整方法中，最小的D为3，所以本例子的答案为6
本题的难点主要是理解题意，解题倒不难，用穷举法即可。 代码：
// Algorithm: Brute-force
#include "cstdio"
using namespace std;
const int maxn=30+10;
int n,c,d[maxn][maxn],t[4][maxn],x,y,z,ans;
int main()
{
ans=0x7fffffff; // 先把答案记为一个极大值，出现更小的就更新
scanf("%d%d",&n,&c);
register int i,j,k,l;
for(i=1;i<=c;i++)
{
// 输入D矩阵(i-j)为颜色i变为颜色j的代价为(i,j)
for(j=1;j<=c;j++)
{
scanf("%d",&d[i][j]);
}
}
for(i=1;i<=n;i++)
{
// 输入矩阵C
for(j=1;j<=n;j++)
{
scanf("%d",&x);
t[(i+j)%3][x]++; // 计算横坐标加纵坐标mod3的数值,颜色为x的个数+1
}
}
for(i=1;i<=c;i++)
{
// 枚举坐标余数为0的颜色，统一变成颜色i，其代价之和为x
// 比如例1中，坐标为1行2列的余数为(1+2)%3=0，其值2，变成i=1则D_21=1
// 坐标2列1行的余数为(2+1)%3=0，其值为3，变成i=1则有D_31=31
// x = D_21 + D_31 = 2
x=0;
for(j=1;j<=c;j++)
{
x+=t[0][j]*d[j][i];
}
for(j=1;j<=c;j++)
{ // 枚举余数为1的颜色，统一变成颜色j,其代价之和为y
if(j==i)
{
continue; // 不同余数的颜色不能相同
}
y=0;
for(k=1;k<=c;k++)
{
y+=t[1][k]*d[k][j];
}
for(k=1;k<=c;k++)
{
// 枚举坐标余数为2的颜色，统一变成颜色k,其代价之和为z
if(k==j || k==i)
{
continue; // 不同余数的颜色不能相同
}
z=0;
for(l=1;l<=c;l++)
{
z+=t[2][l]*d[l][k];
}
if(ans>x+y+z)
{
// 如果当前转换的代价和比之前的最优答案更小，就更新代价和
ans=x+y+z;
}
}
}
}
printf("%d",ans);
return 0;
}