hdu4403A very hard Aoshu problem 线段树
//给一个长度为大于2小于15的字符串
//在当中间加‘+’或‘=’使得其成为一个等式的方法的个数
//枚举等号位置。暴力搜索加号加的位置
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 20;
typedef __int64 ll ;
int ans;
int a[maxn] ,len_a;
int b[maxn] , len_b ;
char str[maxn] , len;
bool judge(int pos)
{
ll ans_1 = 0 ,ans_2 = 0;
int pre = 1 ;
for(int i = 1;i <= len_a;i++)
{
ll temp = 0;
for(int j = pre ; j <= (i == len_a ? pos :a[i]) ; j++)
temp = temp*10 + str[j - 1] - '0' ;
ans_1 += temp ;
pre = a[i] + 1 ;
}
pre = pos + 1 ;
for(int i = 1;i <= len_b ;i++)
{
ll temp = 0 ;
for(int j = pre ; j <= (i == len_b?
len :b[i]) ;j++)
temp = temp*10 + str[j - 1] - '0' ;
ans_2 += temp ;
pre = b[i] + 1 ;
}
return (ans_1 == ans_2);
}
void dfs(int pos , int step)
{
if(step == (len))
{
if(judge(pos))
ans ++ ;
return ;
}
if(step < pos)
{
a[len_a++] = step ;
dfs(pos , step+1) ;
len_a--;
}
if(step > pos)
{
b[len_b++] = step ;
dfs(pos , step+1) ;
len_b-- ;
}
dfs(pos , step+1) ;
}
int main()
{
//freopen("in.txt" , "r" , stdin) ;
while(scanf("%s" ,str))
{
if(str[0] == 'E')
break;
len = strlen(str) ;
ans = 0 ;len_a = len_b = 1 ;
for(int i = 1;i < len ;i++)
dfs(i , 1) ;
printf("%d\n" , ans) ;
}
return 0 ;
}
相关文章
- 简单线段树模板[通俗易懂]
- HDU 1556-差分数组和线段树的对比分析-Color the ball
- zkw线段树 学习笔记
- 别人写线段树写得脑壳疼,你却用二次元少女在骗分……
- LeetCode周赛285,再次翻车,时隔6年,没能写出的线段树
- acwing-个简单的整数问题2(线段树+懒惰标记)「建议收藏」
- 蓝桥杯 分苹果(线段树)---------C语言—菜鸟级
- 算法训练 格子操作(线段树)-----------C语言—菜鸟级
- 计算几何之判断线段相交
- 计算几何之线段相交问题(平面扫描)
- 线段树模板
- 【综合笔试题】难度 4/5,字符处理的线段树经典运用
- 线段树笔记
- 图解线段树
- 空间判断点是否在线段上
- 数据结构之线段树
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树
- 线段树QWQ
- 线段树(结构体建法_QAQ)
- 最大数maxnumber (HYSBZ 1012)(线段树区间查询和单点修改)(优雅的暴力)
- Allegro使用Skill语言实现根据两点p1,p2确定的线段判断是否与bbox构成的矩形相交的函数
- 线段树模板与练习
- 【OpenGL】十二、OpenGL 绘制线段 ( 绘制单条线段 | 绘制多条线段 | 依次连接的点组成的线 | 绘制圈 | 绘制彩色的线 )
- 【Android UI】绘制圆角矩形进度条 ① ( 像素值转化 dp -> px | Paint 标志位设置 | Paint 画笔线帽样式设置 | Paint 画笔线段连接处样式设置 )