火柴棒等式(2008年NOIP全国联赛提高组)
2024-10-01 02:07:56
题目描述 Description
给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示:
注意:
1. 加号与等号各自需要两根火柴棍
2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C>=0)
3. n根火柴棍必须全部用上
输入描述 Input Description
输入文件共一行,又一个整数n(n<=24)。
输出描述 Output Description
输出文件共一行,表示能拼成的不同等式的数目。
样例输入 Sample Input
样例1:
14
样例2:
18
样例输出 Sample Output
样例1:
2
样例2:
9
数据范围及提示 Data Size & Hint
【输入输出样例1解释】
2个等式为0+1=1和1+0=1。
【输入输出样例2解释】
9个等式为:
0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11
代碼實現:
#include<cstdio>
#include<iostream>
using namespace std;
int n,ans;
int s[][];
int sh[]={,,,,,,,,,};
bool v[][];
void knqk(int x,int y,int z,int en){//搜索x根火柴能擺出哪些數。(恰好用光)//x記錄用的火柴數,y記錄剩餘的火柴數,z記錄擺出的數,en恩。
if(y==){s[x][++s[x][]]=z;return;}//滿足條件的數存到s數組中。
for(int i=;i<;i++){
if(en>&&i==) continue;//沒有會出現000=0(擺多個零還是零)。
if(y>=sh[i]) knqk(x,y-sh[i],z+en*i,en*);
}
}
int main(){
scanf("%d",&n);
n-=;
for(int i=;i<=n-;i++) knqk(i,i,,);
for(int i=;i<=n-;i++)//枚舉第一個數用的火柴數。
for(int j=;j<=n-i-;j++){//枚舉第二個數用的火柴數。
int k=n-i-j;//確定第三個數用的火柴數。
for(int ii=;ii<=s[i][];ii++)//枚舉用i根火柴能擺出的數。
for(int jj=;jj<=s[j][];jj++)//枚舉用j根火柴能擺出的數。
for(int kk=;kk<=s[k][];kk++){//枚舉用k根火柴能擺出的數。
if(s[i][ii]+s[j][jj]==s[k][kk]&&!v[s[i][ii]][s[j][jj]]){//滿足條件並且此等式未出現過。
ans++;
v[s[i][ii]][s[j][jj]]=;//標記。
}
}
}
printf("%d\n",ans);
return ;
}
其實還有一種代碼較短的思路(記錄擺出某個數用的火柴數),懶得打了~
最新文章
- 解密FFmpeg播放track mode控制
- 算法系列:FFT 002
- JSP 页面缓存以及清除缓存
- [CareerCup] 2.4 Partition List 划分链表
- SU Demos-03T-F Analysis-01Sugabor
- SQL基础篇---基本概念解析
- [设计模式] 21 策略模式 Strategy
- 要理解javascript中间apply和call
- DOS命令行 定时关机&;取消定时关机
- Python写入文件,但是发现文件为空,竟然未写入!
- Linux Oracle服务启动&;停止脚本与开机自启动[转]
- Request常用方法 (总结)
- Android内核sysfs中switch类使用实例
- openstack操作之一 命令行
- webapi框架搭建-创建项目(三)-webapi owin
- bzoj:1661 [Usaco2006 Nov]Big Square 巨大正方形
- 温故而知新—heap
- RTMPdump(libRTMP) 源代码分析 8: 发送消息(Message)
- 一些android开发实用性网站记录
- Kali Linux Vmware虚拟机(新手)安装