Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k1, k2) = readLine()!!.split(' ').map { it.toInt() }
val (w, b) = readLine()!!.split(' ').map { it.toInt() }
if (k1 + k2 >= 2 * w && (n - k1) + (n - k2) >= 2 * b)
println("YES")
else
println("NO")
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int i = s.find("11");
int j = s.rfind("00");
cout << (i != -1 && j != -1 && i < j ? "NO" : "YES") << endl;
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val c = readLine()!!.split(' ').map { it.toInt() }
val mn = intArrayOf(1e9.toInt(), 1e9.toInt())
val rem = longArrayOf(n.toLong(), n.toLong())
var sum = 0L
var ans = 1e18.toLong()
for (i in c.indices) {
mn[i % 2] = minOf(mn[i % 2], c[i])
rem[i % 2]--
sum += c[i]
if (i > 0) {
val cur = sum + rem[0] * mn[0] + rem[1] * mn[1]
ans = minOf(ans, cur)
}
}
println(ans)
}
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e7 + 13;
int main() {
vector<int> mind(N, -1), val(N);
mind[1] = 1;
for (int i = 2; i < N; ++i) if (mind[i] == -1)
for (int j = i; j < N; j += i) if (mind[j] == -1)
mind[j] = i;
for (int i = 2; i < N; ++i) {
int j = i / mind[i];
val[i] = val[j] + (mind[i] != mind[j]);
}
int t;
scanf("%d", &t);
while (t--) {
int c, d, x;
scanf("%d%d%d", &c, &d, &x);
int ans = 0;
for (int i = 1; i * i <= x; ++i) {
if (x % i != 0) continue;
int k1 = x / i + d;
if (k1 % c == 0) ans += 1 << val[k1 / c];
if (i * i == x) continue;
int k2 = i + d;
if (k2 % c == 0) ans += 1 << val[k2 / c];
}
printf("%d\n", ans);
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (awoo)
#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 main() {
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(2, 0)));
int ans = 0;
forn(i, n + 1) forn(j, m + 1){
if (i < n) dp[i + 1][j][0] = add(dp[i + 1][j][0], 1);
if (j < m) dp[i][j + 1][1] = add(dp[i][j + 1][1], 1);
if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][0]);
if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][1]);
if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][0]);
if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][1]);
ans = add(ans, dp[i][j][0]);
ans = add(ans, dp[i][j][1]);
}
forn(i, n){
int j = i;
while (j + 1 < n && s[j] != s[j + 1]) ++j;
int len = j - i + 1;
int val = (len * 1ll * (len + 1) / 2) % MOD * (m + 1) % MOD;
ans = add(ans, -val);
i = j;
}
forn(i, m){
int j = i;
while (j + 1 < m && t[j] != t[j + 1]) ++j;
int len = j - i + 1;
int val = (len * 1ll * (len + 1) / 2) % MOD * (n + 1) % MOD;
ans = add(ans, -val);
i = j;
}
printf("%d\n", ans);
return 0;
}
Решение 2 (awoo)
#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 main() {
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(m + 1, vector<vector<int>>(2, vector<int>(4, 0))));
int ans = 0;
forn(i, n + 1) forn(j, m + 1){
if (i < n) dp[i + 1][j][0][1] = add(dp[i + 1][j][0][1], 1);
if (j < m) dp[i][j + 1][1][2] = add(dp[i][j + 1][1][2], 1);
forn(mask, 4){
if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][0][mask]);
if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][1][mask]);
if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][0][mask]);
if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][1][mask]);
}
ans = add(ans, dp[i][j][0][3]);
ans = add(ans, dp[i][j][1][3]);
}
printf("%d\n", ans);
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#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 k;
vector<vector<int>> g;
vector<vector<int>> dp;
vector<int> d;
int dfs(int v, int p = -1){
dp[v][d[v]] = 1;
int h = 0;
for (int u : g[v]) if (u != p){
int nh = dfs(u, v);
vector<int> tmp(max(h, nh + 1) + 1);
forn(i, h + 1) forn(j, nh + 1){
if (i + j + 1 <= k)
tmp[max(i, j + 1)] = add(tmp[max(i, j + 1)], mul(dp[v][d[v] + i], dp[u][d[u] + j]));
if (i <= k && j <= k)
tmp[i] = add(tmp[i], mul(dp[v][d[v] + i], dp[u][d[u] + j]));
}
h = max(h, nh + 1);
forn(i, h + 1){
dp[v][d[v] + i] = tmp[i];
}
}
return h;
}
int main() {
int n;
scanf("%d%d", &n, &k);
g.resize(n);
dp.resize(n, vector<int>(n, 0));
d.resize(n);
forn(i, n - 1){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(0);
int ans = 0;
forn(i, k + 1) ans = add(ans, dp[0][i]);
printf("%d\n", ans);
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 1000043;
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 global_hash = 0;
void reverse(deque<pair<int, int>>& d)
{
stack<pair<int, int>> s;
while(!d.empty())
{
s.push(d.back());
d.pop_back();
}
while(!s.empty())
{
d.push_front(s.top());
s.pop();
}
}
void safe_push_front(deque<pair<int, int>>& d, int c, int& res)
{
int z = d.front().first ^ 1;
res = add(res, mul(binpow(2, c), z));
d.push_front(make_pair(z, c));
}
void safe_push_back(deque<pair<int, int>>& d, int c, int& res)
{
int z = d.back().first ^ 1;
res = add(res, mul(binpow(2, c), z));
d.push_back(make_pair(z, c));
}
deque<pair<int, int>> ds[N];
struct path
{
int s;
int t;
int d;
int c;
path() {};
path(int s, int t, int d, int c) : s(s), t(t), d(d), c(c) {};
void push_front(int i)
{
safe_push_front(ds[d], i, c);
}
void push_back(int i)
{
safe_push_back(ds[d], i, c);
}
void pop_front()
{
ds[d].pop_front();
}
void pop_back()
{
ds[d].pop_back();
}
int front()
{
return ds[d].front().second;
}
int back()
{
return ds[d].back().second;
}
void reverse()
{
::reverse(ds[d]);
swap(s, t);
}
int size()
{
return ds[d].size();
}
};
path link_to_left(path x, path y)
{
path z = x;
while(y.size() > 0)
{
z.push_back(y.front());
y.pop_front();
}
z.t = y.t;
return z;
}
path link_to_right(path x, path y)
{
path z = y;
while(x.size() > 0)
{
z.push_front(x.back());
x.pop_back();
}
z.s = x.s;
return z;
}
int cur = 0;
path make(int x, int y, int i)
{
int cost = i;
ds[cur].push_back(make_pair(0, cost));
return path(x, y, cur++, 0);
}
set<int> paths;
vector<int> paths_v[N];
path ps[N];
path merge(path x, path y, int v)
{
if(x.size() > y.size())
swap(x, y);
if(y.s == v)
{
if(x.t != v)
x.reverse();
return link_to_right(x, y);
}
else
{
if(x.s != v)
x.reverse();
return link_to_left(y, x);
}
}
int cur2 = 0;
void modify(vector<int>& v, int x, int y)
{
for(int i = 0; i < v.size(); i++)
if(v[i] == x)
v[i] = y;
}
void reassign(path p, int x, int y)
{
modify(paths_v[p.s], x, y);
modify(paths_v[p.t], x, y);
}
void merge_paths(int x, int y, int v)
{
if(x == y)
{
}
else
{
global_hash = sub(global_hash, ps[x].c);
global_hash = sub(global_hash, ps[y].c);
ps[cur2++] = merge(ps[x], ps[y], v);
paths.erase(x);
paths.erase(y);
paths.insert(cur2 - 1);
reassign(ps[x], x, cur2 - 1);
reassign(ps[y], y, cur2 - 1);
global_hash = add(global_hash, ps[cur2 - 1].c);
}
}
void relax(int v)
{
while(paths_v[v].size() >= 2)
{
int x = paths_v[v].back();
paths_v[v].pop_back();
int y = paths_v[v].back();
paths_v[v].pop_back();
merge_paths(x, y, v);
}
}
void add_edge(int x, int y, int i)
{
//cerr << x << " " << y << " " << i << endl;
int c = cur2;
ps[cur2++] = make(x, y, i);
paths_v[x].push_back(c);
paths_v[y].push_back(c);
paths.insert(c);
relax(x);
relax(y);
}
void print_coloring()
{
vector<int> ans;
for(auto x : paths)
{
for(auto y : ds[ps[x].d])
{
if(y.first == 1)
ans.push_back(y.second);
}
}
printf("%d", int(ans.size()));
for(auto x : ans)
printf(" %d", x);
puts("");
fflush(stdout);
}
int e = 0;
void process_query()
{
int t;
scanf("%d", &t);
if(t == 1)
{
int x, y;
scanf("%d %d", &x, &y);
y += 200001;
add_edge(x, y, ++e);
printf("%d\n", global_hash);
fflush(stdout);
}
else
print_coloring();
}
void print_info()
{
cerr << "Paths\n";
for(auto x : paths)
cerr << x << " start: " << ps[x].s << " " << " end: " << ps[x].t << endl;
cerr << "Vertices\n";
for(int i = 0; i < N; i++)
if(!paths_v[i].empty())
{
cerr << i << ": ";
for(auto x : paths_v[i])
cerr << x << " ";
cerr << endl;
}
}
int main()
{
int n1, n2, m;
scanf("%d %d %d", &n1, &n2, &m);
for(int i = 0; i < m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
y += 200001;
add_edge(x, y, ++e);
}
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
//print_info();
process_query();
}
}