今天佛了，魔鬼周一，在线教学，有点小累，但还好，今天AC了一道，每日一道，还好达成目标，还以为今天完不成了，最近任务越来越多，如何高效完成该好好思考一下了~最重要的还是学业的复习和预习。

今日兴趣新闻：

《流浪地球》中的逃生气囊球和马斯克有什么关系？

链接：https://mbd.baidu.com/newspage/data/landingsuper?context=%7B%22nid%22%3A%22news_8599496962815210358%22%7D&n_type=0&p_from=1

------------------------------------------------题目----------------------------------------------------------

Polycarp and Div 3

3121

 2

 6

 1

1000000000000000000000000000000000

33

201920181

 4

------------------------------------------------题目----------------------------------------------------------

（一） 原题大意：

　　输入一个数，某人可以进行以下的操作：　　

　　某人可以进行任意数量的垂直切割，其中每个切割在一对相邻的数字之间进行。结果数字不能包含额外的前导零（也就是说，当且仅当此数字恰好是一个字符' 0 '时，数字才能以0开头）。例如，007，01和00099不是有效的数字，但90，0和10001是有效的。

　　分割出来的每一部分的数，都能被3整除，则说明可以得到一个整除3的数，其中0也能被3整除，请算一算能为该同学获得最多几个整除3的数呢？

（二） 题目分析：

　　首先，肯定是需要得到每一个数字，如果这个数字是0，那么答案比较简单，如果当前数字能够直接被3整除（0， 3， 6， 9）的话，那就直接结果加一就好了。 

　　然后如果这两种情况都不成立，那么就是两位数以上的组合了，在这里我出了点弯路子，刚开始用求和法，然后却疯狂到test11就WA了，检查了很久也没有找到解决办法，后来心理课结束后和大佬们交谈才发现一些新想法奥秘，那就是符合3整除的数，求余之后有特殊关系，待会列一下我的弯路给自己提个醒。

　　然后我换了一种方法，那就是用加和，利用整除3的特性，下面也列出来了，但还是WA了。

　　最后我翻看一些博客，发现在我原来写得基础上，只要改变if条件的位置就能AC了，总结来说有三种情况：当前数字模3为0、现有的数字之和模3为0（当前正在处理的）、隔了三个数字了一定可以做到模3为0

（三） 错误弯路：

　　第一次直接用long long int 去扔输入，然后丢OJ结果发现第一次就WA了

#include<stdio.h>
#include<math.h> 
long long int temp,num;
int temp_num,counter,ans,k;
int main()
{
    ans = 0;
    scanf("%d",&temp);
    num = temp;
    while(num>0)
    {
        k = num % 10;
        if(k == 0)
        {
            ans++;
            counter = temp_num = 0;
            num = num / 10;
            continue;
        }
        if(k % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
        }
        else
        {
            temp_num += k * pow(10,counter);
            if(temp_num % 3 == 0)
            {
                ans++;
                counter = temp_num = 0;
            }
        }
        num = num / 10;
    }
    printf("%d\n",ans);
    return 0;
 } 

　　结果是因为scanf这里用了%d，结果才发现过样例1000000000000000000000000000的时候错了，然后就换了一种方法，像这样大数都只能用char来处理了：

　　第二步弯路，然后就改了改，扔进去：

#include<stdio.h>
#include<math.h> 
#include<string.h>
char input[2000005];
int num;
int temp_num,counter,ans,k;
int main()
{
    ans = 0;
    scanf("%s",&input);
    for(int i = strlen(input) - 1;i>=0;i--)
    {
        k = input[i];
        if(k == 0)
        {
            ans++;
            counter = temp_num = 0;
            continue;
        }
        if(k % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
        }
        else
        {
            temp_num += k * pow(10,counter);
            if(temp_num % 3 == 0)
            {
                ans++;
                counter = temp_num = 0;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
 } 

　　到这里样例就都全过了，代码思路是：将输入的值扔进char数组里，然后获取到他的长度，从后往前来处理，从判断当前数是否为0，如果是的话就直接加一，然后判断当前数能否被3整除，如果可以就也直接加一。都没有的话，就存到一个temp变量里，然后与后面处理的数求和，然后判断该求和temp是否能被3整除。结果这里到test11就WA了，半天没搞懂，后来和同学讨论了半天，结果发现对于122 221这样的数判断就出现了问题，后来实在解不了，嫌判断太乱，都单独列了出来，结果居然AC了：

#include<stdio.h>
#include<math.h> 
#include<string.h>
char input[200005];
long long int temp_num,counter,ans,k;
int main()
{
    ans = counter = 0;
    scanf("%s",&input);
    for(int i = strlen(input) - 1;i>=0;i--)
    {
        k = input[i] - '0';
        temp_num += k;
        counter++;
        if(counter == 3)
        {
            ans++;
            counter = temp_num = 0;
            continue;
        }
        else if(k % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
            continue;
        }
        else if(temp_num % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
            continue;
        }
    }
    printf("%d\n",ans);
    return 0;
 } 

　　结果误打误撞发现了一些牛皮的数学思维~ 待会献上：

（四）AC代码：

　　　　因为代码比较简单，依旧不分块了~

#include<stdio.h>
#include<math.h> 
#include<string.h>
char input[200005];
long long int temp_num,counter,ans,k;
int main()
{
    ans = counter = 0;
    scanf("%s",&input);
    for(int i = strlen(input) - 1;i>=0;i--)
    {
        k = input[i] - '0';
        temp_num += k;
        counter++;
        if(counter == 3 || k % 3 == 0 || temp_num % 3 == 0)
        {
            ans++;
            counter = temp_num = 0;
        }
    }
    printf("%d\n",ans);
    return 0;
 } 

（五）AC截图：

（六）解后分析：

　　　　分析1 - 能被特殊数整除的特征：

1、能被2整除的数的特征。

   如果一个数能被2整除，那么这个数末尾上的数为偶数，“0”、“2”、“4”、“6”、“8”。

2、能被3整除的数的特征。

   如果一个数能被3整除，那么这个数所有数位上数字的和是3的倍数。例如：225能被3整除，因为2+2+5=9,9是3的倍数，所以225能被3整除。

3、能被4整除的数的特征。

   如果一个数的末尾两位能被4整除，这个数就能被4整除。例如：15692512能不能被4整除呢？因为15692512的末尾两位12，能被4整除，所以15692512能被4整除。

4、能被5整除的数的特征。

   若一个数的末尾是0或5，则这个数能被5整除。

5、能被7整除的数的特征。

方法一：若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。如果差太大或心算不易看出是否是7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否是7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ， 59－5×2＝49，所以6139是7的倍数，以此类推。

方法二：如果一个多位数的末三位数与末三位以前的数字所组成的数的差，是7的倍数，那么这个数就能被7整除。例如：280678末三位数是678，末三位以前数字所组成的数是280,679-280=399,399能被7整除，因此280679也能被7整除。

方法三：首位缩小法，减少7的倍数。

例如，判断452669能不能被7整除，452669-420000=32669，只要32669能被7整除即可。可对32669继续，32669-28000=4669,4669-4200=469,469-420=49,49当然被7整除所以452669能被7整除。
6、能被8整除的数的特征。
   若一个整数的未尾三位数能被8整除，则这个数能被8整除。
7、能被9整除的数的特征。
   若一个数的数位上的数字的和能被9整除，则这个整数能被9整除。例如：111111111能不能被9整除呢？因为1+1+1+1+1+1+1+1+1=9,9是9的倍数，所以111111111能被9整除。
8、能被11整除的数的特征。
   方法一：若一个整数的奇位数字之和与偶位数字之和（从右往左数）的差能被11整除，则这个数能被11整除。例如，判断491678能不能被11整除。奇位数字之和8+6+9=23；偶位数字之和7+1+4=12；23-12=11,11能被11整除，所以491678能被11整除。这种方法叫作“奇偶位差法”。  

方法二：11的倍数检验法也可用上述检查7的「割尾法」处理！过程唯一不同的是：倍数不是2而是1！例如：判断491678能不能被11整除，49167-8=49159,4915-9=4906，

490-6=484,48-4=44。44能被11整除，所以得491678能被11整除。

方法三：还可以根据7的方法二判断。例如：283679的末三位数是679，末三位以前数所组成的数是283,679-283=396,396能被11整除，因此283679就一定能被11整除。
9、能被13整除的数的特征。
   方法一：若一个整数的个位数字截去，再从余下的数中，加上个位数的4倍，如果和是13的倍数，则原数能被13整除。如果和太大或心算不易看出是否13的倍数，就需要继续上述「截尾、倍大、相加、验和」的过程，直到能清楚判断为止。

例如，判断1284322能不能被13整除。128432+2×4=128440,12844+0×4=12844，

1284+4×4=1300,1300÷13=100。所以1284322能被13整除。

方法二：前面7的方法二，也适用判定13。例如：判定1284322能不能被13整除，128432的末尾三位数是322，末尾以前的数字所组成的数是1284,322-1284=-962。962÷13=74。所以1284322能被13整除。
10、能被17整除的数的特征。
    方法一：若一个整数的个位数字截去，再从余下的数中，减去个位数的5倍，如果差是17的倍数，则原数能被17整除。如果差太大或心算不易看出是否17的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断1675282能不能被17整除，167528-2×5=167518,16751-8×5=16711,1671-1×5=1666,166-6×5=136,

136÷17=8，所以1675282能被17整除。

方法二：若一个整数的末三位与3倍的前面的隔出数的差能被17整除，则这个数能被17整除。例如，判断1675282能不能被17整除，1675282的末三位是282，前面的数是1675，

282-1675×3=-4743,4743÷17=279，所以1675282能被17整除。

11、能被19整除的数的特征。  

方法一：若一个整数的末三位与7倍的前面的隔出数的差能被19整除，则这个数能被19整除。例如，判断234555能不能被19整除，234555末尾三位数是555，前面三位是234，

555-234×7=-1083,1083÷19=57，所以234555能被19整除。

方法二：若一个整数的个位数字截去，再从余下的数中，加上个位数的2倍，如果和是19的倍数，则原数能被19整除。如果和太大或心算不易看出是否19的倍数，就需要继续上述「截尾、倍大、相加、验和」的过程，直到能清楚判断为止。
12、能被23整除的数的特征。
    若一个整数的末四位与前面5倍的隔出数的差能被23(或29)整除，则这个数能被23整除。

13、能被25整除的数的特征。

如果一个数的末尾两位能被25整除，则这个数能被25整除。

14、能被125整除的数的特征。

    如果一个数的末尾三位能被125整除，则这个数能被125整除。

分析2-为什么将counter == 3判断单独拿出来就能求解了？

　　考虑将每个数字模3以后的结果。

　　如果对于当前数字能被3整除（0、3、6、9）模3结果为0的数，则直接个数加1

　　如果是两个数字那就有四种可能(1,1) (2, 2) (1, 2) (2, 1)其中后两个组合之和为3能被3整除

　　如果是三个数字对于之前两个数字的组合只剩下(1, 1)和(2, 2) 那么下个数不管是1还是2都可以组成一个3的整数倍

分析3-其他优质解法搜集：

　　解法一：

　　  贪心思路：
　　对每位数字对3求余,则结果只能是0、1、2.如果当前位是0，则对结果贡献为1，如果不为0，则判断连续出现2或者1的数目num，如果num%3为0，则对结果的贡献为num/3，否则可以找到一个与当前数字不相等的数字(前面连续出现的是2，当前为1。或者前面连续出现的是1，当前为2)，则对结果贡献是num/3+1.

#include<bits/stdc++.h>

using namespace std;
string s;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> s;
    for(int i = 0; i < s.length(); i++) {
        s[i] = (s[i] - '0') % 3 + '0';
    }
    int num = 1;
    int ans = 0;
    for(int i = 1; i < s.length(); i++) {
        if(s[i] == s[i-1]) num++;
        else {
            if(s[i] == '0') {
                ans += num / 3;
                num = 1;
            }
            else if(s[i-1] == '0') {
                ans += num;
                num = 1;
            }
            else {
                ans += num / 3;
                if(num % 3) {
                    ans++;
                    num = 0;
                }
                else num = 1;
            }
        }
    }
    if(s[s.length()-1] == '0') ans += num;
    else ans += num / 3;
    cout << ans << endl;
    return 0;
}

　　解法二：

　　dp思路：
　　dp[i]表示截止到下标为i的元素之前最多有多少个片段%3=0。很容易想到当(sum[i]-sum[j]) % 3 == 0时，dp[i] = max{dp[j]} + 1;所以用一个pre[]数组表示和当前sum值相等的上一个sum值，中间肯定经历了一个(+3)%3的过程。所以最终的状态方程是dp[i] = max(dp[pre[sum]]+1, dp[i]);

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e7;
string s;
int dp[maxn], pre[maxn];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    memset(pre, -1, sizeof(pre));
    cin >> s;
    for(int i = 0; i < s.length(); i++) {
        s[i] = (s[i] - '0') % 3 + '0';
    }
    dp[0] = (s[0] == '0');
    int sum = s[0] - '0';
    pre[sum] = 0;
    for(int i = 1; i < s.length(); i++) {
        int t = s[i] - '0';
        sum = (sum + t) % 3;
        dp[i] = dp[i-1];
        if(sum == 0) dp[i] = max(dp[i], 1);
        if(pre[sum] != -1) dp[i] = max(dp[pre[sum]] + 1, dp[i]);
        pre[sum] = i; 
    } 
    cout << dp[s.length()-1] << endl;
    return 0;
}

　　解法三：大师兄的神奇循环解法：

注：如果有更好的解法，真心希望您能够评论留言贴上您的代码呢~互相帮助互相鼓励才能成长鸭~~

原文链接:https://www.cnblogs.com/winniy/p/10474232.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有