首页 > 其他分享 >AtCoder Beginner Contest 253 A~E 题解

AtCoder Beginner Contest 253 A~E 题解

时间:2024-09-08 21:28:15浏览次数:11  
标签:AtCoder cnt le 输出 int 题解 LL text 253

A - Median?

题目大意

给定正整数\(a,b,c\),判断\(b\)是否为三个数中的中位数(即从小到大排序后是第二个,不是平均数)。
\(1\le a,b,c\le 100\)

输入格式

\(a~b~c\)

输出格式

如果\(b\)是三个数中的中位数,输出Yes;否则,输出No

样例

\(a\) \(b\) \(c\) 输出
\(5\) \(3\) \(2\) Yes
\(2\) \(5\) \(3\) No
\(100\) \(100\) \(100\) No

分析

本来就是A题,其实没什么难的,比赛的时候就是看成平均数WA了..(上面应该讲的够清楚了)

当然可以直接将三个数排序(简单粗暴),也可以判断\(a\le b\le c\)和\(c\le b\le a\)中是否有至少一个成立。

代码

#include <cstdio>
using namespace std;

int main()
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	puts((a <= b && b <= c) || (c <= b && b <= a)? "Yes": "No");
	return 0;
}

B - Distance Between Tokens

题目大意

在\(H\times W\)的网格上,有恰好两个位置上各有一颗棋子,别的都是空位。
你可以从任意一个棋子开始,通过上下左右移动,前往另一个棋子的位置。
求至少要移动多少次?

输入格式

先是一行\(H,W\),用空格隔开,然后有\(H\)行,每行是一个长度为\(W\)的字符串,-表示这个位置是空位,o表示这里有一颗棋子(详见样例)。

输出格式

输出一行,即至少要移动的次数。

样例

样例输入1

2 3
--o
o--

样例输出1

3

样例输入2

5 4
-o--
----
----
----
-o--

样例输出2

4

分析

本题不需要\(\text{BFS}\),由于没有障碍物,直接找到两颗棋子,并输出\(x_\text{diff}+y_\text{diff}\)(即\(x,y\)的坐标差之和)即可。

代码

#include <cstdio>
#include <vector>
using namespace std;

int main()
{
	int h = 0, w = 0, x1 = -1, y1 = -1, x2 = -1, y2 = -1;
	char c;
	while((c = getchar()) != ' ')
		h = (h << 3) + (h << 1) + (c ^ 48);
	while((c = getchar()) != '\n')
		w = (w << 3) + (w << 1) + (c ^ 48);
	for(; h--; getchar())
		for(int i=w; i--; )
			if(getchar() == 'o')
				if(x1 == -1) x1 = h, y1 = i;
				else { x2 = h, y2 = i; break; }
	printf("%d\n", x1 - x2 + (y1 > y2? y1 - y2: y2 - y1));
	return 0;
}

C - Max - Min Query

题目大意

我们有一个序列\(S\),初始为空。
请处理如下\(Q\)个操作:

  • 1 x:将\(x\)插入至\(S\)的末尾。
  • 2 x c:从\(S\)中删除\(c\)个\(x\),如果不够删就直接删完。
  • 3:求\(S\)中最大值与最小值的差。

\(1\le Q\le 2\times 10^5\)
\(0\le x\le 10^9\)
\(1\le c\le Q\)

输入格式

\(Q\)
\(\text{query}_1\)
\(\text{query}_2\)
\(\vdots\)
\(\text{query}_Q\)

输出格式

对于每个操作\(3\),输出\(S\)中最大值与最小值的差。

分析

典型STL练习题

本题可以用multisetmap解决,这里介绍使用map的方法(仅限C++使用)。
C++中,我们需要用到std::map<int, int>的如下方法:

  • mp[x]int& operator[](int&& key)
    返回key对应的value的引用,如果之前没有用到过则创建并返回\(0\)。
    时间复杂度:\(\mathcal O(\log n)\),其中\(n\)为map中元素总数。
  • iterator begin()
    返回最小的元素对应的指针,mp.begin()->first可以获得mp的最小元素
    时间复杂度:\(\mathcal O(1)\)
  • iterator rbegin()
    返回最大的元素对应的指针,mp.rbegin()->first可以获得mp的最大元素
    时间复杂度:\(\mathcal O(1)\)
  • size_type erase(const int& key)
    key以及对应的valuemap中删除,返回删除的元素个数(\(0\)或\(1\)),返回值一般可以忽略。
    时间复杂度:\(\mathcal O(\log n)\),其中\(n\)为map中元素总数。

这时,每个查询都可转换为上述操作,详见代码。

代码

#include <cstdio>
#include <map>
using namespace std;

int main()
{
	int q;
	scanf("%d", &q);
	map<int, int> cnt;
	while(q--)
	{
		int op;
		scanf("%d", &op);
		if(op == 3) printf("%d\n", cnt.rbegin()->first - cnt.begin()->first);
		else if(op == 1)
		{
			int x;
			scanf("%d", &x);
			cnt[x] ++;
		}
		else if(op == 2)
		{
			int x, m;
			scanf("%d%d", &x, &m);
			if(cnt[x] > m) cnt[x] -= m;
			else cnt.erase(x);
		}
	}
	return 0;
}

D - FizzBuzz Sum Hard

题目大意

输出\(1\)到\(N\)之间不是\(A\)或\(B\)的倍数的数之和。

\(1\le N,A,B\le 10^9\)

输入格式

\(N~A~B\)

输出格式

输出答案。

分析

根据容斥原理,\(1\)到\(N\)之间\(A\)或\(B\)的倍数的数之和为:
\((A\)的倍数之和\()+(B\)的倍数之和\()-(\)同时为\(A,B\)的倍数之和\()\)。
又因为同时为\(A,B\)的倍数的数是\([A,B]\)(最小公倍数)的倍数,所以可转化为\((A\)的倍数之和\()-(B\)的倍数之和\()+([A,B]\)的倍数之和\()\)。

再设\(f(N)=1+2+\dots+N,g(x,N)=xf(\lfloor\frac N X\rfloor)=(N\)以内所有\(x\)的倍数之和\()\),
则答案为

\[\text{Ans}=f(N)-g(A)-g(B)+g([A,B]) \]

总时间复杂度为求解\([A,B]\)的复杂度,即\(\mathcal O(\log \max\{A,B\})\)。

代码

这里使用了另一种\(g(x,N)\)的求法,思路类似。

#include <cstdio>
using namespace std;

using LL = long long;
inline LL sum(const LL& x, const LL& n)
{
	LL cnt = n / x;
	return x * cnt * (cnt + 1LL) >> 1LL;
}

int main()
{
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	LL x = b, y = a;
	while(b ^= a ^= b ^= a %= b);
	LL t = x / a * y; // t = lcm(a, b)
	printf("%lld\n", sum(1, n) - sum(x, n) - sum(y, n) + sum(t, n));
	return 0;
}

E - Distance Sequence

题目大意

求符合如下条件的\(A=(A_1,\dots,A_N)\)的个数,对\(998244353\)取模:

  • \(1\le A_i\le M\)(\(1\le i\le N\))
  • \(|A_i-A_{i+1}|\ge K\)(\(1\le i<N\))

\(2\le N\le 1000\)
\(1\le M\le 5000\)
\(0\le K<M\)

输入格式

\(N~M~K\)

输出格式

输出符合条件的序列的个数,对\(998244353\)取模。

分析

很明显是\(\text{DP}\)(动态规划)的思路,仿照01背包的方式,我们设计如下状态:

\[\text{dp}(i,j)=(A_i=j\text{的可能数}) \]

状态转移方程也很简单,即:

\[\text{dp}(i,j)=\sum_{p=1}^{j-k}\text{dp}(i-1,p)+\sum_{p=j+k}^m\text{dp}(i-1,p) \]

那么,如果直接暴力循环计算,整个算法的时间复杂度是\(\mathcal O(NM^2)\),显然不能通过。

但是注意到这里有个求和的操作,显然可以用前缀/后缀和优化,用\(\mathcal O(1)\)的时间复杂度求出两个和,因此时间复杂度降到\(\mathcal O(NM)\),可以通过。

最后一个坑,需要注意特判\(K=0\)的情况,答案为\(M^N\bmod 998244353\)。
本题到此结束。

代码

特判使用快速幂,\(\text{DP}\)建议使用滚动表(又称数组重复利用)技巧,优化后实测:

  • 时间:\(49\mathrm{ms}\to39\mathrm{ms}\)
  • 空间:\(21220\mathrm{kb}\to1664\mathrm{kb}\)
#include <cstdio>
#define maxn 1002
#define maxm 5005
#define MOD 998244353
using namespace std;

using LL = long long;
int qpow(LL a, LL b)
{
	LL ans = 1LL;
	while(b > 0)
	{
		if(b & 1LL) ans = ans * a % MOD;
		a = a * a % MOD, b >>= 1LL;
	}
	return ans;
}

inline void mod(int& x) { if(x >= MOD) x -= MOD; }
int dp[2][maxm];

int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	if(k == 0)
	{
		printf("%d\n", qpow(m, n));
		return 0;
	}
	for(int i=1; i<=m; i++)
		dp[0][i] = 1;
	for(int i=1; i<n; i++)
	{
		int c = i & 1, p = c ^ 1, s = 0;
		for(int j=k+1; j<=m; j++)
			mod(s += dp[p][j]);
		for(int j=1; j<=m; j++)
		{
			if(j > k) mod(s += dp[p][j - k]);
			mod(dp[c][j] = s);
			if(j + k <= m)
			{
				mod(s -= dp[p][j + k]);
				if(s < 0) s += MOD;
			}
		}
	}
	int ans = 0, t = n & 1 ^ 1;
	for(int i=1; i<=m; i++)
		mod(ans += dp[t][i]);
	printf("%d\n", ans);
	return 0;
}

标签:AtCoder,cnt,le,输出,int,题解,LL,text,253
From: https://www.cnblogs.com/stanleys/p/18403502/abc253

相关文章

  • AtCoder Beginner Contest 241 (Sponsored by Panasonic) D~F 题解
    D-SequenceQuery题目大意我们有一个空序列\(A\)。请依次处理\(Q\)个命令,每个命令有三种类型,每种类型的格式如下:1x:将\(x\)加入\(A\)(不去重)2xk:求在\(A\)的\(\lex\)的元素中,第\(k\)大的值。3xk:求在\(A\)的\(\gex\)的元素中,第\(k\)小的值。\(1\leQ\le2\times10^5......
  • AtCoder Beginner Contest 242 C~E 题解
    C-1111galpassword题目大意给定正整数\(N\),求符合下列条件的整数\(X\)的个数,对\(998244353\)取模:\(X\)是\(N\)位的正整数\(X\)的每一位数都在\([1,9]\)之间(0不行);\(X\)的相邻两位数之差的绝对值不超过\(1\)。\(2\leN\le10^6\)输入格式\(N\)输出格式输出答案。样......
  • AtCoder Beginner Contest 245 A~E 题解
    A-Goodmorning题目大意在同一天里,Takahashi在\(A\)时\(B\)分起床,Aoki在\(C\)时\(D\)分\(1\)秒起床,请问谁起床更早?\(0\leA,C<24\)\(0\leB,D<60\)输入格式\(A~B~C~D\)输出格式输出起得更早的人的名字(Takahashi或Aoki)。样例\(A\)\(B\)\(C\)\(D\)输出\(7\)......
  • AtCoder Beginner Contest 244 D~F 题解
    D-SwapHats题目大意有\(3\)个Takahashi,他们帽子的颜色分别为\(S_1,S_2,S_3\)。我们现在想通过正好\(10^{18}\)次操作,使得\(S_i=T_i\)。每次操作如下:选择\((i,j)\),交换\(S_i\)和\(S_j\)。试问能否达成目标?输入格式\(S_1~S_2~S_3\)\(T_1~T_2~T_3\)输出格式如果能达......
  • ARC138 B - 01 Generation 题解
    ARC138B-01Generation思路考虑逆向思维,很容易想到可以优先从后面删掉0(操作B的逆向操作),然后如果前面是0则删掉它并将序列翻转(操作A的逆向操作),一直重复这两个步骤直到字符串为空。如果中途无法操作,输出No,否则输出Yes。下面我们来证明这个方法的正确性:首先,假设有一个序列\(A......
  • AtCoder题解集锦
    注:本文原发表于CSDN,现已停止更新。原文如下:AtCoder题解集锦自己从全网整理的一些优质AtCoder题解,目前只有ABC(AtCoderBeginnerContest)的C~F。不定期更新。如您有更多需求,欢迎私信我或在评论区留言!\(\rarr\)题解列表传送门用法表格查找找到对应比赛的行找到对应......
  • AtCoder Beginner Contest 250 C~E 题解
    C-AdjacentSwaps题目大意\(N\)个球从左到右排成一列。开始时,从左往右的第\(i\)个球上写着数字\(i\)。请执行\(Q\)个操作,第\(i\)个操作如下:令\(j=~N\)个球中写着数字\(x_i\)的球的位置如果\(j=N\),将其与第\(j-1\)个球交换;否则,与第\(j+1\)个球交换。求所有操作后的球上分......
  • UNIQUE VISION Programming Contest 2022(AtCoder Beginner Contest 248)C~D 题解
    C-DiceSum题目大意有多少个整数序列\(A=(A_1,\dots,A_N)\)符合如下条件:\(1\leA_i\leM\)\(\sum\limits_{i=1}^NA_i\leK\)输出答案,对\(998244353\)取模。\(1\leN,M\le50\)\(N\leK\leNM\)输入格式\(N~M~K\)输出格式输出答案,对\(998244353\)取模。分析艹C题......
  • AtCoder Beginner Contest 252 A~G 题解
    前言这是我第一次写7题(A~G)的ABC题解,若有写得不好或者不到位的地方请多多指教,我将万分感激,感谢大家的支持!A-ASCIIcode题目大意给定正整数\(N\),输出ASCII码是\(N\)的字母。\(97\leN\le122\)输入格式\(N\)输出格式输出ASCII码是\(N\)的字母。分析注意a对应\(97\)......
  • AtCoder Beginner Contest 192 A~D 题解
    A-Star题目大意下一个大于\(X\)的\(100\)的倍数与\(X\)的差是多少?\(1\leX\le10^5\)输入格式\(X\)输出格式输出答案。样例\(X\)输出\(140\)\(60\)\(1000\)\(100\)分析下一个大于\(X\)的\(100\)的倍数是\((\lfloorX/100\rfloor+1)\times100\)。所......