Разбор
Tutorial is loading...
Решение (Vovuh, O(n^2))
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
string t;
cin >> n >> k >> t;
int cnt = 1;
int pos = 1;
string ans = t;
while (cnt < k) {
if (pos >= sz(ans)) {
ans += t;
++cnt;
} else {
bool ok = true;
int len = 0;
for (int i = 0; i < sz(t); ++i) {
if (pos + i >= sz(ans)) break;
++len;
if (ans[pos + i] != t[i]) ok = false;
}
if (ok) {
ans += t.substr(len);
++cnt;
}
}
++pos;
}
cout << ans << endl;
return 0;
}
Решение (Vovuh, префикс-функция)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
string t;
cin >> n >> k >> t;
vector<int> p(n);
for (int i = 1; i < sz(t); ++i) {
int j = p[i - 1];
while (j > 0 && t[j] != t[i])
j = p[j - 1];
if (t[i] == t[j])
++j;
p[i] = j;
}
int len = sz(t) - p[n - 1];
for (int i = 0; i < k - 1; ++i)
cout << t.substr(0, len);
cout << t << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
vector<int> a(n);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
int ans = 0;
for (int i = 0; i < n; ++i) {
int j = i;
while (j + 1 < n && a[j + 1] <= a[j] * 2)
++j;
ans = max(ans, j - i + 1);
i = j;
}
printf("%d\n", ans);
}
Разбор
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 = 300 * 1000 + 13;
const int INF = int(1e9);
int n;
int prl[N], prr[N], sul[N], sur[N];
int l[N], r[N];
int main() {
scanf("%d", &n);
forn(i, n)
scanf("%d%d", &l[i], &r[i]);
prl[0] = sul[n] = 0;
prr[0] = sur[n] = INF;
forn(i, n){
prl[i + 1] = max(prl[i], l[i]);
prr[i + 1] = min(prr[i], r[i]);
}
for (int i = n - 1; i >= 0; --i){
sul[i] = max(sul[i + 1], l[i]);
sur[i] = min(sur[i + 1], r[i]);
}
int ans = 0;
forn(i, n)
ans = max(ans, min(prr[i], sur[i + 1]) - max(prl[i], sul[i + 1]));
printf("%d\n", ans);
return 0;
}
1029D - Concatenated Multiples
Разбор
Tutorial is loading...
Решение (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;
const int LOGN = 11;
int n, k;
int a[N];
int len[N];
vector<int> rems[LOGN];
int pw[LOGN];
int main() {
scanf("%d%d", &n, &k);
forn(i, n) scanf("%d", &a[i]);
pw[0] = 1;
forn(i, LOGN - 1)
pw[i + 1] = pw[i] * 10 % k;
forn(i, n){
int x = a[i];
while (x > 0){
++len[i];
x /= 10;
}
rems[len[i]].push_back(a[i] % k);
}
forn(i, LOGN)
sort(rems[i].begin(), rems[i].end());
li ans = 0;
forn(i, n){
for (int j = 1; j < LOGN; ++j){
int rem = (a[i] * li(pw[j])) % k;
int xrem = (k - rem) % k;
auto l = lower_bound(rems[j].begin(), rems[j].end(), xrem);
auto r = upper_bound(rems[j].begin(), rems[j].end(), xrem);
ans += (r - l);
if (len[i] == j && (rem + a[i] % k) % k == 0)
--ans;
}
}
printf("%lld\n", ans);
return 0;
}
1029E - Tree with Small Distances
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 11;
int p[N];
int d[N];
vector<int> g[N];
void dfs(int v, int pr = -1, int dst = 0) {
d[v] = dst;
p[v] = pr;
for (auto to : g[v]) {
if (to != pr) {
dfs(to, v, dst + 1);
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
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);
set<pair<int, int>> st;
for (int i = 0; i < n; ++i) {
if (d[i] > 2) {
st.insert(make_pair(-d[i], i));
}
}
int ans = 0;
while (!st.empty()) {
int v = st.begin()->second;
v = p[v];
++ans;
auto it = st.find(make_pair(-d[v], v));
if (it != st.end()) {
st.erase(it);
}
for (auto to : g[v]) {
auto it = st.find(make_pair(-d[to], to));
if (it != st.end()) {
st.erase(it);
}
}
}
printf("%d\n", ans);
}
Разбор
Tutorial is loading...
Решение (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 = 1000 * 1000;
int lens[N];
int k;
li solve(li a, li b){
k = 0;
for (li i = 1; i * i <= b; ++i)
if (b % i == 0)
lens[k++] = i;
li ans = 2 * (a + b) + 2;
li x = a + b;
int l = 0;
for (li i = 1; i * i <= x; ++i){
if (x % i == 0){
while (l + 1 < k && lens[l + 1] <= i)
++l;
if (b / lens[l] <= x / i)
ans = min(ans, (i + x / i) * 2);
}
}
return ans;
}
int main() {
li a, b;
scanf("%lld%lld", &a, &b);
printf("%lld\n", min(solve(a, b), solve(b, a)));
return 0;
}