A - 2UP3DOWN
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int a, b;
cin >> a >> b;
if (a < b and b - a <= 2)
cout << "Yes\n";
else if (a > b and a - b <= 3)
cout << "Yes\n";
else
cout << "No\n";
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
solve();
return 0;
}
B - 326-like Numbers
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
for( int a , b , c; n ; n ++ ){
a = n % 10 , b = ( n / 10 ) % 10 , c = n / 100;
if( b * c == a ){
cout << n << "\n";
return 0;
}
}
return 0;
}
C - Peak
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &i: a) cin >> i;
sort(a.begin(), a.end());
int res = 0;
for( int l = 0 , r = 0 ; l < n ; l ++ ){
while( r+1 < n and a[r+1] - a[l] < m ) r ++;
res = max( res , r - l + 1);
}
cout << res << "\n";
return 0;
}
D - ABC Puzzle
因为n 的范围很小,所以可以直接暴搜过去,加一些剪枝就能跑的飞快
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e10, INF = 1e18;
const int mod = 998244353;
const int N = 1e6;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
string r, c;
cin >> n >> r >> c;
vector g(n, vector<char>(n, '.'));
vi visR(n), visC(n);
auto dfs = [&](auto &&self, int x, int y) -> void {
if (y == n) {
if (visR[x] < 7) return;
self(self, x + 1, 0);
return;
}
if (x == n) {
bool flag = true;
for (int i = 0; flag and i < n; i++)
if (visR[i] != 7 or visC[i] != 7) flag = false;
for (int i = 0; flag and i < n; i++) {
for (int j = 0; flag and j < n; j++) {
if (g[i][j] == '.') continue;
if (g[i][j] != r[i]) flag = false;
break;
}
for (int j = 0; flag and j < n; j++) {
if (g[j][i] == '.') continue;
if (g[j][i] != c[i]) flag = false;
break;
}
}
if (flag) {
cout << "Yes\n";
for (auto it: g) {
for (auto c: it) cout << c;
cout << "\n";
}
exit(0);
}
return;
}
self(self, x, y + 1);
for (int i = 0; i < 3; i++) {
if ((visR[x] & (1 << i)) or (visC[y] & (1 << i))) continue;
visR[x] ^= (1 << i), visC[y] ^= (1 << i);
g[x][y] = char(i + 'A');
self(self, x, y + 1);
visR[x] ^= (1 << i), visC[y] ^= (1 << i);
g[x][y] = '.';
}
};
dfs(dfs, 0, 0);
cout << "No\n";
return 0;
}
E - Revenge of "The Salary of AtCoder Inc."
当前状态是\(x\),\(f[x]\)表示当前掷出值\(x\)为,并继到游戏结束期望获得的钱数。
显然\(f[n]=0\)
对于当前状态\(x\),有两种情况
- \(\frac x n\)掷出$y\le x $,游戏结束,后继收入为\(0\)
- 对于\(i>x\),有$\frac 1 n \(掷出\)i\(,收入为\)a_i\(,后继收入为\)f[i]$
所以\(f[x]=\frac x n \times 0 + \sum_{i=x+1}^{n} \frac 1 n ( f[i] + a[i] )\)
所以倒序枚举状态,在后缀和统计一下可以\(O(1)\)的转移。
#include<bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;
const int mod = 998244353;
int power(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = res * x % mod;
x = x * x % mod, y /= 2;
}
return res;
}
int inv(int x) {
return power(x, mod - 2);
}
i32 main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
vi a(n);
for (auto &i: a) cin >> i;
vi f(n + 1);
int res = 0, invN = inv(n);
for (int i = n - 1; i >= 0; i--)
res = (res + res * invN % mod + a[i]) % mod;
cout << res * invN % mod << "\n";
return 0;
}
- Beginner AtCoder Contest 326beginner atcoder contest 326 326 beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332