首页 > 代码库 > URAL1095 Nikifor 3

URAL1095 Nikifor 3

2024-07-20 10:43:19   217人阅读

题意：给你N个正整数，它们都含有数码1、2、3、4，不超过20位，要求你调整每个正整数中数字的顺序，使它能被7整除。

最朴素的做法，暴搜它的每一种排列，但20位就挂了，肯定TLE。

注意题目中有条件每个正整数都有1,2,3,4，所以应该好好利用这个条件才对。

那么我们可以把1,2,3,4各取出一个，会发现它们组成的四位数模7的余数有7种。

我取了这样一组数4123,1324,4321,2341,1432,2413,4213，它们模7分别余0,1,2,3,4,5,6

剩下的数码随便排列就可以了（0放最后），用这7个数填补其它数码组成的数字模7剩余的部分即可。

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 const int rest[8]={4123,1324,4321,2341,1432,2413,4213,4123}; 5 int T; 6 int count[10]; 7 char str[101]; 8 int main(){ 9     scanf("%d",&T);10     while (T--){11         memset(count,0,sizeof(count));12         scanf("%s",str);int l=strlen(str);13         for (int i=0;i<l;i++) {14             count[int(str[i]-‘0‘)]++;15         }16         for (int i=1;i<=4;i++) count[i]--;17         int now=0;18         for (int i=9;i>=1;i--) {19             for (int j=1;j<=count[i];j++)20             {21                 printf("%d",i);now=(now*10+i)%7;22             }    23         }24         printf("%d",rest[7-(now*10000)%7]);25         for (int j=1;j<=count[0];j++) printf("0");26         printf("\n");27     }28     return 0;    29 }

 

URAL1095 Nikifor 3


联系
我们