Идея: vovuh
Разбор
Tutorial is loading...
Решение (vovuh)
for _ in range(int(input())):
n = int(input())
print(1 + (n == 1) if n <= 3 else (n + 2) // 3)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n = int(input())
p = [i + 1 for i in range(n)]
print(n)
for i in range(n):
print(*p)
if i < n - 1:
p[i], p[i + 1] = p[i + 1], p[i]
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
INF = 2 * 10**9
for _ in range(int(input())):
m = int(input())
a = [[int(x) for x in input().split()] for i in range(2)]
su = [[-INF for j in range(m + 1)] for i in range(2)]
for i in range(2):
for j in range(m - 1, -1, -1):
su[i][j] = max(su[i][j + 1] - 1, a[i][j], a[i ^ 1][j] - (2 * (m - j) - 1))
pr = a[0][0] - 1
ans = INF
for j in range(m):
jj = j & 1
ans = min(ans, max(pr, su[jj][j + 1] - 2 * j - 1, a[jj ^ 1][j] - 2 * m + 1))
pr = max(pr, a[jj ^ 1][j] - 2 * j - 1)
ans = min(ans, max(pr, su[jj ^ 1][j + 1] - 2 * j - 2))
if j < m - 1:
pr = max(pr, a[jj ^ 1][j + 1] - 2 * j - 2)
print(ans + 2 * m)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main() {
int n, k;
cin >> n >> k;
vector<int> dp(n + 1), ans(n + 1);
dp[0] = 1;
for (int mn = 0; mn + k <= n; mn += k++) {
vector<int> sum(k);
for (int i = mn; i <= n; ++i) {
int cur = dp[i];
dp[i] = sum[i % k];
(sum[i % k] += cur) %= MOD;
(ans[i] += dp[i]) %= MOD;
}
}
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}
1716E - Swap and Maximum Block
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int K = 18;
struct node
{
long long sum, pref, suff, ans;
node(const node& l, const node& r)
{
sum = l.sum + r.sum;
pref = max(l.pref, l.sum + r.pref);
suff = max(r.suff, r.sum + l.suff);
ans = max(max(l.ans, r.ans), l.suff + r.pref);
}
node(int x)
{
sum = x;
pref = suff = ans = max(x, 0);
}
node() {};
};
int a[1 << K];
vector<node> tree[2 << K];
void build(int v, int l, int r)
{
tree[v].resize(r - l);
if(l == r - 1)
{
tree[v][0] = node(a[l]);
}
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
for(int i = 0; i < m - l; i++)
{
tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);
tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]);
}
}
}
int main()
{
int n;
scanf("%d", &n);
int m = (1 << n);
for(int i = 0; i < m; i++)
{
scanf("%d", &a[i]);
}
build(0, 0, m);
int q;
scanf("%d", &q);
int cur = 0;
for(int i = 0; i < q; i++)
{
int x;
scanf("%d", &x);
cur ^= (1 << x);
printf("%lld\n", tree[0][cur].ans);
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 2043;
int dp[N][N];
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int sub(int x, int y)
{
return add(x, -y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int divide(int x, int y)
{
return mul(x, inv(y));
}
void precalc()
{
dp[1][1] = 1;
for(int i = 1; i < N - 1; i++)
for(int j = 1; j <= i; j++)
{
dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j));
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
}
}
int solve(int n, int m, int k)
{
int way1 = (m / 2) + (m % 2);
int curA = n;
int ans = 0;
int ways_chosen = way1;
int ways_other = binpow(m, n - 1);
int invm = inv(m);
for(int i = 1; i <= k; i++)
{
ans = add(ans, mul(mul(curA, dp[k][i]), mul(ways_chosen, ways_other)));
curA = mul(curA, sub(n, i));
ways_chosen = mul(way1, ways_chosen);
ways_other = mul(ways_other, invm);
}
return ans;
}
int main()
{
int t;
cin >> t;
precalc();
for(int i = 0; i < t; i++)
{
int n, m, k;
cin >> n >> m >> k;
cout << solve(n, m, k) << endl;
}
}