1 条题解

  • 0
    @ 2025-10-8 16:48:38
    #include<bits/stdc++.h>//这是deque+map版本
    using namespace std;
    struct node{int a[4],dep,kt;};
    deque<node>Q;//多组数据用双端队列,因为有clear()函数
    map<int,bool>V;//相当于bool v[](避免定义v数组的大小),可以这样用v[x]=1或v[x]=0,x是int类型
    //判重用map容器,如果康托值超过1亿,则需采用map容器判重
    int A[4],k; 
    int kt(node no)//a[i]最大值为100,是3位数
    {
    	return no.a[1]*1000000+no.a[2]*1000+no.a[3];
    }
    bool ok(node no)
    {
        for(int i=1;i<=3;i++) if(no.a[i]==k) return 1;
        return 0;
    }
    
    int main()
    {
        while( scanf("%d%d%d%d",&A[1],&A[2],&A[3],&k)!=EOF)
        {
            if(A[1]==k) {printf("yes\n0\n"); continue;}
    
            node stno=node{{0,A[1],0,0},0,0};stno.kt=kt(stno);
            V.clear();V[stno.kt]=1;//因为是多组数据,所以每次都要清空
            Q.clear();Q.push_back(stno);
    		bool bk=0;
    	    while(!Q.empty())
    	    {
    	        for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)
    		        if(i!=j&&Q.front().a[i]>0)
    		        {
    		            node no=Q.front();
    		            int t=A[j]-no.a[j];
    		            if(no.a[i]>=t){  no.a[j]+=t;        no.a[i]-=t;}
    		            else          {  no.a[j]+=no.a[i];  no.a[i]=0; }
    		            no.dep=Q.front().dep+1;
    		            no.kt=kt(no);
    					if(V[no.kt]==0)
    		            {
    		                V[no.kt]=1;
                            Q.push_back(no);
    		                if(ok(no)==1){bk=1;break;}      
    		            }
    		        }
    	        Q.pop_front();
    	        if(bk==1)break;
    	    }
    	    
            if(bk==1) printf("yes\n%d\n",Q.back().dep);
            else      printf("no\n");
        }
        return 0;
    }
    
    • 1

    *【宽搜(难度:S4)】巧妙取量

    信息

    ID
    89
    时间
    1000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    309
    已通过
    61
    上传者