一.填空题
A.幸运数
这题是个很简单的模拟题，枚举每一个数字，按位拆分然后判断统计即可。
简单枚举版：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
const int R=100000000;
bool check(ll x){
int a[11];
int cnt=0;//记录位数
while(x){
int end=x%10;
cnt++;
a[cnt]=end;
x/=10;
}
if(cnt&1)return false;
int l=0,r=0;//左右之和
for(int i=1;i<=cnt;i++){
if(i>cnt/2)r+=a[i];
else l+=a[i];
}
return l==r;
}
int main(){
ll ans=0;
for(ll i=1;i<=R;i++){
if(check(i))ans++;
}
cout<<ans;//4430091
}
|
前缀和版：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
const int R=100000000;
bool check(ll x){
int pre[11];//前缀和
pre[0]=0;
int cnt=0;//记录位数
int t=x;
while(x){
int end=x%10;
cnt++;
pre[cnt]=pre[cnt-1]+end;
x/=10;
}
if(cnt&1)return false;
if(pre[cnt]&1)return false;//如果用前缀和 这是一个坑 和必须是偶数!
return pre[cnt/2]==pre[cnt]/2;//判断相等
}
int main(){
ll ans=0;
for(ll i=1;i<=R;i++){
if(check(i))ans++;
}
cout<<ans;//4430091
}
|
to_string()版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
const int R=100000000;
bool check(int x){
string s=to_string(x);
int n=s.size();
if(n&1)return false;
int l,r;
l=r=0;
for(int i=0;i<n;i++){
if(i>n/2-1)l+=s[i]-'0';
else r+=s[i]-'0';
}
return l==r;
}
int main(){
int ans=0;
for(int i=1;i<=R;i++){
if(check(i))ans++;
}
cout<<ans;//4430091
}
|
不知道为什么官方\(to\_string\) 反而比手写的慢很多。
B.有奖问答
定义\(f(i,j)\) 是第\(i\) 轮取得分数\(j\) 的方案数，第几轮拿\(70\)分都行，所以答案是\(\sum_{i}^{30}f[i][70]\)
由于分数必须是\(10\) 的整数倍，所以\(j\) 不是\(10\) 的整数倍时，方案数必为\(0\)，跳过即可。
若\(j≠0\) ，\(f(i,j)+=f(i-1.j-10)\) ，可以由上一轮的\(j-10\) 分的方案数，这轮答对一题得到。
若\(j=0\) ，\(f(i,j)+=\sum_{j=0}^{99}f(i-1,j)\) ，这一轮得\(0\) 分的话，上一轮得多少分都没关系，所以上一轮所有分数的方案数都可以转移过来，这轮答错即可，但注意上一轮的\(100\) 分不行，因为题目要求到\(100\) 分就必须马上停止，这是个坑点。
初始化\(f(0,0)=1\) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include <iostream>
using namespace std;
int f[31][101];
int main(){
f[0][0]=1;
long long ans=0;
for(int i=1;i<=30;i++){
for(int k=0;k<=99;k++)f[i][0]+=f[i-1][k];
for(int j=10;j<=100;j+=10)f[i][j]+=f[i-1][j-10];
ans+=f[i][70];
}
cout<<ans;//8335366
}
|
二.程序题
C.平方数