神刀安全网

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; } 

TopCoder & Codeforces & AtCoder交流QQ群:648202993
更多内容请关注微信公众号

AtCoder Beginner Contest 099 解题报告

wechat_public_header.jpg

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » AtCoder Beginner Contest 099 解题报告

分享到:更多 ()