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
难度: ⭐⭐⭐
题目大意
解题思路
神秘代码