ARC128 A-D简要题解
A
题意
初始给定(1)个物品1，(0)个物品2 给定序列(A_i),每次可以把所有物品1变为(A_i)倍物品2,或者把所有物品2变为(frac{1}{A_i}) 倍物品1
每次可以选择操作或者不操作，求最终的操作序列
分析
显然我们有一个无脑的DP做法：
(dp[i][0/1])表示前(i)次选择中进行了偶数/奇数次操作
转移(dp[i][0] = max(dp[i -1][0],dp[i-1][1] / A[i]),dp[i][1] = max(dp[i-1][0] imes A[i],dp[i-1][1]))
DP过程中记录转移路径，最后递归输出即可，这样做的问题是(A_i)值域过大，(dp)数组难以存储 处理方法可以用对所有数取log，当然这在有些情况可能出现精度问题
事实上注意到(frac{a}{b} imes frac{b}{c} = frac{a}{c}) 所以直接贪心即可
代码
const int maxn = 2e5 + 5;
double dp[maxn][2];
double a[maxn];
int path[maxn][2];
int n;
void dfs(int n,int op){
if(!n) return;
dfs(n - 1,path[n][op] ? op ^ 1 : op);
printf("%d ",path[n][op]);
}
int main(){
n = rd();
for(int i = 1;i <= n;i++)
a[i] = rd();
dp[0][0] = log(1);
dp[0][1] = -1e9;
for(int i = 1;i <= n;i++){
double x = dp[i - 1][0];
double y = dp[i - 1][1] - log(a[i]);
if(x > y) path[i][0] = 0;
else path[i][0] = 1;
dp[i][0] = max(x,y);
double xx = dp[i - 1][0] + log(a[i]);
double yy = dp[i - 1][1];
if(xx > yy) path[i][1] = 1;
else path[i][1] = 0;
dp[i][1] = max(xx,yy);
}
dfs(n,0);
}
B.
题意
给定(R)个红球，(G)个绿球，(B)个蓝球
可以做任意次以下操作：选择两个不同颜色的球把他们变为剩下颜色的球
求最小的操作次数使得所有球变为同一个颜色
分析
操作其实就是让两个数-1，另一个数+2
手玩一下可以发现，通过3步操作，可以变为0，-3，+3
这表示3步操作可以只改变其中两个数，改变的值是3，如果能够让三个数中某两个数相等，就可以不断对这两个操作达到结果
因为只需要枚举不变的数，判剩下的数是否同余3即可
代码
int main(){
int T = rd();
while(T--){
int a = rd();
int b = rd();
int c = rd();
int ans = 1e9;
if(abs(a - b) % 3 == 0) {
int res = abs(a - b) / 3 * 3;
res += min(a,b);
ans = min(ans,res);
}
if(abs(a - c) % 3 == 0) {
int res = abs(a - c) / 3 * 3;
res += min(a,c);
ans = min(ans,res);
}
if(abs(b - c) % 3 == 0) {
int res = abs(b - c) / 3 * 3;
res += min(b,c);
ans = min(ans,res);
}
if(ans == 1e9) puts("-1");
else cout << ans << '
';
}
}
C
题意
给定数(M,S)
给定长度(N)的数组(A)
构造长度(N)的数组(X)满足
分析
贪心性质还是比较明显吧
(x)分配总是对一段后缀满足(x_i = x_{i + 1} = ...x{N})
若存在(j <i)且(x_j != 0) ,把这个(x_j)分配到(x_i)中最大的显然更优
那么考虑后缀有数的情况就有两种：
大小超过(M) ，这个时候说明有多余的(S),此时只需对前一段继续做一次贪心
没有超过(M),全填(M)
第一种情况的不超过(M)是可以钦定的，其实写起来还是有点烦琐
代码
const int maxn = 2e5 + 5;
int main(){
int n = rd();
int m = rd();
int s = rd();
VI a(n);
for(int i = 0;i < n;i++)
a[i] = rd();
VI x(n + 1),y(n + 1);
ll sum = 0;
for(int i = n - 1;i >= 0;i--){
sum += a[i];
x[n - i] = (ll)(n - i) * m;
y[n - i] = (ll)sum * m;
}
double ans = 0;
for(int i = 0;i <= n;i++){
if(x[i] <= s)
ans = max(ans,(double)y[i]);
}
for(int i = 0;i <= n;i++){
if(x[i] < s) {
for(int j = 0;j <= n;j++){
if(x[j] > s) {
ans = max(ans,((double)y[i] * (x[j] - s) + (double)y[j] * (s - x[i])) / (double)(x[j] - x[i]));
}
}
}
}
printf("%.10f",ans);
}
D
题意
给定(N)个数，若存在连续的(x,y,z)满足(A_x eq A_y ,A_y eq A_z) 就可以删除(A_y)
可以执行无限次操作，求剩余序列的下标组成的序列个数
分析
显然如果存在(A_i = A_{i + 1})那么(i,i+1) 必定无法删除，换言之两边的方案独立
于是问题变为了不存在(A_i = A_{i+1})的情况，可以归纳得出若连续的一段中存在大于等于3种数，则可以任意删除，于是可以DP
考虑转移需要注意(A_{i-1}= A_{i+1})的地方
代码
int a[maxn];
int solve(int l,int r){
int len = r - l + 1;
if(len <= 2) return 1;
VI v(len + 1),pre(len + 1),sum(len + 1),dp(len + 1);
for(int i = 1;i <= len;i++)
v[i] = a[l + i - 1];
pre[1] = 1;
pre[2] = 1;
for(int i = 3;i <= len;i++){
pre[i] = i - 1;
if(v[i] == v[i - 2]) pre[i] = pre[i - 1];
}
dp[1] = dp[2] = sum[1] = 1;
sum[2] = 2;
for(int i = 3;i <= len;i++){
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
add(dp[i],sum[min(i - 2,pre[i]) - 1]);
sum[i] = (sum[i - 1] + dp[i]) % MOD;
}
return dp[len];
}
int main(){
int n = rd();
for(int i = 1;i <= n;i++)
a[i] = rd();
int l = 1;
int ans = 1;
for(int i = 1;i < n;i++){
if(a[i] == a[i + 1]) {
ans = mul(ans,solve(l,i));
l = i + 1;
}
}
ans = mul(ans,solve(l,n));
cout << ans;
}