hdu 1016 简单的dfs 以及 1015 next_permutation的应用

向右看齐 2023-06-13 06:19 6阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1016][http_acm.hdu.edu.cn_showproblem.php_pid_1016]

就是问你n个数不重复的围成一个圈，只有两个数的和为质数才可以相邻，输出符合条件的所有排列

20个数的全排列 就别想了

我们可以预处理出那些数能相邻，用邻接表的方式存储，这样就变成了求哈密顿回路的题了

这时就用下dfs+回溯标记，就可以搞定了

好吧....也只是个弱智题

#include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+7;
    vector<int>son[30];
    int ispermi(int n)
    {
        for(int i=2;i*i<=n;i++)
            if(n%i==0)
            return 0;
        return 1;
    }
    int n;
    int vis[30];
    int ans[30];
    void dfs(int x,int len)
    {
        vis[x]=1;
        ans[len]=x;;
        if(len==n)
        {
            vis[x]=0;
            if(ispermi(x+1)){
            for(int i=1;i<len;i++)
            cout<<ans[i]<<' ';
            cout<<ans[len]<<endl;
        }
            return ;
        }
        for(int i=0;i<son[x].size();i++)
        {
            if(vis[son[x][i]]==0&&son[x][i]<=n)
                dfs(son[x][i],len+1);
        }
        vis[x]=0;///回溯一下
    }
    int main()
    {
      for(int i=1;i<=20;i++)
      {
          for(int j=1;j<=20;j++)
          {
              if(i==j) continue;
              int h=i+j;
              if(ispermi(h)) son[i].push_back(j);
          }
      }
      /*for(int i=1;i<=20;i++)
      {
          cout<<i<<':'<<' ';
          for(int j=0;j<son[i].size();j++) cout<<son[i][j]<<' ';cout<<endl;
      }*/
       int t=1;
       while(cin>>n)
       {
           for(int i=1;i<=20;i++) vis[i]=0;
           cout<<"Case "<<t++<<':'<<endl;
           dfs(1,1);
           cout<<endl;
       }
    }

1015 给你12个字符 你挑5个字符传来 全排列 按题目规则 计算 看是否能得出得数，输出满足条件的字典序最大的

（学弟写的，我好划水，活都交给别人干）

#include <bits/stdc++.h>
    using namespace std;
    string num=" ABCDEFGHIGKLMNOPQRSTUVWXYZ";
    int main ()
    {
    	int n;
    	char a[13];
    	while(scanf("%d",&n)!=EOF)
    	{
    		int  ans[5];
    		string b[121];
    		int sign=0;
    		scanf("%s",a);
    		if(n==0 && a[0]=='E' && a[1]=='N' && a[2]=='D') break;
    		sort(a,a+strlen(a));
    		for(int i=0;i<strlen(a);i++)
    		{
    			for(int j=i+1;j<strlen(a);j++)
    			{
    				for(int k=j+1;k<strlen(a);k++)
    				{
    					for(int o=k+1;o<strlen(a);o++)
    					{
    						for(int p=o+1;p<strlen(a);p++)
    						{
    							ans[0]=a[i]-'A'+1;
    							ans[1]=a[j]-'A'+1;
    							ans[2]=a[k]-'A'+1;	
    							ans[3]=a[o]-'A'+1;
    							ans[4]=a[p]-'A'+1;
    							do
    							{
    								if(ans[0] - pow(ans[1],2) + pow(ans[2],3) - pow(ans[3],4) + pow(ans[4],5) == n)
    								{
    									for(int i=0;i<5;i++) b[sign]+=num[ans[i]];
    									sign++;
    								}
    							}while(next_permutation(ans,ans+5));
    						}
    					}
    				}
    			}
    		}
    		sort(b,b+120);
    		int flag=0;
    		for(int i=120;i>=0;i--)
    		{
    			if(b[i].length()==5)
    			{
    				cout<<b[i]<<endl;
    				flag=1;
    				break;
    			}
    		} 
    		if(flag==0) printf("no solution\n");
    	}
    	return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1016]: http://acm.hdu.edu.cn/showproblem.php?pid=1016