A. Creating Words
思路
模拟，交换输出即可
code
inline void solve() {
string a, b; cin >> a >> b;
swap(a[0], b[0]);
cout << a << ' ' << b << endl;
return;
}B. Maximum Multiple Sum
思路
暴力枚举
数学不会（）
code
inline void solve() {
int n; cin >> n;
int ans = -1, res = -1;
for (int x = 2; x <= n; x ++ ) {
int sum = 0;
for (int i = 1; i <= n / x; i ++ ) {
sum += i * x;
}
if (sum > res) {
res = sum;
ans = x;
}
}
cout << ans << endl;
return;
}C. Good Prefixes
思路
模拟，从左到右维护前缀和和最大值即可
code
inline void solve() {
int n; cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
ll sum = 0, maxv = -1;
int ans = 0;
for (int i = 1; i <= n; i ++ ) {
maxv = max(maxv, a[i]);
sum += a[i];
if (sum - maxv == maxv) ans += 1;
}
cout << ans << endl;
return;
}D. Manhattan Circle
思路
找#最多的行和列即可
code
inline void solve() {
int n, m; cin >> n >> m;
vector<int> col(m + 1), row(n + 1);
int cur1 = 0, cur2 = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
char tmp; cin >> tmp;
if (tmp == '#') {
col[j] += 1;
if (col[j] > col[cur2]) cur2 = j;
row[i] += 1;
if (row[i] > row[cur1]) cur1 = i;
}
}
}
cout << cur1 << ' ' << cur2 << endl;
return;
}E. Secret Box
思路
题目从这里变的开始有一点意思
记一开始给的为 a，b，c
我们选取的是 x，y，z
构成的答案为 (a - x + 1) * (b - y + 1) * (c - z + 1)
其中x，y，z要小于等于对应的边
div4，还是暴力枚举的难度
我们只要sqrtx枚举x，sqrt枚举y就可以了
code
inline void solve() {
ll a, b, c, v; cin >> a >> b >> c >> v;
ll ans = 0;
for (ll x = 1; x <= v / x; x ++ ) {
if (v % x == 0) {
ll i = x, s = v / i;
for (ll y = 1; y <= s / y; y ++ ) {
ll j = y, k = s / j;
if (s % y == 0) {
if (i <= a && j <= b && k <= c) {
ans = max(ans, (a - i + 1) * (b - j + 1) * (c - k + 1));
}
swap(j, k);
if (i <= a && j <= b && k <= c) {
ans = max(ans, (a - i + 1) * (b - j + 1) * (c - k + 1));
}
}
}
swap(i, s);
for (ll y = 1; y <= s / y; y ++ ) {
ll j = y, k = s / j;
if (s % y == 0) {
if (i <= a && j <= b && k <= c) {
ans = max(ans, (a - i + 1) * (b - j + 1) * (c - k + 1));
}
swap(j, k);
if (i <= a && j <= b && k <= c) {
ans = max(ans, (a - i + 1) * (b - j + 1) * (c - k + 1));
}
}
}
}
}
cout << ans << endl;
return;
}F. Final Boss
思路
一开始没想到优先队列的做法（）
不过早用早cd这点都知道，那么轮次越少打的伤害越少，反之亦成立
所以可以二分答案
code
const int N = 2e5 + 9;
ll h, n;
PLL a[N];
bool check(ll x) {
ll res = 0;
for (int i = 1; i <= n; i ++ ) {
res += a[i].first;
res += (x - 1) / a[i].second * a[i].first;
if (res >= h) return true;
}
return false;
}
inline void solve() {
cin >> h >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i].first;
for (int i = 1; i <= n; i ++ ) cin >> a[i].second;
ll l = 0, r = (ll)4e10 + 9;
while (l + 1 != r) {
ll mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid;
}
cout << r << endl;
return;
}G. D-Function
思路
进位是一件极其麻烦的事情，但是自己试过以后，发现进位就不能满足题意，输出0
那么我们只需考虑每位上的选择即可，每位上的选择数为 x // k + 1
一点点的容斥原理+快速幂
code
inline void solve() {
mod = MOD;
int l, r, k; cin >> l >> r >> k;
ll ans = qmi(9 / k + 1, r) - qmi(9 / k + 1, l);
ans = (ans + mod) % mod;
cout << ans << endl;
return;
}H1. Maximize the Largest Component (Easy Version)
思路
我们都会做修改哪一行或者哪一列让总数#最多，而这题只是多了一个连通块而已。
我们首先dfs遍历每个每一个连通块，用矩形将它框起来。
矩形的每一条边即对应了遍历到此连通块的行或者列的上下界。
再利用差分将连通块的数量记录即可。
code
inline void solve() {
int n, m; cin >> n >> m;
vector<vector<char>> mp(n + 1, vector<char>(m + 1));
vector<int> row(n + 1), col(m + 1);
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
cin >> mp[i][j];
if (mp[i][j] == '#') {
row[i] += 1;
col[j] += 1;
}
}
}
//for (int i = 1; i <= n; i ++ ) cout << row[i] << endl;
//for (int i = 1; i <= m; i ++ ) cout << col[i] << endl;
vector<vector<int>> vis(n + 1, vector<int>(m + 1));
vector<ll> r(n + 3), c(m + 3);
int up = 1e9, down = -1e9, left = 1e9, right = -1e9, cnt = 0;
function<void(int, int)> dfs = [&](int x, int y) {
if (vis[x][y]) return;
vis[x][y] = 1;
if (mp[x][y] != '#') return;
up = min(up, x), down = max(down, x), left = min(left, y), right = max(right, y);
cnt += 1;
if (x - 1 >= 1) dfs(x - 1, y);
if (x + 1 <= n) dfs(x + 1, y);
if (y - 1 >= 1) dfs(x, y - 1);
if (y + 1 <= m) dfs(x, y + 1);
};
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
if (mp[i][j] == '#' && !vis[i][j]) {
dfs(i, j);
r[up - 1] += cnt, r[down + 2] -= cnt;
c[left - 1] += cnt, c[right + 2] -= cnt;
//cerr << "cnt:" << cnt << endl;
up = 1e9, down = -1e9, left = 1e9, right = -1e9, cnt = 0;
}
}
}
ll ans = 0;
for (int i = 1; i <= n; i ++ ) r[i] += r[i - 1];
for (int i = 1; i <= m; i ++ ) c[i] += c[i - 1];
for (int i = 1; i <= n; i ++ ) {
ans = max(ans, (ll)(r[i] + m - row[i]));
}
for (int i = 1; i <= m; i ++ ) {
ans = max(ans, (ll)(c[i] + n - col[i]));
}
cout << ans << endl;
return;
}