526互联

AtCoder Beginner Contest(abc) 326

发布时间 2023-11-21 16:10:03作者: mostimali



B - 326-like Numbers

难度: ⭐

题目大意

如果一个三位数的百位和十位的乘积等于个位, 那么这个数就是合法的; 问大于等于n的最小的合法的数是多少;

解题思路

因为数据范围很小, 所以可以直接暴力;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, idx;
signed main(){
    cin >> m;
    while(1){
        n = m;
        int a = n / 100;
        n -= a * 100;
        int b = n / 10;
        n -= b * 10;
        if(a * b == n){
            cout << m;
            break;
        }
        m++;
    }
    return 0;
}



C - Peak

难度: ⭐⭐

题目大意

在一条数轴上有n个礼物, 给定它们的坐标; 你可以选择一个左闭右开的区间, 区间的长度为m; 问这个区间能包含的礼物个数最多是多少;

解题思路

二分加前缀和; 因为最优的情况肯定是区间的左端点恰好在一个礼物上; 所以遍历所有礼物为左端点, 然后用二分找到区间内最右边的那个礼物的坐标, 用前缀和求得数量即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, idx;
int f[N], p[N];
signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> f[i];
    }
    sort(f + 1, f + 1 + n);
    int maxn = 0;
    for(int i = 1; i <= n; i++){
        p[i] = ++idx;
    }
    for(int i = 1; i <= n; i++){
        int x = f[i] + m;
        int l = i, r = n;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(f[mid] >= x) r = mid - 1;
            else l = mid;
        }
        maxn = max(maxn, p[l] - p[i - 1]);
    }
    cout << maxn;
    return 0;
}



D - ABC Puzzle

难度: ⭐⭐⭐

题目大意

给定两个长度为n且由"ABC"组成的字符串s和t; 现在有一个n * n的字符矩阵, 该矩阵有两个要求;
一是: 这个矩阵的每一行和每一列都恰好有1个'A', 1个'B'以及1个'C'; ;
二是: 取这n行中每行最左边的那个字母, 恰好可以组成字符串s; 并且取这n列中每列最上面的那个字母, 恰好可以组成字符串t;
字符矩阵的其他位置为'.'; 输出任意一个满足条件的该矩阵;

解题思路

因为题目要求较为复杂, 并且n的范围最大为5, 所以可以直接考虑暴力; 我们可以暴力枚举所有满足条件一的字符矩阵, 然后再一一检查就可以了; 枚举时的难点主要在于"ABC"的位置选择; 这里我们可以用next_permutation函数进行1~n的全排列; 其中1, 2, 3的位置放'A', 'B', 'C'; dfs构造字符矩阵时可以用n皇后的思路; dfs枚举每一行的情况, 用一个数组表示每一列的"ABC"的存在情况; 这样我们就可以得到一个满足条件一的字符矩阵; 而检查该矩阵也就简单很多了, 只需要按题目说的, 遍历每一行和每一列, 找出最左边和最上边的字符组成的字符串检查一下就可以了;
注意: 这里我踩了一个坑, next_permutation函数的全排列是按字典序来的, 如果当前序列是最大字典序情况就会停止, 如果p数组的初始情况不是12345这样的最小情况, 那么实际上就没有进行完整的全排列, 所以我一层都需要重置p数组; 但是我把p数组设成全局数组了, 这就导致我每一层的dfs都用的同一个数组, 但是每层dfs在全排列时会重置p数组, 所以导致整体都乱了;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 5;
int n, m;
string s, t;
char g[N][N];
int c[N][5];
void check(){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(g[i][j] != '.'){
				if(g[i][j] != s[i - 1]){
					return;
				}
				break;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(g[j][i] != '.'){
				if(g[j][i] != t[i - 1]){
					return;
				}
				break;
			}
		}
	}
	cout << "Yes" << endl;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cout << g[i][j];
		}
		cout << endl;
	}
	exit(0);
}
void dfs(int u){
	if(u > n){
		check();
		return;
	}
	int p[N];
	for(int i = 1; i <= n ; i++) p[i] = i;
	do{
		int pa = 0, pb = 0, pc = 0;
		int f = true;
		for(int i = 1; i <= n; i++){
			if(p[i] == 1){
				if(c[i][1]){
					f = false;
					break;
				}
				c[i][1] = 1;
				g[u][i] = 'A';
				pa = i;
			}
			else if(p[i] == 2){
				if(c[i][2] ){
					f = false;
					break;
				}
				c[i][2] = 1;
				g[u][i] = 'B';
				pb = i;
			}
			else if(p[i] == 3){
				if(c[i][3]){
					f = false;
					break;
				}
				c[i][3] = 1;
				g[u][i] = 'C';
				pc = i;
			}
			else g[u][i] = '.';
		}
		if(f) {
			dfs(u + 1);
		}
		if(pa) c[pa][1] = 0;
		if(pb) c[pb][2] = 0;
		if(pc) c[pc][3] = 0;
	}while(next_permutation(p + 1, p + 1 + n));
}
signed main(){
	cin >> n >> s >> t;
	dfs(1);
	cout << "No";
	return 0;
}



E - Revenge of "The Salary of AtCoder Inc."

难度: ⭐⭐⭐

题目大意

小莫在玩一个骰子游戏, 骰子有n个面; 现在有一个长度为n的数组Ai和一个初始值x = 0; 小莫每回合会掷出一个数y, 如果y > x, 那么小莫就会得到Ay分, 然后截止掷骰子, 知道y <= x时退出; 问小莫可获得的分数的期望值是多少, 对mod取模;

解题思路

一开始我想用dp来做, 但是n的数据范围较大, 一直想不到合适的转移方程; 题解用来前缀和来解决这个问题; 对于Ai来说, 它只能在前i回合做出贡献, 所以它可以从0 ~ i - 1转移而来(0的意思就是第一次就掷到了i); 设dpi是掷到i的概率; 那么dpi = dp0 + dp1 + ... + dpi-1; 其中dp0 = 1 / n, 而dp1 + ... + dpi-1我们可以用前缀和来处理, 这样就可以用O(n)的做法来解决这个问题; 那么Ai所作的贡献就是Ai * dpi; 设sum为前缀和, 则sumi = 1 / n + sum~i - 1~; 其实也可以不用开数组, 因为是线性的, 用一个数来表示当前的前缀和即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
int f[N];
int qmid(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> f[i];
	int res = 0, sum = qmid(n, mod - 2);
	for(int i = 1; i <= n; i++){
		res = (res + f[i] * sum) % mod;
		sum = (sum + sum * qmid(n, mod - 2) % mod) % mod;
	}
	cout << res;
	return 0;
}



F - Robot Rotation

难度: ⭐⭐⭐

题目大意

解题思路

神秘代码