Codeforces Round 952 (Div. 4)

🚀欢迎来到本文🚀
🍉个人简介：陈童学哦，彩笔ACMer一枚。
🏀所属专栏：Codeforces
本文用于记录回顾本彩笔的解题思路便于加深理解。

A. Creating Words

Matthew is given two strings $a$ and $b$, both of length $3$. He thinks it’s particularly funny to create two new words by swapping the first character of $a$ with the first character of $b$. He wants you to output $a$ and $b$ after the swap.

Note that the new words may not necessarily be different.

Input

The first line contains $t$ ($1\le t\le 100$) — the number of test cases.

The first and only line of each test case contains two space-separated strings, $a$ and $b$, both of length $3$. The strings only contain lowercase Latin letters.

Output

For each test case, after the swap, output $a$ and $b$, separated by a space.

解题思路：

交换输出两个字符串的第一个字符即可。

AC代码：

#include<bits/stdc++.h>
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){string s1,s2;cin >> s1 >> s2;cout << s2[0] << s1.substr(1,s1.size() - 1) << " ";cout << s1[0] << s2.substr(1,s2.size() - 1) << "\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}return 0;
} 

B. Maximum Multiple Sum

Given an integer $n$, find an integer $x$ such that:

• $2\le x\le n$.
• The sum of multiples of $x$ that are less than or equal to $n$ is maximized. Formally, $x+2x+3x+\cdots +kx$ where $kx\le n$ is maximized over all possible values of $x$.

Input

The first line contains $t$ ($1\le t\le 100$) — the number of test cases.

Each test case contains a single integer $n$ ($2\le n\le 100$).

Output

For each test case, output an integer, the optimal value of $x$. It can be shown there is only one unique answer.

解题思路：

因为n很小，如果和我一样数学不太敏感的可以直接暴力枚举每个x看看哪个x能够使得小于等于n的倍数和最大。

AC代码：

#include<bits/stdc++.h>
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){int n;cin >> n;int ans = -1e9;int pos = -1;for(int i = 2;i <= n;i ++){int j = i;int cnt = 1;int res = 0;while(j * cnt <= n){res += j * cnt;cnt ++;}if(res >= ans){ans = res;pos = i;}}cout << pos << "\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}return 0;
} 

C. Good Prefixes

Alex thinks some array is good if there exists some element that can be represented as the sum of all other elements (the sum of all other elements is $0$ if there are no other elements). For example, the array $[1,6,3,2]$ is good since $1+3+2=6$. Furthermore, the array $[0]$ is also good. However, the arrays $[1,2,3,4]$ and $[1]$ are not good.

Alex has an array $a_1,a_2,\dots ,a_n$. Help him count the number of good non-empty prefixes of the array $a$. In other words, count the number of integers $i$ ($1\le i\le n$) such that the length $i$ prefix (i.e. $a_1,a_2,\dots ,a_i$) is good.

Input

The first line of the input contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of elements in the array.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($0\le a_i\le 10^9$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output a single integer — the number of good non-empty prefixes of the array $a$.

解题思路：

考虑从左往右计算前缀和并且记录下当前前缀下的最大值，然后判断当前前缀和是否等于目前最大值即可。

AC代码：

#include<bits/stdc++.h>
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){int n;cin >> n;vector<int> a(n + 1);for(int i = 1;i <= n;i ++){cin >> a[i];}i64 maxn = 0;i64 res = 0;int ans = 0;for(int i = 1;i <= n;i ++){res += a[i];maxn = max(maxn,1LL * a[i]);if(res - maxn == maxn){ans ++;}}cout << ans << "\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}return 0;
} 

D. Manhattan Circle

Given a $n$ by $m$ grid consisting of ‘.’ and ‘#’ characters, there exists a whole manhattan circle on the grid. The top left corner of the grid has coordinates $(1,1)$, and the bottom right corner has coordinates $(n,m)$.

Point ($a,b$) belongs to the manhattan circle centered at ($h,k$) if KaTeX parse error: Expected 'EOF', got '&' at position 19: …- a| + |k - b| &̲lt; r, where $r$ is a positive constant.

On the grid, the set of points that are part of the manhattan circle is marked as ‘#’. Find the coordinates of the center of the circle.

Input

The first line contains $t$ ($1\le t\le 1000$) — the number of test cases.

The first line of each test case contains $n$ and $m$ ($1\le n\cdot m\le 2\cdot 10^5$) — the height and width of the grid, respectively.

The next $n$ lines contains $m$ characters ‘.’ or ‘#’. If the character is ‘#’, then the point is part of the manhattan circle.

It is guaranteed the sum of $n\cdot m$ over all test cases does not exceed $2\cdot 10^5$, and there is a whole manhattan circle on the grid.

Output

For each test case, output the two integers, the coordinates of the center of the circle.

解题思路：

观察样例我们发现，#组成的图形基本上都是一个菱形的形状，而进一步对于样例输出的观察我们其实能够发现圆心的坐标就是这个菱形的中心坐标，即含有最多#的行和最多#的列。
所以我们有时候看不太明白题时可以通过观察样例得出一些东西，毕竟是guessforces嘛。

AC代码：

#include<bits/stdc++.h>
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){int n,m;cin >> n >> m;vector<vector<char>> g(n + 1,vector<char>(m + 1));for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){cin >> g[i][j];}}int x1 = 1e9,x2 = 0,y1 = 1e9,y2 = 0;int f1 = 0,f2 = 0;for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){if(g[i][j] == '#'){x1 = min(x1,i);x2 = max(x2,i);y1 = min(y1,j);y2 = max(y2,j);}}}cout << (x1 + x2) / 2 << " " << (y1 + y2) / 2 << "\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}return 0;
} 

E. Secret Box

Ntarsis has a box $B$ with side lengths $x$, $y$, and $z$. It lies in the 3D coordinate plane, extending from $(0,0,0)$ to $(x,y,z)$.

Ntarsis has a secret box $S$. He wants to choose its dimensions such that all side lengths are positive integers, and the volume of $S$ is $k$. He can place $S$ somewhere within $B$ such that:

• $S$ is parallel to all axes.
• every corner of $S$ lies on an integer coordinate.

$S$ is magical, so when placed at an integer location inside $B$, it will not fall to the ground.

Among all possible ways to choose the dimensions of $S$, determine the maximum number of distinct locations he can choose to place his secret box $S$ inside $B$. Ntarsis does not rotate $S$ once its side lengths are selected.

Input

The first line consists of an integer $t$, the number of test cases ($1\le t\le 2000$). The description of the test cases follows.

The first and only line of each test case contains four integers $x,y,z$ and $k$ ($1\le x,y,z\le 2000$, $1\le k\le x\cdot y\cdot z$).

It is guaranteed the sum of all $x$, sum of all $y$, and sum of all $z$ do not exceed $2000$ over all test cases.

Note that $k$ may not fit in a standard 32-bit integer data type.

Output

For each test case, output the answer as an integer on a new line. If there is no way to select the dimensions of $S$ so it fits in $B$, output $0$.

解题思路：

观察到坐标最大为2000，可以考虑n^2枚举任意两个坐标然后通过k求出第三个坐标，再判断第三个坐标是否满足条件然后求满足条件下的x,y,z的最大组合数即可。

AC代码：

#include<bits/stdc++.h>
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){int x,y,z;i64 k;cin >> x >> y >> z >> k;i64 ans = -1;for(int i = 1;i <= x;i ++){for(int j = 1;j <= y;j ++){double res = k / (i * j);if((i64)(i * j * (res)) == k){int t = res;if(t <= z){ans = max(ans,1LL * (x - i + 1) * (y - j + 1) * (z - t + 1));}}}}if(ans == -1){cout << "0\n";}else{cout << ans << "\n";}
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}return 0;
} 

F. Final Boss

You are facing the final boss in your favorite video game. The boss enemy has $h$ health. Your character has $n$ attacks. The $i$’th attack deals $a_i$ damage to the boss but has a cooldown of $c_i$ turns, meaning the next time you can use this attack is turn $x+c_i$ if your current turn is $x$. Each turn, you can use all attacks that are not currently on cooldown, all at once. If all attacks are on cooldown, you do nothing for the turn and skip to the next turn.

Initially, all attacks are not on cooldown. How many turns will you take to beat the boss? The boss is beaten when its health is $0$ or less.

Input

The first line contains $t$ ($1\le t\le 10^4$) – the number of test cases.

The first line of each test case contains two integers $h$ and $n$ ($1\le h,n\le 2\cdot 10^5$) – the health of the boss and the number of attacks you have.

The following line of each test case contains $n$ integers $a_1,a_2,...,a_n$ ($1\le a_i\le 2\cdot 10^5$) – the damage of your attacks.

The following line of each test case contains $n$ integers $c_1,c_2,...,c_n$ ($1\le c_i\le 2\cdot 10^5$) – the cooldown of your attacks.

It is guaranteed that the sum of $h$ and $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output an integer, the minimum number of turns required to beat the boss.

解题思路：

先判断第一回合的所有攻击的总和是否可以大于Boss的生命值，因为第一回合所有的技能都是可以使用的，如果大于那么就直接输出1，否则的话我们可以二分答案，这里需要注意的是答案最多不会超过1e10左右，二分答案时需要判断的就是根据当前的回合数计算出每个攻击能够使用几次，然后计算所有的攻击值乘以攻击次数的总和是否大于h，大于的话说明答案大了，需要向左边缩小区间，否则向右缩小区间。

AC代码：

#include<bits/stdc++.h>
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){i64 h,n;cin >> h >> n;vector<int> a(n + 1),c(n + 1);i64 k = 0;for(int i = 1;i <= n;i ++){cin >> a[i];k += a[i];}for(int i = 1;i <= n;i ++){cin >> c[i];}if(k >= h){cout << "1\n";return;}h -= k;i64 l = 1,r = 1e11;while(l < r){i64 mid = l + r >> 1;i64 res = 0;for(int i = 1;i <= n;i ++){res += (mid / c[i]) * 1LL * a[i];}if(res >= h){r = mid;}else{l = mid + 1;}}cout << l + 1 << "\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}return 0;
} 

G. D-Function

Let $D(n)$ represent the sum of digits of $n$. For how many integers $n$ where KaTeX parse error: Expected 'EOF', got '&' at position 15: 10^{l} \leq n &̲lt; 10^{r} satisfy $D(k\cdot n)=k\cdot D(n)$? Output the answer modulo $10^9+7$.

Input

Input

The first line contains an integer $t$ ($1\le t\le 10^4$) – the number of test cases.

Each test case contains three integers $l$, $r$, and $k$ ($0 \leq l < r \leq 10^9 $, $1\le k\le 10^9$).

Output

For each test case, output an integer, the answer, modulo $10^9+7$.

解题思路：

要让 $D(k\cdot n)=k\cdot D(n)$，我们可以发现$k\cdot n$必然不能发生进位，如果发生进位的话两者肯定是不相等的。那么$k$肯定必须小于10才有意义。
那么对于一个长度为n + 1的数，如果q = n / k + 1，那么这个数的第一位可以为1 - (q - 1），其他位可以为0 - （q - 1）,而10 ^ l <= n < 10 ^ r，因此总共有(q - 1) * q的i次方在l 到 r - 1的求和个数满足条件。然后根据等比数列我们最后可以得出答案为q ^ r - q ^ l，因为指数比较大，所以我们需要用快速幂来求，然后还需要同余一下。

AC代码：

#include<bits/stdc++.h>
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
//using i64 = long long;
//using ld = long double;
typedef long long i64;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
i64 qm(i64 a,i64 b){i64 res = 1;while(b){if(b & 1){res = res * a % MOD1;}a = a * a % MOD1;b >>= 1;}return res;
}
void solve(){i64 l,r,k;cin >> l >> r >> k;i64 q = 9 / k + 1;cout << (qm(q,r) + MOD1- qm(q,l)) % MOD1 << "\n";
}
int main(){ios::sync_with_stdio(false);
//	cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}return 0;
} ```