ABC240 复盘
[ABC240C] Jumping Takahashi
思路解析
显而易见，求是否可能，用可能性 dp 即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10, M = 1e4 + 10;
int n, x, a[N], b[N];
bool f[N][M];
int main() {
cin >> n >> x;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
f[0][0] = true;
for(int i = 1; i <= n; i++) {
for(int j = 0; j + a[i] <= x; j++) f[i][j + a[i]] |= f[i - 1][j];
for(int j = 0; j + b[i] <= x; j++) f[i][j + b[i]] |= f[i - 1][j];
}
if(f[n][x]) puts("Yes");
else puts("No");
return 0;
}
[ABC240D] Strange Balls
思路解析
这题我的做法十分的抽象，我用了一个类似链表一样的东西，存下放完前 \(i\) 个球后，第 \(i\) 个球下面那个球的编号是多少，还有连续的与当前球值相等的长度是多少，这样就可以通过此题。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], top[N], sum[N], sz[N], st[N], l[N];
int main() {
cin >> n;
int lst = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
top[i] = top[lst];
sum[i] = sum[lst];
st[i] = st[lst];
sz[i] = sz[lst];
l[i] = lst;
if(a[i] != top[lst]) {
top[i] = a[i];
st[i] = i;
sum[i] = 0;
}
lst = i;
sum[i]++; sz[i]++;
if(sum[i] == a[i]) {
sz[i] -= sum[i];
sum[i] = 0;
lst = l[st[i]];
}
cout << sz[i] << '\n';
}
return 0;
}
[ABC240E] Ranges on Tree
思路解析
由题意可知，只要一个点的所有儿子节点都被确定了，那么当前节点也就被确定了。也就是说，只要确定了所有叶子节点，也就能一层层地确定所有节点，而叶子节点没有儿子节点不受此条件的约束，同时我们希望 \(\max\limits^N_{i=1}R_i\) 最小，所以我们把所有叶子节点的区间长度都置为 \(1\) 即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, fa[N], son[N], cnt = 0, l[N], r[N];
vector<int> g[N];
void dfs(int u, int f) {
fa[u] = f;
for(auto it : g[u]) if(it != f) son[u]++;
if(son[u] == 0) l[u] = r[u] = ++cnt;
else l[u] = 2e9, r[u] = 0;
for(auto it : g[u]) {
if(it != f) dfs(it, u), l[u] = min(l[u], l[it]), r[u] = max(r[u], r[it]);
}
}
int main() {
cin >> n;
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
for(int i = 1; i <= n; i++) {
cout << l[i] << ' ' << r[i] << '\n';
}
return 0;
}
[ABC240F] Sum Sum Max
思路解析
求两次前缀和，如果暴力肯定会错，但是我们发现 \(N\) 很小，于是可以想到我们将每一个连续的一段长度为 \(y_i\) 的区间记作第 \(i\) 个块，我们可以先只统计块的结尾处的值，这样就可以避免超时。但是肉眼可见这种方法有一个漏洞，那就是在 \(x_i<0\) 时有可能导致块中间的值大于两头的值，所以我们就需要找到这个中间值，然后就可以通过了。
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int T, n, m, x[N], y[N];
int b[N], s[N], p[N];
int sum(int t) {
return t * (t + 1) / 2;
}
signed main() {
cin >> T;
while(T--) {
cin >> n >> m;
for(int i = 0; i <= n; i++) p[i] = x[i] = y[i] = b[i] = s[i] = 0;
int mx = -4e18;
for(int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
b[i] = b[i - 1] + x[i] * y[i];
s[i] = s[i - 1] + b[i - 1] * y[i] + x[i] * sum(y[i]);
mx = max(mx, s[i]);
if(x[i] < 0) {
int l = max(1ll, min(b[i - 1] / (-x[i]), y[i]));
int tmp = s[i - 1] + b[i - 1] * l + x[i] * sum(l);
mx = max(mx, tmp);
}
}
cout << mx << '\n';
}
return 0;
}
[ABC240G] Teleporting Takahashi
思路解析
和我们之前做过的一道题很像，只不过从二维进化成了三维，同时少了一些条件，但是我们依然可以使用那题的想法。我们可以先只考虑在 \(x,y\) 轴上的方案数，在考虑 \(z\) 轴的方案。而对于前者我们可以用上面那题用到的旋转方法来求解，而后者则就没有什么难度，只有组合数了。
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7 + 10, mod = 998244353;
int fact[N], inv[N];
int ksm(int a, int b, int p) {
int ans = 1;
while(b) {
if(b & 1) {
ans = ans * a % p;
}
a = a * a % p;
b >>= 1;
}
return ans;
}
int c(int x, int y) {
return fact[x] * inv[x - y] % mod * inv[y] % mod;
}
int calc(int k, int x, int y) {
int a = abs(x - y), b = abs(x + y);
if((k + a) & 1 || (k + b) & 1 || (k < a) || (k < b)) return 0;
return c(k, k + a >> 1) * c(k, k + b >> 1) % mod;
}
signed main() {
int n, x, y, z, ans = 0;
cin >> n >> x >> y >> z;
x = abs(x), y = abs(y), z = abs(z);
fact[0] = 1;
for(int i = 1; i <= 1e7; i++) fact[i] = fact[i - 1] * i % mod;
inv[(int)1e7] = ksm(fact[(int)1e7], mod - 2, mod);
for(int i = (int)1e7 - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
for(int i = 0, j = x; i + j <= n; i++, j++) {
ans += c(n, i) * c(n - i, j) % mod * calc(n - i - j, y, z) % mod;
ans %= mod;
}
cout << ans;
return 0;
}