首页 > 其他分享 >AtCoder Beginner Contest 203 (Sponsored by Panasonic) A~E 题解

AtCoder Beginner Contest 203 (Sponsored by Panasonic) A~E 题解

时间：2024-09-08 21:03:51浏览次数：10  
标签：AtCoder 203 le limits 输出 int 题解 sum 样例

A - Chinchirorin

题目大意

给定三个整数\(a,b,c\)，如果它们中有两个相等，输出另一个；否则，输出\(0\)。

\(1\le a,b,c\le 6\)

输入格式

\(a~b~c\)

输出格式

如果\(a,b,c\)中有两个相等，输出另一个；否则，输出\(0\)。

样例

\(a\) \(b\) \(c\) 输出
\(2\) \(5\) \(2\) \(5\)
\(4\) \(5\) \(6\) \(0\)
\(1\) \(1\) \(1\) \(1\)

分析

\(A\)题还是一如既往的水……直接暴力判断三种相等的情况即可。

代码

#include <cstdio>
using namespace std;

int main()
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	if(a == b) printf("%d\n", c);
	else if(b == c) printf("%d\n", a);
	else if(a == c) printf("%d\n", b);
	else puts("0");
	return 0;
}

B - AtCoder Condominium

题目大意

给定\(N\)和\(K\)，求\(\sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j}\)。
\(1\le N,K\le 9\)

输入格式

\(N~K\)

输出格式

输出\(\sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j}\)。

样例

\(N\) \(K\) 输出
\(1\) \(2\) \(203\)
\(3\) \(3\) \(1818\)

分析

本题可以直接暴力，但我使用的是如下\(\mathcal O(1)\)算法：
根据\(\overline{i0j}=100i+j\)且\(1+2+\dots+N=\frac{N(N+1)}2\)，则有如下推导：

  • \(\sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j}=\sum\limits_{i=1}^N\sum\limits_{j=1}^K 100i+\sum\limits_{i=1}^N\sum\limits_{j=1}^K j\)
  • \(\sum\limits_{i=1}^N\sum\limits_{j=1}^K 100i=\sum\limits_{i=1}^N 100iK=100K\sum\limits_{i=1}^N i=\frac{100N(N+1)K}2\)
  • \(\sum\limits_{i=1}^N\sum\limits_{j=1}^K j=\sum\limits_{i=1}^N\frac{K(K+1)}2=\frac{K(K+1)N}2\)
  • \(\sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j}=\frac{100N(N+1)K}2+\frac{K(K+1)N}2=\frac{100N(N+1)K+K(K+1)N}2\)

这样，我们就可以直接通过公式\(\frac{100N(N+1)K+K(K+1)N}2\)计算出结果了。

代码

#include <cstdio>
using namespace std;

inline int sum(int x) { return x * (x + 1) >> 1; }

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	printf("%d\n", sum(n) * k * 100 + sum(k) * n);
	return 0;
}

C - Friends and Travel costs

题目大意

有\(10^{100}+1\)个村庄，分别为村庄\(0,1,\dots,10^{100}\)，相邻两个村庄之间的过路费是\(1\)元。
Taro一开始有\(K\)元且在村庄\(0\)。他想要到达编号尽可能大的村庄。
他有\(N\)个朋友。第\(i\)个朋友会在Taro到达村庄\(A_i\)时给他\(B_i\)元。
求Taro最后到达的村庄的编号。

\(1\le N\le 2\times10^5\)
\(1\le K\le 10^9\)
\(1\le A_i\le 10^{18}\)
\(1\le B_i\le 10^9\)

输入格式

\(N~K\)
\(A_1~B_1\)
\(A_2~B_2\)
\(\dots\)
\(A_N~B_N\)

输出

输出Taro最后到达的村庄的编号。

样例

样例输入1

2 3
2 1
5 10

样例输出1

4

样例输入2

5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000

样例输出2

6000000000

请不要使用\(32\)位整数。

样例输入3

3 2
5 5
2 1
2 2

样例输出3

10

Taro在一个村庄可能有多个朋友。

分析

根据题目中的数据范围，我们可以证明答案严格小于\(2^{64}\)，所以我们使用unsigned long long作为存储数据类型。
可是，由于村庄数量还是太多，我们仍然无法依次模拟到达每个村庄。
我们发现\(N\)较小，所以我们可以从朋友的角度考虑。
我们可以按\(A_i\)排序所有朋友（\(B_i\)的顺序不重要），这样就能把整个行程形成分成若干个区间，并依次判断每个区间是否能走完即可。

代码

注意：我这里排序使用的是优先队列（priority_queue）。

#include <cstdio>
#include <queue>
#define maxn 200005
#define INF 18446744073709551615ULL
using namespace std;

using ULL = unsigned long long;
using pll = pair<ULL, ULL>;

int main()
{
	int n;
	ULL k;
	scanf("%d%llu", &n, &k);
	priority_queue<pll, vector<pll>, greater<pll> > q;
	for(int i=0; i<n; i++)
	{
		ULL a, b;
		scanf("%llu%llu", &a, &b);
		q.emplace(a, b);
	}
	ULL lastv = 0ULL;
	q.emplace(INF, 0ULL);
	while(!q.empty())
	{
		auto [a, b] = q.top(); q.pop();
		ULL cost = a - lastv;
		if(k < cost)
		{
			printf("%llu\n", lastv + k);
			return 0;
		}
		k -= cost;
		lastv = a, k += b;
	}
	return 0;
}

D - Pond

题目大意

给定一个\(N\times N\)的正方形矩阵\(A\)，第\(i\)行第\(j\)列的元素是\(A_{i,j}\)。
求\(A\)中所有的\(K\times K\)的子矩阵的中间值的最小值。
一个\(K\times K\)的正方形的中间值为其中第\((\left\lfloor\frac{K^2}2\right\rfloor+1)\)大的值。

\(1\le K\le N\le 800\)
\(1\le A_{i,j}\le 10^9\)

如果不能理解题意，请看下图：

对应的输入输出：

3 2
5 9 8
2 1 3
7 4 6

/

2

输入格式

\(N~K\)
\(A_{1,1}~A_{1,2}~\dots~A_{1,N}\)
\(A_{2,1}~A_{2,2}~\dots~A_{2,N}\)
\(A_{N,1}~A_{N,2}~\dots~A_{N,N}\)

输出格式

输出答案。

样例

样例输入1

3 2
1 7 0
5 8 11
10 4 2

样例输出1

4

\[N=3~~~~~K=2\\ A=\begin{bmatrix} 1 & 7 & 0\\ 5 & 8 & 11\\ 10 & 4 & 2 \end{bmatrix}\]

我们有四个\(2\times2\)的正方形：\(\{8, 7, 5, 1\}, ~\{11,8,7,0\},~ \{10,8,5,4\}, ~\{11,8,4,2\}\)。
我们依次从每个的元素中取第\(\left\lfloor\frac{K^2}2\right\rfloor+1=3\)大的：\(\{5,7,5,4\}\)
最后，我们从\(\{5,7,5,4\}\)中选出最小的：\(4\)。

样例输入2

3 3
1 2 3
4 5 6
7 8 9

样例输出2

5

分析

本题可以二分答案。我们判定一个数是否为一个\(K\times K\)的正方形的中间值时，只需要计算这个正方形内严格大于这个数的数的个数是否为\(\left\lfloor\frac{K^2}2\right\rfloor\)即可。
因此，我们可以使用矩阵前缀和快速计算一个正方形内严格大于一个数的数的数的个数。
总时间复杂度\(\mathcal O(n^2\log\max\{A\})\)。

代码

#include <cstdio>
#define maxn 805
#define INF 2147483647
using namespace std;

int a[maxn][maxn], dp[maxn][maxn], n, k, target;

inline int count(int x1, int y1, int x2, int y2)
{
	return dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
}

inline bool check(int x)
{
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (a[i][j] > x);
	for(int x2=k; x2<=n; x2++)
		for(int y2=k; y2<=n; y2++)
		{
			int x1 = x2 - k + 1, y1 = y2 - k + 1;
			if(count(x1, y1, x2, y2) < target)
				return true;
		}
	return false;
}

int main()
{
	scanf("%d%d", &n, &k);
	target = (k * k >> 1) + 1;
	int l = INF, r = 0, ans = 0;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
		{
			scanf("%d", a[i] + j);
			if(a[i][j] > r) r = a[i][j];
			if(a[i][j] < l) l = a[i][j];
		}
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", ans);
	return 0;
}

E - White Pawn

题目大意

有一个\((2N+1)\times(2N+1)\)的正方形棋盘，行数、列数下标都依次从\(0\)到\(2N\)。我们用\((i,j)\)表示棋盘上\(i\)行\(j\)列的位置。
我们有一颗棋子，初始位置在\((0,N)\)。棋盘上有\(M\)个黑方格，第\(i\)个的位置在\((X_i,Y_i)\)，其余都是白方格。
当棋子在\((i,j)\)时，你可以执行任意下列操作，但不能移出棋盘：

  • \((i+1,j)\)是白色时，移到\((i+1,j)\)；
  • \((i+1,j-1)\)是黑色时，移到\((i+1,j-1)\)。
  • \((i+1,j+1)\)是黑色是，移到\((i+1,j+1)\)。

棋盘上的方格不能移动。求棋盘的最后一行的能到达的列的个数。

\(1\le N\le 10^9\)
\(0\le M\le 2\times 10^5\)
\(1\le X_i\le 2N\)
\(0\le Y_i\le 2N\)
\((X_i,Y_i)\)互不相等。

输入格式

\(N~M\)
\(X_1~Y_1\)
\(X_2~Y_2\)
\(\vdots\)
\(X_M~Y_M\)

输出格式

输出棋盘的最后一行的能到达的列的个数。

样例

样例输入1

2 4
1 1
1 2
2 0
4 2

样例输出1

3

我们可以将棋子移动到\((4,0)\)、\((4,1)\)和\((4,2)\)，如下：

  • \((0,2)\to(1,1)\to(2,1)\to(3,1)\to(4,2)\)
  • \((0,2)\to(1,1)\to(2,1)\to(3,1)\to(4,1)\)
  • \((0,2)\to(1,1)\to(2,0)\to(3,0)\to(4,0)\)

我们不能移动到\((4,3)\)或\((4,4)\)，所以输出\(3\)。

样例输入2

1 1
1 1

样例输出2

0

我们无法移动棋子。

分析

我们发现，当\(N\)较大时，大多数行多是空着的，所以我们从每个\(X_i\)开始考虑。对于白色的位置\((i,j)\)，如果不能到达\((i-1,j)\)，则不能到达\((i,j)\)。相反，对于黑色的\((i,j)\)，如果能到达\((i-1,j-1)\)或\((i-1,j+1)\)，则能到达\((i,j)\)。
因此，我们先排序每个\((X_i,Y_i)\)，再对于每个有黑色的行，用set维护能到达的列数，再按上述方法判断即可。

代码

#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#pragma GCC optimize("Ofast")
using namespace std;

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	vector<pair<int, int> > black;
	black.reserve(m);
	while(m--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		black.emplace_back(x, y);
	}
	m = black.size();
	sort(black.begin(), black.end());
	set<int> cols;
	cols.insert(n);
	for(int l=0, r=0; l<m; l=r)
	{
		while(r < m && black[r].first == black[l].first) r ++;
		vector<int> rem, add;
		for(int i=l; i<r; i++)
		{
			int y = black[i].second;
			bool ok = cols.count(y - 1) || cols.count(y + 1);
			if(cols.count(y))
			{
				if(!ok)
					rem.push_back(y);
			}
			else if(ok)
				add.push_back(y);
		}
		for(int y: rem) cols.erase(y);
		for(int y: add) cols.insert(y);
	}
	printf("%llu\n", cols.size());
	return 0;
}

标签：AtCoder,203,le,limits,输出,int,题解,sum,样例
From： https://www.cnblogs.com/stanleys/p/18403469/abc203

相关文章

  • AtCoder Beginner Contest 199 (Sponsored by Panasonic) A~E 题解
    A-SquareInequality题目大意给定三个整数\(A,B,C\)。判断\(A^2+B^2<C^2\)是否成立。\(0\leA,B,C\le1000\)输入格式\(A~B~C\)输出格式如果\(A^2+B^2<C^2\)，输出Yes；否则，输出No。样例\(A\)\(B\)\(C\)输出\(2\)\(2\)\(4\)Yes\(10\)\(10\)\(10\)N......
  • KYOCERA Programming Contest 2021 (AtCoder Beginner Contest 200) A~E 题解
    A-Century题目大意公元\(N\)年在第几个世纪中？一个世纪是由\(100\)个年份组成的一个区间。如，\(1\)世纪为\([1,100]\)年，\(2\)世纪为\([101,200]\)年，……\(1\leN\le3000\)输入格式\(N\)输出格式将答案输出为一个整数。样例\(N\)输出\(2021\)\(21\)\(200......
  • 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......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99