首页 > 其他分享 >「解题报告」Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311）

「解题报告」Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311）

时间：2023-07-23 22:12:59浏览次数：45  
标签：AtCoder ch Beginner Contest int long read while include

比赛地址：Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311） - AtCoder

后记：大家都太强了%%%，如果我做不出第四题就要掉分了。。。

A - First ABC

A - First ABC (atcoder.jp)

找到第一个 \(\texttt{A, B, C}\) 三种字符都出现的位置。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 110;

int n, fga, fgb, fgc;
char s[N];

int main() {
	n = read<int>();
	scanf("%s", s + 1);
	for (int i = 1; i <= n; ++ i) {
		if (s[i] == 'A')	fga = 1;
		if (s[i] == 'B')	fgb = 1;
		if (s[i] == 'C')	fgc = 1;
		if (fga && fgb && fgc) {
			cout << i << '\n';
			break ;
		}
	}
	return 0;
}

B - Vacation Together

B - Vacation Together (atcoder.jp)

找到最长的连续的区间，使得区间里全为 \(\texttt{o}\)。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 110;

int n, d, ans, mx;
char s[N][N];

int main() {
	n = read<int>(), d = read<int>();
	for (int i = 1; i <= n; ++ i) {
		scanf("%s", s[i] + 1);
	}
	for (int i = 1; i <= d; ++ i) {
		int fg = 1;
		for (int j = 1; j <= n; ++ j) {
			if (s[j][i] == 'x') {
				fg = 0;
				break ;
			}
		}
		if (fg == 0) {
			mx = max(mx, ans);
			ans = 0;
		}
		ans += fg;
	}
	cout << max(mx, ans) << '\n';
	return 0;
}

C - Find it!

C - Find it! (atcoder.jp)

一个找环问题，拓扑排序 + dfs 即可。

这个蒟蒻因为忘记统计入度而罚了两罚。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 2e5 + 5;

int n;
int in[N];
vector<int> e[N], ans;
queue<int> q;
bitset<N> vis;

void print() {
	cout << ans.size() << '\n';
	for (int v : ans) {
		cout << v << ' ';
	}
}

void dfs(int u) {
	if (vis[u]) {
		print();
		exit(0);
	}
	ans.emplace_back(u);
	vis.set(u);
	for (int v : e[u]) {
		dfs(v);
	}
	ans.pop_back();
	vis.reset(u);
}

int main() {
	n = read<int>();
	for (int i = 1, x; i <= n; ++ i) {
		e[i].emplace_back(x = read<int>());
		++ in[x]; // 就是这里！
	}
	for (int i = 1; i <= n; ++ i) {
		if (!in[i]) {
			q.emplace(i);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int v : e[u]) {
			-- in[v];
			if (!in[v]) {
				q.emplace(v);
			}
		}
	}
	for (int i = 1; i <= n; ++ i) {
		if (in[i]) {
			dfs(i);
			break ;
		}
	}
	return 0;
}

D - Grid Ice Floor

D - Grid Ice Floor (atcoder.jp)

一道考验搜索能力的题，我用的广搜，存储下每个节点的方向，防止重复。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 210;
const int dx[5] = {0, 0, 1, 0, -1};
const int dy[5] = {0, 1, 0, -1, 0};

int n, m;
char s[N][N];
bool vis[N][N][5], ok[N][N];

struct node {
	int x, y, dir;
};

void bfs() {
	queue<node> q;
	q.push(node{2, 2, 0});
	while (!q.empty()) {
		node fr = q.front();
		q.pop();
		int x = fr.x, y = fr.y, dir = fr.dir;
		if (vis[x][y][dir])	continue ;
		ok[x][y] = 1;
		vis[x][y][dir] = 1;
		if (dir == 0) {
			for (int i = 1; i <= 4; ++ i) {
				int xx = x + dx[i], yy = y + dy[i];
				if (xx >= 1 && yy >= 1 && xx <= n && yy <= m && s[xx][yy] == '.') {
					q.push(node{xx, yy, i});
				}
			}
			continue ;
		}
		if (x + dx[dir] >= 1 && y + dy[dir] >= 1 && x + dx[dir] <= n && y + dy[dir] <= m) {
			if (s[x + dx[dir]][y + dy[dir]] == '.') {
				q.push(node{x + dx[dir], y + dy[dir], dir});
			}
			else {
				q.push(node{x, y, 0});
			}
		}
	}
}

int main() {
	n = read<int>(), m = read<int>();
	for (int i = 1; i <= n; ++ i) {
		scanf("%s", s[i] + 1);
	}
	bfs();
	int ans = 0;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			if (ok[i][j]) {
				++ ans;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

E - Defect-free Squares

E - Defect-free Squares (atcoder.jp)

用 DP 来解决问题。

设 \(dp\left( i, j\right)\) 代表右下角为 \(\left( i, j \right)\) 的无孔正方形的最大边 \(n\)，如果不存在这样的正方形，则为 \(0\)。

设答案为 \(ans\)，则

\[ans = \sum_{i = 1}^{h} \sum_{j = 1}^{w} dp \left( i, j \right) \]

证明，如果 \(dp \left(i, j \right) = k\)，那么一定存在右下角为 \(\left(i, j \right)\) 的长度为 \(1, 2 \dots k\) 的正方形是无孔正方形。

递推式：

\[dp \left(i, j \right ) = \begin{cases} \min \{dp(i - 1, j), dp(i,j - 1), dp(i - 1, j - 1) \} + 1 & s(i, j) = \texttt{o}\\ 0 & s(i, j) = \texttt{x} \end{cases} \]

小小的说明：

大小为 \(n\) 的正方形区域，其右下角正方形为 \((i，j)\)，是无孔的。

大小为 \((n−1)\) 的正方形区域，其右下角为 \((i，j−1)\)，是无孔的。

大小为 \((n−1)\) 的正方形区域，其右下角为 \((i−1，j)\)，是无孔的。

大小为 \((n−1)\) 的正方形区域，其右下角为 \((i−1，j)\)，是无孔的。

\((i，j)\)没有孔。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 3010;

int h, w, n;
ll dp[N][N];
bool hole[N][N];

int main() {
	h = read<int>(), w = read<int>(), n = read<int>();
	for (int i = 1, a, b; i <= n; ++ i) {
		a = read<int>(), b = read<int>();
		hole[a][b] = 1;
	}
	ll ans = 0;
	for (int i = 1; i <= h; ++ i) {
		for (int j = 1; j <= w; ++ j) {
			if (hole[i][j])	continue ;
			dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
			ans += dp[i][j];
		}
	}
	cout << ans << '\n';
	return 0;
}

还有一位大佬的暴力写法也过了，纯暴力是 \(n^3\) 的，这位大佬优化了枚举边的复杂度，使得他的代码跑过去了，下面展示一下。

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> H >> W;
	vector<vector<int>>sum(H + 1, vector<int>(W + 1));
	cin >> N;
	for (int i = 0; i < N; i++) {
		int y, x;
		cin >> y >> x;
		sum[y][x]++;
	}
	for (int i = 0; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			sum[i][j] += sum[i][j - 1];
		}
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 0; j <= W; j++) {
			sum[i][j] += sum[i - 1][j];
		}
	}
	long long ans = 0;
	for (int i = 0; i < H; i++) {
		int bef = 0;
		for (int j = 0; j < W; j++) {
			int ok = bef - 1;
			for (int k = max(0, bef - 1); i + k <= H && j + k <= W; k++) {
				int num = sum[i + k][j + k] - sum[i][j + k] - sum[i + k][j] + sum[i][j];
				if (num == 0) {
					ok = k;
				} else {
					break;
				}
			}
			ans += ok;
			bef = ok;
		}
	}
	cout << ans << endl;
}

F - Yet Another Grid Task

F - Yet Another Grid Task (atcoder.jp)

一个 \(n \times m\) 的网格，每个格子是黑色的或白色的，一个网格被认为是漂亮的，当且仅当 \((i, j)\) 为黑色时，\((i + 1, j)\) 和 \((i + 1, j + 1)\) 也是黑色的，问有多少种方法使得这个网格变成漂亮的（可以把白色染成黑色），对方案数模上 \(998244353\)。

实在是看不懂了，尽我所能了，下面是一份 AC 代码，但不是我写的，也不是题解的做法，有理解的可以在评论区评论。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 2010;
const int mod = 998244353;

int n, m;
int h[N];
ll g[N][N], f[N][N];
char s[N][N];

int main() {
	n = read<int>(), m = read<int>();
	for (int i = 1; i <= n; ++ i) {
		scanf("%s", s[i] + 1);
	}
	for (int j = 1; j <= m; ++ j) {
		h[j] = n + 1;
		for (int i = 1; i <= n; ++ i) {
			if (s[i][j] == '#') {
				h[j] = i;
				break ;
			}
		}
	}
	f[0][n + 1] = 1;
	for (int i = 0; i <= n + 1; ++ i) {
		g[0][i] = 1;
	}
	for (int i = 1; i <= m; ++ i) {
		for (int j = 1; j <= h[i]; ++ j) {
			f[i][j] = g[i - 1][j - 1];
		}
		for (int j = n + 1; ~j; -- j) {
			g[i][j] = (g[i][j + 1] + f[i][j]) % mod;
		}
	}
	cout << g[m][1] << '\n';
	return 0;
}

标签：AtCoder,ch,Beginner,Contest,int,long,read,while,include
From： https://www.cnblogs.com/yifan0305/p/17576033.html

相关文章

  • Atcoder ARC058B Iroha and a Grid
    考虑从第\(b\)列与第\(b+1\)之间分开这个矩阵，钦定\((i,b)\)下一步必须走到\((i,b+1)\)，可以发现这样是不会漏算或算重的。于是就可以用乘法原理算出这个\(i\)的贡献：\(\binom{(i-1)+(b-1)}{i-1}\times\binom{(n-i)+(m-b-1)}{n-i}\)，左半部分的就......
  • The 2023 Guangdong Provincial Collegiate Programming Contest(2023广东省赛)
    链接：https://codeforces.com/gym/104369A.ProgrammingContestC++Code#include"bits/stdc++.h"usingnamespacestd;usingi64=longlong;voidsolve(){inty1,y2;cin>>y1;intn;cin>>n;vector<int>......
  • 练习记录-AtCoder Beginner Contest 311-(A-E)
    写的还挺顺的F之后补A-FirstABC找abc三个字母什么时候出现了一次输出即可B-VacationTogether题意：最长的几个人一排里面均有时间#include<bits/stdc++.h>#defineclosestd::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)usingnamespacestd;typedeflon......
  • Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311）——D
    https://atcoder.jp/contests/abc311/tasks/abc311_d思路题目说如果当前方向的下一个点能走，那么就一直走，否则才能转向。根据题意模拟即可，这道题的难点在于，碰到已经走过的点到底要不要走。如果当前方向走到底，其中的点之前全部都走过那么就不能再走了。我们用bfs模拟，对于能一直走......
  • AtCoder Beginner Contest 311 A-E题解
    A-FirstABC题意给一个长度为N的仅由ABC三个字符组成的字符串S，问S中ABC三个字符第一次出现的位置的最大值。题解使用map<char,bool>判重，记录当前不同的字符串的个数cnt，当cnt等于3时，输出此时的下标+1作为答案。Code#include<bits/stdc++.h>usingnamespacestd;usingll......
  • AtCoder Beginner Contest 311
    A-FirstABC(abc311A)题目大意给定一个字符串，问最短的一个前缀，包含ABC这三个字符。解题思路注意到这个前缀的末尾字母一定是这三个字母中的一个，因此答案就是这三个字母出现位置最早的最大值。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=lo......
  • 2023.07.21 SMU Summer 2023 Contest Round 5
    2023.07.21SMUSummer2023ContestRound5A.PointsinSegments给n个，1～m的子集，求1～n中所有没在这些子集中出现过的数字把子集区间合并为集合s，输出1～n中没有在s中出现过的数#include"bits/stdc++.h"usingnamespacestd;typedefpair<int,int>PII;intn,m;vector<P......
  • Atcoder Regular Contest 154 E - Reverse and Inversion
    只要你发现是诈骗题就好办了。不要像我那样傻傻地瞪一个小时然后才发现那俩sigma里的东西相减是有性质的。先考虑计算单个\(f(p)\)，一眼的树状数组……吗？考虑最终答案式子里\(i\)的系数：\(\sum\limits_{j<i}[p_j>p_i]-\sum\limits_{j>i}[p_j<p_i]\)，因为\(\sum\limits_{j<i}[p......
  • SMU Summer 2023 Contest Round 5
    SMUSummer2023ContestRound5A.PointsinSegments\(\mathcal{O}(n\timesm)\)做法数据范围小,直接把每次的\(l-r\)跑一遍标记一下,最后跑一遍循环统计哪些没有被标记的并且输出就好了#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signed......
  • Atcoder Regular Contest 124 E - Pass to Next
    首先第一步是一个浅显的观察：我们要求的是所有可能的最终序列的贡献之和，如果能改为计算所有操作序列的贡献之和那问题会简单很多，并且我们惊奇地发现，如果一组\(x_i\)全大于\(0\)，那么把它们全减去\(1\)以后得到的答案序列不会改变，而对于任意一种可能的最终序列，必然存在一组\(\m......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99