首页 > 其他分享 >AtCoder Beginner Contest 173 A~D 题解

AtCoder Beginner Contest 173 A~D 题解

时间:2024-09-08 20:52:09浏览次数:13  
标签:AtCoder AC le 输出 int 题解 样例 TLE 173

A - Payment

题目大意

如果使用价值\(1000\)元的纸币(假设有)支付\(N\)元,服务员会找多少钱?

\(1\le N\le 10000\)

输入格式

\(N\)

输出格式

一行,即服务员找的钱数。

样例

输入 输出
1900 100
3000 0

分析

特判:
如果\(N\)除以\(1000\)能整除,那么不需要找钱,输出\(0\);
如果有余,输出\(1000 - (n\mod1000)\)。

代码

#include <cstdio>
using namespace std;

int main(int argc, char** argv)
{
	int n;
	scanf("%d", &n);
	if(n % 1000 == 0) puts("0");
	else printf("%d\n", 1000 - n % 1000);
	return 0;
}

B - Judge Status Summary

题目大意

某人完成了某道算法竞赛题,有ACWATLERE四种结果(status)。题目有\(N\)个测试样例,测试结果分别为\(S_1, S_2, \dots, S_N\),请分别统计并输出ACWATLERE的个数。(格式详见输出格式)

\(1\le N\le 10^5\)
\(S_i\)是ACWATLERE

输入格式

\(N\)
\(S_1\)
\(S_2\)
\(:\)
\(S_N\)

输出格式

AC x [AC的个数]
WA x [WA的个数]
TLE x [TLE的个数]
RE x [RE的个数]

注意:这里的“乘号”不是“×”,而是英文字母“x”!

样例

样例输入1

6
AC
TLE
AC
AC
WA
TLE

样例输出1

AC x 3
WA x 1
TLE x 2
RE x 0

ACWATLERE分别有\(3, 1, 2, 0\)个。

样例输入2

10
AC
AC
AC
AC
AC
AC
AC
AC
AC
AC

样例输出2

AC x 10
WA x 0
TLE x 0
RE x 0

他全都AC了……

分析

要统计个数,可以用别的方法,但我个人喜欢偷懒,使用了map(似乎大材小用了……)

代码

#include <iostream>
#include <string>
#include <map>
using namespace std;

map<string, int> cnt;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=0; i<n; i++)
	{
		string s;
		cin>>s;
		cnt[s] ++;
	}
	cout<<"AC x "<<cnt["AC"]<<endl;
	cout<<"WA x "<<cnt["WA"]<<endl;
	cout<<"TLE x "<<cnt["TLE"]<<endl;
	cout<<"RE x "<<cnt["RE"]<<endl;
	return 0;
}

C - H and V

题目大意

给定\(H\)行\(W\)列的方格。在第\(i\)行\(j\)列(\(1\le i\le H\), \(1\le j\le W\))的方格是\(c_i\)\(_,\)\(_j\)。它可能是#(黑色)或.(白色)。
可以选某些行和列(都可以不选),将行和列上的方格全部涂成红色。

给定整数\(K\)。有多少种选法使图中只剩\(K\)个黑方格?

\(1\le H, W\le 6\)
\(1\le K\le HW\)
\(c_i\)\(_,\)\(_j\)是#.

输入格式

\(H~W~K\)
\(c_{1,1}~c_{1,2}~\dots~c_{1,W}\)
\(c_{2,1}~c_{2,2}~\dots~c_{2,W}\)
\(\vdots\)
\(c_{H,1}~c_{H,2}~\dots~c_{1,W}\)

输出格式

一行,即符合条件的选法数量。

样例

样例输入1

2 3 2
..#
###

样例输出1

5

有五种方法:

  • 第\(1\)行和第\(1\)列
  • 第\(1\)行和第\(2\)列
  • 第\(1\)行和第\(3\)列
  • 第\(1\)、\(2\)列
  • 第\(3\)列

样例输入2

2 3 4
..#
###

样例输出2

1

只有一种方法:啥也不干!

样例输入3

2 2 3
##
##

样例输出3

0

无解。

样例输入4

6 6 8
..##..
.#..#.
#....#
######
#....#
#....#

博主提示:这是最大的数据,如果程序在本地运行此样例没有超时,则提交后不会TLE!

样例输出4

208

分析

本题没有巧妙的方法,且数据范围较小,所以使用二进制法枚举行和列。
因为输入颜色只有黑或白,所以题目中“涂成红色”只要涂成白色(.)即可。

代码

#include <cstdio>
#include <cstring>
#define maxn 6
using namespace std;

char c[maxn][maxn];
int h, w, k;
int cnt = 0;

int main(int argc, char** argv)
{
	scanf("%d%d%d", &h, &w, &k);
	for(int i=0; i<h; i++)
		scanf("%s", c[i]);
	int m1 = 1 << h, m2 = 1 << w, ans = 0;
	for(int hs=0; hs<m1; hs++)
		for(int ws=0; ws<m2; ws++)
		{
			char tmp[maxn][maxn]; // 不能修改原数组,所以复制一个数组
			memcpy(tmp, c, sizeof(c));
			for(int i=0; i<h; i++) // 行
				if(hs & (1 << i)) for(int j=0; j<w; j++) // 列
					tmp[i][j] = '.';
			for(int i=0; i<w; i++) // 列
				if(ws & (1 << i)) for(int j=0; j<h; j++) // 行
					tmp[j][i] = '.'; // 注意:绝对不能写成tmp[i][j]!
			int cnt = 0;
			for(int i=0; i<h; i++)
				for(int j=0; j<w; j++) if(tmp[i][j] == '#')
					cnt ++;
			if(cnt == k) ans ++;
		}
	printf("%d\n", ans);
	return 0;
}

D - Chat in a Circle

题目大意

有\(N\)个人要在某地会和,编号为\(i\)的人的友情值为整数\(A_i\)。这些人要围成一圈,每人到达该地后会在某个位置插入圈子。每个人的舒适度是入圈时相邻两个人的友情值中较小的一个(第一个人的舒适度为\(0\))。现在,由你决定他们的入圈顺序和插入位置,问:\(N\)个人的最大舒适度之和是多少?

\(2\le N\le 2\times10^5\)
\(1\le A_i\le 10^9\)

输入格式

\(N\)
\(A_1~A_2~\dots~A_N\)

输出格式

一行,即\(N\)个人的最大舒适度之和。

样例

样例输入1

4
2 2 1 3

样例输出1

7

最大的舒适度之和为\(0+3+2+2=7\)。
舒适度

样例输入2

7
1 1 1 1 1 1 1

样例输出2

6

分析

贪心算法。先从大到小排序(这是顺序),再将每个人在舒适度最大的地方入圈。
priority_queue搞定。

代码

#include <cstdio>
#include <queue>
#include <algorithm>
#define maxn 200005
using namespace std;

int a[maxn], n;

struct Position
{
	int lf, rf, comfort;
	inline Position(int l, int r)
	{
		lf = l, rf = r;
		comfort = min(l, r);
	}
	inline bool operator<(const Position& p) const
	{
		return comfort < p.comfort;
	}
};

priority_queue<Position> q;

inline bool cmp(int x, int y) {return x > y;}

int main(int argc, char** argv)
{
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d", a + i);
	sort(a, a + n, cmp);
	q.push(Position(a[0], a[1]));
	long long res = a[0];
	for(int i=2; i<n; i++)
	{
		Position p = q.top();
		if(q.size() > 1) q.pop();
		res += p.comfort;
		q.push(Position(a[i], p.lf));
		q.push(Position(a[i], p.rf));
	}
	printf("%lld\n", res);
	return 0;
}

标签:AtCoder,AC,le,输出,int,题解,样例,TLE,173
From: https://www.cnblogs.com/stanleys/p/18403445/abc173

相关文章

  • Panasonic Programming Contest 2020 C (Sqrt Inequality) 题解
    题目大意输入三个整数\(a\),\(b\),\(c\),如果\(\sqrta+\sqrtb<\sqrtc\)成立,输出Yes,否则输出No。样例输入#1239输出#1No\(\sqrt2+\sqrt3<\sqrt9\)不成立。输入#22310输出#2Yes\(\sqrt2+\sqrt3<\sqrt10\)成立。分析错误思路首先,由......
  • AtCoder Beginner Contest 188 A~D 题解
    A-Three-PointShot题目大意有两个球队,分别得到\(X\)分和\(Y\)分,问得分较少的球队能否在获得三分后超越对方。\(0\leX,Y\le100\)\(X\neY\)\(X\)和\(Y\)都是整数。输入格式\(X~Y\)输出格式如果能,输出Yes;否则,输出No。样例XY输出35Yes分析这个不用......
  • AtCoder Beginner Contest 161D 题解
    原题链接:洛谷链接;AtCoder链接思路每次根据上一位,计算下一位为TA-1/TA/TA+1,放入queue中,最后输出第\(K\)次弹出的整数。注意事项不用longlong会WA!上一位为\(0\)时下一位不能为\(-1\)!(要特判)上一位为\(9\)时下一位不能为\(10\)!(也要特判)代码#include<cstdio>#include<que......
  • CodeForces Round #621 ABC (1307A+1307B+1307C) 题解
    A.CowandHaybales题面TheUSAConstructionOperation(USACO)recentlyorderedFarmerJohntoarrangearowofnhaybalepilesonthefarm.The\(i\)-thpilecontains\(a_i\)haybales.However,FarmerJohnhasjustleftforvacation,leavingBessieal......
  • 2024CCPC网络赛题解
    前言开局掉线30min比较搞心态,不过比赛延迟了1个小时,但是后面也一直没过题,如果时间再少点可能排名还更好看。最后是8题前面,这里简单讲一下我有写的题,队友写的题就放一下队友的赛时代码,大家自己看看吧。B队友写的,签到,但是数据范围\(n\)给\(10^3\)给队友整不自信了,因为答案的......
  • 网络设备开局配置生成器(第三次更新) QQ交流群:(4817315)
     网络设备开局配置生成器(SecureCRTvbs脚本)QQ交流群:(4817315)一、工具介绍本工具主要是针对简化网络工程师重复繁琐的工作而开发。工具只是将重复工作通过自己配置生成脚本代码来执行,工具的大致功能可以概括为以下几点:1.可以1分钟生成华为、华三、锐捷等交换机的开......
  • AT_dwacon6th_prelims_c Cookie Distribution 题解
    组合意义保平安。思路发现\(\prod\)的贡献不好统计。我们可以考虑\(\prod\)的组合意义。容易发现:\[\prodc_i=\prod\sum_{j=1}^{c_i}1\]那么依照分配律,我们发现这个东西的组合意义是每个人从获得的饼干中选一个出来的方案。这样就会变好统计很多。设\(dp_{i,j}\)为......
  • CF1534F2 Falling Sand (Hard Version) 题解
    题目链接点击打开链接题目解法做法1一个沙子消失,会带走所有它所在列下面的沙子我们记每列从下往上第\(a_i\)个沙子为关键点,第\(i\)列至少消失\(a_i\)个沙子等价于所有关键点都消失一个显然的事情是:记一列最上面的沙子为起始点,则我们只会干扰起始点第一感觉是找到一......
  • LOJ4218 「IOI2024」尼罗河船运 题解
    题目描述有\(n\)件手工艺品,第\(i\)件重量为\(w_i\),有参数\(a_i\)和\(b_i\)。每艘船最多可以运输两件手工艺品:如果只运输第\(i\)件,重量没有要求,代价为\(a_i\)。如果同时运输第\(i\)和第\(j\)件,要求\(|w_i-w_j|\leD\),代价\(b_i+b_j\)。\(q\)次询问,给......
  • Leetcode第 414 场周赛题解
    Leetcode第414场周赛题解Q1.将日期转换为二进制表示给你一个字符串date,它的格式为yyyy-mm-dd,表示一个公历日期。date可以重写为二进制表示,只需要将年、月、日分别转换为对应的二进制表示(不带前导零)并遵循year-month-day的格式。返回date的二进制表示。解法:STL一......