小睿睿的等式 (思维dp)

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

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld

题目描述

小睿睿在游戏开始时有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

题意:不解释~~

题解:首先利用dp[i]=dp[i/10]+a[i%10],预处理一下,dp[i]表示数字i用几根火柴棒,dp[0]需要写代码的时候注意一下。然后避免重复,就要从0找到n/2,利用公式dp[i]+2+dp[n-i]+2+dp[n]=n/k判断是否符合条件,统计一下就ok了,上代码:

#include <iostream>
using namespace std;
const int MAX = 5*1e7+100;
int a[10] = {6,2,5,5,4,5,6,3,7,6};
int dp[MAX];
int main(){
	int n,k;
	cin >> n >> k;
	int w=n/k;
	for (int i = 1; i <= n;i++){
		dp[i]=dp[i/10]+a[i%10];//预处理数字i有几根火柴棒
	}
	dp[0]=6;//最后对dp[0]赋值,因为dp[0]提前赋值,会对一位数有影响,进而影响后面的数
	int sum=0;
	for (int i = 0; i <= n/2;i++){
		if(dp[i]+2+dp[n-i]+2+dp[n]==w) sum++;//统计结果个数
	}
	cout << sum << endl;
	return 0;
} 

 

全部评论

相关推荐

零OFFER战士:另一个版本查看图片
点赞 评论 收藏
分享
白火同学:先说结论,准大三不是特别好找实习,boss沟通300+没有实习是很正常的情况。一是暑期实习时间太短了,二是在这么多准大四都找不到实习,从实习时间和掌握技术层面,企业会优先看他们。 再说简历,其实985本+准大三到这水平的简历也很优秀了,要说的话,项目经历可以再优化一下,可以基本围绕采取STAR原则,分为项目概述、技术架构、技术亮点、实现结果,再发给AI润色一下。 最后说操作,准大三的话,如果想找实习那就多投,不过现在也7月中旬了,时间上已经略晚了。如果7月底实在找不到,也可以多刷点算法,多学点技术,这实习也不至于一定得有,当然有更好。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务