custoj 233-很有趣的一道题

描述

lzp喜欢搞笑数，所有搞笑的数都非常地搞笑，比如23333、233333、2333333。

所以说，一个搞笑数的每位上只能出现2或3

现给定一个正整数n，求一个搞笑数x，要求x是n的整数倍。

输入

多组数据每行一个正整数n，n<=100000

输出

对于每组数据，输出一个搞笑数x，x的位数不能超过500若不存在这样的搞笑数，输出Unhappy

输入样例 1

4

输出样例 1

32

输入样例 2

6

输出样例 2

222222222222222222222222

来源

ccw630

刚看到这道题我是蒙蔽的，请教了杭电的大佬才做出来。

主要还是运用了dp的思想 s[x][y]表示当该数除以n余数为y时位数为x的解。比如不能整除2的个位数的一个解即为s[1][2]=2；显然，一个合法的解就是s[x][0],x可以为任意数。然后如果当前s[x][y]有解（不为空时），可以得到s[x+1][(y+2)%n]="2"+s[x][y],换成3同理。用文字表示就是在解的前面加上一位2 相当于给余数前面加上一位2然后对n取模（判断整除或者超过），这就是核心思想了。我是万万想不到的。

除此以外，由于x位的数据只与x-1位的数据相关联，所以可以采用滚动数组，因为只要找一个就行，本身算法就是从小到大判断。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int maxn=100010;
string s[2][maxn];
int a[510];
string two="2",three="3";
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n%5==0)
{
cout<<"Unhappyn";
continue;
}
a[1]=1%n;
for(int i=2;i<501;i++)
a[i]=a[i-1]*10%n;
for(int i=0;i<n;i++)
s[1][i]=s[0][i]="";
s[1][2%n]="2",s[1][3%n]="3";
if(s[1][0]!="")
cout<<s[1][0]<<endl;
else
{
int flag=0;
for(int i=2;i<501;i++)
{
int t2=2*a[i]%n,t3=3*a[i]%n;
for(int j=1;j<n;j++)
{
if(s[(i+1)%2][j]!="")
{
s[i%2][(j+t2)%n]=two+s[(i+1)%2][j];
s[i%2][(j+t3)%n]=three+s[(i+1)%2][j];
}
}
for(int j=1;j<=n;j++)
s[(i+1)%2][j]="";
if(s[i%2][0]!="")
{
cout<<s[i%2][0]<<endl;
flag=1;
break;
}
}
if(!flag)
cout<<"Unhappyn";
}
}
return 0;
}

最后

以上就是激动手套为你收集整理的custoj 233-很有趣的一道题的全部内容，希望文章能够帮你解决custoj 233-很有趣的一道题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。