CWOI2019 暑假提高组模拟题十二

博主： literature
发布时间：2019 年 08 月 22 日
283 次浏览
关闭评论
1161字数
分类：主机教程

本应$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 
#include 
#include 
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;ia[i]&&a[i]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+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

`Problem B 石头剪刀布`

`题面`

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

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

`题解`

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

`代码`

#include 
#include 
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%100){
            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>n;
    for(int i=1;i<=n;i++){
        int q;
        cin>>q;
        if(fuck[q]){
            cout<<"YES"<

`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 
#include 
#include 
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 
#include 
#include 
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



                              
                 


                          
             
                     
                     最后修改：2023 年 08 月 27 日
                 
© 允许规范转载
                 
             
                         
             
                  
                 
                     
                         
                             
                             赞赏作者
                         
                         
                             
                                        
                                    

                             
 
 
                         

                     

                 

        
                        如果觉得我的文章对你有用，请随意赞赏


     
             
     
               
       
        
          
热门文章 
                             
 最新评论 
                          
  随机文章
             
            
        
       
       
       
        
         热门文章
         
          
                
                
                      live/msn等微软绝版邮箱详细的注册教程 
                      浏览次数: 4671
                    
              

                
                
                      欢迎使用 Typecho 
                      浏览次数: 3149
                    
              

                
                
                      一个功能强大又好用的RSS订阅器：FreshRSS安装教程 
                      浏览次数: 2490
                    
              

                
                
                      使用Aria2下载BT磁力的时候，速度慢或者没速度的解决方法 
                      浏览次数: 2170
                    
              

                
                
                      VPS使用BaiduPCS-Go高速下载百度网盘的文件，支持上传/离线下载等操作 
                      浏览次数: 1990
                    
              
         
        
                   
        
         最新评论
         
                              

              
                                
              
                  
              
              
                  
                       YY 
                  
                  
                      
                          22222                      
                  
              
          
                    

              
                                
              
                  
              
              
                  
                       Typecho 
                  
                  
                      
                          欢迎加入 Typecho 大家族                      
                  
              
          
                   
        
                   
        
            随机文章
            
            
                
                
                      如何在CentOS上安装Node.js和npm- 星泽V社 
                      浏览次数: 212
                    
              

                
                
                      关于kali blog 
                      浏览次数: 253
                    
              

                
                
                      snag.gy：一个快捷在线保存截图的网站 
                      浏览次数: 308
                    
              

                
                
                      kkFileView 文件在线预览解决方案 - 星泽V社 
                      浏览次数: 348
                    
              

                
                
                      Linux端口限速 
                      浏览次数: 238
                    
              
            
        
       
      
               
               
       博客信息
       
                        2547文章数目
                        
               3评论数目
                       
               3年279天运行天数
             1 年前最后活动
       
      
                        
         
             广告
            











依赖工具
此为Severless服务的Python环境依赖包下载工具，输入包名，点击获取，下载zip后解压到你的项目文件夹即可



        
              
                  
            
            
                  

                  
            
        
    
    



    
        
            
        
    
    
         
                  
                
          
              文章标签
              
                  OI 题解 成都外国语学校 日记 考试              
          
                    
              
                  文章目录




    

        
            CWOI2019 暑假提高组模拟题十二
            literature • 2019 年 08 月 22 日     
            <p>本应$280$的，结果打表太大，拒绝评测，只有$180$。</p><h2>Problem A 旅行</h2><h3>题面</h3><p>现在有一段不平整的路，第$i$段的高度为$a_i$。你可以花费$|a_i-k|$，使第$i$段的高度变为$k$，使$\sum_{i=1}^{n-1}|a_i-a_{i+1}|$最小。</p><h3>题解</h3><p>贪心地从左到右扫一遍，枚举第$i$段路。如果要使得从$i-1$到$i+1$的体力消耗最小，那么就要两端距离间的差距最小。</p><ul>
 <li>如果$a_{i-1}$和$a_{i+1}$都小于$a_i$，那么就将$a_i$改变为$max(a_{i-1},a_{i+1})$。</li>
 <li>如果$a_{i-1}$和$a_{i+1}$都大于$a_i$，那么就将$a_i$改变为$min(a_{i-1},a_{i+1})$。</li>
</ul><h3>代码</h3><pre><code class="lang-cpp">#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;
}</code></pre><h2>Problem B 石头剪刀布</h2><h3>题面</h3><p>小菜给出一个自然数$n$，小明和小头轮流操作，每次操作可以把$n$减去$n$所拥有的数字中的最大值或者最小值（不包括0），不能操作者输（即$n=0$ 时）。</p><p>试求双方最优策略时的胜负情况。（小明先手）</p><h3>题解</h3><p>递推。$$fuck_x=(!fuck_{x-findmax(x)})||(!fuck_{x-findmin(x)})$$</p><h3>代码</h3><pre><code class="lang-cpp">#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;
}</code></pre><h2>Problem C 环中环</h2><h3>题面</h3><p>$n$个整数围成一个环，选出其中的若干数，使得选中的数所组成的<strong>环</strong>中，两个相邻数的差的绝对值<strong>不等于</strong>$1$。在满足这个前提下，问最多能取多少个数。</p><h3>题解</h3><p>动态规划。设$f_i$表示以$i$为终点时最多能取多少个数。$$f_i=f_j+1(abs( a_i-a_j) \neq 1)$$</p><p>由于题目要求是环形，因此可以将原数列复制一份接在后面，处理完后答案除以$2$即可。</p><p>我们发现$(abs( a_ i-a_ j ) \neq 1)$的数最多只有两个，所以我们只要记录$3$个不同的$a_i$所对应的最大的$3$个$f$的值，直接转移即可。</p><h3>代码</h3><pre><code class="lang-cpp">#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;
}</code></pre><h2>Problem D 寻找神格</h2><h3>题面</h3><p>维护一个序列，使之支持下列操作：</p><ul>
 <li>一个区间增加一个定值。</li>
 <li>求指定区间方差。</li>
 <li>求指定区间和。</li>
</ul><h3>题解</h3><p>分块。</p><h3>代码</h3><pre><code class="lang-cpp">#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;
}</code></pre><p><hr class="content-copyright" style="margin-top:50px"></p>