A – N-choice question (abc300 a)
题目大意
给定一个元素互不相同的数组(c)和 (a,b),找到 (i)使得 (c_i = a + b)
解题思路
直接for
循环寻找即可。
神奇的代码
#include
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 > c;
if (c == a + b){
cout
B – Same Map in the RPG World (abc300 b)
题目大意
给定两个矩阵(A,B),问能否对 (A)进行若干次变换操作得到 (B)。
变换分两种,一种是将第一列放到最后一列,另一种是将第一行放到最后一行。
解题思路
范围不大,直接枚举所有变换操作判断即可。
如果我们将左右连通,上下连通,那么变换操作实际上不改变每个点的上下左右点。即变换操作可以看成将矩形左上角的点移动。
时间复杂度为(O(H^2W^2))
神奇的代码
#include
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 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
C – Cross (abc300 c)
题目大意
给定一个包含.#
的矩形,问由#
组成的形如X
的最长长度,每个长度的数量。
解题思路
范围不大,枚举X
的位置和大小判断即可。
时间复杂度为(O(HWmin(HW)))
神奇的代码
#include
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 s(h);
for(auto &i : s)
cin >> i;
int sz = min(h, w);
vector ans(sz + 1);
auto check = [&](int x, int y){
if (s[x][y] != '#')
return 0;
for(int i = 0; i = h || nx = w)
return i - 1;
if (s[nx][ny] != '#')
return i - 1;
}
}
return sz;
};
for(int i = 0; i
D – AABCC (abc300 d)
题目大意
问(1 sim n)中能表示成 (a^2 times b times c^2(a 且 (a,b,c)为质数的数的个数。
解题思路
由于(n leq 10^{12}),预处理(1 to 10^6)的质数,然后枚举(c)和 (a),计算得到乘积小于等于 (n)的最大的 (b),此时符合条件的数量就是 (1 sim b)中的质数个数,这个事先预处理即可。
时间复杂度是 (O(sqrt{n} log n))
神奇的代码
#include
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay::type i = (x), _##i = (y); i ::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 n)
break;
LL maxb = min(n / sum, pr[i] - 1);
if (maxb
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
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 cache;
LL inv5 = inv(5);
function 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 = mo)
ans -= mo;
}
cache[n] = ans * inv5 % mo;
return cache[n];
};
cout
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
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 pos;
LL cnt = 0;
for(int i = 0; i 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 1){
m -= 1;
LL r = solve(0);
ans = max(ans, n + r - pos.back() - 1);
}
cout
求第(k)个 x
可能有些情况要讨论,官方题解采用的二分法就可以以(log)的代价避免这个讨论。
且x
的数量和串(s)的长度是同一个数量级,我们也可以枚举答案的左端点,然后二分找到恰好包含(k)个x
的最右端点,长度取个最大值。
神奇的代码
#include
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 sum(n);
LL cnt = 0;
for(int i = 0; i > 1;
if (count(mid) - down
G – P-smooth number (abc300 g)
题目大意
解题思路
神奇的代码
Ex – Fibonacci: Revisited (abc300 h)
题目大意
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net