◆赛时·III◆ ABC-099


■唠叨■

不要问我为什么先给ABC-100写了博客再写的ABC-099……

莫名觉得这次比赛特别简单……虽然我并没有参加比赛,只是之后再补做的。QwQ


■试题&解析■

◇不动脑子◇ A-ABD

  • 【Atcoder ABC-099 A】
  • 【翻译】

    从ABC开始举办的数十年后,

    每轮比赛被编号为 ABC-001,ABC-002...,但是第999轮比赛后,一个问题产生了:如何给之后的比赛编号?

    最后,决定第1000轮到第1998轮被依次编号为 ABD-001,ABD-002...

    求第N轮比赛(1≤N≤1998)的编号的前3位(ABC or ABD)
  • 【解析】

    其实看样例就能够看出来——当N≤999时,输出ABC,否则输出ABD。就不解释了(⊙ᗜ⊙)
  • 【源代码】
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int n;scanf("%d",&n);
printf("%s",n<=999? "ABC":"ABD");
return 0;
}

◇论英语的重要性◇ B-Stone Monument

  • 【Atcoder ABC-099 B】
  • 【翻译】

    在一些村庄里,共有999座塔自西向东排列,第i座塔的高度为 (1+2+3+...+i)米。

    雪下了很久才停,我们测量了两个相邻的塔分别露出雪面的高度,靠西的塔是A米,靠东的塔是B米。

    若村庄的地面相平,且雪覆盖深度相同(即雪在各处的高度是一样的),给出A,B,求积雪的深度。保证有解。
  • 【解析】

    虽然我知道这道题有数学方法,但还是直接上大暴力……先算出999座塔的高度。再直接枚举第i座塔,如果第i-1座塔(靠西)的高度减去A等于第i座塔的高度减去B,即雪的深度。
  • 【源代码】
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int tower[1005];
int main()
{
for(int i=1;i<=999;i++)
tower[i]=tower[i-1]+i;
int a,b;
scanf("%d%d",&a,&b);
for(int i=2;i<=999;i++)
if(tower[i-1]-a==tower[i]-b)
{
printf("%d\n",tower[i-1]-a);
return 0;
}
return 0;
}

◇奇怪,真的奇怪◇ C-Strange Bank

  • 【Atcoder ABC-099 C】
  • 【翻译】

    为了使人们取钱更困难(????),一家银行在提款时只允许取走1日元、6的幂日元(如6、36、216)以及9的幂日元。且不允许将取出的钱再存入,请问取出N日元最少需要提款多少次?
  • 【解析】

    其实是一个类似于完全背包的背包问题……

    简单地定义状态dp[i]表示取出n日元的最少次数。那么物品有1,6,36,...,9,81,...日元。最终状态是dp[n]。

    于是我就用记忆化搜索,当前钱数为x,每次枚举取出钱数i(i < x),dp[x]=min{dp[x-i]}。
  • 【源代码】
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,dp[100005];
int DP(int x)
{
if(x<0) return 1e8;
if(x==0) return 0;
if(dp[x]!=-1) return dp[x];
dp[x]=1e8;
for(int i=6;i<=x;i*=6)
dp[x]=min(dp[x],DP(x-i)+1);
for(int i=9;i<=x;i*=9)
dp[x]=min(dp[x],DP(x-i)+1);
dp[x]=min(dp[x],DP(x-1)+1);
return dp[x];
}
int main()
{
scanf("%d",&n);
memset(dp,-1,sizeof dp);
printf("%d\n",DP(n));
return 0;
}

◇压轴大暴力?◇ D-Good Grid

  • 【Atcoder ABC-099 D】
  • 【翻译】

    有一个N*N的正方形,(i,j)表示i行j列。

    共有C种颜色,这个正方形的所有块都被涂上了这些颜色。若某一个块上原来涂的是颜色x,要将其改为颜色j,则需要花费C[i][j]。

    特别的,对于(i,j),令F(i,j)=(i+j)%3,则给出改变颜色的花费和该正方形原本每个块涂上的颜色,求出要使F(i,j)值不同的格子涂的颜色不同,F(i,j)值相同的格子涂的颜色相同的最小花费。
  • 【解析】

    用tot[x][y]统计F(i,j)=x的格子中,原本颜色为y的格子的个数。然后枚举3种不同的格子(模3余0,1,2)将要被涂成的颜色,分别计算每一种格子需要的花费,最后统计取最小值。简单说来就是大暴力,时间复杂度大概是 O(颜色种类数^3)=O(27000)。

    好像时间复杂度也不是特别大……(o^^)o
  • 【源代码】
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXCOL=30;
int n_col,siz,spd[MAXCOL+5][MAXCOL+5];
int tot[3][MAXCOL+5];
int main()
{
scanf("%d%d",&siz,&n_col);
for(int i=0;i<n_col;i++)
for(int j=0;j<n_col;j++)
scanf("%d",&spd[i][j]);
for(int i=0;i<siz;i++)
for(int j=0;j<siz;j++)
{
int col;
scanf("%d",&col);
tot[(i+j+2)%3][col-1]++;
}
int ans=1e9;
for(int i=0;i<n_col;i++)
{
int A=0;
for(int col=0;col<n_col;col++)
A+=tot[0][col]*spd[col][i];
for(int j=0;j<n_col;j++)
if(i!=j)
{
int B=0;
for(int col=0;col<n_col;col++)
B+=tot[1][col]*spd[col][j];
for(int k=0;k<n_col;k++)
if(i!=k && j!=k)
{
int C=0;
for(int col=0;col<n_col;col++)
C+=tot[2][col]*spd[col][k];
ans=min(ans,A+B+C);
}
}
}
printf("%d\n",ans);
return 0;
}

The End

Thanks for reading!

- Lucky_Glass

最新文章

  1. DEV皮肤颜色获取
  2. BZOJ3542:DZY Loves March
  3. NOIP 2005 青蛙过河
  4. linux 入门教程
  5. JavaScript入门(9)
  6. (转载)php flush()刷新不能输出缓冲的原因分析
  7. 算法导论(第三版)Exercises2.3(归并排序、二分查找、计算集合中是否有和为X的2个元素)
  8. mvc 防止客服端多次提交
  9. UIButton 中高亮取消
  10. 零碎的JS基础
  11. redis源码分析之发布订阅(pub/sub)
  12. Druid数据库连接池源码分析
  13. 泡菜的使用pickle
  14. 上下div高度动态自适应--另类处理方案
  15. qt界面操作
  16. Redis 配置内容总结
  17. centos 6.8安装redis
  18. 强网杯2018 Web签到
  19. Laravel学习--时间
  20. Spring MVC与注解相关的一些配置的方法

热门文章

  1. Sean McGinnis
  2. OpenStack Weekly Rank 2015.07.27
  3. 动态资源不缓存 filter
  4. rsync+inotify实现数据的实时同步更新
  5. php-fpm 进程在云服务器cpu分配不均匀
  6. c#ArrayList 对象集合 按某字段(属性)排序
  7. 20170802,css样式优先级
  8. Design Pattern -&gt;Prototype
  9. Struts2_HelloWorld_2
  10. php的yii框架开发总结9