1073A - Разнообразная подстрока
Разбор
Tutorial is loading...
Решение (PikMike)
n = int(input())
s = input()
for i in range(n - 1):
if (s[i] != s[i + 1]):
print("YES")
print(s[i], s[i + 1], sep="")
exit(0)
print("NO")
Разбор
Tutorial is loading...
Решение (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 9;
int n;
int a[N];
int b[N];
bool u[N];
int main() {
// freopen("input.txt", "r", stdin);
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", a + i);
}
for(int i = 0; i < n; ++i){
scanf("%d", b + i);
}
int pos = 0;
for(int i = 0; i < n; ++i){
int x = b[i];
if(u[x]){
printf("0 ");
continue;
}
int cnt = 0;
while(true){
++cnt;
u[a[pos]] = true;
if(a[pos] == x) break;
++pos;
}
++pos;
printf("%d ", cnt);
}
puts("");
return 0;
}
Разбор
Tutorial is loading...
Решение (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
const int N = int(1e5) + 9;
string s;
int n;
int x, y;
void upd(pair<int, int> &pos, char mv, int d){
if(mv == 'U')
pos.second += d;
if(mv == 'D')
pos.second -= d;
if(mv == 'L')
pos.first -= d;
if(mv == 'R')
pos.first += d;
}
bool can(pair<int, int> u, pair<int, int> v, int len){
int d = abs(u.first - v.first) + abs(u.second - v.second);
if(d % 2 != len % 2) return false;
return len >= d;
}
bool ok(int len){
pair<int, int> pos = make_pair(0, 0);
for(int i = len; i < n; ++i)
upd(pos, s[i], 1);
int l = 0, r = len;
while(true){
if(can(pos, make_pair(x, y), len))
return true;
if(r == n) break;
upd(pos, s[l++], 1);
upd(pos, s[r++], -1);
}
return false;
}
int main() {
//freopen("input.txt", "r", stdin);
cin >> n;
cin >> s;
cin >> x >> y;
if(!ok(n)){
puts("-1");
return 0;
}
int l = -1, r = n;
while(r - l > 1){
int mid = (l + r) / 2;
if(ok(mid)) r = mid;
else l = mid;
}
cout << r << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 200 * 1000 + 13;
typedef long long li;
int n;
int a[N];
void get(li T, li& pr, li& cnt){
pr = 0, cnt = 0;
forn(i, n){
if (T >= a[i]){
T -= a[i];
pr += a[i];
++cnt;
}
}
}
int main() {
li T;
scanf("%d%lld", &n, &T);
forn(i, n)
scanf("%d", &a[i]);
int mn = *min_element(a, a + n);
li ans = 0;
while (T >= mn){
li pr, cnt;
get(T, pr, cnt);
ans += cnt * (T / pr);
T %= pr;
}
printf("%lld\n", ans);
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<long long, int> pt;
const int N = 20;
const int M = 1 << 10;
const int MOD = 998244353;
int k;
int pw10[N];
int bitCnt[M];
pt dp[N][M][2];
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 calc(const string &s) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
dp[i][j][0] = dp[i][j][1] = { 0ll, 0 };
}
}
int len = s.size();
dp[0][0][1] = { 1ll, 0 };
for (int i = 0; i < len; ++i) {
int cdig = s[i] - '0';
for (int mask = 0; mask < M; ++mask) {
if (dp[i][mask][0].x == 0 && dp[i][mask][1].x == 0) continue;
for (int dig = (i == 0); dig <= 9; ++dig) {
int nmask = mask | (1 << dig);
long long cnt = dp[i][mask][0].x;
int sum = add(dp[i][mask][0].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
dp[i + 1][nmask][0].x += cnt;
dp[i + 1][nmask][0].y = add(dp[i + 1][nmask][0].y, sum);
}
for (int dig = (i == 0); dig <= cdig; ++dig) {
int nmask = mask | (1 << dig);
long long cnt = dp[i][mask][1].x;
int sum = add(dp[i][mask][1].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
dp[i + 1][nmask][dig == cdig].x += cnt;
dp[i + 1][nmask][dig == cdig].y = add(dp[i + 1][nmask][dig == cdig].y, sum);
}
}
}
int ans = 0;
for (int mask = 0; mask < M; ++mask) {
if (bitCnt[mask] > k) continue;
ans = add(ans, dp[len][mask][0].y);
ans = add(ans, dp[len][mask][1].y);
}
return ans;
}
int calc(long long n) {
int len = to_string(n).size();
int ans = 0;
for (int l = 1; l < len; ++l) {
ans = add(ans, calc(string(l, '9')));
}
ans = add(ans, calc(to_string(n)));
return ans;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
pw10[0] = 1;
for (int i = 1; i < N; ++i) {
pw10[i] = mul(pw10[i - 1], 10);
}
for (int i = 0; i < M; ++i) {
bitCnt[i] = __builtin_popcount(i);
}
long long l, r;
cin >> l >> r >> k;
int ans = add(calc(r), -calc(l - 1));
cout << ans << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define size(a) int((a).size())
typedef pair<int, int> pt;
const int N = 200 * 1000 + 11;
int n;
vector<int> g[N];
int p[N];
int dist[N];
bool bad[N];
int value[N];
pt res[N];
vector<pt> best[N];
void dfs(int v, int par = -1, int d = 0) {
p[v] = par;
dist[v] = d;
for (auto to : g[v]) {
if (to == par) {
continue;
}
dfs(to, v, d + 1);
}
}
int getFarthest(int v) {
dfs(v);
int res = v;
for (int i = 0; i < n; ++i) {
if (bad[i]) {
continue;
}
if (dist[res] < dist[i]) {
res = i;
}
}
return res;
}
pt get(int v) {
return { dist[v], value[v] };
}
int getBetter(int v, int u) {
if (get(v) > get(u)) {
return v;
}
return u;
}
int getBest(int v, int par) {
int res = v;
for (auto to : g[v]) {
if (to == par || bad[to]) {
continue;
}
res = getBetter(res, getBest(to, v));
}
return res;
}
pt calc(int v) {
dfs(v);
vector<int> ch;
for (auto to : g[v]) {
if (!bad[to]) {
ch.push_back(to);
}
}
if (size(ch) == 1) {
return { v, ch[0] };
}
vector<int> pref(size(ch));
vector<int> suf(size(ch));
vector<int> best(size(ch));
for (int i = 0; i < size(ch); ++i) {
int to = ch[i];
best[i] = pref[i] = suf[i] = getBest(to, v);
}
for (int i = 1; i < size(ch); ++i) {
pref[i] = getBetter(pref[i], pref[i - 1]);
suf[size(ch) - i - 1] = getBetter(suf[size(ch) - i - 1], suf[size(ch) - i]);
}
pt ans = { -1, -1 };
pt res = { 0, 0 };
for (int i = 0; i < size(ch); ++i) {
int bst = -1;
if (i == 0) {
bst = suf[i + 1];
} else if (i + 1 == size(ch)) {
bst = pref[i - 1];
} else {
bst = getBetter(pref[i - 1], suf[i + 1]);
}
pt curRes = { dist[bst] + dist[best[i]], value[bst] + value[best[i]] };
if (res < curRes) {
res = curRes;
ans = { best[i], bst };
}
}
return ans;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> 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);
}
int root = -1;
for (int i = 0; i < n; ++i) {
if (size(g[i]) > 2) {
root = i;
dfs(i);
break;
}
}
for (int i = 0; i < n; ++i) {
if (size(g[i]) != 1) {
continue;
}
int v = i;
while (size(g[v]) < 3) {
bad[v] = true;
v = p[v];
}
best[v].push_back({dist[i] - dist[v], i});
}
for (int i = 0; i < n; ++i) {
if (size(best[i]) >= 2) {
sort(best[i].rbegin(), best[i].rend());
value[i] = best[i][0].first + best[i][1].first;
res[i] = { best[i][0].second, best[i][1].second };
}
}
int u = getFarthest(root);
int v = getFarthest(u);
vector<int> path;
while (v != u) {
path.push_back(v);
v = p[v];
}
path.push_back(u);
pt ans = calc(path[size(path) / 2]);
printf("%d %d\n", res[ans.x].x + 1, res[ans.y].x + 1);
printf("%d %d\n", res[ans.x].y + 1, res[ans.y].y + 1);
return 0;
}
1073G - Очередная задача на строки
Разбор
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;
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) {
out << "[";
fore(i, 0, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int N = 200 * 1000 + 555;
const int LOGN = 18;
int n, q;
char s[N];
bool read() {
if(!(cin >> n >> q))
return false;
assert(scanf("%s", s) == 1);
return true;
}
int c[N], id[N], lcp[N];
int mn[LOGN][N];
int lg2[N];
void buildSuffArray() {
s[n++] = '$';
for(int l = 1; l < 2 * n; l <<= 1) {
vector< pair<pt, int> > d;
fore(i, 0, n)
d.emplace_back(l == 1 ? pt(s[i], 0) : pt(c[i], c[(i + (l >> 1)) % n]), i);
stable_sort(d.begin(), d.end());
c[d[0].y] = 0;
fore(i, 1, n)
c[d[i].y] = c[d[i - 1].y] + (d[i].x != d[i - 1].x);
if(c[d.back().y] == n - 1)
break;
}
fore(i, 0, n)
id[c[i]] = i;
int l = 0;
fore(i, 0, n) {
if(c[i] == n - 1)
continue;
l = max(0, l - 1);
int j = id[c[i] + 1];
while(i + l < n && j + l < n && s[i + l] == s[j + l])
l++;
lcp[c[i]] = l;
}
n--;
lg2[0] = lg2[1] = 0;
fore(i, 2, N) {
lg2[i] = lg2[i - 1];
if((1 << (lg2[i] + 1)) <= i)
lg2[i]++;
}
fore(i, 0, n)
mn[0][i] = lcp[i];
fore(pw, 1, LOGN) fore(i, 0, n) {
mn[pw][i] = mn[pw - 1][i];
if(i + (1 << (pw - 1)) < n)
mn[pw][i] = min(mn[pw][i], mn[pw - 1][i + (1 << (pw - 1))]);
}
}
int getMin(int l, int r) {
int ln = lg2[r - l];
return min(mn[ln][l], mn[ln][r - (1 << ln)]);
}
int getLCP(int i, int j) {
if(i == j) return n - i;
i = c[i], j = c[j];
return getMin(min(i, j), max(i, j));
}
bool cmp(const pt &a, const pt &b) {
if(a.x == b.x)
return a.y < b.y;
int l = getLCP(a.x, b.x);
return s[a.x + l] < s[b.x + l];
}
void solve() {
buildSuffArray();
fore(_, 0, q) {
int k, l;
assert(scanf("%d%d", &k, &l) == 2);
vector<int> a(k), b(l);
fore(i, 0, k)
assert(scanf("%d", &a[i]) == 1), a[i]--;
fore(j, 0, l)
assert(scanf("%d", &b[j]) == 1), b[j]--;
li ans = 0;
vector<pt> c;
for(auto v : a)
c.emplace_back(v, 1);
for(auto v : b)
c.emplace_back(v, 0);
sort(c.begin(), c.end(), cmp);
fore(k, 0, 2) {
li sum = 0;
map<int, int> cnt;
fore(i, 0, sz(c)) {
int id = c[i].x, tp = c[i].y;
if(tp == 0)
ans += sum;
else {
cnt[n - id]++;
sum += (n - id);
}
if(i + 1 < sz(c)) {
int len = getLCP(c[i].x, c[i + 1].x);
while(!cnt.empty()) {
auto it = --cnt.end();
if(it->x <= len)
break;
sum -= it->x * 1ll * it->y;
cnt[len] += it->y;
sum += it->y * 1ll * len;
cnt.erase(it);
}
}
}
reverse(c.begin(), c.end());
}
printf("%lld\n", ans);
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
#endif
}
return 0;
}