A
双指针
#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
const int N = 2e5 + 10;
int T, n, d;
int a[N];
int main() {
scanf("%d", &T);
while (T -- ) {
scanf("%d", &n);
d = -1;
vector<PII> ans;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; ) {
int j = i + 1;
while (j <= n && a[j] >= a[j - 1]) j ++;
d = max(d, a[j - 1] - a[i]);
i = j;
}
for (int i = 1; i <= n; ) {
int j = i + 1;
while (j <= n && a[j] >= a[j - 1]) j ++;
if (d == a[j - 1] - a[i]) ans.push_back({i, j - 1});
i = j;
}
for (auto x : ans)
printf("%d %d ", x.first, x.second);
puts("");
}
return 0;
}
B
暴力
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int T, n, m;
char s[N];
char a[N][N];
int main() {
scanf("%d", &T);
while (T -- ) {
int ans = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
scanf("%s", s + 1);
for (int j = 1; j <= m; j ++ )
a[i][j] = s[j];
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (a[i][j] == '*')
for (int i1 = -1; i1 <= 1; i1 ++ )
for (int j1 = -1; j1 <= 1; j1 ++ )
if (i + i1 >= 1 && i + i1 <= n && j + j1 <= m && j + j1 >= 1 && a[i + i1][j + j1] != '*')
a[i + i1][j + j1] = 'Z';
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (a[i][j] == 'P')
ans ++;
printf("%d\n", ans);
}
return 0;
}
C
根据题意模拟
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int T, n, r, g, ex;
int m, m1, m2;
int main() {
scanf("%d", &T);
while (T -- ) {
scanf("%d%d.%d", &n, &m1, &m2);
ex = 0;
m = (m1 - 1) * 100 + m2 * 10;
while (n) {
r = n * 100, g = min(10000, n * m);
n = r / 200, ex += r / 10;
ex += g / 10;
}
printf("%d\n", ex);
}
return 0;
}
D
简单数学
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
int T, p, ans;
int len1, len2;
string s1, s2;
signed main() {
cin >> T;
while (T -- ) {
p = 1;
ans = 0;
cin >> s1 >> s2;
len1 = s1.size(), len2 = s2.size();
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
for (int i = 0; i < len1; i ++ ) {
int k = s1[i] - '0';
ans = (ans + k * p % MOD * len2) % MOD;
p = (p * 10) % MOD;
}
p = 1;
for (int i = 0; i < len2; i ++ ) {
int k = s2[i] - '0';
ans = (ans + k * p % MOD * len1) % MOD;
p = (p * 10) % MOD;
}
cout << ans << endl;
}
return 0;
}
E
找到所有黑点的数量后,\(C_{cnt}^{2}\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e6 + 10;
int T, n, res;
bool st[N];
int h[N], e[N * 2], ne[N * 2], idx;
struct node {
int ver, d;
};
signed main() {
scanf("%lld", &T);
while (T -- ) {
scanf("%lld", &n);
int max_d = 1;
idx = 0, res = 0;
for (int i = 1; i <= n; i ++ ) st[i] = 0;
for (int i = 1; i <= n; i ++ ) h[i] = -1;
function<void(int, int)> add = [&](int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
};
for (int i = 1; i < n; i ++ ) {
int a, b;
scanf("%lld%lld", &a, &b);
add(a, b), add(b, a);
}
function<void()> bfs = [&]() {
queue<node> q;
q.push({1, 1});
st[1] = 1;
while (q.size()) {
auto t = q.front();
q.pop();
int u = t.ver, step = t.d;
if (step % 2 == 1) res ++;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (st[j]) continue;
q.push({j, step + 1});
st[j] = true;
}
}
};
bfs();
printf("%lld\n", res + res * (res - 1) / 2);
}
return 0;
}
F
贪心,如果最长的数量小于总长的一半则所有点都成立
否则,只有在最长链上的点才成立,用最长链的长度减去两端不满足条件的即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int T, n, sum, maxx;
int a[N];
signed main() {
scanf("%lld", &T);
while (T -- ) {
scanf("%lld", &n);
sum = 0, maxx = 0;
for (int i = 1; i <= n; i ++ )
scanf("%lld", &a[i]), sum += a[i], maxx = max(maxx, a[i]);
if (maxx <= sum - maxx)
printf("%lld\n", sum);
else
printf("%lld\n", maxx - (maxx - sum / 2 - 1) * 2);
}
return 0;
}