Atcoder

Beginner Contest 276

No.	Task Name	Solution
A	Rightmost	模拟
B	Adjacency List	模拟
C	Previous Permutation	模拟+思维
D	Divide by 2 or 3	模拟+数学
E	Round Trip	bfs+优化
F (待完成)	Double Chance	数学
G (待完成)	Count Sequences	数学

A – Rightmost

题目大意

给你一个字符串，让你找到在最右边的
a
，如果没有就输出
-1

解法分析

模拟。

先设答案为
-1

然后去找最右边的
a

AC Code#1

# include <bits/stdc++.h>
# define RI register int
# define REP(i, n, m) for (RI i = (n);i <= (m);i++)
# define rep(i, n) REP(i, 1, n)
using namespace std;

char s[205]; 

int main(){
	scanf("%s", s+1);
	int n = strlen(s+1), ans = -1;
	rep(i, n) if (s[i] == 'a') ans = i;
	cout << ans;
	return 0;
}

B – Adjacency List

题目大意

给你一张无向图，让你升序输出每个节点所连的点。

解法分析

AC Code#1

# include <bits/stdc++.h>
# define mod 998244353
//# define mod 1000000007
# define inf 1000000000
# define pb push_back
# define RI register int
# define REP(i, n, m) for (RI i = (n);i <= (m);i++)
# define rep(i, n) REP(i, 1, n)
using namespace std;

int n, m;

vector <int> g[200005];

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= m;i++){
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].pb(v);
		g[v].pb(u);
	}
	for (int i = 1;i <= n;i++){
		printf("%d ", g[i].size());
		sort (g[i].begin(), g[i].end());
		for (int j = 0;j < g[i].size();j++) printf("%d ", g[i][j]); puts("");
	}
	return 0;
}

C – Previous Permutation

题目大意

有一个 1 到 n 的排序，问它的上一个全排列是什么

解法分析

这题很像

这题

，观察数据可以发现直接枚举是不行的，经过思考可以发现只要把后面的顺序改一下就可以了，具体看代码。

AC Code#1

# include <bits/stdc++.h>
# define REP(i, n, m) for (RI i = (n);i <= (m);i++)
# define rep(i, n) REP(i, 1, n)
using namespace std;

int n, arr[105];

bool cmp(int a, int b){
	return a > b;
}

int main(){
	scanf("%d", &n);
	for (int i = 1;i <= n;i++) scanf("%d", &arr[i]);
	arr[n+1] = inf;
	int ind = 0;
	for (int i = n;i >= 1;i--) if (arr[i] < arr[i-1]){
		ind = i-1; break;
	}
	int nxt = ind, num = -1;
	for (int i = ind;i <= n;i++){
		if (arr[i] < arr[ind] && arr[i] > num)  num = arr[i], nxt = i; 
	}
	swap(arr[ind], arr[nxt]);
	sort (arr+ind+1, arr+n+1, cmp);
	rep(i, n) printf("%d ", arr[i]);
	return 0;
}

D – Divide by 2 or 3

题目大意

有一个长度为
n
的数组，对于每个数

a_i

$a_{i}$

，你可以把它变成

\frac{a_i}{2}

$\frac{a _{i}}{2}$

或

\frac{a_i}{3}

$\frac{a _{i}}{3}$

，问最后可以把 a 所有的数变成同一个数吗，如果可以就输出最小操作次数。

解法分析

可以先把每个数变成与
2
和
3
互质的数，判断是否相同。

然后找最大公约数。

AC Code#1

# include <bits/stdc++.h>
//# include "windows.h"
# define ll long long
//# define int ll
# define db double
# define mod 998244353
//# define mod 1000000007
# define inf 1000000000
# define INF 1000000000000000000
# define fi first
# define se second
# define pb push_back
# define RI register int
# define vi vector <int>
# define REP(i, n, m) for (RI i = (n);i <= (m);i++)
# define rep(i, n) REP(i, 1, n)
# define foreach(i, c) for (__typeof__((c).end()) i = (c).begin();i != (c).end();i++)
# define pi acos(-1)
# define pii pair <int, int>
using namespace std;
int dx[15] = {0, 0, 1, -1, -1, -1, 1, 1};
int dy[15] = {1, -1, 0, 0, -1, 1, -1, 1};

int n, arr[1005], f[1005][5], ans = 0;

// f_{i,2} : 第 i 个数字有多少个 2
// f_{i,3} : 同上

int main(){
	scanf("%d", &n);
	rep(i, n){
		scanf("%d", &arr[i]);
		while (arr[i] % 2 == 0) arr[i] /= 2, f[i][2]++, ans++;
		while (arr[i] % 3 == 0) arr[i] /= 3, f[i][3]++, ans++;
	}
	rep(i, n) if (arr[i] != arr[1]){
		puts("-1");
		return 0;
	}
	int num1 = f[1][2], num2 = f[1][3];
	rep(i, n) num1 = min(num1, f[i][2]), num2 = min(num2, f[i][3]);
	printf("%d", ans-num1*n-num2*n);
	// 每一个数都要减一遍
	return 0;
}

/*
5
3 6 9 6 6
*/

E – Round Trip

题目大意

有一个

n \times m

$n \times m$

的矩阵，其中有

.
：代表空地
#
：代表障碍物
S
：代表起点

问能不能从起点经过空地走回到起点，其中每个起点只能走一遍。

解法分析

观察数据发现矩阵大小只有

10^6

$1 0^{6}$

，考虑
bfs
，但是可能会出现

1 \times 10^6

$1 \times 1 0^{6}$

的神奇数据，所以对于每一个点

i,j

$i, j$

，可以把它存到

−

)

(i-1) \times m + j

$(i - 1) \times m + j$

的位置，接着就是
bfs
模板。

AC Code#1

# pragma GCC optimize(2)
# include <bits/stdc++.h>
//# include "windows.h"
# define ll long long
//# define int ll
# define db double
# define mod 998244353
//# define mod 1000000007
# define inf 1000000000
# define INF 1000000000000000000
# define fi first
# define se second
# define pb push_back
# define RI register int
# define vi vector <int>
# define REP(i, n, m) for (RI i = (n);i <= (m);i++)
# define rep(i, n) REP(i, 1, n)
# define foreach(i, c) for (__typeof__((c).end()) i = (c).begin();i != (c).end();i++)
# define pi acos(-1)
# define pii pair <int, int>
using namespace std;
int dx[15] = {0, 0, 1, -1, -1, -1, 1, 1};
int dy[15] = {1, -1, 0, 0, -1, 1, -1, 1};

char s[1000005], col[1000005], cnt = 0, vis[1000005];

int n, m;

int main(){
	scanf("%d%d", &n, &m);
	int sx, sy;
	for (int i = 1;i <= n;i++){
		getchar(); 
		for (int j = 1;j <= m;j++){
			scanf("%c", &s[(i-1)*m+j]);
			if (s[(i-1)*m+j] == 'S') sx = i, sy = j;
		}
	}
	queue <pii> q;
	q.push({sx, sy});
	col[(sx-1)*m+sy] = 0;
	while (q.size()){
		int x = q.front().fi, y = q.front().se; q.pop();
		int nownum = (x-1)*m+y;
		if (vis[nownum]) continue;
		vis[nownum] = 1;
		for (int i = 0;i < 4;i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nxtnum = (nx-1)*m+ny;
			if (nx < 1 || nx > n || ny < 1 || ny > m || s[nxtnum] == '#' || vis[nxtnum]) continue;
			if (col[nxtnum] && col[nxtnum] != col[nownum]){
				puts("Yes");
				return 0;
			}
			col[nxtnum] = col[nownum];
			if (col[nownum] == 0){
				col[nxtnum] = ++cnt;
			}
			q.push({nx, ny});
		}
	}
	puts("No");
	return 0;
}

/*
5
3 6 9 6 6
*/

F – Double Chance

题目大意

解法分析

AC Code #1

G –

题目大意

解法分析

AC Code #1

Ex –

题目大意

解法分析

AC Code #1

原文链接：https://blog.csdn.net/yh2021tanghao/article/details/127710146

Atcoder Beginner Contest abc 276 A~E

Atcoder

Beginner Contest 276

A – Rightmost

B – Adjacency List

C – Previous Permutation

D – Divide by 2 or 3

E – Round Trip

F – Double Chance

G –

Ex –

标签云

近期文章

分类

Atcoder Beginner Contest abc 276 A~E

Atcoder Beginner Contest 276

A – Rightmost

B – Adjacency List

C – Previous Permutation

D – Divide by 2 or 3

E – Round Trip

F – Double Chance

G –

Ex –

相关文章

Atcoder

Beginner Contest 276