A - Square
- 思维
- 按行或列排序
signed main() {
int T = 1;
T = read();
while (T--) {
vector<pii> vec;
for (int i = 1; i <= 4; ++i) {
int u = read(), v = read();
vec.push_back({u, v});
}
sort(vec.begin(), vec.end());
int a = abs(vec[0].second - vec[1].second);
int b = abs(vec[0].first - vec[2].first);
writeln(a * b);
}
return 0;
}
B - Arranging Cats
- 思维
- 记录两个的
1
1
1 的数量。
- 相同位置同为
1
1
1 则不用操作。
- 谁大则答案加上减去相同位置同为
1
1
1 的数量（要么补，移，删）
signed main() {
int T = 1;
T = read();
while (T--) {
int n = read();
string s1, s2; cin >> s1 >> s2;
int cnt1 = count(s1.begin(), s1.end(), '1'), cnt2 = count(s2.begin(), s2.end(), '1');
int ans = 0;
int cnt = 0;
// tf(cnt1),tf(cnt2);
for (int i = 0; i < n; ++i) {
if (s1[i] == s2[i] && s1[i] == '1') ++cnt;
}
if (cnt1 >= cnt2) ans += cnt1 - cnt;
else ans += cnt2 - cnt;
writeln(ans);
}
return 0;
}
C - Sending Messages
- 模拟
- 两种方事选择消耗小的一种
signed main() {
int T = 1;
T = read();
while (T--) {
int n = read(), f = read(), a = read(), b = read();
vector<int> e(n + 1);
bool ff = 1;
int pre = 0;
for (int i = 1; i <= n; ++i) e[i] = read();
for (int i = 1; i <= n; ++i) {
if ((e[i] - pre) * a <= b) f -= (e[i] - pre) * a;
else f -= b;
if (f <= 0) {
ff = 0;
break;
}
pre = e[i];
}
ff? puts("yes"): puts("no");
}
return 0;
}
D - Very Different Array
- 贪心
-
a
a
a 最小的与
b
b
b 最大的匹配，
a
a
a 最大的与
b
b
b 最小的匹配。
signed main() {
int T = 1;
T = read();
while (T--) {
int n = read(), m = read();
deque<int> a, b;
for (int i = 1; i <= n; ++i) {
int u = read();
a.push_back(u);
}
for (int i = 1; i <= m; ++i) {
int u = read();
b.push_back(u);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end(), greater<int>());
int ans = 0;
for (int i = 0; i < n; ++i) {
int t1 = abs(a.front() - b.front()), t2 = abs(a.back() - b.back());
if (t1 > t2) {
ans += t1;
a.pop_front(), b.pop_front();
}
else {
ans += t2;
a.pop_back(), b.pop_back();
}
}
writeln(ans);
}
return 0;
}
E - Eat the Chip 待补
F - Sum of progression
- 根号分治
- 预处理
d
≤
n
dleq sqrt{n}
d≤n
d
>
s
q
r
t
??
O
(
n
?
n
)
d>sqrt{};O(ncdot sqrt{n})
d>sqrtO(n?n
vector<vector<int>> pref(N + 322, vector<int>(323)), sum(N + 322, vector<int>(323));
signed main() {
int T = 1;
T = read();
while (T--) {
int n = read(), q = read();
int D = sqrt(n);
// while (D * D < n) ++D;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= D; ++i) pref[1][i] = sum[1][i] = 0;
for (int d = 1; d <= D; ++d) {
for (int i = 1; i <= n; ++i) {
pref[i + d][d] = pref[i][d] + a[i];
sum[i + d][d] = sum[i][d] + a[i] * (i / d + 1);
}
}
while (q--) {
int s = read(), d = read(), k = read();
if (d <= D) {
int r = s + d * k;
writesp(sum[r][d] - sum▼显示[d] - (pref[r][d] - pref▼显示[d]) * (s / d));
}
else {
int ans = 0;
for (int i = 0; i < k; ++i) ans += a▼显示 * (i + 1);
writesp(ans);
}
}
puts("");
}
return 0;
}
G - Mischievous Shooter
- 枚举 + 模拟
- 枚举每一个点即可，只考虑图里第一个的情况，其余三个可以翻转矩形。
c
o
d
e
??
l
e
a
r
n
??
f
r
o
m
??
j
i
a
n
g
l
y
code ;learn;from;jiangly
codelearnfromjiangly 简洁多了
signed main() {
int T = 1;
T = read();
while (T--) {
int n = read(), m = read(), k = read();
vector<string> s(n);
for (int i = 0; i < n; ++i) cin >> s[i];
int ans = 0;
auto solve = [&] () {
vector<vector<int>> pref1(n, vector<int>(m)), pref2(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i) pref1[i][j] = pref1[i - 1][j];
if (i && j < m - 1) pref2[i][j] = pref2[i - 1][j + 1];
pref1[i][j] += (s[i][j] == '#');
pref2[i][j] += (s[i][j] == '#');
}
}
vector<vector<int>> dp(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (j) {
dp[i][j] = dp[i][j - 1];
if (i + j > k) {
int x = i, y = j - (k + 1);
if (y < 0) x += y, y = 0;
dp[i][j] -= pref2[x][y];
}
if (i >= k + 1) dp[i][j] += pref2[i - (k + 1)][j];
}
dp[i][j] += pref1[i][j];
if (i >= k + 1) dp[i][j] -= pref1[i - (k + 1)][j];
ans = max(ans, dp[i][j]);
}
}
};
solve();
reverse(s.begin(), s.end());
solve();
for (auto &it: s) reverse(it.begin(), it.end());
solve();
reverse(s.begin(), s.end());
solve();
writeln(ans);
}
return 0;
}