大数削除kビット3,MG loves apple(HDU)

トランスファゲート
MG loves apple
Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 442    Accepted Submission(s): 76
Problem Description
MG is a rich boy. He has 
n apples, each has a value of V(
0<=V<=9). 
A valid number does not contain a leading zero, and these apples have just made a valid 
N digit number. 
MG has the right to take away 
K apples in the sequence, he wonders if there exists a solution: After exactly taking away 
K apples, the valid 
N−K digit number of remaining apples mod 
3 is zero. 
MG thought it very easy and he had himself disdained to take the job. As a bystander, could you please help settle the problem and calculate the answer?
Input
The first line is an integer 
T which indicates the case number.(
1<=T<=60)
And as for each case, there are 
2 integer 
N(1<=N<=100000),
K(0<=K
<
N) in the first line which indicate apple-number, and the number of apple you should take away.
MG also promises the sum of 
N will not exceed 
1000000.
Then there are 
N integers 
X in the next line, the i-th integer means the i-th gold’s value(
0<=X<=9).
Output
As for each case, you need to output a single line.
If the solution exists, print”yes”,else print “no”.(Excluding quotation marks)
Sample Input

 
   

     2 5 2 11230 4 2 1000 
   
 
  

我们设S0S0、S1S1、S2S2分别为原串上mod 3=0mod3=0、11、22数字的个数。 我们假定删除取模后为00、11、22的数字各Aa、Bb、Cc个，则显然有0<=A<=S0,0<=B<=S1,0<=C<=S20<=A<=S0,0<=B<=S1,0<=C<=S2且K=A+B+CK=A+B+C且Sum 

$mod3=(A\ast 0+B\ast 1+C\ast 2)mod3=(S0\ast 0+S1\ast 1+S2\ast 2)mod3=bias$ 。 枚举 CC 的值，我们可得

mod 3=(A*0+B*1+C*2)mod 3=(S0*0+S1*1+S2*2)mod 3=biasB mod 3=(bias-C*2)mod 3,A=K-B-CBmod3=(bias−C∗2)mod3,A=K−B−C。如果有若干组A,BA,B不逾界，可知这些(A,B,C)(A,B,C)是在模意义下合法的解，但不一定满足没有前导零。

所以，对于【大于00的数】我们贪心地从后往前删除，对于00我们贪心地从前往后删除。

需要统计出：a3E3=第一个【mod 3=0mod3=0且非00的数】前00的个数（如果mod 3=0mod3=0且非00的数不存在，那么a3a3就取所有零的个数），E1E1=【第一个00前是否存在mod 3=1mod3=1的数】，E2E2=【第一个00前是否存在mod 3=2mod3=2的数】。

则以下情况满足任一种都能保证无前导零：A>=a3A>=E3。B<B<S1S1且E1E1。C<C<S2S2且E2E2。

还需要加一种情况 满足k==n-1 也是yes:

AC代码：

#include
#include
#include
#include
#include
#include
#include
#include

もう一つの良い問題をお勧めします.https://oj.ejq.me/problem/24  (大数整除6の最大桁数)
私のブログhttp://blog.csdn.net/xiangaccepted/article/details/69951928この問題の解法がある(dpを使っている).