Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение (adedalic)
fun main(args: Array<String>) {
val tc = readLine()!!.toInt()
for (i in 1..tc) {
val (n, s, t) = readLine()!!.split(' ').map { it.toInt() }
println(maxOf(n - s, n - t) + 1)
}
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n, m;
string s, t;
vector<int> pos[26];
int main() {
cin >> n >> s;
forn(i, n)
pos[s[i] - 'a'].push_back(i + 1);
cin >> m;
forn(i, m){
cin >> t;
vector<int> cnt(26);
for (auto &c : t)
++cnt[c - 'a'];
int ans = -1;
forn(j, 26) if (cnt[j] > 0)
ans = max(ans, pos[j][cnt[j] - 1]);
cout << ans << "\n";
}
return 0;
}
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int n, m;
int l[N], r[N], s[N];
int d[N];
int dx[N];
int res[N];
int nxt[N];
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < m; ++i){
scanf("%d %d %d", s + i, l + i, r + i);
--l[i], --r[i];
if(s[i] == 1)
++d[l[i]], --d[r[i]];
}
memset(dx, -1, sizeof dx);
int sum = 0;
for(int i = 0; i < n - 1; ++i){
sum += d[i];
if(sum > 0)
dx[i] = 0;
}
res[0] = n;
for(int i = 1; i < n; ++i)
res[i] = res[i - 1] + dx[i - 1];
nxt[n - 1] = n - 1;
for(int i = n - 2; i >= 0; --i){
if(res[i] <= res[i + 1])
nxt[i] = nxt[i + 1];
else
nxt[i] = i;
}
for(int i = 0; i < m; ++i){
if(s[i] != (nxt[l[i]] >= r[i])){
puts("NO");
return 0;
}
}
puts("YES");
for(int i = 0; i < n; ++i)
printf("%d ", res[i]);
puts("");
return 0;
}
1187D - Сортировка подотрезков
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
const int INF = int(1e9) + 99;
int t, n;
int a[N], b[N];
vector <int> p[N];
int st[4 * N + 55];
int getMin(int v, int l, int r, int L, int R){
if(L >= R) return INF;
if(l == L && r == R)
return st[v];
int mid = (l + r) / 2;
return min(getMin(v * 2 + 1, l, mid, L, min(R, mid)),
getMin(v * 2 + 2, mid, r, max(mid, L), R));
}
void upd(int v, int l, int r, int pos, int x){
if(r - l == 1){
st[v] = x;
return;
}
int mid = (l + r) / 2;
if(pos < mid) upd(v * 2 + 1, l, mid, pos, x);
else upd(v * 2 + 2, mid, r, pos, x);
st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
}
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i < n; ++i)
p[i].clear();
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
--a[i];
p[a[i]].push_back(i);
}
for(int i = 0; i < n; ++i){
scanf("%d", b + i);
--b[i];
}
for(int i = 0; i < 4 * n; ++i) st[i] = INF;
for(int i = 0; i < n; ++i){
reverse(p[i].begin(), p[i].end());
if(!p[i].empty()) upd(0, 0, n, i, p[i].back());
}
bool ok = true;
for(int i = 0; i < n; ++i){
if(p[b[i]].empty()){
ok = false;
break;
}
int pos = p[b[i]].back();
if(getMin(0, 0, n, 0, b[i]) < pos){
ok = false;
break;
}
p[b[i]].pop_back();
upd(0, 0, n, b[i], p[b[i]].empty()? INF : p[b[i]].back());
}
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int n;
long long ans;
vector<int> siz;
vector<long long> dp;
vector<vector<int>> g;
int calcsize(int v, int p = -1) {
siz[v] = 1;
for (auto to : g[v]) {
if (to == p) continue;
siz[v] += calcsize(to, v);
}
return siz[v];
}
long long calcdp(int v, int p = -1) {
dp[v] = siz[v];
for (auto to : g[v]) {
if (to == p) continue;
dp[v] += calcdp(to, v);
}
return dp[v];
}
void dfs(int v, int p = -1) {
ans = max(ans, dp[v]);
for (auto to : g[v]) {
if (to == p) continue;
dp[v] -= dp[to];
dp[v] -= siz[to];
siz[v] -= siz[to];
siz[to] += siz[v];
dp[to] += siz[v];
dp[to] += dp[v];
dfs(to, v);
dp[to] -= dp[v];
dp[to] -= siz[v];
siz[to] -= siz[v];
siz[v] += siz[to];
dp[v] += siz[to];
dp[v] += dp[to];
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n;
g = vector<vector<int>>(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
ans = 0;
siz = vector<int>(n);
dp = vector<long long>(n);
calcsize(0);
calcdp(0);
dfs(0);
cout << ans << endl;
return 0;
}
Альтернативное решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
typedef long long li;
using namespace std;
const int N = 200 * 1000 + 13;
int n;
vector<int> g[N];
int siz[N];
li sum[N];
void init(int v, int p = -1){
siz[v] = 1;
sum[v] = 0;
for (auto u : g[v]) if (u != p){
init(u, v);
siz[v] += siz[u];
sum[v] += sum[u];
}
sum[v] += (siz[v] - 1);
}
li dp[N];
void dfs(int v, int p = -1){
dp[v] = 0;
li tot = 0;
for (auto u : g[v]) if (u != p)
tot += sum[u];
for (auto u : g[v]) if (u != p){
dfs(u, v);
dp[v] = max(dp[v], (n - siz[u] - 1) + dp[u] + (tot - sum[u]));
}
if (g[v].size() == 1){
dp[v] = n - 1;
}
}
int main() {
scanf("%d", &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);
}
if (n == 2) {
cout << 3 << endl;
return 0;
}
forn(i, n) if (int(g[i].size()) > 1){
init(i);
dfs(i);
printf("%lld\n", dp[i] + n);
break;
}
return 0;
}
1187F - Ожидаемый квадрат красоты
Разбор
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 MOD = int(1e9) + 7;
int norm(int a) {
while(a >= MOD) a -= MOD;
while(a < 0) a += MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
int ans = 1;
for(; k > 0; k >>= 1) {
if(k & 1)
ans = mul(ans, a);
a = mul(a, a);
}
return ans;
}
int inv(int a) {
int b = binPow(a, MOD - 2);
assert(mul(a, b) == 1);
return b;
}
int n;
vector<int> l, r;
inline bool read() {
if(!(cin >> n))
return false;
l.resize(n);
r.resize(n);
fore(i, 0, n)
cin >> l[i];
fore(i, 0, n) {
cin >> r[i];
r[i]++;
}
return true;
}
vector<int> p;
int calcEq(int i0) {
int i1 = i0 + 1;
int pSame = 0;
if(i0 > 0) {
int cnt = max(0, min({r[i0 - 1], r[i0], r[i1]}) - max({l[i0 - 1], l[i0], l[i1]}));
pSame = mul(cnt, inv(mul(mul(r[i0 - 1] - l[i0 - 1], r[i0] - l[i0]), r[i1] - l[i1])));
}
return norm(1 - norm(2 - p[i0] - p[i1]) + pSame);
}
inline void solve() {
p.assign(n, 0);
p[0] = 1;
fore(i, 1, n) {
int cnt = max(0, min(r[i - 1], r[i]) - max(l[i - 1], l[i]));
p[i] = norm(1 - mul(cnt, inv(mul(r[i - 1] - l[i - 1], r[i] - l[i]))));
}
int sum = 0;
fore(i, 0, n)
sum = norm(sum + p[i]);
int ans = 0;
fore(i, 0, n) {
int curS = sum;
for(int j = max(0, i - 1); j < min(n, i + 2); j++)
curS = norm(curS - p[j]);
ans = norm(ans + mul(p[i], curS));
if(i > 0)
ans = norm(ans + calcEq(i - 1));
ans = norm(ans + p[i]);
if(i + 1 < n)
ans = norm(ans + calcEq(i));
}
cout << ans << 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);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
struct edge
{
int y, c, f, cost;
edge() {};
edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
};
vector<edge> e;
const int N = 14043;
vector<int> g[N];
long long ans = 0;
long long d[N];
int p[N];
int pe[N];
int inq[N];
const long long INF64 = (long long)(1e18);
int s = N - 2;
int t = N - 1;
int rem(int x)
{
return e[x].c - e[x].f;
}
void push_flow()
{
for(int i = 0; i < N; i++) d[i] = INF64, p[i] = -1, pe[i] = -1, inq[i] = 0;
d[s] = 0;
queue<int> q;
q.push(s);
inq[s] = 1;
while(!q.empty())
{
int k = q.front();
q.pop();
inq[k] = 0;
for(auto x : g[k])
{
if(!rem(x)) continue;
int c = e[x].cost;
int y = e[x].y;
if(d[y] > d[k] + c)
{
d[y] = d[k] + c;
p[y] = k;
pe[y] = x;
if(inq[y] == 0)
{
inq[y] = 1;
q.push(y);
}
}
}
}
int cur = t;
// vector<int> zz(1, cur);
while(cur != s)
{
e[pe[cur]].f++;
e[pe[cur] ^ 1].f--;
cur = p[cur];
// zz.push_back(cur);
}
// reverse(zz.begin(), zz.end());
// for(auto x : zz) cerr << x << " ";
// cerr << endl;
ans += d[t];
}
void add_edge(int x, int y, int c, int cost)
{
g[x].push_back(e.size());
e.push_back(edge(y, c, 0, cost));
g[y].push_back(e.size());
e.push_back(edge(x, 0, 0, -cost));
}
int main()
{
int n, m, k, c, d;
cin >> n >> m >> k >> c >> d;
for(int i = 0; i < k; i++)
{
int x;
cin >> x;
--x;
add_edge(s, x, 1, 0);
}
int tt = 101;
for(int i = 0; i < tt; i++)
add_edge(0 + i * n, t, k, i * c);
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
for(int i = 0; i < tt - 1; i++)
for(int j = 0; j < k; j++)
add_edge(x + i * n, y + i * n + n, 1, d * (j * 2 + 1));
for(int i = 0; i < tt - 1; i++)
for(int j = 0; j < k; j++)
add_edge(y + i * n, x + i * n + n, 1, d * (j * 2 + 1));
}
for(int i = 0; i < n; i++)
for(int j = 0; j < tt - 1; j++)
add_edge(i + j * n, i + j * n + n, k, 0);
for(int i = 0; i < k; i++)
push_flow();
cout << ans << endl;
}