A
读入两个字符串，交换第一位即可。
B
题意
给定整数 \(n\)，求一个整数 \(x\)，满足：
-
\(2\leq x \leq n\)。
-
\(\displaystyle \sum\limits_{i = 1}^k i\cdot x\) 最大，其中 \(k\) 为满足 \(kx \leq n\) 最大的正整数。
思路
赛时思路
可以直接枚举 \(x\) 的所有情况，暴力计算答案。
由于是像筛法那样的暴跳，总复杂度为 \(O(Tn\log n)\)。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e6 + 100;
int t , n;
signed main() {
cin >> t;
while(t --) {
cin >> n;
int maxx = 0 , ans = n;
for(int j = 2;j <= n;j ++) {
int sum = 0;
for(int k = 1;k * j <= n;k ++)
sum += k * j;
if(sum > maxx) {
ans = j;
maxx = sum;
}
}
cout << ans << "\n";
}
return 0;
}
另解
我们注意到当 \(n = 3\) 时，答案为 \(3\)。否则答案一定为 \(2\)。
证明：
\(n=2\) 和 \(n = 3\) 的情况显然，这里我们证明 \(n \geq 4\) 的情况。
根据等差数列求和公式我们得到：
\[\displaystyle \sum\limits_{i = 1}^k i\cdot x = \displaystyle x\cdot \frac{(1+\lfloor \frac{n}{x} \rfloor)\cdot \lfloor \frac{n}{x} \rfloor}{2} \]\[\because \displaystyle x\cdot\left\lfloor \frac{n}{x}\right\rfloor = n - n \bmod x \]\[\therefore \displaystyle n - x + 1\leq x\cdot\left\lfloor \frac{n}{x}\right\rfloor \leq n \]根据以上式子放缩：
当 \(x\) 取 \(2\)，原式 \(\leq \displaystyle \frac{(n - 1)\cdot(1+\lfloor \frac{n}{2} \rfloor)}{2}\)。
当 \(x\) 取 \(s(s \geq 3)\)，原式 \(\geq \displaystyle \frac{n\cdot(1+\lfloor \frac{n}{s} \rfloor)}{2} \geq \displaystyle \frac{n\cdot(1+\lfloor \frac{n}{3} \rfloor)}{2}\)。
上式比下式：
\[\displaystyle \frac{n - 1}{n} \cdot \frac{1+\lfloor \frac{n}{2} \rfloor}{1+\lfloor \frac{n}{3} \rfloor} \]我们只需要证明这个式子 \(\geq 1\) 即可证明 \(2\) 为答案，这里我们分类讨论一下。
若 \(n = 6m\) 或 \(6m + 1\)，此时 \(m \geq 1\)，则原式 \(\displaystyle\geq \frac{n - 1}{n}\cdot \frac{1+3m}{1+2m} \geq \frac{5}{6}\cdot\frac{4}{3} = \frac{10}{9}\)。
若 \(n = 6m + 2\)，此时 \(m \geq 1\)，则原式 \(\displaystyle\geq \frac{n - 1}{n}\cdot \frac{2+3m}{1+2m} \geq \frac{7}{8}\cdot\frac{5}{3} = \frac{35}{24}\)。
若 \(n = 6m + 3\)，此时 \(m \geq 1\)，则原式 \(\displaystyle\geq \frac{n - 1}{n}\cdot \frac{2+3m}{2+2m} \geq \frac{8}{9}\cdot\frac{5}{4} = \frac{10}{9}\)。
若 \(n = 6m + 4\) 或 \(6m + 5\)，此时 \(m \geq 0\)，则原式 \(\displaystyle\geq \frac{n - 1}{n}\cdot \frac{3+3m}{2+2m} \geq \frac{3}{4}\cdot\frac{3}{2} = \frac{9}{8}\)。
证毕。
如果有简单证明请速速告诉我，我被这证明折磨麻了！
C
题意
一个序列中若存在一个数等于序列中其他所有数的和，则该序列为好序列。
问有多少个 \(k(1\leq k \leq n)\)，满足 \((a_1,a_2,\cdots,a_k)\) 是好序列。
思路
如果存在一个数等于其他数的和，那么这个数必然是序列中最大的。
设最大的数为 \(s_0\)，序列和为 \(sum\)，则对于每个 \(k\) 只需判断是否满足 \(s_0 = sum - s_0\) 即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e6 + 100;
int t , n , a[N];
signed main() {
cin >> t;
while(t --) {
cin >> n;
int maxx = 0 , sum = 0 , ans = 0;
for(int i = 1;i <= n;i ++) {
cin >> a[i];
sum += a[i];
maxx = max(maxx , a[i]);
if(maxx * 2 == sum) ans ++;
}
cout << ans << "\n";
}
return 0;
}
D
题意
给定一个由 # 和 . 组成的 \(n \times m\) 的网格，网格上存在一个由 # 构成的完整的曼哈顿圆，求这个曼哈顿圆的中心。
以 \((a,b)\) 为中心，半径为 \(r\) 的曼哈顿圆的定义：将与 \((a,b)\) 曼哈顿距离小于 \(r\) 的点全设置成 #，\(r\) 为正整数。
思路
画图发现曼哈顿圆一定是一个菱形（\(r = 1\) 的时候是一个点）。
那么中心点就是 # 最长的一行的连续 # 的中点。
扫一遍得到横坐标 \(x_0\)，记录下该行第一个 # 纵坐标 \(y_1\) 和最后一个 # 纵坐标 \(y_2\)，中心即为 \(\displaystyle (x_0 , \frac{y_1+y_2}{2})\)。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e6 + 100;
char ch[N];
int t , n , m , a[N];
signed main() {
cin >> t;
while(t --) {
cin >> n >> m;
int maxx = 0;
int x , y;
for(int i = 1;i <= n;i ++) {
scanf("%s" , ch + 1);
int now = 0 , zh = 0 , zq = 0;
for(int j = 1;j <= m;j ++) {
if(ch[j] == '#') {
if(now == 0) zq = j;
now ++ , zh = j;
}
}
if(now > maxx) {
maxx = now;
x = i;
y = (zq + zh) / 2;
}
}
cout << x << ' ' << y << "\n";
}
return 0;
}
E
思路
可以枚举长和宽 \(x_0\) 和 \(y_0\)，这样就直接能算出高为 \(\displaystyle \frac{k}{x_0y_0}\) 了，但前提是 \(k\) 能被 \(x_0y_0\) 整除。
根据乘法原理可得，放置方案数为 \(\displaystyle(x - x_0 + 1)(y - y_0 + 1)(z-\frac{k}{x_0y_0} + 1)\)，取个 \(\max\) 即可。
复杂度 \(O(xy)\)。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e6 + 100;
char ch[N];
int t , x , y , z , k;
signed main() {
cin >> t;
while(t --) {
cin >> x >> y >> z >> k;
int maxx = 0;
for(int i = 1;i <= x;i ++) {
for(int j = 1;j <= y;j ++) {
if(k % i == 0) {
int now = k / i;
if(now % j == 0) {
int dsw = now / j;
maxx = max(maxx , (x - i + 1) * (y - j + 1) * max(0ll , (z - dsw + 1)));
}
}
}
}
cout << maxx << "\n";
}
return 0;
}
F
小时候看这集 fst 了。
题意
有个 boss 有 \(h\) 的血量，你作为玩家有 \(n\) 个技能，每个技能伤害为 \(a_i\)，冷却时间为 \(c_i\)。
每一回合你可以使用所有已冷却的技能，然后该技能会进入冷却并在 \(c_i\) 回合后才可使用。
求最少多少回合击败 boss。
思路
对 boss 造成的伤害是随着回合数单调不降的。
所以直接二分答案就行了。
若进行了 \(x\) 回合，则技能 \(i\) 的使用次数为 \(\displaystyle\frac{x - 1}{c_i} + 1\)，造成的伤害为 \(\displaystyle a_i\cdot(\frac{x - 1}{c_i} + 1)\)。
注意：计算总伤害会爆 long long。所以在计算过程中若足够击败 boss 就应直接退出循环。笔者就是因为这个 fst 了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e6 + 100;
char ch[N];
int t , n , m , z , k , a[N] , b[N];
signed main() {
cin >> t;
while(t --) {
cin >> n >> m;
for(int i = 1;i <= m;i ++)
cin >> a[i];
for(int i = 1;i <= m;i ++)
cin >> b[i];
int l = 1 , r = 1e12;
int ans = 1;
while(l <= r) {
int mid = l + r >> 1;
int sum = 0;
for(int i = 1;i <= m;i ++) {
int cs = (mid - 1) / b[i] + 1;
sum += cs * a[i];
if(sum >= n) break;
}
if(sum >= n) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
cout << ans << "\n";
}
return 0;
}
G
题意
设 \(D(x)\) 为 \(x\) 的各数位之和。
给定 \(l,r,k\)，求多少 \(n\) 满足：
-
\(10^l \leq n < 10^r\)。
-
\(k\cdot D(n) = D(k\cdot n)\)。
思路
首先满足该条件的一个充分条件是 \(n \times k\) 不产生进位。
所以我们猜测这个也是它的必要条件，考虑证明。
对于单独的一位 \(n_i\)，若它乘 \(k\) 有进位。
则 \(k \cdot D(n_i) = kn_i\)，\(\displaystyle D(k\cdot n_i) = \frac{kn_i}{10} + (kn_i \bmod 10)\)。
后者小于前者，证明：
把 \(kn_i\) 表示成 \(10x + y\)，\(x\) 为正整数，\(y\) 为非负整数，且 \(y < 10\)。则 \(D(k\cdot n_i)\) 为 \(x + y\)。证毕。
所以必要条件成立。
计算答案
这题计算答案也没那么简单，根据最高位不能填 \(0\)，所以最高位有 \(\displaystyle \frac{9}{k}\) 种填法，其他位有 \((\displaystyle \frac{9}{k} + 1)\) 种填法。
对于 \(10^i \le n < 10^{i+1}\)，满足条件的情况共 \(\displaystyle \frac{9}{k}\cdot (\frac{9}{k} + 1)^i\) 种。
所以对于 \(10^l \le n < 10^{r}\)，满足条件的情况共 \(\displaystyle \frac{9}{k}\cdot \sum\limits_{i = l}^{r - 1}(\frac{9}{k} + 1)^i\) 种。
根据等比数列求和公式可得到上式等于 \(\displaystyle (\frac{9}{k}+1)^l\cdot ((\frac{9}{k}+1)^{r-l} - 1)\)。
这个式子用快速幂和逆元相关知识就能求出来了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e6 + 100;
const int mod = 1e9 + 7;
char ch[N];
int t , n , m , z , k , a[N] , b[N];
int ksm(int x,int y) {
int res = 1;
for(;y;y >>= 1 , x = x * x % mod)
if(y & 1)
res = res * x % mod;
return res;
}
signed main() {
cin >> t;
while(t --) {
cin >> n >> m >> k;
int wd = (9 / k);
int now = (((ksm(wd + 1 , m - n) - 1) % mod) + mod) % mod;
now = ksm(wd + 1 , n) % mod * now % mod;
cout << now << "\n";
}
return 0;
}
H1
题意
给定一个由 # 和 . 组成的 \(n \times m\) 的网格，请进行以下的操作一次，使图中由 # 构成的连通块最大。
操作：选定一行或一列，将其全部变为 #。
输出操作后最大连通块点数。
思路
很自然地想到枚举每一行/每一列，难点在于怎么计算答案。
我们先考虑填行的情况。
如果我们把一行填满，则相当于桥一样把这条线两边的连通块连起来了。
所以当我们枚举第 \(i\) 行时，答案为：第 \(i\) 行 . 的数量，并将第 \(i - 1\) 到 \(i + 1\) 这三行的连通块不重不漏地加入贡献。
这里选择先 \(\text{dfs}\) 给每个连通块标个号，并计算该连通块大小。时间复杂度 \(O(nm)\)。
然后计算答案的时候，用 \(\text{map}\) 对编号去一下重，就能做到不重了。
填列的做法和填行没有任何区别。
代码
代码复杂程度远难于思路的一题。
H2
题意
给定一个由 # 和 . 组成的 \(n \times m\) 的网格，请进行以下的操作一次，使图中由 # 构成的连通块最大。
操作：选定一行和一列，将其全部变为 #。
输出操作后最大连通块点数。
思路
如果使用 Easy Version 的思路，复杂度是 \(O(n^2m^2)\) 的，无法接受。
由于选一行一列会有交集的连通块，所以无法单独考虑行或列再计算答案。
因此还是考虑枚举行和列，到这复杂度为 \(O(nm)\)。
既然暴力计算答案不行，那么我们就想想能不能预处理出答案。
对于一个连通块，向上延伸到 \(l_1\) 行，向下延伸到 \(r_1\) 行，向左延伸到 \(l_2\) 列，向右延伸到 \(r_2\) 列，那么它将对 \(l_1 - 1\) 到 \(r_1 + 1\) 行和 \(l_2 - 1\) 到 \(r_2 + 1\) 列有贡献。
这个贡献，我们用差分数组记录，比如行差分数组 \(s_1\) 和连通块大小 \(c\)，我们将 \(s_1\) 的 \(l_1 - 1\) 的位置 \(+c\)，\(r_1 + 2\) 的位置 \(-c\)，在差分数组构造完之后前缀和一下就行了。
列差分数组也是同理。
做到这里会发现枚举行列的话，会有连通块被重复计算了一次。那么考虑怎么减掉这个贡献。
再整一个二维数组 \(S_{i,j}\)，代表第 \(i\) 行和第 \(j\) 列重复计算的连通块贡献的差分数组。一个连通块有重复贡献的部分为左上角为 \((l_1 - 1,l_2 - 1)\)，右下角为 \((r_1 + 1，r_2 + 1)\) 的矩形，把这个矩形二维差分的形式存在 \(S\) 里，然后再转回来即可。
时间复杂度 \(O(nm)\)。