首页 > 其他分享 >KYOCERA Programming Contest 2021 (AtCoder Beginner Contest 200) A~E 题解

KYOCERA Programming Contest 2021 (AtCoder Beginner Contest 200) A~E 题解

时间:2024-09-08 21:03:13浏览次数:11  
标签:AtCoder le return 200 int 题解 Contest long 输出

A - Century

题目大意

公元\(N\)年在第几个世纪中?

一个世纪是由\(100\)个年份组成的一个区间。如,\(1\)世纪为\([1,100]\)年,\(2\)世纪为\([101,200]\)年,……

\(1\le N\le 3000\)

输入格式

\(N\)

输出格式

将答案输出为一个整数。

样例

\(N\) 输出
\(2021\) \(21\)
\(200\) \(2\)

分析

根据本题条件我们可以推出:公元\(N\)年在世纪\(\lceil \frac N {100}\rceil\)。

代码

#include <cstdio>
using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", n % 100 == 0? n / 100: n / 100 + 1);
	return 0;
}

B - 200th ABC-200

题目大意

对于整数\(N\),执行\(K\)次如下操作:

  • 如果\(N\)是\(200\)的倍数,将\(N\)除以\(200\)。
  • 否则,在\(N\)后面添上\(200\)。(如,\(123\)变为\(123200\))。

\(1\le N\le 10^5\)
\(1\le K\le 20\)

输入格式

\(N~K\)

输出格式

输出最终的\(N\)。

样例

\(N\) \(K\) 输出
\(2021\) \(4\) \(50531\)
\(40000\) \(2\) \(1\)
\(8691\) \(20\) \(84875488281\)

分析

本题我们按照题意模拟即可,但我们需要证明答案不会超过\(2^{63}-1\),这样才能使用long long

  • 任何数\(N\)添上\(200\)都是\(200\)的倍数。证明:一个数只要是\(100\)和\(2\)的公倍数,它就是\(200\)的倍数。\(N\)添上\(200\)后以00结尾,就证明了它是\(200\)的倍数。
  • 这样,\(N\)每次添上\(200\)后都要除以\(200\),相当于去掉两个零再将\(N\)除以\(2\)。
  • 所以,\(N\)每次最多增加一位,还经常减少位数(除以\(200\)),肯定严格小于\(2^{63}\)。

代码

#include <cstdio>
using namespace std;

int main()
{
	long long n;
	int k;
	scanf("%lld%d", &n, &k);
	while(k--)
		n = n % 200LL == 0LL? n / 200LL: n * 1000LL + 200LL;
	printf("%lld\n", n);
	return 0;
}

C - Ringo's Favorite Numbers 2

题目大意

给定序列\(A=(A_1,A_2,\dots,A_N)\),找到符合下列条件的所有\((i,j)\):

  • \(1\le i < j\le N\);
  • \(|A_i-A_j|\)是\(200\)的倍数。

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

输出格式

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

样例

\(A\) 输出
\((123,223,123,523,200,2000)\) \(4\)
\((1,2,3,4,5)\) \(0\)
\((199,100,200,400,300,500,600,200)\) \(9\)

分析

首先,最容易想到的\(\mathcal O(n^2)\)的暴力算法肯定不行,因为\(2\le N\le 2\times 10^5\)。
我们考虑用桶优化:
我们有\(200\)个桶,分别如下:

桶的编号 元素\(1\) 元素\(2\) 元素\(3\) 元素\(4\) …… 元素除以\(200\)的余数
\(0\) \(0\) \(200\) \(400\) \(600\) …… \(0\)
\(1\) \(1\) \(201\) \(401\) \(601\) …… \(1\)
\(2\) \(2\) \(202\) \(402\) \(602\) …… \(2\)
…… …… …… …… …… …… ……
\(198\) \(198\) \(398\) \(598\) \(798\) …… \(198\)
\(199\) \(199\) \(399\) \(599\) \(799\) …… \(199\)
这时,我们发现,每个桶中的每个元素都能与这个同种的其他元素组成一对,所以我们只要在将元素加入桶中前将答案加上桶目前的大小即可。

总时间复杂度\(\mathcal O(n)\)。

代码

我们的桶中不需要真正的元素,只需要记录桶的大小即可。
注意:答案的数据类型一定要用long long

#include <cstdio>
#define MOD 200
using namespace std;

int cnt[MOD];

int main()
{
	int n;
	scanf("%d", &n);
	long long ans = 0LL;
	while(n--)
	{
		int x;
		scanf("%d", &x);
		ans += cnt[x %= MOD] ++;
	}
	printf("%lld\n", ans);
	return 0;
}

D - Happy Birthday! 2

题目大意

给定序列\(A=(A_1,A_2,\dots,A_N)\)。你要从中选出两个子序列\(B\)和\(C\)(下标不同,不要求连续),使得\(\sum B\equiv \sum C\pmod{200}\)。

\(2\le N\le 200\)
\(1\le A_i\le 10^9\)

输入格式

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

输出

如果没有合法的\(B\)和\(C\),输出No
如果有合法的\(B\)和\(C\),按下列格式输出,其中\(x\)为\(B\)的长度、\(y\)为\(C\)的长度,\(B'\)为\(B\)中元素对应的下标,\(C'\)为\(C\)中元素对应的下标:
\(\text{Yes}\)
\(x~B'_1~B'_2~\dots~B'_x\)
\(y~C'_1~C'_2~\dots~C'_y\)

样例

略,请自行前往AtCoder查看

分析

我们可以证明,只要\(N\ge 8\),那么就一定有解。证明如下:

  • \(8\)个元素能组成的子序列有\(2^8-1=255\)种。(每个元素可以选或不选,去掉全不选的情况)
  • 根据抽屉原理,我们将这\(255\)种子序列按照他们除以\(200\)的余数分别放入抽屉中,则至少有两个子序列在一个抽屉中,即必定有合法的\(A\)和\(B\)。

当\(N<8\)时,我们暴力枚举所有可能;
当\(N\ge8\)时,我们暴力枚举其中任意\(8\)个元素组成的所有可能即可找到解。

代码

#include <cstdio>
#include <vector>
#define maxn 10
#define MOD 200
using namespace std;

int a[maxn];
vector<int> bkt[MOD];

inline void print(const vector<int>& v)
{
	printf("%llu", v.size());
	for(int x: v)
		printf(" %d", x + 1);
	putchar('\n');
}

int main()
{
	int n;
	scanf("%d", &n);
	if(n > 8) n = 8;
	for(int i=0; i<n; i++)
		scanf("%d", a + i);
	int lim = 1 << n;
	for(int st=0; st<lim; st++)
	{
		int s = 0;
		vector<int> pos;
		for(int i=0; i<n; i++)
			if(st >> i & 1)
				s = (s + a[i]) % MOD, pos.push_back(i);
		if(!bkt[s].empty())
		{
			puts("Yes");
			print(bkt[s]);
			print(pos);
			return 0;
		}
		else bkt[s] = pos;
	}
	puts("No");
	return 0;
}

E - Patisserie ABC 2

题目大意

有\(N^3\)个三元组\((i,j,k)\)(\(1\le i,j,k\le N\)),按如下排序:

  • \(i+j+k\)小的排在前面。
  • 对于\(i+j+k\)相同的三元组,\(i\)小的排在前面,对于\(i\)相同的,\(j\)小的排在前面。

求第\(K\)个\((i,j,k)\)。

\(1\le N\le 10^6\)
\(1\le K\le N^3\)

输入格式

\(N~K\)

输出格式

输出第\(K\)个\((i,j,k)\),用空格分隔。

样例

\(N\) \(K\) 输出
\(2\) \(5\) \(1~2~2\)
\(1000000\) \(1000000000000000000\) \(1000000~1000000~1000000\)
\(9\) \(47\) \(3~1~4\)

分析

由于每个三元组的和都不会超过\(3N\),所以我们考虑暴力枚举三元组的和,这样就能快速算出第\(K\)个三元组的和。那么,问题来了:符合\(i+j+k=n\)的三元组\((i,j,k)\)(\(i,j,k\)均不超过\(N\))有多少个?
这可以用容斥原理解决。首先,我们发现,上述问题实际上就是在求如下方程解的个数:

\[\begin{cases}i+j+k=n\\1\le i,j,k\le N\end{cases} \]

如果我们将问题改成求如下方程解的个数(注意\(n\)和\(N\)的区别):

\[\begin{cases}i+j+k=n\\1\le i,j,k\le n\end{cases} \]

这个可以用挡板法解决,在\(n-1\)个位置上任选\(2\)个插入挡板,挡板分开的就是\(i,j,k\),则公式为\(C_{n-1}^2\)。我们设\(f(n)=~\)上述方程解的个数(\(C_{n-1}^2=(n-1)(n-2)\)),则总方程解的个数为\(f(n)\)。
我们考虑一个、两个(不可能有三个)数大于\(N\)的情况,这样\(\begin{cases}i+j+k=n\\1\le i,j,k\le N\end{cases}\)这个方程解的个数就为\(f(n)+3f(n-2N)-3f(n-N)\)。

代码

计算\(f(n)\)时注意特判\(n\le 2\)的情况,否则可能会出现负数!

#include <cstdio>
using namespace std;

using LL = long long;
int n;

inline int max(int x, int y) { return x > y? x: y; }
inline int min(int x, int y) { return x < y? x: y; }

inline LL f(LL n) { return n-- > 2? n * (n - 1LL) >> 1LL: 0LL; }
inline LL count(int s) { return f(s) - 3 * (f(s - n) - f(s - (n << 1))); }

int main()
{
	LL k;
	scanf("%d%lld", &n, &k);
	int lim = n * 3;
	for(int sum=3; sum<=lim; sum++)
	{
		LL cnt = count(sum);
		if(k > cnt) { k -= cnt; continue; }
		for(int a=1; a<=n; a++)
		{
			int minb = max(1, sum - a - n), maxb = min(n, sum - a - 1);
			if(minb > maxb) continue;
			int num = maxb - minb + 1;
			if(k <= num)
			{
				int b = minb + k - 1;
				int c = sum - a - b;
				printf("%d %d %d\n", a, b, c);
				return 0;
			}
			k -= num;
		}
	}
	return 0;
}

标签:AtCoder,le,return,200,int,题解,Contest,long,输出
From: https://www.cnblogs.com/stanleys/p/18403475/abc200

相关文章

  • AtCoder Beginner Contest 205 A~E 题解
    A-kcal题目大意我们有一种每\(100\)毫升含有\(A\)千卡热量的饮料。\(B\)毫升的这种饮料含有多少千卡热量?\(0\leA,B\le1000\)输入格式\(A~B\)输出格式输出\(B\)毫升这种饮料包含的的千卡数。最大允许浮点数精度误差\(10^{-6}\)。样例\(A\)\(B\)输出\(45\)......
  • AtCoder Beginner Contest 168 C~D 题解
    这次比赛的题名很特殊,是由符号+(+英文+)组成的......
  • AtCoder Beginner Contest 171 A~D 题解
    A-αlphabet题目大意输入一个英文字母\(a\),判断它是大写还是小写。输入格式\(a\)输出格式如果\(a\)为小写,输出a;如果\(a\)为大写,输出A。样例输入1B样例输出1AB为大写,所以输出A。样例输入2a样例输出2aa为小写,所以输出a。代码#include<cstdio>usingnames......
  • AtCoder Beginner Contest 187 A~D 题解
    A-LargeDigits题目大意给定两个三位整数\(A\)和\(B\),求它们数位和的最大值。数位和:例如,\(123\)的数位和是\(1+2+3=6\)。\(100\leA,B\le999\)输入格式\(A~~B\)输出格式一行,即\(A\)和\(B\)数位和的最大值。样例输入输出12323495939531710099927......
  • AtCoder Beginner Contest 173 A~D 题解
    A-Payment题目大意如果使用价值\(1000\)元的纸币(假设有)支付\(N\)元,服务员会找多少钱?\(1\leN\le10000\)输入格式\(N\)输出格式一行,即服务员找的钱数。样例输入输出190010030000分析特判:如果\(N\)除以\(1000\)能整除,那么不需要找钱,输出\(0\);如果......
  • 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\)给队友整不自信了,因为答案的......