链接：https://codeforces.com/contest/1985
A. Creating Words
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
string a, b;
cin >> a >> b;
swap(a[0], b[0]);
cout << a << ' ' << b << endl;
}B. Maximum Multiple Sum
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
int n;
cin >> n;
ll ans = -1;
ll maxx = MIN;
for (int i = 2; i <= n; ++i)
{
ll sum = 0;
for (int j = i; j <= n; j += i)
sum += j;
if (sum > maxx)
{
ans = i;
maxx = sum;
}
}
cout << ans << endl;
}C. Good Prefixes
算法：
前缀和，哈希表。
思路：
判断前缀中有没有等于区间和一半值的元素即可。
关键代码：
void solve()
{
int n;
cin >> n;
vi a(n + 10, 0);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<ll> s(n + 10, 0);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + a[i];
ll ans = 0;
map<ll, ll> m;
for (int i = 1; i <= n; ++i)
{
m[a[i]] = 1;
if (s[i] % 2 == 0)
{
if (m.count(s[i] / 2))
++ans;
}
}
cout << ans << endl;
}D. Manhattan Circle
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<string> g(n + 10);
for (int i = 0; i < n; ++i)
cin >> g[i];
ll maxx = MIN;
ll pos = -1;
for (int i = 0; i < n; ++i)
{
ll cnt = 0;
for (int j = 0; j < m; ++j)
{
if (g[i][j] == '#')
++cnt;
}
if (cnt > maxx)
{
maxx = cnt;
pos = i;
}
}
ll cnt = 0;
for (int i = 0; i < m; ++i)
{
if (g[pos][i] == '#')
++cnt;
if (cnt == maxx / 2 + 1)
{
cout << pos + 1 << ' ' << i + 1 << endl;
return;
}
}
}E. Secret Box
算法：
暴力枚举。
思路：
无。
关键代码：
void solve()
{
ll x, y, z, k;
cin >> x >> y >> z >> k;
ll ans = 0;
for (int a = 1; a <= x; a++)
{
for (int b = 1; b <= y; b++)
{
if (k % (a * b))
continue;
ll c = k / (a * b);
if (c > z)
continue;
ll cnt = (ll)(x - a + 1) * (y - b + 1) * (z - c + 1);
ans = max(ans, cnt);
}
}
cout << ans << endl;
}F. Final Boss
算法：
堆模拟。
思路：
无。
关键代码：
void solve()
{
int h, n;
cin >> h >> n;
vector<int> a(n + 10);
vector<int> c(n + 10);
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
cin >> c[i];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
ll time = 1;
for (int i = 1; i <= n; ++i)
q.push({1, i});
while (h > 0)
{
auto t = q.top();
q.pop();
time = t.first;
h -= a[t.second];
q.push({time + c[t.second], t.second});
}
cout << time << endl;
}G. D-Function
算法：
数学，数论，组合数学，快速幂。
思路：
通过观察题目不难发现，\(D(kn)\)一般来说是小于等于\(k * D(n)\)，因为在乘法的过程中会有进位，数位就会变小。
所以只有在没有进位时 \(D(kn)\)才会严格等于\(k * D(n)\) 。
每一位 \(d\) 的选择为 \(d * k < 10\)，既每一位都要小于等于 \(d = ⌊9 / k⌋\)。
对于一个长度为 \(L\) 的数字串，其每一位都可以在 \([0, d]\) 中任选，所以共有 \((d + 1)^L\) 种选择。
合法个数共有 \((d+1)^r−(d+1)^l\) 种。
快速幂处理即可。
关键代码：
ll qmi(ll a, ll b, ll p)
{
ll ans = 1 % p;
while (b)
{
if (b & 1)
ans = ans * a % p;
b >>= 1;
a = a * a % p;
}
return ans;
}
void solve()
{
int l, r, k;
cin >> l >> r >> k;
ll cnt = 9 / k + 1;
cout << (qmi(cnt, r, MOD) - qmi(cnt, l, MOD) + MOD) % MOD << endl;
}H1. Maximize the Largest Component (Easy Version)
算法：
floodfill，差分。
思路：
观察到：当在一行或一列添加上 # 后，该行或列周围的连通块会被连接成一个更大的连通块。
首先，预处理每一行和每一列中 . 的数量，记录下来，后续在填充整行或整列时，这些 . 会变成新的 #，贡献新的点数。
接着，使用 BFS 找出所有的 # 连通块，并记录每个连通块的点数及其上下左右的边界范围。对于每个连通块，我们在其边界的外侧扩展出一圈，用来表示它可能通过某一行或列与其他连通块连接。
为了统计某一行或列可能连接的所有连通块的点数，我们使用两个差分数组，分别对应每一行和每一列，在每个连通块所能影响的范围内进行区间加法操作，值为该连通块的大小。最后对差分数组做一次前缀和，得到每一行和每一列最终能连接的所有连通块的总点数。
最终，枚举每一行和每一列，计算其能连接的连通块点数加上当前行或列新增的 # 点数，取其中的最大值作为答案。这个方法既高效又准确，能够在较大的数据范围内快速求解。
关键代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<string> g(n + 10);
for (int i = 1; i <= n; ++i)
{
cin >> g[i];
g[i] = ' ' + g[i];
}
vector<int> cntR(n + 10, 0);
vector<int> cntC(m + 10, 0);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (g[i][j] == '.')
{
++cntR[i];
++cntC[j];
}
}
}
ll size = 0;
ll minR = MAX, minC = MAX;
ll maxR = MIN, maxC = MIN;
vector<ll> R(n + 10, 0);
vector<ll> C(m + 10, 0);
vector<vector<ll>> st(n + 10, vector<ll>(m + 10, 0));
auto bfs = [&](int x, int y) -> void
{
queue<pii> q;
q.push({x, y});
st[x][y] = 1;
++size;
while (q.size())
{
auto [x, y] = q.front();
q.pop();
minR = min(minR, 1ll * x);
maxR = max(maxR, 1ll * x);
minC = min(minC, 1ll * y);
maxC = max(maxC, 1ll * y);
for (int i = 0; i < 4; ++i)
{
int a = x + dx[i], b = y + dy[i];
if (a > 0 && a <= n && b > 0 && b <= m && !st[a][b] && g[a][b] == '#')
{
st[a][b] = 1;
q.push({a, b});
++size;
}
}
}
};
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (st[i][j] || g[i][j] == '.')
continue;
size = 0;
minR = MAX, minC = MAX;
maxR = MIN, maxC = MIN;
bfs(i, j);
minR = max(minR - 1ll, 1ll);
maxR = min(maxR + 1ll, 1ll * n);
minC = max(minC - 1ll, 1ll);
maxC = min(maxC + 1ll, 1ll * m);
R[minR] += size;
R[maxR + 1] -= size;
C[minC] += size;
C[maxC + 1] -= size;
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
R[i] += R[i - 1];
ans = max(ans, cntR[i] + R[i]);
}
for (int i = 1; i <= m; ++i)
{
C[i] += C[i - 1];
ans = max(ans, cntC[i] + C[i]);
}
cout << ans << endl;
}H2. Maximize the Largest Component (Hard Version)
还没补。
