AcWing 2058. 笨拙的手指 枚举+哈希表+秦九韶算法

题

代码关键：

枚举。用unordered_set哈希表来表示某个数字是否出现过。insert插入，count返回集合内某个数字出现的次数。将b进制的string a转化为十进制的方式：秦九韶算法。二进制的转换：0变1，1变0，对应到ASCII码就是48->49,49->48，就是亦或 *** 作^。三进制的转换：见代码，很巧妙。

代码：

#include 
#include 
#include 
#include 

using namespace std;
unordered_sets;
int get(string a,int b)//把b进制的数转换为十进制
{
    //秦九韶算法
    int res=0;
    for(int i=0;a[i];i++)
    {
        res=res*b+a[i]-'0';
    }
    return res;
}
int main()
{
    
   string a,b;
   cin>>a>>b;
   
   //二进制的转换
   for(auto &c:a)
   {
       c^=1;//可以把48变49 49变48——正好对应'1'变'0','0'变'1'
       s.insert(get(a,2));
       c^=1;//变回去
   }
   
   //三进制的转换
   for(auto &c:b)
   {
       char t=c;
       for(int j=0;j<=2;j++)
       {
           if(j+'0'!=t)//变了
           {
               c=j+'0';
               int x=get(b,3);
               if(s.count(x))
               {
                   cout< 
上面的代码是看了y总视频写的，自己写的暴力枚举代码：
 是真的有够暴力
 
#include
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=1e5+10;
string a,b;
mapmp;
//三进制转为int
int num3(string a)
{
	int n=a.size();
	int ans=0;
	for(int i=0,j=n-1;a[i];i++,j--)
	{
		ans+=pow(3,j)*(a[i]-'0');
	}
	//cout<
	return ans;
} 
//二进制转为int
int num2(string a)
{
	int n=a.size();
	int ans=0;
	for(int i=0,j=n-1;a[i];i++,j--)
	{
		ans+=pow(2,j)*(a[i]-'0');
	}
//	cout<
	return ans;
} 
int main()
{
	cin>>a>>b;
	//对b *** 作
	string t;
	//三进制 
	for(int i=0;b[i];i++)
	{
		if(b[i]=='0')
		{
			string t1=t,t2=t;
			t1+='1';t2+='2';
			for(int j=i+1;b[j];j++)
			{
				t1+=b[j];
				t2+=b[j];
			}
			int tt=num3(t1);
			mp[tt]++;
		//	cout<由此可见，写代码是一门艺术。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5713845.html