Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (l, r) = readLine()!!.split(' ').map { it.toInt() }
println(if (2 * l > r) "YES" else "NO");
}
}
1437B - Развороты бинарных строк
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
const int INF = int(1e9);
int n;
string s;
inline bool read() {
if(!(cin >> n >> s))
return false;
return true;
}
int cntSame(const string &s) {
int ans = 0;
fore (i, 1, sz(s))
ans += (s[i - 1] == s[i]);
assert(ans % 2 == 0);
return ans / 2;
}
inline void solve() {
int ans = INF;
fore (k, 0, 2) {
ans = min(ans, cntSame(string(1, '0' + k) + s + string(1, '1' - k)));
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
assert(read());
solve();
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int INF = 1e9;
void solve(){
int n;
scanf("%d", &n);
vector<int> t(n);
forn(i, n){
scanf("%d", &t[i]);
--t[i];
}
sort(t.begin(), t.end());
vector<vector<int>> dp(n + 1, vector<int>(2 * n, INF));
dp[0][0] = 0;
forn(i, n + 1) forn(j, 2 * n - 1) if (dp[i][j] < INF){
if (i < n) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(t[i] - j));
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
}
printf("%d\n", dp[n][2 * n - 1]);
}
int main() {
int q;
scanf("%d", &q);
forn(_, q) solve();
}
Решение 2 (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
template<typename T>
T hungarian(const vector<vector<T>>& cost) {
const T INF = numeric_limits<T>::max();
int n = cost.size(), m = cost[0].size();
vector<T> u(n + 1), v(m + 1), dist(m + 1);
vector<int> p(m + 1), way(m + 1), used(m + 1);
for (int i = 1; i <= n; ++i) {
p[0] = i;
int j0 = 0;
fill(dist.begin(), dist.end(), INF);
do {
used[j0] = i;
int i0 = p[j0], j1 = -1;
T delta = INF;
for (int j = 1; j <= m; ++j) if (used[j] != i) {
T cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
if (cur < dist[j]) dist[j] = cur, way[j] = j0;
if (dist[j] < delta) delta = dist[j], j1 = j;
}
forn(j, m + 1) {
if (used[j] == i) u[p[j]] += delta, v[j] -= delta;
else dist[j] -= delta;
}
j0 = j1;
} while (p[j0] != 0);
for (int j1; j0; j0 = j1)
p[j0] = p[j1 = way[j0]];
}
return -v[0];
}
void solve(){
int n;
scanf("%d", &n);
vector<int> t(n);
forn(i, n){
scanf("%d", &t[i]);
--t[i];
}
vector<vector<int>> cost(n, vector<int>(2 * n));
forn(i, n) forn(j, 2 * n) cost[i][j] = abs(t[i] - j);
printf("%d\n", hungarian(cost));
}
int main() {
int q;
scanf("%d", &q);
forn(_, q) solve();
}
1437D - Дерево минимальной высоты
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
int n;
vector<int> a;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
return true;
}
inline void solve() {
vector<int> h(n, INF);
h[0] = 0;
int lst = 0;
fore (i, 1, n) {
if (i - 1 > 0 && a[i - 1] > a[i])
lst++;
h[i] = h[lst] + 1;
}
cout << h[n - 1] << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int N = 500 * 1000 + 13;
int n, k;
int a[N], b[N];
int main() {
scanf("%d%d", &n, &k);
forn(i, n) scanf("%d", &a[i + 1]);
a[0] = -1e9;
a[n + 1] = 2e9;
forn(i, n + 2) a[i] -= i;
forn(i, k) scanf("%d", &b[i + 1]);
b[k + 1] = n + 1;
int ans = 0;
forn(i, k + 1) {
int l = b[i], r = b[i + 1];
if (a[l] > a[r]) {
puts("-1");
return 0;
}
vector<int> lis;
for (int j = l + 1; j < r; ++j) if (a[l] <= a[j] && a[j] <= a[r]) {
auto pos = upper_bound(lis.begin(), lis.end(), a[j]);
if (pos == lis.end()) lis.push_back(a[j]);
else *pos = a[j];
}
ans += (r - l - 1) - int(lis.size());
}
printf("%d\n", ans);
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 5043;
const int MOD = 998244353;
int dp[N][N];
int pdp[N][N];
int cntLess[N];
int lastLess[N];
int a[N];
int 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, MOD - y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
for(int i = 0; i < n; i++)
{
cntLess[i] = 0;
lastLess[i] = -1;
for(int j = 0; j < n; j++)
if(a[j] * 2 <= a[i])
{
lastLess[i] = j;
cntLess[i]++;
}
}
for(int i = 0; i < n; i++)
{
dp[i][1] = 1;
pdp[i + 1][1] = add(pdp[i][1], dp[i][1]);
}
for(int k = 2; k <= n; k++)
for(int i = 0; i < n; i++)
{
if(cntLess[i] + 1 >= k)
dp[i][k] = add(mul(dp[i][k - 1], add(cntLess[i], sub(2, k))), pdp[lastLess[i] + 1][k - 1]);
else
dp[i][k] = 0;
//cerr << i << " " << k << " " << dp[i][k] << endl;
pdp[i + 1][k] = add(pdp[i][k], dp[i][k]);
}
cout << dp[n - 1][n] << endl;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int AL = 26;
vector<int> val;
vector<int> pos;
struct aho_corasick {
struct node {
map<int, int> nxt, go;
int p, pch;
int suf, ssuf;
multiset<int> vals;
bool term;
node() {
nxt.clear();
go.clear();
suf = ssuf = -1;
term = false;
vals.clear();
p = -1, pch = -1;
}
};
vector<node> nodes;
aho_corasick() {
nodes = vector<node>(1, node());
}
int add(const string& s) {
int v = 0;
forn(i, s.size()) {
int c = s[i] - 'a';
if (!nodes[v].nxt.count(c)) {
nodes.push_back(node());
nodes[v].nxt[c] = int(nodes.size()) - 1;
nodes.back().p = v;
nodes.back().pch = c;
}
v = nodes[v].nxt[c];
}
nodes[v].term = true;
nodes[v].vals.insert(0);
return v;
}
int feed(const string &s){
int v = 0;
int ans = -1;
forn(i, s.size()){
int c = s[i] - 'a';
v = go(v, c);
int u = v;
while (u != 0){
if (!nodes[u].vals.empty())
ans = max(ans, *nodes[u].vals.rbegin());
u = ssuf(u);
}
}
return ans;
}
int go(int v, int c) {
if (nodes[v].go.count(c))
return nodes[v].go[c];
if (nodes[v].nxt.count(c))
return nodes[v].go[c] = nodes[v].nxt[c];
if (v == 0)
return nodes[v].go[c] = 0;
return nodes[v].go[c] = go(suf(v), c);
}
int suf(int v) {
if (nodes[v].suf != -1)
return nodes[v].suf;
if (v == 0 || nodes[v].p == 0)
return nodes[v].suf = 0;
return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
}
int ssuf(int v) {
if (nodes[v].ssuf != -1)
return nodes[v].ssuf;
if (v == 0 || nodes[v].p == 0)
return nodes[v].ssuf = 0;
int s = suf(v);
if (nodes[s].term)
return nodes[v].ssuf = s;
return nodes[v].ssuf = ssuf(s);
}
};
aho_corasick ac;
int main() {
int n, m;
ios::sync_with_stdio(!cin.tie(0));
cin >> n >> m;
pos.resize(n);
val.resize(n, 0);
vector<int> tp2;
ac = aho_corasick();
forn(i, n){
string s;
cin >> s;
pos[i] = ac.add(s);
}
forn(i, m){
int t;
cin >> t;
if (t == 1){
int j, x;
cin >> j >> x;
--j;
ac.nodes[pos[j]].vals.erase(ac.nodes[pos[j]].vals.find(val[j]));
val[j] = x;
ac.nodes[pos[j]].vals.insert(val[j]);
}
else{
string q;
cin >> q;
printf("%d\n", ac.feed(q));
}
}
return 0;
}
Решение 2 (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int AL = 26;
vector<vector<pair<int, int>>> upd;
vector<int> ans;
int n, m;
struct segtree{
vector<int*> where;
vector<int> vals;
vector<int> t;
int n;
segtree(){}
segtree(int n) : n(n){
t.assign(4 * n, -1);
where.clear();
vals.clear();
}
void updh(int v, int l, int r, int L, int R, int val){
if (L >= R)
return;
if (l == L && r == R){
where.push_back(&t[v]);
vals.push_back(t[v]);
t[v] = max(t[v], val);
return;
}
int m = (l + r) / 2;
updh(v * 2, l, m, L, min(m, R), val);
updh(v * 2 + 1, m, r, max(m, L), R, val);
}
void upd(int l, int r, int val){
updh(1, 0, n, l, r, val);
}
int geth(int v, int l, int r, int pos){
if (l == r - 1)
return t[v];
int m = (l + r) / 2;
if (pos < m)
return max(t[v], geth(v * 2, l, m, pos));
return max(t[v], geth(v * 2 + 1, m, r, pos));
}
int get(int pos){
return geth(1, 0, n, pos);
}
void rollback(){
*where.back() = vals.back();
where.pop_back();
vals.pop_back();
}
};
segtree st;
struct aho_corasick {
struct node {
map<int, int> nxt, go;
int p, pch;
int suf, ssuf;
vector<int> term, qs;
node() {
nxt.clear();
go.clear();
suf = ssuf = -1;
term.clear();
p = -1, pch = -1;
qs.clear();
}
};
vector<node> nodes;
vector<vector<int>> g;
aho_corasick() {
nodes = vector<node>(1, node());
}
void add(const string& s, int id) {
int v = 0;
forn(i, s.size()) {
int c = s[i] - 'a';
if (!nodes[v].nxt.count(c)) {
nodes.push_back(node());
nodes[v].nxt[c] = int(nodes.size()) - 1;
nodes.back().p = v;
nodes.back().pch = c;
}
v = nodes[v].nxt[c];
}
nodes[v].term.push_back(id);
}
void feed(const string &s, int id){
int v = 0;
forn(i, s.size()){
int c = s[i] - 'a';
v = go(v, c);
nodes[v].qs.push_back(id);
}
}
int go(int v, int c) {
if (nodes[v].go.count(c))
return nodes[v].go[c];
if (nodes[v].nxt.count(c))
return nodes[v].go[c] = nodes[v].nxt[c];
if (v == 0)
return nodes[v].go[c] = 0;
return nodes[v].go[c] = go(suf(v), c);
}
int suf(int v) {
if (nodes[v].suf != -1)
return nodes[v].suf;
if (v == 0 || nodes[v].p == 0)
return nodes[v].suf = 0;
return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
}
void build_tree() {
g.resize(nodes.size());
forn(v, nodes.size()) {
int u = suf(v);
if (v != u)
g[u].push_back(v);
}
}
void dfs(int v){
int cur = st.where.size();
for (auto i : nodes[v].term){
int lst = m;
for (auto it : upd[i]){
st.upd(it.first, lst, it.second);
lst = it.first;
}
st.upd(0, lst, 0);
}
for (auto j : nodes[v].qs){
ans[j] = max(ans[j], st.get(j));
}
for (int u : g[v]){
dfs(u);
}
int nw = st.where.size();
forn(_, nw - cur){
st.rollback();
}
}
};
aho_corasick ac;
int main() {
ios::sync_with_stdio(!cin.tie(0));
cin >> n >> m;
upd.resize(n);
ans.resize(m, -1);
vector<int> tp2;
ac = aho_corasick();
st = segtree(m);
forn(i, n){
string s;
cin >> s;
ac.add(s, i);
}
forn(i, m){
int t;
cin >> t;
if (t == 1){
int j, x;
cin >> j >> x;
--j;
upd[j].push_back(make_pair(i, x));
}
else{
string q;
cin >> q;
ac.feed(q, i);
tp2.push_back(i);
}
}
forn(i, n){
reverse(upd[i].begin(), upd[i].end());
}
ac.build_tree();
ac.dfs(0);
for (auto it : tp2)
cout << ans[it] << "\n";
return 0;
}