A - N-choice question (abc300 a)
题目大意
给定一个元素互不相同的数组\(c\)和 \(a,b\),找到 \(i\)使得 \(c_i = a + b\)
解题思路
直接for
循环寻找即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, a, b;
cin >> n >> a >> b;
for(int i = 0; i < n; ++ i){
int c;
cin >> c;
if (c == a + b){
cout << i + 1 << '\n';
return 0;
}
}
return 0;
}
B - Same Map in the RPG World (abc300 b)
题目大意
给定两个矩阵\(A,B\),问能否对 \(A\)进行若干次变换操作得到 \(B\)。
变换分两种,一种是将第一列放到最后一列,另一种是将第一行放到最后一行。
解题思路
范围不大,直接枚举所有变换操作判断即可。
如果我们将左右连通,上下连通,那么变换操作实际上不改变每个点的上下左右点。即变换操作可以看成将矩形左上角的点移动。
时间复杂度为\(O(H^2W^2)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int h, w;
cin >> h >> w;
vector<string> a(h), b(h);
for(auto &i : a){
cin >> i;
}
for(auto &i : b){
cin >> i;
}
auto equal = [&](int x, int y){
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j){
int X = (x + i) % h;
int Y = (y + j) % w;
if (a[X][Y] != b[i][j]){
return false;
}
}
return true;
};
auto check = [&](){
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j)
if (equal(i, j))
return true;
return false;
};
if (check()){
cout << "Yes" << '\n';
}
else
cout << "No" << '\n';
return 0;
}
C - Cross (abc300 c)
题目大意
给定一个包含.#
的矩形,问由#
组成的形如X
的最长长度,每个长度的数量。
解题思路
范围不大,枚举X
的位置和大小判断即可。
时间复杂度为\(O(HW\min(HW))\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int h, w;
cin >> h >> w;
vector<string> s(h);
for(auto &i : s)
cin >> i;
int sz = min(h, w);
vector<int> ans(sz + 1);
auto check = [&](int x, int y){
if (s[x][y] != '#')
return 0;
for(int i = 0; i <= sz; ++ i){
for(int dx = -1; dx <= 1; dx += 2)
for(int dy = -1; dy <= 1; dy += 2){
int nx = x + i * dx, ny = y + i * dy;
if (nx >= h || nx < 0 || ny < 0 || ny >= w)
return i - 1;
if (s[nx][ny] != '#')
return i - 1;
}
}
return sz;
};
for(int i = 0; i < h; ++ i)
for(int j = 0; j < w; ++ j)
ans[check(i, j)] ++;
for(int i = 1; i <= sz; ++ i)
cout << ans[i] << " \n"[i == sz];
return 0;
}
D - AABCC (abc300 d)
题目大意
问\(1 \sim n\)中能表示成 \(a^2 \times b \times c^2(a < b < c)\)且 \(a,b,c\)为质数的数的个数。
解题思路
由于\(n \leq 10^{12}\),预处理\(1 \to 10^6\)的质数,然后枚举\(c\)和 \(a\),计算得到乘积小于等于 \(n\)的最大的 \(b\),此时符合条件的数量就是 \(1 \sim b\)中的质数个数,这个事先预处理即可。
时间复杂度是 \(O(\sqrt{n} \log n)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
const LL p_max = 1E6 + 100;
LL pr[p_max], p_sz;
int cnt[p_max];
void get_prime() {
static bool vis[p_max];
FOR (i, 2, p_max) {
if (!vis[i]) {
pr[p_sz++] = i;
cnt[i] = 1;
}
FOR (j, 0, p_sz) {
if (pr[j] * i >= p_max) break;
vis[pr[j] * i] = 1;
if (i % pr[j] == 0) break;
}
}
FOR(i, 2, p_max)
cnt[i] += cnt[i - 1];
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL n;
cin >> n;
LL ans = 0;
get_prime();
for(int i = 0; i < p_sz; ++ i){
for(int j = 0; j < i; ++ j){
LL sum = 1ll * pr[i] * pr[i] * pr[j] * pr[j];
if (sum > n)
break;
LL maxb = min(n / sum, pr[i] - 1);
if (maxb <= pr[j])
break;
ans += cnt[maxb] - cnt[pr[j]];
}
}
cout << ans << '\n';
return 0;
}
E - Dice Product 3 (abc300 e)
题目大意
六面骰子,每面等概率出现。
现在不断掷骰子,直到掷出来的数的乘积大于等于\(N\)。
问恰好为 \(N\)的概率。对 \(998244353\)取模。
解题思路
显然\(n\)的质因数只能有 \(2,3,5\)。
设\(dp[n]\)表示最终是 \(n\)的概率,根据定义, \(dp[n] = \frac{1}{6}dp[\frac{n}{1}] + \frac{1}{6}dp[\frac{n}{2}] + \frac{1}{6}dp[\frac{n}{3}] + \frac{1}{6}dp[\frac{n}{4}] + \frac{1}{6}dp[\frac{n}{5}] + \frac{1}{6}dp[\frac{n}{6}]\),即掷出\(n\)的概率,应当是先掷出 \(\frac{n}{1}\) ,然后再以\(\frac{1}{6}\)的概率掷出 \(1\),或者先掷出 \(\frac{n}{2}\) ,然后再以\(\frac{1}{6}\)的概率掷出 \(2\),依次类推。
当然,如果不整除就没有这部分的概率贡献。
化简一下就是\(dp[n] = \frac{1}{5}dp[\frac{n}{2}] + \frac{1}{5}dp[\frac{n}{3}] + \frac{1}{5}dp[\frac{n}{4}] + \frac{1}{5}dp[\frac{n}{5}] + \frac{1}{5}dp[\frac{n}{6}]\)
因为每次转移状态大小都会除以一个数,所以最终的状态数量应该不会超过\(O(n \log n)\),写个记忆化就可以了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
long long qpower(long long a, long long b){
long long qwq = 1;
while(b){
if (b & 1)
qwq = qwq * a % mo;
a = a * a % mo;
b >>= 1;
}
return qwq;
}
long long inv(long long x){
return qpower(x, mo - 2);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL n, ba;
cin >> n;
ba = n;
int cnt2 = 0, cnt3 = 0, cnt5 = 0;
while (n % 2 == 0){
++ cnt2;
n /= 2;
}
while (n % 3 == 0){
++ cnt3;
n /= 3;
}
while (n % 5 == 0){
++ cnt5;
n /= 5;
}
if (n != 1)
cout << 0 << '\n';
else{
map<LL, int> cache;
LL inv5 = inv(5);
function<LL(LL)> dfs = [&](LL n){
if (n == 1)
return 1;
if (cache.find(n) != cache.end())
return cache[n];
LL ans = 0;
for(int i = 2; i <= 6; ++ i)
if (n % i == 0){
ans = (ans + dfs(n / i));
if (ans >= mo)
ans -= mo;
}
cache[n] = ans * inv5 % mo;
return cache[n];
};
cout << dfs(ba) << '\n';
}
return 0;
}
F - More Holidays (abc300 f)
题目大意
给定一个包含xo
的字符串\(t\),它由一个长度为\(n\)的串\(s\)重复 \(m\)次拼接得到。要求将恰好 \(k\)个 x
变成o
,问连续o
的最大长度。
解题思路
把x
的位置都记录下来,容易发现我们进行变换的x
肯定是一组连续的x
。
我们枚举进行变化的第一个x
,然后找到之后的第 \(k\)个 x
,之间的长度取个最大值即可。
虽然这个x
有\(nm = 10^{14}\)个,但由于串是重复拼接得到的,第二部分的串的 x
实际上跟第一个串的情况一致(并且不会更优),因此我们只需要枚举第一个串x
和第二个串的第一个x
(注意这个情况,会利用第一个串最后一个x
和第二个串的第一个x
之间的o
,可能从第一个串的第一个x
更优)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
LL k;
cin >> n >> m >> k;
string s;
cin >> s;
vector<int> pos;
LL cnt = 0;
for(int i = 0; i < n; ++ i){
cnt += (s[i] == 'x');
if (s[i] == 'x')
pos.push_back(i);
}
LL ans = 0;
LL la = -1;
auto solve = [&](int st){
LL left = pos.size() - st;
LL minn = min(left, k);
left = k - minn;
if (left == 0){
if (st + k == pos.size()){
return 1ll * n + pos[0] * (m > 1);
}else {
return 1ll * pos[st + k];
}
}
LL shift = left / cnt + 1;
LL remain = left % cnt;
if (remain == 0 && shift == m){
return shift * n;
}else if (shift > m || shift == m && remain > 0)
return 0ll;
else{
return shift * n + pos[remain];
}
};
for(int i = 0; i < pos.size(); ++ i){
LL r = solve(i);
ans = max(ans, r - la - 1);
la = pos[i];
}
if (m > 1){
m -= 1;
LL r = solve(0);
ans = max(ans, n + r - pos.back() - 1);
}
cout << ans << '\n';
return 0;
}
求第\(k\)个 x
可能有些情况要讨论,官方题解采用的二分法就可以以\(\log\)的代价避免这个讨论。
且x
的数量和串\(s\)的长度是同一个数量级,我们也可以枚举答案的左端点,然后二分找到恰好包含\(k\)个x
的最右端点,长度取个最大值。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
LL k;
cin >> n >> m >> k;
string s;
cin >> s;
vector<int> sum(n);
LL cnt = 0;
for(int i = 0; i < n; ++ i){
if (s[i] == 'x'){
sum[i] = 1;
}
}
partial_sum(sum.begin(), sum.end(), sum.begin());
LL ans = 0;
LL la = -1;
auto count = [&](LL pos){
LL shift = pos / n, remain = pos % n;
return shift * sum.back() + sum[remain] * (shift != m);
};
auto solve = [&](int st){
LL l = st, r = 1ll * n * m;
LL down = st == 0 ? 0 : sum[st - 1];
while(l + 1 < r){
LL mid = (l + r) >> 1;
if (count(mid) - down <= k)
l = mid;
else
r = mid;
};
return r;
};
for(int i = 0; i < n; ++ i){
LL r = solve(i);
ans = max(ans, r - i);
}
cout << ans << '\n';
return 0;
}
G - P-smooth number (abc300 g)
题目大意
<++>
解题思路
<++>
神奇的代码
Ex - Fibonacci: Revisited (abc300 h)
题目大意
<++>
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 300beginner atcoder contest 300 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315 beginner atcoder contest 334