圆弧128a-d的简单解法。

ARC128 A-D简要题解

A

题意

给定初始\(1\)项1和\(0\)项2以及序列\(A_i\)，所有项1可以一次更改为\(A_i\)次项2，或者所有项2可以更改为\(\frac{1}{A_i}\。

您可以选择每次操作或不操作，以找到最终的操作顺序。

2\times10^5\\

1 \leq A_i \leq 10^9

\]

分析

显然，我们有一个无脑的DP实践：

\(dp[i][0/1]\)表示在之前的\(i\)选择中执行了偶/奇操作。

转移\ (DP [I] [0]=最大值(DP [I-1] [0]，DP [I-1] [1]/a [I])，DP [I] [1]=最大值(DP [I-1] [0] \乘以a [I]。

记录DP过程中的传递路径，然后递归输出。问题是\(A_i\)的取值范围太大，\(dp\)的数组很难存储。处理方法可以对所有数字使用日志。当然，在某些情况下可能会有精度问题。

其实我注意到了\(\ frac { a } { b } \ times \ frac { b } { c }=\ frac { a } { c } \)，所以可以直接贪心。

代码

const int maxn=2e5 5

双DP[maxn][2]；

double a[maxn]；

int路径[maxn][2]；

int n；

void dfs(int n，int op){ 0

if(！n)返回；

dfs(n - 1，路径[n][op]op ^ 1 : op)；

printf('%d '，路径[n][op])；

}

int main(){ 0

n=rd()；

for(int I=1；I=n；(一)

a[I]=rd()；

DP[0][0]=log(1)；

DP[0][1]=-1e 9；

for(int I=1；I=n；I){ 0

double x=DP[I-1][0]；

double y=DP[I-1][1]-log(a[I])；

if(x y)路径[I][0]=0；

else路径[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)路径[I][1]=1；

else路径[I][1]=0；

dp[i][1]=最大值(xx，YY)；

}

dfs(n，0)；

}

B.

题意

给定红球、绿球和蓝球。

您可以随时执行以下操作：选择两个不同颜色的球，并将它们变成剩余颜色的球。

找到使所有球变成相同颜色的最小操作数。

10^8

\]

分析

实际上，操作是做两个数字-1和另一个数字2。

你可以发现它可以被改变为0，-3，3到3步。

这意味着三个步骤中只能更改两个，更改后的值为3。如果三个数字中的两个可以相等，那么这两个操作的结果可以连续获得。

因为你只需要枚举常量数，就可以判断剩下的数是否与3全等。

代码

int main(){ 0

int T=rd()；

而(T-){ 0

int a=rd()；

int b=rd()；

int c=rd()；

int ans=1e9

if(ABS(a-b)% 3==0){ 0

int RES=ABS(a-b)/3 * 3；

res=min(a，b)；

ans=min(ans，RES)；

}

if(ABS(a-c)% 3==0){ 0

int RES=ABS(a-c)/3 * 3；

res=min(a，c)；

ans=min(ans，RES)；

}

if(ABS(B- c)% 3==0){ 0

int RES=ABS(B- c)/3 * 3；

res += min(b,c);
ans = min(ans,res);
}
if(ans == 1e9) puts("-1");
else cout ans '\n';
}
}

C

题意

给定数\(M,S\)

给定长度\(N\)的数组\(A\)

构造长度\(N\)的数组\(X\)满足

\[0 \leq x_1 \leq x_2...\leq x_n \leq M\\
\sum x_i = S
\]\[1 \leq N \leq 5000\\
1 \leq M \leq 10^6\\
1 \leq S \leq min(N \times M,10^6)\\
1 \leq A_i\leq 10^6
\]

分析

贪心性质还是比较明显吧

\(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 \neq A_y ,A_y \neq A_z\) 就可以删除\(A_y\)

可以执行无限次操作，求剩余序列的下标组成的序列个数

\[2 \leq N \leq 200000\\
1 \leq A_i \leq N
\]

分析

显然如果存在\(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;
}