P10571 [JRKSJ R8] 三七二十一 题解

· · 题解

P10571 [JRKSJ R8] 三七二十一 题解

骗分

个人认为这一部分极具正解引导性。

首先有一个比较好的暴力，即只消除单个字符组成的 2 的任意非负数次幂，因为这些都是必须替换的数。

代码如下：

#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin>>s;
    int len=s.size(),cnt=0;
    for(int i=0;i<len;i++)
    {
        int t=log2(s[i]-'0');
        if((1<<t)==s[i]-'0')
        {
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}

这个只能得 10 分。

正解

考虑题目是如何卡 10 分骗分做法的？

于是打个判断，找出所有 2 的非负整数次幂每一位都不含 2 的非负整数次幂的数。

代码如下：

#include <bits/stdc++.h>
using namespace std;
long long t=1;
int book[11]; 
int main()
{
    for(int i=1;t<10000000;i++)
    {
        int flag=0;
        long long x=t;
        while(x)
        {
            int e=log2(x%10);
            if((1<<e)==x%10)
            {
                flag=1;
            }
            x/=10;
        }
        if(flag==0)cout<<t<<' ';
        t*=2;
    }
    return 0;
}

结果是令人惊讶的！！！

65536

只有这一个数不包含 2 的非负整数次幂同时是2的非负整数次幂！！！

那么就在 10 分骗分代码之上再特判一下 65536，将它删去，即它换成 65537 或 75536 等更改一个数其不是 2 的非负整数次幂的数。

代码如下：

#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin>>s;
    int len=s.size(),cnt=0;
    for(int i=0;i<len;i++)
    {
        int t=log2(s[i]-'0');
        if((1<<t)==s[i]-'0')
        {
            cnt++;
            s[i]='9';
        }
    }
    for(int i=0;i+4<len;i++)
    {
        if(s[i]=='6'&&s[i+1]=='5'&&s[i+2]=='5'&&s[i+3]=='3'&&s[i+4]=='6')
        {
            cnt++;
            s[i+4]='7';
        }
    }
    cout<<cnt;
    return 0;
}

一道好题~~

有问题请指出----