UOJ Logo Yu的博客

博客

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

2017-12-19 21:54:12 By Yu

T1

贪心

这道题第一次去做还以为是搜索,可是码着码着就发现了这其实是一道贪心的题目(其实这道题搜索是可以做的,见满分统计中的其他代码)。

那接下来就讲讲怎么贪心

从题目中,我们可以看出:每当找到了一个可以用的句子,那么这个句子的末尾之前的所有的字就不能再使用了,也就是题目中所说的句子间不能交错

那么我们就可以看出句子的位置越靠前的方案就越优,也就是说能被我们所用的字越多,那么能构成的句子就一定越多。

举个栗子: 一个序列 1 1 2 3 2 4 3 4 ....

从中的句子就有

1 1 2 3 2 4 3 4

1 1 2 3 2 4 3 4

1 1 2 3 2 4 3 4 ..... (句子已被加粗)

那么我们就可以看出 1 1 2 2 这个方案是更优的,这样子我们能用的字一定就比其他的方案的多,换言之,能构成的句子就越多吧。

行,我们现在已经找到了贪心的思想了,接下来就简单了吧。

(下文所说的字是指没被用过的字)

我们发现只要一个字出现了4次或者出现了2次并且之前有出现2次的与之不同的字就可以构成一个句子了

所以我们只要存储每个数出现的次数,然后做一次上述的判断,如果可以就把之前的全清空掉(句子间不能交错),把答案+1,如果不能,就用自己去与后面的数构成句子。

代码。

#include <cstdio>
#include <cstring>
using namespace std;
int n,a[4001],ans,sum[10001];   //用sum[i]来统计i出现的次数
bool flag;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[a[i]]++;
        if (sum[a[i]]==4){        //如果这个字出现了4次,就可以构成一个句子了,就把ans+1,再把之前的清空
            memset(sum,0,sizeof(sum));
            ans++;
            flag=0;
        }
        if (sum[a[i]]==2){     //如果i出现了2次
            if (flag){
                memset(sum,0,sizeof(sum));     //这里我用了一个bool变量flag来表示之前可不以与现在的字构成句子
                flag=0;                         //可以就ans+1,清空
                ans++;
            }
            else flag=1;                //如果不可以就用自己去与后面的去构成句子
        }
    }
    printf("%d\n",ans);
    return 0;
}

T2

这道题洛谷上是有的(P1498)。

在洛谷上看了几篇题解发现有一篇和自己的思路差不多,而且写得蛮详细的,于是就偷懒了....

大家有兴趣可以去洛谷上看一下其他题解,方法不止一种,大家也可以学习一下。

那么就无耻地贴题解了。

典型的分治算法

首先我们考虑这个“分形”图形的状态表示方法

显然我们用它的底边上的中点可以很好的定位该“分形”的所有点。

其次考虑状态分割方案

我们可以发现每个所谓的“分形”图形可以分为左下右下 三个子“分形”图形。

然后用递归解决就可以了。

#include <cstdio>
#include <cstring>
#define REP(I,start,end) for(int I=start;I<=end;I++)
using namespace std;
int n;
char sav[2000][2000];
inline void DFS(int len,int x,int y,int base){//len表示当前“分形”大小,x,y表示上述中点,base表示该“分形”前面的空格数
    if(len==1)        //如果当前“分形”图形已变为最小的三角形,存储并回溯
    {
        sav[x][y]='_';
        sav[x][y+1]='_';
        sav[x][y-1]='/';
        sav[x][y+2]='';
        sav[x-1][y]='/';
        sav[x-1][y+1]='';
        return;
    }
    int tmp=1<<len-1;
    DFS(len-1,x,base+y>>1,base);      //搜左下子“分形”
    DFS(len-1,x,y+tmp,base+(tmp<<1));      //搜右下子“分形”
    DFS(len-1,x-tmp,y,base+tmp);      //搜上子“分形”
}
int main(){
    scanf("%d",&n);
    memset(sav,' ',sizeof(sav));         //所有点赋为空格
    int n1=1<<n;
    DFS(n,n1,n1,0);              //递归分治
    for (int i=1;i<=n1;i++){
        for (int j=1;j<=n1<<1;j++) putchar(sav[i][j]);
        putchar('\n');
    }
    return 0;
}

T3

高精度乘单精度

感觉这道题的思考难度要比前两题都要简单啊

只要无脑用高精度从 1 to n 乘一遍,在把结果上的每一位的数字加起来作为ans就可以了吧,也不用考虑会不会超时。

最后再考虑阶乘的结果是否为素数。

一下就能发现只要n>2,那么这个阶乘就一定不是素数了吧。

这样子,这道题目就可以过了。

那么高精度乘单精度不会的同学就自行百度吧,毕竟自学的能力是oier必不可少的技能。

#include <cstdio>
#include <cmath>
using namespace std;
int a[100000],n,len;             //用a数组储存答案,len表示这个答案的位数共有几位
int main(){
    a[1]=1; len=1;                 //初始化,储存1的阶乘
    scanf("%d",&n);
    if (n==0){                    //这里注意一下0的阶乘是1,所以特判一下就可以了。
        printf("1R\n");
        return 0;
    }
    for (int i=2;i<=n;i++){               //模拟阶乘运算,高精度乘单精度
        for (int j=1;j<=len;j++) a[j]*=i;
        for (int j=1;j<=len+5;j++){
            a[j+1]+=a[j]/10;
            a[j]%=10;
        }
        int p=len+5;
        while (a[p]==0) p--;
        len=p;
    //    printf("%d\n",len);
    }
    int sum=0;
    for (int i=1;i<=len;i++) sum+=a[i];
    if (n>2) printf("%dR\n",sum);
    else printf("%dD\n",sum);
    return 0;
}

T4

(nm)DP

从数据规模我们就可以看出这是一道(nm)的DP

用f[i][j]来表示前i段代码且第i段代码是用第j种键盘完成的最小时间

为什么可以这么表示呢?

我们可以从题目中看出:

不管是第几种键盘,换到其他键盘的速度是一样的

所以我们只要得到前i段代码所用的最小时间就可以去转移变了键盘的情况了吧。

所以我们就可以得出两个转移方案

一个是键盘不变,从f[i-1][j]来转移。

一个是键盘变了,从min[i]来转移(min[i]表示前i段代码所用的最小时间)。

那么就可以得到转移方程$f[i][j]=min(f[i-1][j]+t(这段代码用的时间),min[i]+c(换键盘的时间))$。

因为n和m都≤1000,所以O(nm)的时间复杂度是可以承受的吧。

所以这里就有一个小技巧了:当我们对一个DP的题目没有思路的时候,我们就可以用给出的数据范围猜状态,毕竟DP的题目往往不能一下就想出思路,所以不要放过一种可能的方案,多多思考,努力地做出来。

附上代码。

#include <cstdio>
#include <iostream>
#define INF 1<<30     //这里是定义了一个大数
using namespace std;
int n,m,c,f[1001][1001],t[1001][1001],a[1001];     //用a[i]表示前i段所用的最小时间
int main(){
    scanf("%d%d%d",&n,&m,&c);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            scanf("%d",&t[i][j]);
            f[i][j]=INF;             //初始化f数组
        }
    }
    for (int i=1;i<=n;i++) a[i]=INF;        //初始化
    for (int i=1;i<=m;i++){
        f[1][i]=t[1][i];
        if (f[1][i]<a[1]) a[1]=f[1][i];
    }
    for (int i=2;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (f[i-1][j]<a[i-1]+c)    f[i][j]=f[i-1][j]+t[i][j];        //两个转移方案
            else f[i][j]=a[i-1]+t[i][j]+c;
        }
        for (int j=1;j<=m;j++) a[i]=min(a[i],f[i][j]);           //更新a[i]
    }
    int ans=INF;
    for (int i=1;i<=m;i++) ans=min(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
}

总结

这4道题目总体来说难度适中,没有很难的题目,思考难度也不大,但大部分同学做的并不理想,希望大家平时能多多练习,尽量做难度偏大的题目,因为以后的比赛不会简单了。

希望大家看了我的题解能有所收获

我的QQ1447565807 QQ名:Yu 如果有什么好的建议或者认为我的题解有什么欠缺的地方,有疑问我们可以一起探讨。

GL&HF

评论

root
Good Jonb!

发表评论

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