发表文章

[最新] 【题解】 CF550C Divisibility by Eight

SSHoj 2月前 1

这道题的思路其实很简单,先用特判处理掉数字中有 0 或者有 8 的情况(也就是直接输出 0 或8),然后剩下的暴力判断即可。。。

那暴力如何去判断呢?我们先来注意一个性质,能被 8 整除的数的后三位一定能被 8 整除。因为本题要求输出任意解,所以只需判断三位数之内 8 的倍数是否在这个数字里面即可。

那么我们用 s[i] 和 e[i] 来记录 i 最先出现和最后出现的位置,然后对于 8~992(实际上是 16~992) 中每一个数,暴力取出三个位上的数 a,b,c ,然后判断 b 有没有在 s[a] 和 e[c]之间出现就可以了。复杂度 O(125N)。(因为此题中 N 特别小,所以直接暴搞就能过)

最后注意一个细节,取出来的数是不含前导 0 的,所以这里必须要加一个特判。

剩下的看代码实现吧:

#include<iostream>
using namespace std;
int sum[105],s[10],e[10];
int main()
{
    int n=0;string str;
    cin>>str;
    for(int k=0;k<str.size();k++)
    {
        int i=++n,now=str[k]-'0';sum[i]=now;
        s[now]=(s[now]?s[now]:i),e[now]=i;  //蛇皮方法求 s[i] e[i]
    }
    if(s[0])    {cout<<"YES\n0"; return 0;} if(s[8])    {cout<<"YES\n8"; return 0;} //特判 0 和 8
    for(int i=8;i<=992;i+=8)
    {
        int a=i/100,b=i/10%10,c=i%10;   //取出 a,b,c
        if((!s[a] && a) || (!s[b] && a && b) || !s[c])  continue;   //如果 a,b,c 不在数列里,直接跳过
        for(int j=(a?s[a]+1:1);j<e[c];j++)
            if(sum[j]==b || (a==0 && b==0)) {cout<<"YES\n";if(a)cout<<a;if(b)cout<<b;if(c)cout<<c; return 0;}   //暴力判断
    }
    cout<<"NO";
    return 0;
}
相关推荐
最新评论 (0)
返回
发表文章
SSHoj
文章数
14
评论数
0
注册排名
1343597