Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n = int(input())
p = [int(x) - 1 for x in input().split()]
ans = 3
for i in range(n):
if p[p[i]] == i:
ans = 2
print(ans)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readln().toInt()) {
val s = readln().map { it.code - '0'.code }
val zeroes = s.count { it == 0 }
val cnt = intArrayOf(0, 0)
var ans = 0L
for (c in s) {
cnt[c]++
if (c == 0)
ans += if (cnt[1] > 0) 1 else 0
else
ans += (zeroes - cnt[0])
}
println(ans)
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
const li INF = 1e18;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<li> a(n);
for (auto& x : a) cin >> x;
vector<vector<li>> dp(n + 1, vector<li>(k + 1, INF));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
li mn = INF;
for (int d = 0; j + d <= k && i + d < n; ++d) {
mn = min(mn, a[i + d]);
dp[i + d + 1][j + d] = min(dp[i + d + 1][j + d], dp[i][j] + (d + 1) * mn);
}
}
}
cout << *min_element(dp[n].begin(), dp[n].end()) << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
using li = long long;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return b[i] > b[j];
});
li f = 0, p = 0;
for (int i : ord) p += max(0, b[i] - a[i]);
li ans = 0;
multiset<int> s;
if (sz(s) == k) ans = max(ans, p - f);
for (int i : ord) {
p -= max(0, b[i] - a[i]);
s.insert(a[i]);
f += a[i];
if (sz(s) > k) {
f -= *s.rbegin();
s.erase(--s.end());
}
if (sz(s) == k) ans = max(ans, p - f);
}
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
vector<int> t, p;
void push(int v) {
if (v * 2 + 2 >= sz(t)) return;
t[v * 2 + 1] += p[v]; p[v * 2 + 1] += p[v];
t[v * 2 + 2] += p[v]; p[v * 2 + 2] += p[v];
p[v] = 0;
}
void upd(int v, int l, int r, int L, int R, int x) {
if (L >= R) return;
if (l == L && r == R) {
t[v] += x; p[v] += x;
return;
}
int m = (l + r) / 2;
push(v);
upd(v * 2 + 1, l, m, l, min(m, R), x);
upd(v * 2 + 2, m, r, max(m, L), R, x);
t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}
int get(int v, int l, int r, int L, int R) {
if (L >= R) return 1e9;
if (l == L && r == R) return t[v];
int m = (l + r) / 2;
push(v);
return min(
get(v * 2 + 1, l, m, l, min(m, R)),
get(v * 2 + 2, m, r, max(m, L), R)
);
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x, --x;
t = p = vector<int>(4 * n);
vector<vector<int>> pos(n);
int ans = 0, st = 0;
for (int i = 0; i < n; ++i) {
int x = a[i];
pos[x].push_back(i);
int k = sz(pos[x]);
if (k > 0) upd(0, 0, n, st, pos[x][k - 1] + 1, +1);
if (k > 1) upd(0, 0, n, st, pos[x][k - 2] + 1, -2);
if (k > 2) upd(0, 0, n, st, pos[x][k - 3] + 1, +1);
if (get(0, 0, n, st, i + 1) == 0) {
ans += 1;
st = i + 1;
}
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rnd(12341234);
int n, k;
vector<int> deck;
vector<int> dp;
vector<vector<bool>> odd;
vector<bool> full_odd;
vector<long long> val;
vector<long long> hs;
bool bad(const vector<bool>& v)
{
for(int i = 0; i < k; i++)
if(!v[i])
return false;
return true;
}
vector<bool> inv(const vector<bool>& v)
{
vector<bool> res(k);
for(int i = 0; i < k; i++)
res[i] = !v[i];
return res;
}
vector<bool> get_suffix(int l)
{
vector<bool> v(k);
for(int i = l; i < n; i++) v[deck[i]] = !v[deck[i]];
return v;
}
int get_next(long long cur, int x)
{
for(int i = x; i <= n; i += 2)
if(hs[i] == cur)
return i;
return -1;
}
int main()
{
cin >> n >> k;
deck.resize(n);
for(int i = 0; i < n; i++) cin >> deck[i];
for(int i = 0; i < n; i++) --deck[i];
val.resize(k);
for(int i = 0; i < k; i++)
while(val[i] == 0)
val[i] = rnd();
int max_score = 0;
dp.resize(n + 1);
full_odd.resize(k);
odd.resize(n + 1, vector<bool>(k));
hs.resize(n + 1);
long long cur_hash = 0;
for(int i = 0; i < n; i++)
{
cur_hash ^= val[deck[i]];
if(full_odd[deck[i]]) max_score++;
full_odd[deck[i]] = !full_odd[deck[i]];
odd[i + 1] = full_odd;
hs[i + 1] = cur_hash;
}
for(int i = k; i <= n; i++)
dp[i] = 1e9;
long long start = 0ll;
for(int i = 0; i < k; i++) start ^= val[i];
int pos = get_next(start, k);
if(pos == -1)
{
cout << max_score << endl;
}
else
{
dp[pos] = 0;
int ans = 1e9;
for(int p = k; p <= n; p += 2)
{
if(dp[p] > 1e8) continue;
vector<bool> suff = get_suffix(p);
vector<int> o, e;
for(int j = 0; j < k; j++)
if(suff[j])
e.push_back(j);
else
o.push_back(j);
int es = e.size();
int os = o.size();
bool flag = true;
for(int i = 0; i < os && flag; i++)
for(int j = 0; j < i && flag; j++)
{
int x = o[i];
int y = o[j];
int add = 0;
long long h = hs[p] ^ val[x] ^ val[y];
int pos = get_next(h, p);
if(pos == -1)
{
flag = false;
ans = min(ans, dp[p] + add);
}
else
dp[pos] = min(dp[pos], dp[p] + add);
}
for(int i = 0; i < os && flag; i++)
for(int j = 0; j < es && flag; j++)
{
int x = o[i];
int y = e[j];
int add = 1;
long long h = hs[p] ^ val[x] ^ val[y];
int pos = get_next(h, p);
if(pos == -1)
{
flag = false;
ans = min(ans, dp[p] + add);
}
else
dp[pos] = min(dp[pos], dp[p] + add);
}
for(int i = 0; i < es && flag; i++)
for(int j = 0; j < i && flag; j++)
{
int x = e[i];
int y = e[j];
int add = 2;
long long h = hs[p] ^ val[x] ^ val[y];
int pos = get_next(h, p);
if(pos == -1)
{
flag = false;
ans = min(ans, dp[p] + add);
}
else
dp[pos] = min(dp[pos], dp[p] + add);
}
}
cout << max_score - ans << endl;
}
}