题目链接：
题目大意：给n个k位数的数，对这n个数以相同的方式进行数位之间的调换（即数字可以任意调换位置），找出其中最大值与最小值之差的最小值。
思路：注意到k和n的范围，最大为8。可以进行暴力枚举进行比较。
#include<stdio.h>#include<string.h>#include<stdlib.h>char s[10][10],c[10][10];int mini,vis[10],n,k,maxi;int power(int x){int ans=1;for(int i=1;i<=x;i++)ans=ans*10; return ans; }void dfs(int x,int cnt){ if(vis[x]){for(int j=1;j<=n;j++){c[j][cnt]=s[j][x-1];}}if(cnt==k){maxi=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int a=0;int b=0;for(int l=1;l<=k;l++){a=a+c[i][l]*power(k-l);b=b+c[j][l]*power(k-l);}if(maxi<abs(a-b))maxi=abs(a-b);//printf("%d`%d`%d~\n",a,b,maxi);}}if(mini>maxi)mini=maxi;return ;}for(int i=1;i<=k;i++){if(!vis[i]){vis[i]=1;dfs(i,cnt+1);vis[i]=0;}} }int main(){int i,j,t;while(scanf("%d%d",&n,&k)!=EOF){mini=999999999;maxi=0;memset(vis,0,sizeof(vis));for(i=1;i<=n;i++)scanf("%s",s[i]);for(i=1;i<=n;i++)for(j=0;j<k;j++){s[i][j]=s[i][j]-'0';}dfs(1,0);printf("%d\n",mini);} return 0;}
题目链接：
题目大意：给一个字符串，，可以对字符串进行位置的调换。算出一个字符串经过位置互换以后，满足以下条件：对于一个字符串s，存在任意素数p<=s，有属于[1,s/p]的i对于Sp=Sp*i成立。
思路：这么考虑：如果s足够大，那么2的倍数上的字符要相同，3的倍数上的字符要相同，5的倍数上的字符要相同……
也就是prime[k]的倍数上字符要相同。这里面是有公倍数的，也就是说2和3的字符要相同。。以此类推：2~s/2上的字符都是相同的。
所以我们构造一个字符串，2~s/2上的字符全部都要相同。然后对于s/2~s的字符来说，只要是前面素数的倍数，都需要构造相同的字符。
剩下的就好办了：对于超过s/2的字符来说，只剩下那些素数没有被构造了，那就相当于把剩下的没有被用掉的字符全部放进去就好了。
#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#define MAXN 1000using namespace std;int prime[1000],vis[1005];void getPrime() {memset(prime,0,sizeof(prime));for(int i=2;i<=MAXN;i++){if(!prime[i])prime[++prime[0]]=i;for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++){prime[prime[j]*i]=1;if(i%prime[j]==0) break;}} } //先处理处1-1000的素数。struct node{int h,num;}p[100];bool cmp(node a,node b){return a.h>b.h;}int main(){getPrime();char s[1005],str[1005];int i,j,k,l,flag;while(scanf("%s",s)!=EOF){l=strlen(s);flag=1;memset(p,0,sizeof(p));memset(vis,0,sizeof(vis));for(i=0;i<l;i++){p[s[i]-'a'].h++;} //对出现过的字符进行哈希for(i=0;i<26;i++)p[i].num=i;sort(p,p+26,cmp);//排序以后p[0].h一定是最大的。if(p[0].h<l/2-1)flag=0;else{for(i=2;i<=l/2;i++){vis[i]=1;str[i]=p[0].num+'a';//对2-l/2以内的字符进行构造。p[0].h–;}for(k=1;prime[k]<=l/2;k++){for(i=prime[k];i<=l;i+=prime[k]){if(vis[i])continue;vis[i]=1;str[i]=p[0].num+'a';p[0].h–;}//printf("%d\n",p[0].h);if(p[0].h<0)flag=0;}for(;prime[k]<=l&&!vis[prime[k]];k++){vis[prime[k]]=1;for(i=0;i<26;i++){if(p[i].h>0){str[prime[k]]=p[i].num+'a';p[i].h–;break;}}}for(i=0;i<26;i++){if(p[i].h>0){str[1]=p[i].num+'a';break;}}}if(flag==0)printf("NO\n");else {printf("YES\n");for(i=1;i<=l;i++)printf("%c",str[i]);printf("%\n");}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
当一个人真正觉悟的一刻，他放弃追寻外在世界的财富，而开始追寻他内心世界的真正财富
