题干:

链接:https://ac.nowcoder.com/acm/contest/371/A
来源:牛客网
 

小睿睿在游戏开始时有n根火柴棒,他想知道能摆成形如“A+B=n”的等式且使用的火柴棒数也恰好等于n/k的等式有多少种(B+A=n与A+B=n看作一种)
注:

“=”与“+”分别需要使用2根火柴棒

 

输入描述:

一行2个整数n,k,保证n取模k为0

输出描述:

一行一个整数,表示答案

示例1

输入

复制

60 2

输出

复制

4

说明

11+49=60
13+47=60
17+43=60
19+41=60

示例2

输入

复制

100000 1250

输出

复制

3092

备注:

对于30%的数据,0<=n<=100

对于50%的数据,0<=n<=1000000

对于100%的数据,0<=n<=50000000;A,B>=0

解题报告:

    预处理出所有数字对应的需要用的火柴数,然后暴力枚举就行了。

AC代码:

#include<cstdio>
#include<assert.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 5e7 + 6;
int dd[10] = {6,2,5,5,4,5,6,3,7,6};
int cal[MAX];
//int cal(int x) {
//	int res = 0;
//	while(x) {
//		res += dd[x%10];
//		x/=10; 
//	}
//	return res;
//}
int main()
{
	int n,k;
	int ans = 0;
	cin>>n>>k;
	for(int i = 1; i<=n; i++) cal[i] = cal[i/10] + dd[i%10];
	int use = n/k - 4 - cal[n];
	for(int i = 1; i<=n/2; i++) {
		//printf("%d %d %d\n",i,cal(i),cal(n-i));
		if(cal[i] + cal[n-i] == use) ans++;
	}
	cout << ans;
	return 0 ;
 } 

如果每次log查询的话只能得到70~90的分数。