A
9，98,989,9890......
#include <bits/stdc++.h>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define dow(i,j,k) for (int i = j; i >= k; i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> pi;
typedef long long ll;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
if (n == 1) puts("9");
else if (n == 2) puts("98");
else {
printf("98");
n -= 2;
int i = 9;
while (n--) {
putchar('0' + i);
i = (i + 1) % 10;
}
puts("");
}
}
}
B
考虑中间那个数，它如果要变相当于只有变成左边这个数或者右边这个数这两种情况，然后求一下最多能减少几个就好。
#include <bits/stdc++.h>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define dow(i,j,k) for (int i = j; i >= k; i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> pi;
typedef long long ll;
const int N = 3e5 + 100;
int a[N];
int n;
inline bool pd(int x, int y, int z){
return (x > 0 && z <= n && ((a[x] < a[y] && a[y] > a[z]) || (a[x] > a[y] && a[y] < a[z])));
}
void solve() {
int cnt = 0, ans = 0;
scanf("%d", &n);
rep(i,1,n) scanf("%d", &a[i]);
rep(i,2,n-1) {
if (a[i] > a[i-1] && a[i] > a[i+1]) cnt++;
else if (a[i] < a[i-1] && a[i] < a[i+1]) cnt++;
else continue;
int tmp1 = pd(i-2, i-1, i) + pd(i, i+1, i+2) - pd(i-1, i+1, i+2);
int tmp2 = pd(i-2, i-1, i) - pd(i-2, i-1, i+1) + pd(i, i+1, i+2);
ans = max(ans, 1 + max(tmp1, tmp2));
}
printf("%d\n", cnt - ans);
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
}
C
两种情况，牺牲元素和最小的背包，牺牲两个背包里的最小元素。然后去最大就好了。
#include <bits/stdc++.h>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define dow(i,j,k) for (int i = j; i >= k; i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<long long, long long> pi;
pi b[4];
bool cmp(pi x, pi y) {
if (x.se == y.se) return x.fi < y.fi;
return x.se < y.se;
}
int main() {
int n[4];
rep(i,1,3) scanf("%d", &n[i]);
rep(j,1,3)
rep(i,1,n[j]) {
ll x;
scanf("%lld", &x);
b[j].fi+= x;
if (!b[j].se) b[j].se = x;
else b[j].se = min(b[j].se, x);
}
ll ans = 0;
sort(b + 1, b + 4);
ans = b[3].fi + b[2].fi - b[1].fi;
sort(b + 1, b + 4, cmp);
ans = max(ans, b[1].fi + b[2].fi + b[3].fi - 2 * b[1].se - 2 * b[2].se);
cout << ans << endl;
}
D
计数问题，考虑每个位置会被计算多少次。
\(dp[i][j]\)表示长度为i的路径j为结尾的路有多少种。\(dp[0][i] = 1\)作为初始值。那么位置i出现在第j个的路径数是\(dp[i][j] * dp[i][k-j]\)，这里是将第j个位置到开头和到结尾分成两条长度为\(j\)和\(k-j\)的分别以\(i\)作为结尾和开头的路径。
#include <bits/stdc++.h>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define dow(i,j,k) for (int i = j; i >= k; i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> pi;
typedef long long ll;
const int N = 5005;
const int mod = 1e9 + 7;
ll f[N][N];
ll cnt[N];
int a[N];
int n, k, q;
int main() {
scanf("%d%d%d", &n, &k, &q);
rep(i,1,n) f[0][i] = 1;
rep(i,1,k) rep(j,1,n) {
f[i][j] = (f[i-1][j-1] + f[i-1][j+1]) % mod;
}
rep(i,0,k) rep(j,1,n) cnt[j] = (cnt[j] + (f[i][j] * f[k-i][j]) % mod) % mod;
rep(i,1,n) scanf("%d", &a[i]);
ll ans = 0;
rep(i,1,n) ans = (ans + cnt[i] * a[i] % mod) % mod;
rep(i,1,q) {
int x;
scanf("%d", &x);
ans = (ans - a[x] * cnt[x] % mod) % mod;
scanf("%d", &a[x]);
ans = (ans + a[x] * cnt[x] % mod + mod) % mod;
printf("%lld\n", ans);
}
}
E
考虑把\(x\)当做树根，如果在某个儿子为根的子树中有\(u\)满足\(a[x] = a[u]\)，那么满足条件的点一定在\(x\)的这个子树中。
用上面这个结论，用树上差分来打标记，就能找到所有的符合条件的点。
#include <bits/stdc++.h>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define dow(i,j,k) for (int i = j; i >= k; i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> pi;
typedef long long ll;
const int N = 2e5 + 100;
vector<int>G[N];
int cnt[N], num[N], a[N], b[N];
int st[N], ed[N], n, sum[N];
int tot;
void dfs(int x, int fa) {
st[x] = ++tot;
int tmp = num[a[x]];
num[a[x]]++;
for (auto v:G[x]) {
if (v == fa) continue;
int tmp1 = num[a[x]];
dfs(v, x);
if (num[a[x]] > tmp1) {
sum[1]++;
sum[st[v]]--;
sum[ed[v]+1]++;
}
}
ed[x] = tot;
if (num[a[x]] - tmp != cnt[a[x]]) {
sum[st[x]]++;
sum[ed[x]+1]--;
}
}
int main() {
scanf("%d", &n);
rep(i,1,n) scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + n + 1);
rep(i,1,n) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b, cnt[a[i]]++;
rep(i,1,n-1) {
int u, v;
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
dfs(1,-1);
int ans = 0;
rep(i,1,n) {
sum[i]+=sum[i-1];
if (sum[i] == 0) ans++;
}
printf("%d\n", ans);
}