P1112 波浪数 题解

难度：⭐⭐
知识点：构造法
题目链接

序言：以后想不出序言说什么就放一句名言吧

 我们都是阴沟里的虫子,但总还是得有人仰望星空

						——刘慈欣 《三体》

1. 入手程序

第一步，分析数据，暴力肯定不行

第二部，考虑是否可以模拟，发现虽然不能纯模拟，但可以使用...

构造法

2. 编程思路

所谓的构造法，指的是逆向的通过枚举或其他方法来构造出题目要求的数或情况

具体到这一题，就是枚举i进制下j，k轮流出现构成的波浪数的存在并存到对应重数数组下

最后将题目要求的重数输出出来

注意：

1. 一位数也可以是波浪数
2. 波浪数轮流出现的两个数不能一样
3. 波浪数不一定要是“ababab...”形式，也可以是“abababa...”形式
4. 一个波浪数不一定一定要在十进制下是波浪数

3. AC代码

#include<bits/stdc++.h>
using namespace std;
int m[10000005];//存重数 
int a,b,c,d,e;
int main()
{
	cin>>a>>b>>c>>d>>e;
	for(int i=a;i<=b;i++)//在i进制下 
	{
		for(int j=0;j<i;j++)//枚举第一个数 
		{
			for(int k=1;k<i;k++)//枚举第二个数 
			{
				if(j!=k)//两数不能一样 
				{
					int v1=0;//构造用 
					int v2=0;//计数 用 
					while(v1<=d)
					{
						//循环用两个数构造 
						if(v2%2==0)
						{
							v1=v1*i+j;
						}
						else
						{
							v1=v1*i+k;
						} 
						v2++;
						if(v1>=c && v1<=d)
						{
							m[v1]++;//如果是波浪数，存到对应位置 
						}
					}
				}
			}	
		} 
	}
	for(int i=c;i<=d;i++)
	{
		if(m[i]==e)//如果有题目要求的重数，输出
		{
			cout<<i<<endl;	
		} 
	}
	return 0;
}

我是千文杜博，记住我呦~~

The end