本文主要是介绍17年武汉大学网络赛—Divide by Six，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接： 点击打开链接 ；
第一篇博客啊...
题目意思大概是这样的，给出一个长为10^5的数，然后让你删掉其中某些数，使其为6的倍数（前缀0也要删去），求删除后所可能保留的最长的。
思路一：（大佬学长说的歪门邪道解法）
一个数是6的倍数，那么它肯定也是2和3的倍数。2的倍数很好判断末尾的数可以被2整除，3的倍数：所有位上的数值相加是3的倍数。
这样的话，就可以控制一个可行区间[l, r]（s[l]!= ‘0’, (s[r]-‘0’)%2== 0;），然后在这个区间删除就可以了。
这样想是正确的，但是又会碰到一系列问题，怎么删...
设sum为该区间所有位上的数值的和，sum%3== 1 || 2 || 0；显然，0是我们想要的结果，如果等于1呢，可以删掉一个1、2个2...so on；如果等于2呢，也会有好多种情况。因为3、6、9不用考虑（加上或者删除不会影响sum%3的值），就变成了删1、2、4、5、7、8这些数...然后会越想越麻烦，当时在赛场上就是这样陷入脑残的世界。
大佬给出了此方法的正解，也是他们赛场上的代码（为什么我没想到- -！）...将可行区间内的所有的数都%3，这样这个区间就相当于0、1、2三种元素的组合...这样的话，sum%3== 1，只意味着两种情况的删除 1个1或者2个2；sum%3== 2，删掉一个2或者2个1。
ok！想到这里再加上对前缀零的删除就可以很完美的a掉了。（不过还要分清一个细节，对区间维护的时候应该是用s[i]来判断，一个粗心wa了一次）
#include <bits/stdc++.h>using namespace std;string s;
int a[100050];int main()
{cin >> s;int ans= -1, pr= 0;for(int i= 0; i< s.length(); i++) { a[i]= (s[i]- '0')% 3; pr+= a[i]; if(s[i]== '0') ans= 1; }int l= 0, r= s.length()- 1;while(s[l]== '0') l++;while(r>= l){if((s[r]- '0')% 2!= 0) { pr-= a[r]; r--; continue; }if(pr% 3== 1){int p= r;while(a[p]!= 1 && p>= l) p--;if(p== l){int ll= l+ 1;while(s[ll]== '0') ll++;ans= max(ans, r- ll+ 1);}else if(p> l) ans= max(ans, r- l);p= r- 1;while(a[p]!= 2 && p> l) p--;if(a[p]== 2){p--;while(a[p]!= 2 && p>= l) p--;if(p== l){int ll= l+ 1;while(s[ll]== '0') ll++;ans= max(ans, r- ll);} else if(p> l) ans= max(ans, r- l- 1);}} else if(pr% 3== 2){int p= r- 1;while(a[p]!= 2 && p>= l) p--;if(p== l){int ll= l+ 1;while(s[ll]== '0') ll++;ans= max(ans, r- ll+ 1);}else if(p> l) ans= max(ans, r- l);p= r- 1;while(a[p]!= 1 && p> l) p--;if(a[p]== 1){p--;while(a[p]!= 1 && p>= l) p--;if(p== l){int ll= l+ 1;while(s[ll]== '0') ll++;ans= max(ans, r- ll);} else if(p> l) ans= max(ans, r- l- 1);}} else ans= max(ans, r- l+ 1);r--;}if(ans== -1) printf("-1s\n"); else printf("%d\n", ans);return 0;
}思路二：（dp...）
之前没有接触过数位dp，赛场上虽然很努力想用dp解决，但是还是想不到递推关系...赛后看了大佬的代码就傻眼了。
对整个进行序列逐个删选。
dp[i][j]:表示取到第i位，余数为j的最优解；（是不是顿时想到了一切......跟背包一样）
删第i位：dp[i][j]==max(dp[i][j], dp[i- 1][j])；
不删： dp[i][(j* 10+ a)]== max(dp[i][j* 10+ a],dp[i- 1][j]+１)；（ａ为第i位上的数值）
这样就可以完美解决了。但是还是要注意一下初始化的问题...
#include<bits/stdc++.h> using namespace std;int f[100050][6];
char s[100050];int main()
{ scanf("%s", s+ 1); int l= strlen(s+ 1), ans= -1;for(int i= 1; i<= l; i++) if(!(s[i]- '0')) ans= 1; // ???0???ans???1?for(int i= 0; i<= l; i++) for(int j= 0; j< 6; j++) f[i][j]= -100050; // ??? for(int i= 1; i<= l; i++){int a= s[i]- '0';if(a!= 0) f[i][a% 6]= 1;for(int j= 0; j< 6; j++) f[i][j]= max(f[i][j], f[i- 1][j]); // ???i?for(int j= 0; j< 6; j++) f[i][(j* 10+ a)% 6]= max(f[i][(j* 10+ a)% 6], f[i- 1][j]+ 1); // ??i?ans= max(ans, f[i][0]);}if(ans!= -1) printf("%d\n", ans); else printf("-1s\n");return 0;
}
这篇关于17年武汉大学网络赛—Divide by Six的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
