Topic link: https://codeforces.com/contest/1822
A – Tube Tube Feed
Problem-solving ideas: binary search
#include <bits/stdc++.h>
using namespace std;
const int mx = 1e3 + 10;
struct node {
int a;
int b;
int c;
bool operator < (const node &A) const
{
return a < A.a;
}
node() {}
node (int aa, int bb, int cc): a(aa), b(bb), c(cc) {}
\t
}s[mx];
int main() {
auto check = [](string str) {
for (char ch: str) {
if ('a' <= ch & amp; & amp; ch <= 'z')
continue;
return 0;
}
return 1;
};
int q;
scanf("%d", &q);
while(q--) {
int n,t;
scanf("%d%d", &n, &t);
for (int i=1;i<=n;i + + ) {
scanf("%d", &s[i].a);
s[i].a + = i - 1;
s[i].c = i;
}
for (int i=1;i<=n;i + + ) {
scanf("%d", &s[i].b);
}
sort(s + 1, s + 1 + n);
int e = upper_bound(s + 1, s + 1 + n, node(t, 0, 1)) - s;
int ans = -1, ma = 0;
for (int i=1;i<e;i + + ) {
if (ma < s[i].b) {
ma = s[i].b;
ans = s[i].c;
}
}
printf("%d\\
", ans);
}
\t
return 0;
}
B – Karina and Array
Problem-solving ideas: slightly
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
using ull = unsigned long long;
using ll = long long;
ll a[mx];
int main() {
auto check = [](string str) {
for (char ch: str) {
if ('a' <= ch & amp; & amp; ch <= 'z')
continue;
return 0;
}
return 1;
};
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
for (int i=1;i<=n;i + + ) {
scanf("%lld", a + i);
}
sort (a + 1, a + 1 + n);
printf("%lld\\
", max(a[n] * a[n-1], a[2] * a[1]));
}
return 0;
}
C – Bun Lover
Problem-solving ideas: (n + 1)^2 + 1
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
using ull = unsigned long long;
using ll = long long;
ll a[mx];
int main() {
auto check = [](string str) {
for (char ch: str) {
if ('a' <= ch & amp; & amp; ch <= 'z')
continue;
return 0;
}
return 1;
};
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
printf("%lld\\
", 1ll * (n + 1) * (n + 1) + 1);
}
return 0;
}
D – Super-Permutation
Problem-solving ideas: You can construct such an array after taking the modulus, 0, n-1, 1, n-2, 2, n-3…. You can know that when n is an odd number, the answer is unsolvable. Because the sum is divisible by n.
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
using ull = unsigned long long;
using ll = long long;
ll a[mx];
int main() {
auto check = [](string str) {
for (char ch: str) {
if ('a' <= ch & amp; & amp; ch <= 'z')
continue;
return 0;
}
return 1;
};
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
if (n == 1) {
puts("1");
continue;
}
if (n & 1) {
puts("-1");
continue;
}
printf("%d %d ", n, n-1);
int v = n - 1;
for (int i=1;i<n/2;i + + ) {
printf("%d %d ", n - v + i, v - i - 1);
v--;
}
puts("");
}
return 0;
}
E – Making Anti-Palindromes
Problem-solving ideas: If there is a character with more than half of the number, then there must be no solution, otherwise, even if the logarithm of the existing logarithm, if the logarithm of a letter exceeds the logarithm of the existing logarithm, then the answer is the logarithm of the letter. Otherwise just divide all logarithms by 2.
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
using ull = unsigned long long;
using ll = long long;
char a[mx];
int main() {
auto check = [](vector <int> & amp; vec, int n) {
for (int v: vec) {
if (v > n / 2)
return false;
}
return true;
};
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
scanf("%s", a + 1);
if (n & 1) {
puts("-1");
continue;
}
vector <int> vec(26, 0), vec1(26, 0);
for (int i=1;i<=n;i + + ) {
vec[a[i]-'a'] + + ;
}
int sum = 0;
for (int i=1;i<=n/2;i + + ) {
if (a[i] == a[n-i + 1]) {
vec1[a[i]-'a'] + + ;
sum + + ;
}
}
if (!check(vec, n)) {
puts("-1");
continue;
}
int ans = 0;
for (int v: vec1) {
if (v > sum/2) {
ans = v;
break;
}
}
if (sum == 0) {
puts("0");
continue;
}
\t\t
\t\t
printf("%d\\
", max(ans, (sum -1) / 2 + 1));
}
return 0;
}
F – Gardening Friends
Problem-solving ideas: Calculate the diameter of the number, and then enumerate until the value of each point is the largest.
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
using ull = unsigned long long;
using ll = long long;
vector <int> vec[mx], link;
int x, y, val;
int dep[mx];
int son[mx], dis[mx];
bool vis[mx];
void get_long(int u, int fa)
{
dep[u] = dep[fa] + 1;
son[u] = u;
for (int v: vec[u]) {
if (v == fa)
continue;
get_long(v, u);
if (dep[son[v]] + dep[son[u]] - 2 * dep[u] > val) {
x = son[v];
y = son[u];
val = dep[son[v]] + dep[son[u]] - 2 * dep[u];
}
if (dep[son[v]] > dep[son[u]]) {
son[u] = son[v];
}
}
}
bool find_link(int u, int fa)
{
if (u == y)
return 1;
for (int v: vec[u]) {
if (v == fa)
continue;
if (find_link(v, u)) {
link.push_back(v);
return 1;
}
}
return 0;
}
void dfs(int u, int d)
{
vis[u] = 1;
dis[u] = d;
for (int v: vec[u]) {
if (vis[v])
continue;
dfs(v, d + 1);
}
}
int main() {
int t;
scanf("%d", &t);
dep[0] = -1;
while (t--) {
int n, k, c;
scanf("%d%d%d", &n, &k, &c);
for (int i=1;i<=n;i + + ) {
vec[i].clear();
vis[i] = dis[i] = 0;
}
val = 0;
for (int i=1;i<n;i + + ) {
int u,v;
scanf("%d%d", &u, &v);
vec[u].push_back(v);
vec[v].push_back(u);
}
get_long(1, 0);
link. clear();
find_link(x, -1);
link. push_back(x);
for (int i=0; i<link. size(); i ++ ) {
dis[link[i]] = max(i, (int)link. size() - 1 - i);
vis[link[i]] = 1;
}
for (int v: link) {
dfs(v, dis[v]);
}
ll ans = 0;
for (int i=1;i<=n;i + + ) {
int step = dep[i];
ans = max(ans, 1ll * dis[i] * k - 1ll * step * c);
}
printf("%lld\\
", ans);
}
return 0;
}
G1 – Magic Triples (Easy Version)
Problem-solving idea: violence each number as the maximum number, and then violence their factors.
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
using ull = unsigned long long;
using ll = long long;
int a[mx];
map <int, int> mp;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
mp. clear();
for (int i=1;i<=n;i + + ) {
scanf("%d", a + i);
mp[a[i]] + + ;
}
ll ans = 0;
for (auto temp: mp) {
ll cnt = temp.second;
ans + = cnt * (cnt - 1) * (cnt - 2);
//cout << temp.first << " " << temp.second << endl;
for (int i=2; i*i<= temp.first; i ++ ) {
if (temp.first % (i*i) == 0) {
ans += cnt * mp[temp.first/i] * mp[temp.first/i/i];
}
}
}
printf("%lld\\
", ans);
}
return 0;
}
G2 – Magic Triples (Hard Version)
Problem-solving ideas: Break down the factors, and then cut some branches.
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
using ull = unsigned long long;
using ll = long long;
int a[mx];
map <int, int> mp;
vector <int> pri;
bool vis[mx];
void init()
{
for (int i=2;i<mx;i + + ) {
if (!vis[i]) {
pri.push_back(i);
}
for (int v: pri) {
if (i * v >= mx)
break;
vis[i * v] = 1;
if (i % v == 0)
break;
}
}
}
void add_ans(vector<int> & amp; ve, int idx, ll & amp; ans, ll v, ll u)
{
if (v*v > u)
return;
if (idx == ve. size()) {
if (v != 1 & amp; & amp; u % (v*v) == 0)
ans += 1ll * mp[u] * mp[u/v] * mp[u/v/v];
return;
}
\t
ll base = 1;
for (int i=0; ;i ++ ) {
if (u % (base*v*v*base) != 0)
return;
add_ans(ve, idx + 1, ans, v * base, u);
base *= ve[idx];
}
}
int main() {
int t;
init();
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
mp. clear();
for (int i=1;i<=n;i + + ) {
scanf("%d", a + i);
mp[a[i]] + + ;
}
ll ans = 0;
for (auto temp: mp) {
ll cnt = temp.second;
ans + = cnt * (cnt - 1) * (cnt - 2);
int val = temp.first;
vector <int> ve;
for (int v: pri) {
if (1ll * v * v > val)
break;
if (val % (v * v) == 0) {
ve.push_back(v);
val /= v * v;
}
while(val % v == 0) val /= v;
}
add_ans(ve, 0, ans, 1, temp. first);
}
printf("%lld\\
", ans);
}
return 0;
}