Идея: BledDest
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int n;
int a[N];
void solve() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 1; i < n - 1; ++i) {
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
cout << "YES" << endl;
cout << i << ' ' << i + 1 << ' ' << i + 2 << endl;
return;
}
}
cout << "NO" << endl;
}
int main() {
int T;
cin >> T;
while (T--)
solve();
}
Идея: adedalic
fun main() {
val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S')
repeat(readLine()!!.toInt()) {
val s = readLine()!!
val maxCnt = s.groupingBy { it }.eachCount().maxBy { it.value }!!.key
println("${winBy[maxCnt]}".repeat(s.length))
}
}
Идея: Roms
for _ in range(int(input())):
n, x = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
res, cur = 0, 1
for s in a:
if s * cur >= x:
res += 1
cur = 0
cur += 1
print(res)
Идея: Roms
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 9;
int n, m;
long long x, k, y;
int a[N];
int b[N];
bool upd(int l, int r, long long &res) {
if (l > r) return true;
bool canDel = false;
int mx = *max_element(a + l, a + r + 1);
int len = r - l + 1;
if (l - 1 >= 0 && a[l - 1] > mx) canDel = true;
if (r + 1 < n && a[r + 1] > mx) canDel = true;
if (len < k && !canDel) return false;
int need = len % k;
res += need * y;
len -= need;
if (y * k >= x) {
res += len / k * x;
} else if(canDel) {
res += len * y;
} else {
res += (len - k) * y + x;
}
return true;
}
int main(){
scanf("%d %d", &n, &m);
scanf("%lld %lld %lld", &x, &k, &y);
for (int i = 0; i < n; ++i) scanf("%d", a + i);
for (int i = 0; i < m; ++i) scanf("%d", b + i);
long long res = 0;
int lst = -1, posa = 0, posb = 0;
while (posb < m) {
while(posa < n && a[posa] != b[posb]) ++posa;
if (posa == n) {
puts("-1");
return 0;
}
if (!upd(lst + 1, posa - 1, res)) {
puts("-1");
return 0;
}
lst = posa;
++posb;
}
if (!upd(lst + 1, n - 1, res)) {
puts("-1");
return 0;
}
printf("%lld\n", res);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 200043;
const int L = 20;
vector<int> g[2 * N];
int p[2 * N];
int up[2 * N][L];
int idx[N];
int psum[N];
int cur[N];
int tin[2 * N];
int tout[2 * N];
int T = 0;
void dfs(int x, int y)
{
tin[x] = T++;
p[x] = y;
up[x][0] = y;
for(int i = 1; i < L; i++)
up[x][i] = up[up[x][i - 1]][i - 1];
for(auto z : g[x])
dfs(z, x);
tout[x] = T++;
}
bool is_ancestor(int x, int y)
{
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int lca(int x, int y)
{
if(is_ancestor(x, y))
return x;
for(int i = L - 1; i >= 0; i--)
if(!is_ancestor(up[x][i], y))
x = up[x][i];
return p[x];
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
{
scanf("%d", &idx[i]);
idx[i]--;
}
for(int i = 0; i < m; i++)
cur[i] = i;
for(int i = 0; i < m - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
int nidx = m + i;
g[nidx].push_back(cur[x]);
g[nidx].push_back(cur[y]);
cur[x] = nidx;
}
int root = m * 2 - 2;
dfs(root, root);
for(int i = 0; i < n - 1; i++)
{
int t = lca(idx[i], idx[i + 1]);
if(t < m)
psum[0]++;
else
psum[t - m + 1]++;
}
for(int i = 0; i < m - 1; i++)
psum[i + 1] += psum[i];
for(int i = 0; i < m; i++)
printf("%d\n", n - 1 - psum[i]);
}
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n, m;
vector<int> p;
vector<vector<int>> val;
vector<int> who;
int getp(int a){
return a == p[a] ? a : p[a] = getp(p[a]);
}
int main(){
scanf("%d%d", &n, &m);
p.resize(m);
val.resize(m);
who.resize(n);
int ans = n - 1;
forn(i, m)
p[i] = i;
forn(i, n){
int x;
scanf("%d", &x);
--x;
who[i] = x;
ans -= (i && who[i] == who[i - 1]);
val[who[i]].push_back(i);
}
printf("%d\n", ans);
forn(i, m - 1){
int v, u;
scanf("%d%d", &v, &u);
v = getp(v - 1), u = getp(u - 1);
if (val[v].size() < val[u].size())
swap(v, u);
for (int x : val[u]){
if (x) ans -= who[x - 1] == v;
if (x < n - 1) ans -= who[x + 1] == v;
}
for (int x : val[u]){
val[v].push_back(x);
who[x] = v;
}
p[u] = v;
printf("%d\n", ans);
}
return 0;
}
Идея: Roms
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int MOD = 998244353;
const int N = 500 * 1000 + 13;
string s;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
struct node{
int val[4], len;
};
node merge(const node &a, const node &b, int l, int r){
node c;
int na = a.len == 1 ? 0 : 1;
int nb = b.len == 1 ? 0 : 2;
c.len = a.len + b.len;
c.val[0] = mul(a.val[na], b.val[nb]);
c.val[1] = mul(a.val[na], b.val[3]);
c.val[2] = mul(a.val[3], b.val[nb]);
c.val[3] = mul(a.val[3], b.val[3]);
if (l == 1){
na = a.len == 1 ? 2 : 0;
nb = b.len == 1 ? 1 : 0;
c.val[na + nb] = add(c.val[na + nb], mul(mul(a.val[0], b.val[0]), 19 - (l * 10 + r)));
c.val[1 + na] = add(c.val[1 + na], mul(mul(a.val[0], b.val[1]), 19 - (l * 10 + r)));
c.val[2 + nb] = add(c.val[2 + nb], mul(mul(a.val[2], b.val[0]), 19 - (l * 10 + r)));
c.val[3] = add(c.val[3], mul(mul(a.val[2], b.val[1]), 19 - (l * 10 + r)));
}
return c;
}
node t[4 * N];
void build(int v, int l, int r){
t[v].len = r - l;
if (l == r - 1){
t[v].val[0] = 1;
t[v].val[3] = s[l] + 1;
return;
}
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m, r);
t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}
void upd(int v, int l, int r, int x, int val){
if (l == r - 1){
s[l] = val;
t[v].val[3] = s[l] + 1;
return;
}
int m = (l + r) / 2;
if (x < m)
upd(v * 2, l, m, x, val);
else
upd(v * 2 + 1, m, r, x, val);
t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
static char buf[N];
scanf("%s", buf);
s = buf;
forn(i, n) s[i] -= '0';
memset(t, 0, sizeof(t));
build(1, 0, n);
forn(i, m){
int x, v;
scanf("%d%d", &x, &v);
--x;
upd(1, 0, n, x, v);
printf("%d\n", t[1].val[3]);
}
}
#include <bits/stdc++.h>
using namespace std;
const int N = int(5e5) + 9;
const int MOD = 998244353;
int mul(int a, int b) {
return (a * 1LL * b) % MOD;
}
void add(int &a, int x) {
a += x;
a %= MOD;
}
int bp(int a, int n) {
int res = 1;
for (; n > 0; n >>= 1) {
if (n & 1) res = mul(res, a);
a = mul(a, a);
}
return res;
}
int inv(int a) {
int ia = bp(a, MOD - 2);
assert(mul(a, ia) == 1);
return ia;
}
int n, m;
string s;
int dp[N][10];
int idp[N][10];
set <pair<int, int> > lr;
int res = 1;
void updRes(int l, int r, int c) {
assert(l <= r);
if (c == 1) {
assert(!lr.count(make_pair(l, r)));
lr.insert(make_pair(l, r));
res = mul(res, dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']);
} else {
assert(lr.count(make_pair(l, r)));
lr.erase(make_pair(l, r));
res = mul(res, inv(dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']));
}
}
void getLR(int &l, int &r, int pos) {
l = r = -1;
auto it = lr.lower_bound(make_pair(pos, n));
if(it == lr.begin()) return;
--it;
if(!(it->first <= pos && pos <= it->second)) return;
l = it->first, r = it->second;
}
char buf[N];
int main(){
scanf("%d %d\n", &n, &m);
scanf("%s", buf);
s = string(buf);
for (int i = 0; i <= 9; ++i) {
dp[0][i] = i + 1; //idp[0][i] = inv(dp[0][i]);
dp[1][i] = 2 * (i + 1) + (9 - i); //idp[1][i] = inv(dp[1][i]);
}
for (int i = 2; i < N; ++i)
for (int j = 0; j <= 9; ++j) {
dp[i][j] = (2LL * dp[i - 1][j] + 8LL * dp[i - 2][j]) % MOD;
//idp[i][j] = inv(dp[i][j]);
}
for (int i = 0; i < N; ++i) for(int j = 0; j < 10; ++j) assert(dp[i][j] != 0);
for (int l = 0; l < n; ) {
int r = l;
while(r < n && s[r] == '1') ++r;
res = mul(res, dp[r - l - (r == n)][r == n? 1 : s[r] - '0']);
if (l != r) lr.insert(make_pair(l, r - 1));
l = r + 1;
}
for (int i = 0; i < m; ++i) {
int pos;
char x;
scanf("%d %c\n", &pos, &x);
--pos;
if (x == '1') {
if (s[pos] != '1'){
int l1, r1, l2, r2;
getLR(l1, r1, pos - 1);
getLR(l2, r2, pos + 1);
int l = pos, r = pos;
if (l1 != -1) {
assert(r1 == pos - 1);
updRes(l1, r1, -1);
l = l1;
} else {
res = mul(res, inv(dp[0][s[pos] - '0']));
}
if (l2 != -1) {
assert(l2 == pos + 1);
updRes(l2, r2, -1);
r = r2;
} else {
if (pos + 1 != n) res = mul(res, inv(dp[0][s[pos + 1] - '0']));
}
s[pos] = x;
updRes(l, r, 1);
}
} else {
if (s[pos] != '1') {
if (pos - 1 >= 0 && s[pos - 1] == '1') {
int l, r;
getLR(l, r, pos - 1);
updRes(l, r, -1);
s[pos] = x;
updRes(l, r, 1);
} else {
res = mul(res, dp[0][x - '0']);
res = mul(res, inv(dp[0][s[pos] - '0']));
s[pos] = x;
}
} else {
int l, r;
getLR(l, r, pos);
assert(l != -1 && r != -1);
updRes(l, r, -1);
s[pos] = x;
if (l == r) {
res = mul(res, dp[0][s[pos] - '0']);
if (pos + 1 < n) res = mul(res, dp[0][s[pos + 1] - '0']);
} else if (pos == l) {
res = mul(res, dp[0][s[pos] - '0']);
updRes(l + 1, r, 1);
} else if (pos == r) {
if (pos + 1 != n) res = mul(res, dp[0][s[pos + 1] - '0']);
updRes(l, r - 1, 1);
} else {
updRes(l, pos - 1, 1);
updRes(pos + 1, r, 1);
}
}
}
printf("%d\n", res);
}
}
Идея: BledDest
Для начала, скажем, что математическое ожидание равно среднему значению дохода по всем позициям и равно сумме значений дохода по всем позициям, деленной на $$$n$$$. Поэтому перейдем к минимизации суммы.
Научимся решать для фиксированного $$$k$$$. Возьмем некоторую расстановку и повернем комнаты так, чтобы последняя комната содержала мимика. Тогда у нас стоят $$$cnt_1$$$ обычных сундуков, затем один мимик, $$$cnt_2$$$ обычных сундуков, один мимик, $$$\dots$$$, $$$cnt_k$$$ обычных сундуков, один мимик. Все $$$cnt_i \ge 0$$$ и $$$\sum \limits_{i=1}^{k} cnt_i = n - k$$$.
Взглянем на один из таких интервалов длины $$$cnt_i$$$. Последний сундук на интервале взят из $$$cnt_i$$$ начальных позиций, второй с конца — $$$cnt_i - 1$$$ раз и так далее.
Найдем оптимальный способ выбрать $$$cnt_i$$$. Зафиксируем некоторые значения $$$cnt_i$$$. Взглянем на наименьшее из них и на наибольшее. Пусть их значения будут равны $$$x$$$ и $$$y$$$. Если они отличаются хотя бы на $$$2$$$ ($$$x \le y - 2$$$), то результат всегда можно сделать лучше, если подвинуть один обычный сундук из большего интервала в меньший.
Рассмотрим две последовательности коэффициентов для обоих интервалов: $$$[1, 2, \dots, x - 1, x]$$$ и $$$[1, 2, \dots, y - 1, y]$$$.
Однако, если переместить один сундук, то они будут равны $$$[1, 2, \dots, x - 1, x, x + 1]$$$ и $$$[1, 2, \dots, y - 1]$$$.
Если только посмотреть на разницу между числами в обеих последовательностях, то можно понять, что только коэффициент $$$y$$$ был удален и $$$x + 1$$$ был добавлен. Тогда можно переставить сундуки таким образом, что всем сундукам присвоились те же самые значения, а сундук с коэффициентом $$$y$$$ становится на $$$x+1$$$, уменьшая итоговое значение.
Теперь все значения $$$cnt_i$$$ выставлены. Осталось только присвоить сундуки оптимальным способом. Выпишем объединение всех последовательностей коэффициентов интервалов $$$\bigcup \limits_{i=1}^{n-k} [1, \dots, cnt_i-1, cnt_i]$$$ и отсортируем в неубывающем порядке. Легко показать, что сундуки должны быть отсортированы в невозрастающем порядке (очень стандартная штука, можно доказать опять же показав, что другая расстановка легко может быть улучшена).
Это позволяет нам написать решение за $$$O(n^2)$$$. Отсортируем все сундуки в самом начале, а затем для любого $$$k$$$ домножим значение $$$i$$$-го сундука на $$$\lfloor \frac{i}{k} \rfloor$$$ и сложим результаты.
Наконец, ускорим решение с помощью префиксных сумм. Заметим, что первые $$$k$$$ значений домножаются на $$$0$$$, вторые $$$k$$$ значений — на $$$1$$$ и так далее. Если $$$n$$$ не делится на $$$k$$$, то последний блок имеет длину меньше $$$k$$$. Тогда можно посчитать ответ для любого $$$k$$$ за $$$O(\frac{n}{k})$$$. А это равно $$$O(\sum \limits_{k=1}^{n} \frac{n}{k})$$$ = $$$O(n \log n)$$$.
Асимптотика решения: $$$O(n \log n)$$$.
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
vector<int> pr;
int main() {
int n;
scanf("%d", &n);
vector<int> c(n);
forn(i, n)
scanf("%d", &c[i]);
sort(c.begin(), c.end(), greater<int>());
pr.push_back(0);
forn(i, n)
pr.push_back(add(pr.back(), c[i]));
int invn = binpow(n, MOD - 2);
for (int k = 1; k <= n; ++k){
int ans = 0;
for (int i = 0, j = 0; i < n; i += k, ++j)
ans = add(ans, mul(j, add(pr[min(n, i + k)], -pr[i])));
printf("%d ", mul(ans, invn));
}
puts("");
return 0;
}