【23.05.03】好题题解
好题题解
A
题目大意：
计算一个项数为 \(n\) 的多项式除以 \(x^3-x\) 的余数多项式。
数据范围：
对于 \(100\%\) 的数据：
- \(2 \leq n \leq 2 \times 10 ^ 5\)
解题分析：
水题，直接多项式除法模拟即可。
需要注意细节。
AC Code：
# include <bits/stdc++.h>
using namespace std;
# define int long long
# define f(i,a,b) for(int i = a; i <= b; i ++)
# define g(i,b,a) for(int i = b; i >= a; i --)
# define CI const int
CI maxn = 2e5 + 7;
int n;
int a[maxn];
signed main(){
freopen("remainder.in", "r", stdin);
freopen("remainder.out", "w", stdout);
cin >> n;
f (i, 1, n + 1)
scanf("%lld", &a[i]);
g (i, n + 1, 4){
a[i - 2] += a[i];
a[i] = 0;
}
int m = 1;
f (i, 1, n + 1)
if (a[i])
m = i;
printf("%lld\n", m - 1);
f (i, 1, m)
printf("%lld ", a[i]);
return 0;
}
B
题目大意：
有一个 \(n * n\) 的网格，每个网格有一个数 \(a_{i,j}\)，每走一步可以走到相邻的格子，走到 \((i,j)\) 需要耗费 \(a_{i,j}\) 的体力，体力 \(<= 0\) 就嘎了。若刚开始有 \(v\) 点体力，从 \(x_1, y_1\) 出发，问在不嘎的情况下，最少需要多少步，可以走到 \(x_2, y_2\)。如果走不到，输出 NO。
数据范围：
对于 \(100\%\) 的数据：
- \(1 \leq n \leq 100\)
- \(0 \leq a_{i,j} \leq 9\)
- \(0 \leq v \leq 10000\)
解法分析：
注意到数据范围很小，可以考虑 \(dp\)。
设 \(dp_{i,j,k}\) 表示走 \(i\) 步到达 \((j,k)\) 时的最大体力值。那么，\(dp_{i,j,k} = \min{\{dp_{i-1,u,v} - a_{j,k}\}}\)。
需要注意的是，第一维需要开滚动数组优化。
AC Code：
# include <bits/stdc++.h>
using namespace std;
# define int long long
# define f(i,a,b) for(int i = a; i <= b; i ++)
# define g(i,b,a) for(int i = b; i >= a; i --)
# define CI const int
CI maxn = 107;
CI maxm = 5507;
CI dx[] = {0, 1, 0, -1};
CI dy[] = {1, 0, -1, 0};
int n, v;
int stx, sty, edx, edy;
int a[maxn][maxn];
int dp[2][maxn][maxn];
signed main(){
freopen("desert.in", "r", stdin);
freopen("desert.out", "w", stdout);
cin >> n >> v >> sty >> stx >> edy >> edx;
f (i, 1, n)
f (j, 1, n)
scanf("%lld", &a[i][j]);
f (j, 0, n)
f (k, 0, n)
dp[0][j][k] = -2e18;
dp[0][stx][sty] = v;
f (i, 1, n * n){
f (j, 1, n){
f (k, 1, n){
dp[i % 2][j][k] = -2e18;
f (l, 0, 3){
int nx = j + dx[l];
int ny = k + dy[l];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
dp[i % 2][j][k] = max(dp[(i - 1) % 2][nx][ny] - a[j][k], dp[i % 2][j][k]);
}
// if (dp[i][j][k] == -2e18) printf("-inf ");
// else printf("%lld ", dp[i][j][k]);
}
// printf("\n");
}
if (dp[i % 2][edx][edy] > 0){
printf("%lld\n", i);
// system("pause");
return 0;
}
// printf("\n");
}
printf("-1\n");
// system("pause");
return 0;
}
C
题目大意：
给定一个长度为 \(n\) 的仅包含 \(\{-1,0,1\}\) 的序列，你可以做任意多次如下操作：
选择一个 \(2 \leq i \leq n\)，执行 \(a_i += a_{i-1}\)。
你的目标是将序列优化为单调不降的，你想知道最少要做多少次操作。
数据范围：
对于 \(100\%\) 的数据：
- \(1 \leq n \leq 10^6\)
解法分析：
一道线性 \(dp\) 好题。
设 \(dp_{i,j=-1/0/1}\) 表示第 \(i\) 位要变成 \(j\) 且前 \(i\) 项单调不降的最少操作次数。则只需根据变大/变小/不变三种情况分类讨论即可。
注意：第二维的 \(-1/0/1\) 可以改成 \(0/1/2\)。
AC Code：
# include <bits/stdc++.h>
using namespace std;
# define int long long
# define f(i,a,b) for(int i = a; i <= b; i ++)
# define g(i,b,a) for(int i = b; i >= a; i --)
# define CI const int
CI maxn = 1e6 + 7;
int n;
int a[maxn];
int dp[maxn][3];
signed main(){
freopen("optimize.in", "r", stdin);
freopen("optimize.out", "w", stdout);
cin >> n;
f (i, 1, n) scanf("%lld", &a[i]);
f (i, 1, n)
f (j, 0, 2)
dp[i][j] = 2e18;
dp[1][a[1] + 1] = 0;
f (i, 2, n){
f (j, -1, 1){
if (a[i] == j){
f (k, -1, j)
dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][k + 1]);
}
else if (a[i] > j)
dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][0] + (a[i] - j));
else if (j == 1)
dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][2] + (j - a[i]));
}
}
int ans = min(dp[n][0], min(dp[n][1], dp[n][2]));
if (ans >= 2e18) printf("NO");
else printf("%lld", ans);
// system("pause");
return 0;
}
还没写完呢，还有 Atcoder 的题没写呢。
吃饭去了，尽请期待。