题解 P7227 【[COCI2015-2016#3] ESEJ】

· · 题解

P7227 题解

题目大意

写一篇英语作文，满足以下要求：

解题思路

首先，英语中的单词，根据保守估计一共有五十万个。就算去掉十五个字母以上的单词（大多数时候是医学等专业的名词），也能够满足本题中五万个不同单词的限制。因此，只要您有足够多的肝，打表来做显然可以。（但有没有 50kb 的代码长度限制那就不得而知）

本题的第一篇题解介绍了一种通过 \text{STL} 中 \text{next\_permutation} 函数求排列的做法。这种做法在时间上是很为优秀的，但从文学的角度来看，这篇文章中包含的单词会显得不美观，而且单词的局部是重复累赘的。

为了解决这样的问题，我们考虑随机生成这篇作文，让小M的文章更加引人入胜，生动多样，更容易获得高分。

为了简化程序的实现，我们做如下考虑：

这两种考虑显然满足题目中的要求。

这样一来，我们可以开一个计数器 cnt，当随机生成出一个并未使用过的单词时，令其自增，并将这个单词加入作文；如果碰巧这个单词使用过了，则舍弃，重新生成。当 cnt=b 时，输出这篇作文即可。对于单词有没有出现过的判断，我们考虑使用 \text{map} 实现。

当然，这样的考虑是基于”小M是好学生“这个假设而来的。

代码的实现细节请看：

完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
/*随机必备的两行*/
#include <cstdlib>
#include <ctime>
/*随机必备的两行*/
#include <map>
#include <cmath>
#define ll long long
#define re register int
#define rl register ll
#define rep(i,a,b) for(re i=(a),i##end=(b);i<=i##end;++i)
#define pre(i,a,b) for(re i=(a),i##end=(b);i>=i##end;--i)
using namespace std;

int a,b,cnt;
string ans;
map <string,int> app;

inline int rint()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48); ch=getchar();}
    return x*f;
}

inline int random(int n){return (ll)rand()*rand()%n;} //这个函数的功能为随机返回一个 0~n 之间的数 

int main()
{
    srand((unsigned)time(0));  //初始化随机种子 
    a=rint(),b=rint();
    while(cnt<b)
    {
        re len=random(15)+1;  //随机生成单词长度，1<=len<=15 
        string tmp="";  //单词 
        rep(i,1,len)
        {
            char ch=(char)(random(26)+97);  //随机生成单词上的第 i 位字符，其中 97 为 a 的 ASCII 码值 
            tmp+=ch;  //将此字母加入单词 
        }
        if(!app[tmp])  //如果未被使用 
        {
            app[tmp]=1;
            if(ans=="")
                ans=tmp;
            else
            {
                ans+=' ';
                ans+=tmp;
            }  //如果这篇作文中已经有单词了，加入的时候要记得单词之间的空格 
            cnt++;
        }
    }
    cout<<ans;
    return 0;
}

感谢阅读！