Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n = int(input())
s = input()
print("NO" if s.count('1') == n else "YES")
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main(args: Array<String>) {
repeat(readln().toInt()) {
val (n, p, l, t) = readln().split(' ').map { it.toLong() }
val cntTasks = (n + 6) / 7
fun calc(k: Long) = k * l + minOf(2 * k, cntTasks) * t
var lf = 0L
var rg = n
while (rg - lf > 1) {
val mid = (lf + rg) / 2
if (calc(mid) >= p)
rg = mid
else
lf = mid
}
println(n - rg)
}
}
Разбор
Tutorial is loading...
Решение (awoo)
from math import gcd
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
g = 0
for i in range(n - 1):
g = gcd(g, a[i + 1] - a[i])
g = max(g, 1)
a.sort()
j = n - 1
res = a[-1]
while True:
while j >= 0 and a[j] > res:
j -= 1
if j < 0 or a[j] != res:
break
res -= g
print((a[-1] * (n + 1) - (sum(a) + res)) // g)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
using pt = pair<int, int>;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector<pt> pos(n + 1);
for (int i = 0; i < n; ++i) {
pos[i + 1].x = pos[i].x + (s[i] == 'R') - (s[i] == 'L');
pos[i + 1].y = pos[i].y + (s[i] == 'U') - (s[i] == 'D');
}
map<pt, vector<int>> mp;
for (int i = 0; i <= n; ++i) mp[pos[i]].push_back(i);
auto check = [&](pt p, int l, int r) {
if (!mp.count(p)) return false;
auto it = lower_bound(mp[p].begin(), mp[p].end(), l);
return it != mp[p].end() && *it <= r;
};
while (q--) {
int x, y, l, r;
cin >> x >> y >> l >> r;
int nx = pos[r].x + pos[l - 1].x - x, ny = pos[r].y + pos[l - 1].y - y;
bool f = check({x, y}, 0, l - 1)
| check({nx, ny}, l, r - 1)
| check({x, y}, r, n);
cout << (f ? "YES" : "NO") << '\n';
}
}
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(1e6) + 99;
int nxt;
int to[N][26];
int sum[N];
long long res;
void add(const string& s) {
int v = 0;
++sum[v];
for (auto c : s) {
int i = c - 'a';
if (to[v][i] == -1)
to[v][i] = nxt++;
v = to[v][i];
++sum[v];
}
}
void upd(const string& s) {
int curLen = s.size();
int v = 0;
for (auto c : s) {
int i = c - 'a';
if (to[v][i] == -1) {
res += sum[v] * 1LL * curLen;
break;
} else {
int nxtV = to[v][i];
res += (sum[v] - sum[nxtV]) * 1LL * curLen;
--curLen;
v = nxtV;
}
}
}
void solve(int n, vector <string> v) {
int sumSizes = 0;
for (int i = 0; i < n; ++i)
sumSizes += v[i].size();
nxt = 1;
memset(sum, 0, sizeof sum);
memset(to, -1, sizeof to);
for(int i = 0; i < n; ++i)
add(v[i]);
for (int i = 0; i < n; ++i) {
reverse(v[i].begin(), v[i].end());
upd(v[i]);
}
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector <string> v(n);
for (int i = 0; i < n; ++i)
cin >> v[i];
res = 0;
solve(n, v);
for(int i = 0; i < n; ++i)
reverse(v[i].end(), v[i].end());
solve(n, v);
cout << res << endl;
return 0;
}
1902F - Снова деревья и XOR-запросы
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 200043;
const int K = 20;
typedef array<int, K> base;
int a[N];
vector<int> g[N];
vector<int> path_up[N];
int tin[N], tout[N];
int T = 0;
int fup[N][K];
base make_empty()
{
base b;
for(int i = 0; i < K; i++)
b[i] = 0;
return b;
}
int reduce(const base& b, int x)
{
for(int i = K - 1; i >= 0; i--)
if(x & (1 << i))
x ^= b[i];
return x;
}
bool add(base& b, int x)
{
x = reduce(b, x);
if(x != 0)
{
for(int i = K - 1; i >= 0; i--)
if(x & (1 << i))
{
b[i] = x;
return true;
}
}
return false;
}
bool check(const base& b, int x)
{
return reduce(b, x) == 0;
}
vector<int> rebuild_path(const vector<int>& path, int v)
{
base b = make_empty();
vector<int> ans;
if(add(b, a[v])) ans.push_back(v);
for(auto x : path) if(add(b, a[x])) ans.push_back(x);
return ans;
}
void dfs(int v, int u)
{
tin[v] = T++;
if(u == v)
path_up[v] = rebuild_path(vector<int>(0), v);
else
path_up[v] = rebuild_path(path_up[u], v);
fup[v][0] = u;
for(int i = 1; i < K; i++)
fup[v][i] = fup[fup[v][i - 1]][i - 1];
for(auto y : g[v])
if(y != u)
dfs(y, v);
tout[v] = T++;
}
bool is_ancestor(int u, int v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int x, int y)
{
if(is_ancestor(x, y)) return x;
for(int i = K - 1; i >= 0; i--)
if(!is_ancestor(fup[x][i], y))
x = fup[x][i];
return fup[x][0];
}
bool query(int x, int y, int k)
{
base b = make_empty();
int z = LCA(x, y);
for(auto v : path_up[x])
if(!is_ancestor(v, y))
add(b, a[v]);
for(auto v : path_up[y])
if(!is_ancestor(v, x))
add(b, a[v]);
add(b, a[z]);
return check(b, k);
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(0, 0);
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
int x, y, k;
scanf("%d %d %d", &x, &y, &k);
--x;
--y;
if(query(x, y, k)) puts("YES");
else puts("NO");
}
}