本应$280$的，结果打表太大，拒绝评测，只有$180$。

Problem A 旅行

题面

现在有一段不平整的路，第$i$段的高度为$a_i$。你可以花费$|a_i-k|$，使第$i$段的高度变为$k$，使$\sum_{i=1}^{n-1}|a_i-a_{i+1}|$最小。

题解

贪心地从左到右扫一遍，枚举第$i$段路。如果要使得从$i-1$到$i+1$的体力消耗最小，那么就要两端距离间的差距最小。

• 如果$a_{i-1}$和$a_{i+1}$都小于$a_i$，那么就将$a_i$改变为$max(a_{i-1},a_{i+1})$。
• 如果$a_{i-1}$和$a_{i+1}$都大于$a_i$，那么就将$a_i$改变为$min(a_{i-1},a_{i+1})$。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN=100005;
int main(){
#ifndef FILE_IN
    freopen("travel.in","r",stdin);
#endif
#ifndef FILE_OUT
    freopen("travel.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    int n;
    int a[MAXN]={0};
    long long ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<n;i++){
        if((a[i-1]>a[i]&&a[i]<a[i+1])){
            if(a[i-1]>a[i+1]){
                ans+=a[i+1]-a[i];
                a[i]=a[i+1];
            }
            else{
                ans+=a[i-1]-a[i];
                a[i]=a[i-1];
            }
        }
        else if(a[i-1]<a[i]&&a[i]>a[i+1]){
            if(a[i-1]>a[i+1]){
                ans+=a[i]-a[i-1];
                a[i]=a[i-1];
            }
            else{
                ans+=a[i]-a[i+1];
                a[i]=a[i+1];
            }
        }
    }
    for(int i=1;i<n;i++){
        ans+=abs(a[i]-a[i+1]);
    }
    cout<<ans<<endl;
    return 0;
}

Problem B 石头剪刀布

题面

小菜给出一个自然数$n$，小明和小头轮流操作，每次操作可以把$n$减去$n$所拥有的数字中的最大值或者最小值（不包括0），不能操作者输（即$n=0$ 时）。

试求双方最优策略时的胜负情况。（小明先手）

题解

递推。$$fuck_x=(!fuck_{x-findmax(x)})||(!fuck_{x-findmin(x)})$$

代码

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=1000005;
bool fuck[MAXN]={0,1,1,1,1,1,1,1,1,1};
short findmin(int x){
    short ans;
    do{
        ans=x%10;
        x/=10;
    }
    while(x!=0&&ans==0);
    while(x){
        if(x%10<ans&&x%10>0){
            ans=x%10;
        }
        x/=10;
    }
    return ans;
}
short findmax(int x){
    short ans;
    do{
        ans=x%10;
        x/=10;
    }
    while(x!=0&&ans==0);
    while(x){
        if(x%10>ans&&(x%10)){
            ans=x%10;
        }
        x/=10;
    }
    return ans;
}
void dfs(int x){
    fuck[x]=(!fuck[x-findmax(x)])||(!fuck[x-findmin(x)]);
}
int main(){
    ios::sync_with_stdio(false);
    for(int i=10;i<MAXN;i++){
        dfs(i);
    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int q;
        cin>>q;
        if(fuck[q]){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

Problem C 环中环

题面

$n$个整数围成一个环，选出其中的若干数，使得选中的数所组成的环中，两个相邻数的差的绝对值不等于$1$。在满足这个前提下，问最多能取多少个数。

题解

动态规划。设$f_i$表示以$i$为终点时最多能取多少个数。$$f_i=f_j+1(abs( a_i-a_j) \neq 1)$$

由于题目要求是环形，因此可以将原数列复制一份接在后面，处理完后答案除以$2$即可。

我们发现$(abs( a_ i-a_ j ) \neq 1)$的数最多只有两个，所以我们只要记录$3$个不同的$a_i$所对应的最大的$3$个$f$的值，直接转移即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, a[200001], f[200001], tr[5000000], zl;
void find( int z, int x, int y, int l, int r ) {
    if ( ( x == l ) && ( y == r ) )
        zl = max( zl, tr[z] );
    else {
        int mid = ( x + y ) / 2;
        if ( r <= mid )
            find( z * 2, x, mid, l, r );
        else {
            if ( l > mid )
                find( z * 2 + 1, mid + 1, y, l, r );
            else {
                find( z * 2, x, mid, l, mid );
                find( z * 2 + 1, mid + 1, y, mid + 1, r );
            }
        }
    }
}
int findx( int x, int y ) {
    zl = 0;
    if ( x >= 0 && y >= 0 )
        find( 1, 0, 1100000, x, y );
    else
        return ( 0 );
    return ( zl );
}
void change( int z, int x, int y, int l ) {
    if ( x == y )
        tr[z] = zl;
    else {
        int mid = ( x + y ) / 2;
        if ( l <= mid )
            change( z * 2, x, mid, l );
        else
            change( z * 2 + 1, mid + 1, y, l );
        tr[z] = max( tr[z * 2], tr[z * 2 + 1] );
    }
}
int main() {
    ios::sync_with_stdio( false );
    cin >> n;
    int i, j, k;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    memset( tr, 0, sizeof( tr ) );
    for ( int i = 1; i <= 2 * n; i++ ) {
        f[i] = max( findx( a[i] + 2, 1100000 ), max( findx( 0, a[i] - 2 ), findx( a[i], a[i] ) ) );
        zl = f[i] + 1;
        f[i] += 1;
        change( 1, 0, 1100000, a[i] );
    }
    cout << ( tr[1] >> 1 ) << endl;
    return 0;
}

Problem D 寻找神格

题面

维护一个序列，使之支持下列操作：

• 一个区间增加一个定值。
• 求指定区间方差。
• 求指定区间和。

题解

分块。

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N=100010;
const int M=350;
int n,Q,T,L[M],R[M],pos[N];
ll ans[M],add[M],sum[M],a[N],Read,f,x,y,z;
char ch;

ll read(){
    Read=0;f=1;ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9')Read=(Read<<3)+(Read<<1)+ch-48,ch=getchar();
    return Read*f;
}
void change(int l,int r,ll z)  //修改
{
    int q=pos[l],p=pos[r];
    if (q==p)  //一个块暴力修改
    {
        for (register int i=l;i<=r;i++)
            ans[q]+=2*(a[i]+add[q])*z+z*z,a[i]+=z,sum[q]+=z;
        return;
    }
    for (register int i=l;i<=R[q];i++)
        ans[q]+=2*(a[i]+add[q])*z+z*z,a[i]+=z,sum[q]+=z;
    for (register int i=L[p];i<=r;i++)  //分开
        ans[p]+=2*(a[i]+add[p])*z+z*z,a[i]+=z,sum[p]+=z;
    for (register int i=q+1;i<p;i++)  //lazy修改
        add[i]+=z,ans[i]+=2*sum[i]*z+z*z*(R[i]-L[i]+1),sum[i]+=z*(R[i]-L[i]+1);
}
ll ask1(int l,int r)  //询问和
{
    int q=pos[l],p=pos[r];
    ll s=0;
    if (q==p){
        for (register int i=l;i<=r;i++) s+=(ll)(a[i]+add[q]);  //暴力求和
        return s;
    }
    for (register int i=l;i<=R[q];i++) s+=(ll)(a[i]+add[q]);
    for (register int i=L[p];i<=r;i++) s+=(ll)(a[i]+add[p]);
    for (register int i=q+1;i<p;i++) s+=sum[i];
    return s;
}
ld ask2(int l,int r)  //询问方差
{
    int q=pos[l],p=pos[r];
    ll Ans=0,Sum=0;
    if (q==p){
        for (register int i=l;i<=r;i++)  //暴力
            Sum+=a[i]+add[q];
        ld Ave=(ld)Sum/(ld)(r-l+1),s=0.0;
        for (register int i=l;i<=r;i++)
            s+=((ld)a[i]+(ld)add[q]-Ave)*((ld)a[i]+(ld)add[q]-Ave);
        return (ld)s/(ld)(r-l+1);
    }
    for (register int i=l;i<=R[q];i++)  //左边
    {
        Ans+=(a[i]+add[q])*(a[i]+add[q]);
        Sum+=a[i]+add[q];
    }
    for (register int i=L[p];i<=r;i++)  //右边
    {
        Ans+=(a[i]+add[p])*(a[i]+add[p]);
        Sum+=a[i]+add[p];
    }
    for (register int i=q+1;i<p;i++)  //中间直接利用lazy
    {
        Ans+=ans[i];
        Sum+=sum[i];
    }
    ld Ave=(ld)Sum/(ld)(r-l+1);
    return ((ld)Ans-2.0*(ld)Sum*Ave+(ld)(r-l+1)*Ave*Ave)/(ld)(r-l+1);
    //完全平方公式输出
}

int main()
{ 
    freopen("find.in","r",stdin);
    freopen("find.out","w",stdout);
    n=read(),Q=read();
    for (register int i=1;i<=n;i++)
        a[i]=read();
    T=sqrt(n);
    if (T*T<n) T++;
    for (register int i=1;i<=T;i++){
        L[i]=R[i-1]+1;
        R[i]=min(i*T,n);
        for (register int j=L[i];j<=R[i];j++){
            pos[j]=i;
            ans[i]+=a[j]*a[j];
            sum[i]+=a[j];
        }
    }
    while (Q--){
        x=read();
        if (x==0){
            x=read(),y=read();
            change(x,x,y);
        }
        else if (x==1){
            x=read(),y=read(),z=read();
            change(x,y,z);
        }
        else if (x==2){
            x=read(),y=read();
            printf("%lld\n",ask1(x,y));
        }
        else if (x==3){
            x=read(),y=read();
            printf("%0.3Lf\n",ask2(x,y));
        }
    }
    return 0;
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/459.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。