# 2022icpc西安（The 2022 ICPC Asia Xian Regional Contest）()-其他

## 2022icpc西安（The 2022 ICPC Asia Xian Regional Contest）()

### C

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
i64 a, b, c;
cin >> a >> b >> c;
i64 tmp = 1;
i64 ans = c * b;
int cnt = 0;
while (tmp < c) {
ans = min(ans, (c + tmp - 1) / tmp * b + cnt * a);
tmp *= 2;
cnt++;
}
ans = min(ans, (c + tmp - 1) / tmp * b + cnt * a);
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````

### G

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

static constexpr int p[2] = {223333333, 773333333};
static constexpr int mod[2] = {1000000033, 1000002233};

constexpr int N = 1E5;

i64 pw[2][N + 10];

void init() {
pw[0][0] = 1;
pw[1][0] = 1;
for (int i = 1; i <= N; i++) {
pw[0][i] = pw[0][i - 1] * p[0] % mod[0];
pw[1][i] = pw[1][i - 1] * p[1] % mod[1];
}
}

class StringHash {
public:
vector<vector<i64>> h;
StringHash() : h(2, vector<i64>(1)) {}
inline void push_back(char ch) {
h[0].push_back((h[0].back() * p[0] + ch) % mod[0]);
h[1].push_back((h[1].back() * p[1] + ch) % mod[1]);
}
inline i64 get(int l, int r) {
return (h[0][r + 1] - h[0][l] * pw[0][r - l + 1] % mod[0] + mod[0]) % mod[0] + (((h[1][r + 1] - h[1][l] * pw[1][r - l + 1] % mod[1] + mod[1]) % mod[1]) << 30);
}
};

void solve() {
int n;
cin >> n;
set<i64> mp;
vector<string> a(n);
vector<StringHash> h(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<pair<int, string>> b(n);
for (int i = 0; i < n; i++) {
int len = a[i].size();
b[i].first = len;
b[i].second = a[i];
}
sort(b.begin(), b.end(), greater<>());
for (int i = 0; i < n; i++) {
int len = b[i].second.size();
StringHash tmph;
for (int j = 0; j < len; j++) {
tmph.push_back(b[i].second[j]);
}
mp.insert(tmph.get(0, len - 1));
h[i] = tmph;
}
for (int i = 0; i < n; i++) {
int len = b[i].first;
bool ok = 1;
for (int j = 1; j <= len; j++) {
for (int k = 0; k + j - 1 < len; k++) {
if (mp.find(h[i].get(k, k + j - 1)) == mp.end()) {
ok = 0;
break;
}
}
if (!ok) {
break;
}
}
if (ok) {
cout << len << '\n';
return;
}
}
cout << 0 << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
init();
while (tt--) {
solve();
}
return 0;
}
``````

### E

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

i64 f(i64 x) {
if (x == 0) {
return 1;
}
if (x > 0 && x % 3 == 0) {
return f(x / 3) + 1;
}
return f(x - 1) + 1;
}

void solve() {
i64 l, r;
cin >> l >> r;
i64 ans = max(f(r), f(l));
vector<int> R;
i64 tmpr = r;
while (tmpr) {
R.push_back(tmpr % 3);
tmpr /= 3;
}
int SIZE = R.size();
reverse(R.begin(), R.end());
for (int i = 0; i < SIZE; i++) {
if (R[i] == 0) {
continue;
}
i64 p = 0;
for (int j = 0; j < i; j++) {
p = p * 3 + R[j];
}
p = p * 3 + R[i] - 1;
for (int j = i + 1; j < SIZE; j++) {
p = p * 3 + 2;
}
if (p >= l) {
ans = max(ans, f(p));
}
}
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````

### F

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
i64 n, c1, c2;
cin >> n >> c1 >> c2;
vector<string> a(n);
i64 ans = 0;
for (int i = 0; i < n; i++) {
i64 res = 1E9;
cin >> a[i];
set<char> ST;
for (auto x : a[i]) {
ST.insert(x);
}
if ((int) ST.size() == 3) {
res = min(res, c1 * 3);
res = min(res, c2 * 3);
res = min(res, 2 * c2 + c1);
res = min(res, 2 * c1 + c2);
}
if ((int) ST.size() == 2) {
res = min(res, c2 + c1);
res = min(res, c1 * 3);
res = min(res, c2 * 3);
res = min(res, c2 * 2);
res = min(res, 2 * c2 + c1);
res = min(res, 2 * c1 + c2);
}
if ((int) ST.size() == 1) {
res = min(res, c2 + c1);
res = min(res, c1 * 3);
res = min(res, c2 * 2);
res = min(res, c2 * 3);
res = min(res, 2 * c2 + c1);
res = min(res, 2 * c1 + c2);
}
ans += res;
}
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````

### J

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
if (a[n - 1] <= 0) {
cout << 0 << '\n';
return;
}
if (a[n - 1] > 0) {
if (a[n - 2] < 0) {
cout << a[n - 1] << '\n';
return;
}
cout << a[n - 1] + a[n - 2] << '\n';
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````

### L

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
vector<int> d(n + 1);
for (int i = 2; i <= n; i++) {
int u;
cin >> u;
d[u]++;
g[i].push_back(u);
}
vector<int> dep(n + 1);
queue<int> q;
for (int i = 1; i <= n; i++) {
if (d[i] == 0) {
q.push(i);
dep[i] = 1;
}
}
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto nex : g[cur]) {
dep[nex] = dep[cur] + 1;
if (--d[nex] == 0) {
q.push(nex);
}
}
}
int ans = 2E9;
vector<int> val(n + 1);
for (int i = 1; i <= n; i++) {
val[dep[i]]++;
}
for (int i = 1; i <= n; i++) {
ans = min(ans, val[i] + i - 1);
}
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````
————————

### C

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
i64 a, b, c;
cin >> a >> b >> c;
i64 tmp = 1;
i64 ans = c * b;
int cnt = 0;
while (tmp < c) {
ans = min(ans, (c + tmp - 1) / tmp * b + cnt * a);
tmp *= 2;
cnt++;
}
ans = min(ans, (c + tmp - 1) / tmp * b + cnt * a);
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````

### G

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

static constexpr int p[2] = {223333333, 773333333};
static constexpr int mod[2] = {1000000033, 1000002233};

constexpr int N = 1E5;

i64 pw[2][N + 10];

void init() {
pw[0][0] = 1;
pw[1][0] = 1;
for (int i = 1; i <= N; i++) {
pw[0][i] = pw[0][i - 1] * p[0] % mod[0];
pw[1][i] = pw[1][i - 1] * p[1] % mod[1];
}
}

class StringHash {
public:
vector<vector<i64>> h;
StringHash() : h(2, vector<i64>(1)) {}
inline void push_back(char ch) {
h[0].push_back((h[0].back() * p[0] + ch) % mod[0]);
h[1].push_back((h[1].back() * p[1] + ch) % mod[1]);
}
inline i64 get(int l, int r) {
return (h[0][r + 1] - h[0][l] * pw[0][r - l + 1] % mod[0] + mod[0]) % mod[0] + (((h[1][r + 1] - h[1][l] * pw[1][r - l + 1] % mod[1] + mod[1]) % mod[1]) << 30);
}
};

void solve() {
int n;
cin >> n;
set<i64> mp;
vector<string> a(n);
vector<StringHash> h(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<pair<int, string>> b(n);
for (int i = 0; i < n; i++) {
int len = a[i].size();
b[i].first = len;
b[i].second = a[i];
}
sort(b.begin(), b.end(), greater<>());
for (int i = 0; i < n; i++) {
int len = b[i].second.size();
StringHash tmph;
for (int j = 0; j < len; j++) {
tmph.push_back(b[i].second[j]);
}
mp.insert(tmph.get(0, len - 1));
h[i] = tmph;
}
for (int i = 0; i < n; i++) {
int len = b[i].first;
bool ok = 1;
for (int j = 1; j <= len; j++) {
for (int k = 0; k + j - 1 < len; k++) {
if (mp.find(h[i].get(k, k + j - 1)) == mp.end()) {
ok = 0;
break;
}
}
if (!ok) {
break;
}
}
if (ok) {
cout << len << '\n';
return;
}
}
cout << 0 << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
init();
while (tt--) {
solve();
}
return 0;
}
``````

### E

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

i64 f(i64 x) {
if (x == 0) {
return 1;
}
if (x > 0 && x % 3 == 0) {
return f(x / 3) + 1;
}
return f(x - 1) + 1;
}

void solve() {
i64 l, r;
cin >> l >> r;
i64 ans = max(f(r), f(l));
vector<int> R;
i64 tmpr = r;
while (tmpr) {
R.push_back(tmpr % 3);
tmpr /= 3;
}
int SIZE = R.size();
reverse(R.begin(), R.end());
for (int i = 0; i < SIZE; i++) {
if (R[i] == 0) {
continue;
}
i64 p = 0;
for (int j = 0; j < i; j++) {
p = p * 3 + R[j];
}
p = p * 3 + R[i] - 1;
for (int j = i + 1; j < SIZE; j++) {
p = p * 3 + 2;
}
if (p >= l) {
ans = max(ans, f(p));
}
}
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````

### F

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
i64 n, c1, c2;
cin >> n >> c1 >> c2;
vector<string> a(n);
i64 ans = 0;
for (int i = 0; i < n; i++) {
i64 res = 1E9;
cin >> a[i];
set<char> ST;
for (auto x : a[i]) {
ST.insert(x);
}
if ((int) ST.size() == 3) {
res = min(res, c1 * 3);
res = min(res, c2 * 3);
res = min(res, 2 * c2 + c1);
res = min(res, 2 * c1 + c2);
}
if ((int) ST.size() == 2) {
res = min(res, c2 + c1);
res = min(res, c1 * 3);
res = min(res, c2 * 3);
res = min(res, c2 * 2);
res = min(res, 2 * c2 + c1);
res = min(res, 2 * c1 + c2);
}
if ((int) ST.size() == 1) {
res = min(res, c2 + c1);
res = min(res, c1 * 3);
res = min(res, c2 * 2);
res = min(res, c2 * 3);
res = min(res, 2 * c2 + c1);
res = min(res, 2 * c1 + c2);
}
ans += res;
}
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````

### J

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
if (a[n - 1] <= 0) {
cout << 0 << '\n';
return;
}
if (a[n - 1] > 0) {
if (a[n - 2] < 0) {
cout << a[n - 1] << '\n';
return;
}
cout << a[n - 1] + a[n - 2] << '\n';
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````

### L

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
vector<int> d(n + 1);
for (int i = 2; i <= n; i++) {
int u;
cin >> u;
d[u]++;
g[i].push_back(u);
}
vector<int> dep(n + 1);
queue<int> q;
for (int i = 1; i <= n; i++) {
if (d[i] == 0) {
q.push(i);
dep[i] = 1;
}
}
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto nex : g[cur]) {
dep[nex] = dep[cur] + 1;
if (--d[nex] == 0) {
q.push(nex);
}
}
}
int ans = 2E9;
vector<int> val(n + 1);
for (int i = 1; i <= n; i++) {
val[dep[i]]++;
}
for (int i = 1; i <= n; i++) {
ans = min(ans, val[i] + i - 1);
}
cout << ans << '\n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````