UOJ Logo Venus的博客

博客

“剑锋OI”普及组多校联盟系列赛(16)#Sooke#MerryChristmas 题解报告

2017-12-31 23:14:00 By Venus

作者博客,欢迎前来吃瓜

T1 白雪皑皑的圣诞

自古T1水题,这题虽有一个非常NB的名字,但是也逃脱不了水题的命运 一眼看过去,一片海阔天空——模拟 只需枚举每个时间点,加上时间点下的雪,再计算能堆多少个雪人即可 要注意一个人每个时间点最多只能堆一个雪人,所以当能堆的雪人大于人数时,加上人数而不是雪人数 代码如下

#include<cstdio>
int n,m,k,p,t,ans;
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    scanf("%d %d",&p,&t);//读入数据
    for(int i=1;i<=t;i++)//枚举每个时间点
    {
        n+=m;//加上当前时间点下的雪
        int cnt=n/k;//算出能堆多少雪人
        if(cnt>p)//判断雪人与人数的关系
        {
            ans+=p;
            n-=p*k;//减掉花费的雪
        }
        else
        {
            ans+=cnt;
            n-=cnt*k;//同上
        }
    }
    printf("%d",ans);//输出答案
    return 0;
}

T2 灯光闪闪的圣诞

这道题目还是有一定难度的,比如我看到的第一想法是! 贪心。 我认为,对输入数据进行排序,然后从最小的开始,选用小的数量$a[i]$的全部及比它大的数量的部分,可以分为$a[i]$个部分,每个部分的灯数为$n-i+1$,一共的盏数为其乘积,则美观值为$a[i]^2 * (n-i+1)$ 显然,这种方法是不正确的,但当一个不正确的算法骗到60分后它就有意义了(huaji) 那么正解是什么呢? 还是模拟,或者说是枚举。 我们枚举灯分成的部分的数量,然后再进行计算即可

我们这里可以用的思想,或者叫计数思想 什么是桶呢? 用f[i]=j表示值为i的数有j个 举个栗子: 假设我们有如下数组 a[1]=5 a[2]=7 a[3]=2 a[4]=1 a[5]=3 a[6]=2 用桶计数之后变为(设桶数组为f): f[1]=1 f[2]=2 f[3]=1 f[5]=1 f[7]=1 那么这怎么运用这题呢?

设灯数中最大的为maxn,桶f[i]表示灯数为i的灯有几种颜色 我们可以枚举灯分为i个部分(从1到maxn),因为前面我们已经用桶存了数据,而小于i的灯数都是无法分成i个部分的,所以f[i]之前的值都没有用 于是我们从i到maxn再进行一次枚举(设变量为j),计算能挂多少个灯 这里我们要善于使用整除下取整的特点,直接j/i就可以得到分成几个部分,再乘上i就可以得到取几个灯 此时我们已算出了灯数为j的一种颜色的灯能取多少个,再乘上f[j]即可 此时我们得到了灯数,再乘上i即为美观值 代码如下

#include<cstdio>
long long n,f[5005],x;
long long cnt,ans,maxn;//注意数据范围!!!
long long Max(long long a,long long b)//STL 自带的max不适用longlong,需要手打
{
    return a > b ? a : b;//三目运算符,推荐新人学习
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        f[x]++;//桶的思想,f[i]=j表示数量为i的灯有j种颜色
        maxn=Max(maxn,x);//统计最大灯数
    }
    for(int i=1;i<=maxn;i++)//枚举分成的组数
    {
        cnt=0;//初始化变量
        for(int j=i;j<=maxn;j++) cnt+=(j/i*i)*f[j];//上方描述过的算式
        cnt*=i;//计算美观度
        ans=Max(cnt,ans);//记录答案
    }
    printf("%lld",ans);//输出即可
    return 0;
}

T3 其乐融融的圣诞

来到T3,我们迎来了喜闻乐见的广搜(BFS) 有人就要问了:BFS是啥? 我在这里就不作详细介绍了,大概就是把能走的点存进队列里,然后每次取队首进行处理 那么这道题要怎么做呢? 我们可以将 Kornal 和 Lacone 两人分别走到每个格子的最小步数算出来,然后再暴力一波,分别假设 Kornal 在 Lacone 的上、下、左、右四个方向,再分别进行计算即可 我们首先来讲讲广搜怎么写 首先上方已经提到了,要用队列,那么

queue <int> qx,qy;//推荐使用 STL

然后取出当前位置

nx=qx.front(),ny=qy.front();//当前位置
qx.pop(),qy.pop();//推出队首

接下来就是对上下左右四个方格进行判断,那么这四个方格可以分别表示为 nx+1,ny nx-1,ny nx,ny+1 nx,ny-1 代码如下

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define INF 2000000000
using namespace std;
queue <int> qx,qy;
int Cx[5]={0,1,-1,0,0};
int Cy[5]={0,0,0,1,-1};
int n,a[505][505],b[505][505],ux,uy;
int f[505][505];
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) cin >> f[i][j];//读入数据
    }
    memset(a,60,sizeof(a));//初始化数组为一个大值
    //这里是 Kornal 的 bfs
    a[1][1]=0;
    qx.push(1);
    qy.push(1);//初始值
    while(!qx.empty())
    {
        ux=qx.front();
        uy=qy.front();
        qx.pop();
        qy.pop();//取出数据,弹出队首
        for(int i=1;i<=4;i++)
        {
            int vx=ux+Cx[i],vy=uy+Cy[i];//计算转移后的坐标
            if(vx<1 || vx>n || vy<1 || vy>n || f[vx][vy] || a[vx][vy]<=250000) continue;
            //转移后的坐标超出边界,当前格为雪或当前格已经走过了都要跳过此格
            a[vx][vy]=a[ux][uy]+1;//转移步数
            qx.push(vx);
            qy.push(vy);//将获得的坐标压入队列
        }
    }
    //Kornal 篇章到此结束,接下来是 Lacone
    memset(b,60,sizeof(b));//和上方一样的操作
    //这里是 Lacone 的 bfs
    b[n][n]=0;
    qx.push(n);
    qy.push(n);//注意 Lacone 从 n,n 开始
    while(!qx.empty())
    {
        //操作和上方基本一致,不赘述了
        ux=qx.front();
        uy=qy.front();
        qx.pop();
        qy.pop();
        for(int i=1;i<=4;i++)
        {
            int vx=ux+Cx[i],vy=uy+Cy[i];
            if(vx<1 || vx>n || vy<1 || vy>n || f[vx][vy] || b[vx][vy]<=250000) continue;
            b[vx][vy]=b[ux][uy]+1;
            qx.push(vx);
            qy.push(vy);
        }
    }
    int cnt=0,ans=INF;
    //大暴力开始 
    for(int i=1;i<=n;i++)
    {
        //假设 Kornal 在 Lacone 的左方 
        cnt=INF;
        for(int j=1;j<=n;j++)
        {
            if(f[i][j]) cnt=INF;
            else
            {
                cnt=min(cnt,a[i][j]);
                ans=min(cnt+b[i][j],ans);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        //假设 Kornal 在 Lacone 的右方 
        cnt=INF;
        for(int j=n;j>=1;j--)
        {
            if(f[i][j]) cnt=INF;
            else
            {
                cnt=min(cnt,a[i][j]);
                ans=min(cnt+b[i][j],ans);
            }
        }
    }
    for(int j=1;j<=n;j++)
    {
        //假设 Kornal 在 Lacone 的上方 
        cnt=INF;
        for(int i=1;i<=n;i++)
        {
            if(f[i][j]) cnt=INF;
            else
            {
                cnt=min(cnt,a[i][j]);
                ans=min(cnt+b[i][j],ans);
            }
        }
    }
    for(int j=1;j<=n;j++)
    {
        //假设 Kornal 在 Lacone 的下方 
        cnt=INF;
        for(int i=n;i>=1;i--)
        {
            if(f[i][j]) cnt=INF;
            else
            {
                cnt=min(cnt,a[i][j]);
                ans=min(cnt+b[i][j],ans);
            }
        }
    }
    if(ans<=1000000) cout << ans;//判断,输出即可 
    else cout << -1;
    return 0;
}

T4 情意绵绵的圣诞

这道题目难度还是比较大的,比如作者本人都没有AC之类的 所以我们来讲讲暴力 首先看到题目,我们会发现这道题目可以使用暴力贪心的策略 将数据从大到小排序后,从第一个开始,向后找,如果后面的没有被装,那么我们就把它加上,一直到大于当前的容量为止 即伪代码如下

sort(a+1,a+n+1,cmp);
for i=1 to n
    int cnt=0;
    for j=i+1 to n
        if used[j] continue;
        else cnt+=a[j]
        if cnt>=a[i] break;
        else used[j]=1;

事实上,这种策略虽不是最优,却可以骗到很多分,在这题里是48分的高分 那么正解是什么呢?想必是搜索。 搜索的主要思想是什么呢? 1. 从最大的盒子a开始 2. 往后找第一个能被盒子a装下的盒子b 3. 再往后,找到一个能被盒子b装下的盒子c 4. 以此类推 当然想要拿到满分要加一下剪枝 这里给出一位dalao的代码,没有太大的剪枝,拿到了80分

#include<bits/stdc++.h>
using namespace std;
int n,gg,kk,ans=1;
int ch[200005],len;
struct troom
{
    bool f,hh;
    long long lef,hu;//hu指大小,lef指容量
}a[200005];
long long read()
{
    char c=getchar();
    long long x=0;
    int f=1;
    while(!isdigit(c) && c!='-')    { if(c=='-') f=-1;  c=getchar(); }
    while(isdigit(c))    {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
    return x*f;
}//读优
bool cmp(troom x,troom y)
{
    return x.hu>y.hu;
}
void dfs(int h)
{
    if(a[gg].lef<kk)
    {
        kk=a[gg].lef;
        len=0;
        for(int i=gg;i<=n;++i)
            if(a[i].hh) ch[++len]=i;
    }
    for(int i=h+1;i<=n;++i)
    {
        if(a[i].f)
            continue;
        if(a[i].hu<=a[gg].lef)
        {
            a[i].hh=1;
            a[gg].lef-=a[i].hu;
            dfs(i);
            a[i].hh=0;
            a[gg].lef+=a[i].hu;
            if(a[gg].lef-a[i].hu==0)
                return ;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        a[i].hu=read();
        a[i].lef=a[i].hu-1;
    }
    sort(a+1,a+n+1,cmp);
    for(gg=n-1;gg>0;--gg)
    {
        kk=a[gg].lef;
        dfs(gg);
        for(int i=1;i<=len;++i)
            a[ch[i]].f=1;
    }

    for(int i=1;i<=n;++i)
    {
        if(a[i].f)
            continue;
        ans+=a[i].hu;
    }
    cout<<ans<<endl;
    return 0; 
}

总结

这次比赛还是难度比较大的,尤其是数据很毒,所以想骗分的难度也是很大的,所以掌握一手神奇的骗分技巧还是很有必要的

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。