纪中训练 day14【NOIP普及组】模拟赛B组&C组 解题报告

目录

• • ☞第一题 教主的花园☜
    • 大意
      • 数据范围
    • 60分思路
      • 时间复杂度
    • 60分代码
    • AC思路
      • 时间复杂度：
    • AC代码
  • ☞第二题 教主泡嫦娥☜
    • 大意
      • 数据范围
    • 思路
    • 代码
  • ☞第三题 保镖排队☜
    • 大意
      • 数据范围
    • 思路
    • 代码
  • ☞第四题 教主的别墅☜
    • 大意
      • 数据范围
    • 思路
    • 代码

☞第一题 教主的花园☜

大意

有一个，坐标系；在x轴，有障碍；问m次，最短路！

数据范围

　　对于20%的数据，有n，m≤10，ai，xi，yi绝对值不超过100；
　　对于40%的数据，有n，m≤100，ai，xi，yi绝对值不超过1000；
　　对于60%的数据，有n，m≤1000，ai，xi，yi绝对值不超过100000；
　　对于100%的数据，有n，m≤100000，ai，xi，yi绝对值不超过100000000。

60分思路

直接暴力模拟，如果同在第一第二象限或者是同在第三第四象限就直接输出曼哈顿距离，否则枚举所有点。

时间复杂度

O（nm） $O（nm）$

60分代码

#include<bits/stdc++.h>
#define LL long long
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;int a[100001],n,m,ans;
int x,y,q,p;
LL read()//输入流
{
    int f=0,d=1;char c;
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
    while (c=getchar(),c>='0'&&c<='9') f=(f<<3)+(f<<1)+c-48;
    return d*f;
}
void write(LL x){if(x<0){x=-x;putchar('-');}if(x>9)write(x/10);putchar(x%10+48);}//输出流
void writeln(LL x){write(x);putchar(10);}
bool xx(int x,int y)//判断是否在同一象限
{
    if(y>0) return 1;
    if(y<0) return 0;
}
int jl(int a,int b,int c,int d)//判断两点间的曼哈顿距离
{
    return abs(a-c)+abs(b-d);
}
int main()
{
    n=read();
    r(i,1,n) a[i]=read();
    m=read();
    while(m--)
     {
        x=read();y=read();q=read();p=read();//输入
        if(xx(x,y)==xx(q,p))//若同在一个象限
         writeln(jl(x,y,q,p));//输出距离
        else
         {
            ans=2147483647;
            r(i,1,n)
             ans=min(ans,jl(x,y,a[i],0)+jl(q,p,a[i],0));//枚举最小值
            writeln(ans);//输出
         }
     }
}

AC思路

上一种方法没拿到满分的原因是因为枚举过多次数，针对这一情况，就要用到二分了。

时间复杂度：

O(mlogn) $O(m\log n)$

AC代码

#include<bits/stdc++.h>
#define LL long long
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;int a[100001],n,m,ans,x,y,q,p,l,r,mid,last;bool ok;
LL read()//输入流
{
    int f=0,d=1;char c;
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
    while (c=getchar(),c>='0'&&c<='9') f=(f<<3)+(f<<1)+c-48;
    return d*f;
}
void write(LL x){if(x<0){x=-x;putchar('-');}if(x>9)write(x/10);putchar(x%10+48);}//输出流
void writeln(LL x){write(x);putchar(10);}
bool xx(int x,int y)//判断是否同在第一第二或者第三第四象限
{
    if(y>0) return 1;
    if(y<0) return 0;
}
int jl(int a,int b,int c,int d)//求两点的曼哈顿距离
{
    return abs(a-c)+abs(b-d);
}
int main()
{
    n=read();
    r(i,1,n) a[i]=read();
    m=read();
    sort(a+1,a+1+n);
    while(m--)
     {
        x=read();y=read();q=read();p=read();//输入
        if(xx(x,y)==xx(q,p))//判断
         writeln(jl(x,y,q,p));//输出
        else
         {
            l=1;r=n;
            while(l<r)//二分
            {
                mid=(l+r)>>1;
                ans=abs(y-p)+abs(x-a[mid])+abs(q-a[mid]);
                if(mid>1&&ans>abs(y-p)+abs(x-a[mid-1])+abs(q-a[mid-1]))
                 r=mid-1;//调整右边界
                else
                 if(mid<n&&ans>abs(y-p)+abs(x-a[mid+1])+abs(q-a[mid+1]))
                  l=mid+1;//调整左边界
                else
                 {
                    l=mid;
                    r=mid;//强制退出
                 }
            }
            writeln(abs(y-p)+abs(a[l]-x)+abs(a[l]-q));//输出
         }
     }
}

☞第二题 教主泡嫦娥☜

大意

有一环，有n长；每个点，有高度；现在有，两形态；一上升，二下降；转一态，耗m力；任意点，任意态；现要求，最小值！

j的海拔高于i的海拔：如果教主处于上升状态，教主需要耗费两段高度差的绝对值的体力；否则耗费高度差平方的体力。
j的海拔低于i的海拔：如果教主处于下降状态，教主需要耗费两段高度差的绝对值的体力；否则耗费高度差平方的体力。

数据范围

　　对于10%的数据，N ≤ 10；
　　对于30%的数据，N ≤ 100，a[i] ≤ 1000；
　　对于50%的数据，N ≤ 1000，a[i] ≤ 100000；
　　对于100%的数据，N ≤ 10000，a[i] ≤ 1000000，M ≤ 1000000000；

思路

50分很简单，就是枚举所有点然后dp，时间复杂度 O(n2) $O(n^2)$，可以拿到50分。
100分的方法就很多了，有随机数优化，三维dp，顺逆双向循环等等，这里用到的是计次优化——就是记下循环了几次，当超过一个会超时的次数时直接退出。
好吧，你可能会说这样很悬，当其实是可行的，因为其实很多次枚举时重复的，这样也能达到优化的效果，同时也可以AC

代码

#include<bits/stdc++.h>
#define LL long long
#define r(i,a,b) for(int i=a;i<=b;i++)
#define min(a,b) ((a)<(b)?(a):(b))//最小值
using namespace std;long long f[100001][2];int n,m,a[100001],ime;long long t;//记得开longlong
long long ans=1e17;//初始化
LL read()//输入流
{
    int f=0,d=1;char c;
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
    while (c=getchar(),c>='0'&&c<='9') f=(f<<3)+(f<<1)+c-48;
    return d*f;
}
void write(LL x){if(x<0){x=-x;putchar('-');}if(x>9)write(x/10);putchar(x%10+48);}
void writeln(LL x){write(x);putchar(10);}//输出流
int main()
{
    n=read();m=read();
    r(i,1,n) 
     {a[i]=read();a[i+n]=a[i];}//输入+初始化
    r(i,1,n)
    {
        f[i][0]=0;
        f[i][1]=0;
        if(ime>10000000) break;//计次优化
        r(j,i+1,i+n)
         {
            ime++;
            t=a[j]-a[j-1];
            if(a[j]<a[j-1]) t*=t;
            f[j][0]=min(f[j-1][0]+t,f[j-1][1]+m+t);
            t=a[j-1]-a[j];
            if(a[j]>a[j-1]) t*=t;
            f[j][1]=min(f[j-1][1]+t,f[j-1][0]+m+t);//动态转移
         }
        ans=min(ans,min(f[i+n][1],f[i+n][0]));//取最优值
    }
    writeln(ans);//输出
}

☞第三题 保镖排队☜

大意

一共有，n个人；关系为，上下级；上在前，下在后；同为下，武力前；现排列，有几种？

数据范围

　　对于20%的数据，有N ≤ 9；
　　对于40%的数据，有对于所有K，有K ≤ 2；
　　对于60%的数据，有N ≤ 100；
　　对于100%的数据，有T ≤ 10，N ≤ 1000，K ≤ N。

思路

树形dp，把下属看做是这个结点的儿子，一遍dfs就可以了。记得要用到组合，所以提前打杨辉。

代码

#include<bits/stdc++.h>
#define LL long long
#define mod 10007
#define N 2018
#define r(i,a,b) for(int i=a;i<=b;i++)
#define C(a,b) f[(a-1)][(b-1)]//组合数等于杨辉金字塔的横列减1
using namespace std;int n,T,k,p,m;
int f[N][N],dp[N],s[N][N],num[N];//num是数字，s是儿子，dp是这个结点对应的方案数，f是杨辉金字塔
LL read()
{
    int f=0,d=1;char c;
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
    while (c=getchar(),c>='0'&&c<='9') f=(f<<3)+(f<<1)+c-48;
    return d*f;
}
void write(LL x){if(x<0){x=-x;putchar('-');}if(x>9)write(x/10);putchar(x%10+48);}
void writeln(LL x){write(x);putchar(10);}
void work(int x)
{
    if(!s[x][0]){dp[x]=1;num[x]=1;return;}//到结点为0时退出
    int tot=0;
    dp[x]=1;//初始化
    for(int i=s[x][0];i;i--)
    {
        work(s[x][i]);//dfs
        tot+=num[s[x][i]];//加进去
        dp[x]=dp[x]%mod*dp[s[x][i]]%mod*C(tot,num[s[x][i]])%mod;//动态转移
    }
    num[x]=tot+1;//加进去
}
int main()
{
    T=read();f[0][0]=1;
    for(int i=1;i<=2000;i++){f[i][0]=1;
     for(int j=1;j<=i;j++)
        f[i][j]=(f[i-1][j-1]%mod+f[i-1][j]%mod)%mod;}//杨辉金字塔
    while(T--)
    {
        memset(num,0,sizeof(num));
        memset(s,0,sizeof(s));
        memset(dp,0,sizeof(dp));//初始化
        n=read();
        r(i,1,n){
         s[i][0]=read();
         r(j,1,s[i][0])
          s[i][j]=read();}//输入
        work(1);//工作
        printf("%d\n",dp[1]);//输出
    }
}

☞第四题 教主的别墅☜

大意

一共有，n个数；每个数，为01；现在要，分m组；使每组，差最小；先求出，字典序；最小的，最大的！

数据范围

　　对于40%的数据，有N ≤ 100；
　　对于50%的数据，有N ≤ 1000；
　　对于65%的数据，有N ≤ 100000；
　　对于100%的数据，有N ≤ 5000000，M ≤ N且M ≤ 100000。

思路

贪心+模拟。

代码

#include<bits/stdc++.h>
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;int n,m,m1,l,ans,k;string s;
int sum[5000001],ans1[5000000],gs;//gs是序列的长度，ans1是反过来的结果
int main()
{
    scanf("%d %d\n",&n,&m);m1=m;//提前存储m
    cin>>s;//输入
    for(int i=0;i<s.size();i++)
     if(s[i]=='1')
      sum[i+1]=sum[i]-1;
     else sum[i+1]=sum[i]+1;//记到sum数组
    if(sum[n]==0)
     {
        l=0;
        r(i,1,n)
         if(!sum[i]) l++;
        if(l>=m) ans=0;
        else ans=1;//特殊处理
     }
    else
     {
        ans=floor(abs(sum[n])/m);
        if(abs(sum[n])%m) ans++;//否则
     }
    l=0;
    r(i,1,n)
     {
        if(sum[i]-sum[l]<=ans)
         {
            k=floor(abs(sum[n]-sum[i])/(m-1));
             if(abs(sum[n]-sum[i])%(m-1)) k++;//若不能整除就+1
            if(k<=ans)
            {
                printf("%d ",i-l);//输出
                l=i;
                m--;//标记已经少了一个
            }
         }
         if(m==1)
         {
            printf("%d\n",n-l);//只有最后一个就直接输出
            break;
         }
     }
    for(int i=s.size()-1;i>=0;i--)
     if(s[i]=='1')
      sum[i+1]=sum[i+2]-1;
     else
      sum[i+1]=sum[i+2]+1;//反过来做一遍
    if(!sum[1])
    {
        l=0;
        r(i,1,n)
         if(!sum[i]) l++;
        if(l>=m1) ans=0;
        else ans=1;//特判
    }
    else
    {
        ans=floor(abs(sum[1])/m1);
        if(abs(sum[1])%m1) ans++;//向下取整+1
    }
    l=n+1;
    for(int i=n;i>0;i--)
    {
        if(sum[l]-sum[i]<=ans)
         {
            k=floor(abs(sum[i]-sum[1])/(m1-1));
             if(abs(sum[i]-sum[1])%(m1-1)) k++;//同理
            if(k<=ans)
            {
                gs++;
                ans1[gs]=l-i;//存到数组里
                l=i;
                m1--;
            }
            if(m1==1)
            {
                printf("%d ",l-1);
                break;
            }
         }
    }
    for(int i=gs;i>0;i--)
     printf("%d ",ans1[i]);//倒序输出
}