NSUOJ -<<8>>- Problem 2697
程序员文章站
2022-03-05 23:22:49
...
题目来源 http://acm.ccniit.com/problem.php?id=2697
一.题目描述
众所周知,飛機飛过天空学长喜欢听*的歌(听天空之城就知道为什么了),连2016年发行的公益专辑《8》也不例外(但是大多数人难以接受)。大数nsir也很喜欢这张专辑,nsir很大,他可以从0到10100之间任意改变,当他听到这张专辑的时候他在想一个问题,他想让自己每一位的数字重新排列,这个排列后的new_nsir能够被8整除,问最大的new_nsir是多少。如果不满足,new_nsir=-1。
Sample Input Copy
0
1
480
Sample Output Copy
0
-1
840
二.解题思路
由题延申一个话题判断整除,例如个位数是偶数的数可以被2整除,各位数字和能被3整除的数可以被3整除,各位是0或5的数可以被5整数等等。判断被8整除同样有规律,一个整数的未尾三位数能被8整除,则这个数能被8整除。因为三位数往上的部分都是整除1000的呀,1000整除8呀!
更多整除规律转载自https://www.cnblogs.com/xz816111/p/4580491.html
下面这道题的解法:首先数组记录每个数字的个数 思路是当后三位可以被8整除,那么剩下位置从前由大到小输出 肯定有9输出9 有8输出8的整数 将被八整除的三位数预处理存入vector 判断输入的数能否将这三位数放最后 最后有多种被8整除时比较从9到0判断个数 不一样则能比出大小 如果前面数和个数都一样也更换 因为vector存后三位时从小到大的 最后一位数 000 008 二位数 相应加0判断个数。代码如下
三.代码
#include<bits/stdc++.h>
using namespace std;
long long int a[20],b[20],v[20],c[20];
vector<int>q;
void f()
{
for (int i = 1; i <=9 ; ++i) {
v[i]=c[i];
}
}
int main()
{ int d=0,tt,n,m,t,num,z,zz;
for (int i = 0; i <=999 ; ++i) {
if (i%8==0)
{
q.push_back(i);
}
}
string s;char bb[5];
while (cin>>s)
{ memset(v,0,sizeof(v));memset(b,0,sizeof(b));
memset(a,0,sizeof(a));t=0;num=-1;z=0;
if (s.size()==3) { //小于等于三位数直接暴力
for (int i = 0; i <3; ++i) {
bb[i]=s[i];
}bb[s.size()]='\0';d=atoi(bb);tt=1;if (d%8==0){num=max(num,d);}
n=d/100,m=d/10%10,t=d%10;
d=n*100+m+t*10;if (d%8==0)num=max(num,d);
d=m*100+n*10+t;if (d%8==0)num=max(num,d);
d=m*100+t*10+n;if (d%8==0)num=max(num,d);
d=t*100+n*10+m;if (d%8==0)num=max(num,d);
d=t*100+m*10+n;if (d%8==0)num=max(num,d);
printf("%d\n",num);
}
else if (s.size()==2)
{
d=(s[0]-'0')*10+s[1]-'0';
if (d%8==0)num=max(num,d);
d=d/10+d%10*10;if (d%8==0)num=max(num,d);
printf("%d\n",num);
}
else if (s.size()==1)
{
if (s[0]=='8')printf("8\n");
else if (s[0]=='0')printf("0\n");
else printf("-1\n");
}
else
{
for (int i = 0; i < s.size(); ++i) {
a[s[i]-'0']++; //统计数字的个数
}tt=0;z=0;
for (int i = 0; i <q.size() ; ++i) { zz=0;
if (q[i]<10){
n=0,m=0,t=q[i];d=q[i];//前两位模拟为0
}
else if (q[i]<100)
{
n=0;d=q[i];m=d/10,t=d%10;//第一位模拟为0
}
else
{d=q[i]; n=d/100,m=d/10%10,t=d%10;}
b[n]++;b[m]++;b[t]++; //三个数字个数
if (a[n]>=b[n]&&a[m]>=b[m]&&a[t]>=b[t])//如果满足后三位可以整除0 接着判断
{
for (int j = 0; j <=9 ; ++j) {
c[j]=a[j];
}
z=1;c[n]--,c[m]--,c[t]--;//减去后三位的数字个数
for (int j = 9; j >=0 ; --j) {
if (c[j]>v[j])//比维护的最大序列大 则更换
{ zz=1;tt=d;
f();break;
}
else if (c[j]==v[j])continue;
else { zz=1;
break;
}
}
if (zz==0)tt=max(tt,d);//如果 序列相同 后三位交换
}
memset(b,0,sizeof(b));
} if (z==0){ printf("-1\n");
continue;
}a[tt/100]--,a[tt/10%10]--,a[tt%10]--;
for (int i = 9; i >=0 ; --i) {
while (a[i]--)printf("%d",i);//从9开始 有多少个输出多少个
}if (tt==0)printf("000\n");
else if (tt==8)printf("800\n");
else if (tt<=100)printf("%d0\n",tt);
else
printf("%d\n",tt);
}
}
}
推荐阅读
-
Problem 8: Largest product in a series
-
NSUOJ 2697
-
NSUOJ - 暴力 - Problem 3155
-
BZOJ 2697 Watery Problem
-
NSUOJ - 歌词显示 - Problem 2292
-
NSUOJ - 找子串 - Problem 2701
-
SyntaxError: encoding problem:gbk(UTF-8)错误梳理
-
SyntaxError: encoding problem: utf8 with BOM
-
Problem 8: Largest product in a series
-
CentOS 8安装Docker报错(Problem: package docker-ce-3:19.03.8-3.el7.x86_64 requires containerd.io >= 1.2.)