Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
cout << (count(s.begin(), s.end(), 'N') == 1 ? "NO\n" : "YES\n");
}
}
1620B - Треугольники на прямоугольнике
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
w, h = map(int, input().split())
ans = 0
for i in range(4):
a = [int(x) for x in input().split()][1:]
ans = max(ans, (a[-1] - a[0]) * (h if i < 2 else w))
print(ans)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n, k, x = map(int, input().split())
x -= 1
s = input()[::-1]
res = []
i = 0
while i < n:
if s[i] == 'a':
res.append(s[i])
else:
j = i
while j + 1 < n and s[j + 1] == s[i]:
j += 1
cur = (j - i + 1) * k + 1
res.append('b' * (x % cur))
x //= cur
i = j
i += 1
print(''.join(res[::-1]))
Идея: 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())
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
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;
}
bool p(int val, int c1, int c2, int c3) {
fore (cur1, 0, c1 + 1) fore (cur2, 0, c2 + 1) {
if (cur1 + 2 * cur2 > val)
continue;
if ((val - cur1 - 2 * cur2) % 3 != 0)
continue;
if ((val - cur1 - 2 * cur2) / 3 <= c3)
return true;
}
return false;
}
bool possible(int c1, int c2, int c3) {
for (int v : a) {
if (!p(v, c1, c2, c3))
return false;
}
return true;
}
inline void solve() {
int m = *max_element(a.begin(), a.end());
int ans = int(1e9);
const int MAG = 3;
fore (c1, 0, MAG) fore (c2, 0, MAG) {
int c3 = max(0, (m - c1 - 2 * c2 + 2) / 3);
assert(c1 + 2 * c2 + 3 * c3 >= m);
if (possible(c1, c2, c3))
ans = min(ans, c1 + c2 + c3);
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int t; cin >> t;
while(t--) {
read();
solve();
}
return 0;
}
Идея: Neon
Разбор
Tutorial is loading...
Решение 1 (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 500 * 1000 + 13;
int main() {
int q;
scanf("%d", &q);
vector<int> t(q), x(q), y(q);
for (int i = 0; i < q; ++i) {
scanf("%d%d", &t[i], &x[i]);
if (t[i] == 2) scanf("%d", &y[i]);
}
vector<int> p(N);
iota(p.begin(), p.end(), 0);
vector<int> ans;
for (int i = q - 1; i >= 0; --i) {
if (t[i] == 1) {
ans.push_back(p[x[i]]);
} else {
p[x[i]] = p[y[i]];
}
}
reverse(ans.begin(), ans.end());
for (int &x : ans) printf("%d ", x);
}
Решение 2 (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 500 * 1000 + 13;
int n, q;
vector<int> pos[N];
int main() {
scanf("%d", &q);
while (q--) {
int t, x, y;
scanf("%d", &t);
if (t == 1) {
scanf("%d", &x);
pos[x].push_back(n++);
} else {
scanf("%d%d", &x, &y);
if (x != y) {
if (pos[x].size() > pos[y].size()) pos[x].swap(pos[y]);
for (int &i : pos[x]) pos[y].push_back(i);
pos[x].clear();
}
}
}
vector<int> ans(n);
for (int x = 0; x < N; ++x)
for (int &i : pos[x])
ans[i] = x;
for (int &x : ans) printf("%d ", x);
}
Разбор
Tutorial is loading...
Решение 1 (Neon)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int INF = 1e9;
const int N = 1000 * 1000 + 13;
int n;
int p[N], a[N];
int dp[N][2][2];
pair<int, int> pr[N][2][2];
void solve() {
scanf("%d", &n);
forn(i, n) scanf("%d", &p[i]);
forn(i, n) forn(pos, 2) forn(sg, 2)
dp[i][pos][sg] = INF;
dp[0][0][0] = dp[0][0][1] = -INF;
forn(i, n - 1) forn(pos, 2) forn(sg, 2) if (dp[i][pos][sg] != INF) {
forn(nsg, 2) {
int x = sg ? -p[i] : p[i];
int y = dp[i][pos][sg];
if (pos) swap(x, y);
int z = nsg ? -p[i + 1] : p[i + 1];
if (z > x) {
if (dp[i + 1][0][nsg] > y) {
dp[i + 1][0][nsg] = y;
pr[i + 1][0][nsg] = make_pair(pos, sg);
}
} else if (z > y) {
if (dp[i + 1][1][nsg] > x) {
dp[i + 1][1][nsg] = x;
pr[i + 1][1][nsg] = make_pair(pos, sg);
}
}
}
}
int pos = -1, sg = -1;
forn(j, 2) forn(k, 2) if (dp[n - 1][j][k] != INF)
pos = j, sg = k;
if (pos == -1) {
puts("NO");
return;
}
for (int i = n - 1; i >= 0; i--) {
a[i] = sg ? -p[i] : p[i];
tie(pos, sg) = pr[i][pos][sg];
}
puts("YES");
forn(i, n) printf("%d ", a[i]);
puts("");
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
}
Решение 2 (Neon)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int INF = 1e9;
const int N = 1000 * 1000 + 13;
int n;
int p[N], a[N];
int dp[N][2], pr[N][2];
void solve() {
scanf("%d", &n);
forn(i, n) scanf("%d", &p[i]);
forn(i, n) forn(j, 2) dp[i][j] = INF;
dp[0][0] = dp[0][1] = -INF;
forn(i, n - 1) forn(j, 2) if (dp[i][j] != INF) {
int x = j ? -p[i] : p[i];
int y = dp[i][j];
if (x < y) swap(x, y);
forn(nj, 2) {
int z = nj ? -p[i + 1] : p[i + 1];
if (z > x) {
if (dp[i + 1][nj] > y) {
dp[i + 1][nj] = y;
pr[i + 1][nj] = j;
}
} else if (z > y) {
if (dp[i + 1][nj] > x) {
dp[i + 1][nj] = x;
pr[i + 1][nj] = j;
}
}
}
}
int j = -1;
forn(i, 2) if (dp[n - 1][i] != INF) j = i;
if (j == -1) {
puts("NO");
return;
}
for (int i = n - 1; i >= 0; i--) {
a[i] = j ? -p[i] : p[i];
j = pr[i][j];
}
puts("YES");
forn(i, n) printf("%d ", a[i]);
puts("");
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
}
1620G - Подпоследовательности повсюду
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 23;
const int A = 26;
const int S = 20043;
int n;
string inp[N];
char buf[S];
int cnt[N][A];
const int MOD = 998244353;
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;
}
void flip_all(vector<int>& a)
{
int msk = (1 << n) - 1;
for(int i = 0; i < (1 << (n - 1)); i++)
swap(a[i], a[i ^ msk]);
}
int val[S];
int* where[S];
int cur = 0;
void change(int& x, int y)
{
where[cur] = &x;
val[cur] = x;
x = y;
cur++;
}
void rollback()
{
--cur;
(*where[cur]) = val[cur];
}
void zeta_transform(vector<int>& a)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < (1 << n); j++)
if((j & (1 << i)) == 0)
a[j ^ (1 << i)] = add(a[j ^ (1 << i)], a[j]);
}
}
void mobius_transform(vector<int>& a)
{
for(int i = n - 1; i >= 0; i--)
{
for(int j = (1 << n) - 1; j >= 0; j--)
if((j & (1 << i)) != 0)
a[j] = sub(a[j], a[j ^ (1 << i)]);
}
}
int cur_max[A];
vector<int> mask_cnt;
void rec(int depth, int mask)
{
if(depth == n)
{
mask_cnt[mask] = 1;
for(int i = 0; i < A; i++)
mask_cnt[mask] = mul(mask_cnt[mask], cur_max[i] + 1);
}
else
{
int state = cur;
for(int i = 0; i < A; i++)
change(cur_max[i], min(cur_max[i], cnt[depth][i]));
rec(depth + 1, mask + (1 << depth));
while(state != cur) rollback();
rec(depth + 1, mask);
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%s", buf);
inp[i] = buf;
for(auto x : inp[i])
cnt[i][x - 'a']++;
}
for(int i = 0; i < A; i++)
cur_max[i] = S;
mask_cnt.resize(1 << n);
rec(0, 0);
flip_all(mask_cnt);
mobius_transform(mask_cnt);
flip_all(mask_cnt);
int sum = 0;
for(int i = 0; i < (1 << n); i++) sum = add(sum, mask_cnt[i]);
zeta_transform(mask_cnt);
vector<int> res(1 << n);
for(int i = 0; i < (1 << n); i++)
res[i] = sub(sum, mask_cnt[((1 << n) - 1) ^ i]);
long long ans = 0;
for(int i = 0; i < (1 << n); i++)
{
int c = 0, s = 0;
for(int j = 0; j < n; j++)
{
if(i & (1 << j))
{
c++;
s += j + 1;
}
}
ans ^= res[i] * 1ll * c * 1ll * s;
}
//for(int i = 0; i < (1 << n); i++) printf("%d\n", res[i]);
printf("%lld\n", ans);
}