hdu4403A very hard Aoshu problem 线段树
2024-08-25 19:53:35
//给一个长度为大于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 ;
}
最新文章
- python学习笔记(python介绍)
- 使用KRPano资源分析工具强力加密KRPano项目(XML防破解,切片图保护,JS反调试)
- BurpSuite设置公共WIFI抓包
- C# DataGrid合并单元格
- 《深入理解Spark:核心思想与源码分析》正式出版上市
- Android性能优化方法(七)
- hdu Line belt
- ADO.NET中ExcuteReader读取存储过程获取的多行数据
- $(";#id a";) - $(";#id .c a";) = ?
- Mysql实时双备
- Tomcat部署问题及解决方法
- 深度解析PHP数组函数array_combine
- 高仿腾讯QQ即时通讯IM项目
- 基于Spring Security和 JWT的权限系统设计
- Day 04 列表,元祖,range
- css3的calc()属性
- OleDbConnection SqlConnection DB2Connection 区别
- Web 进化
- 多重检验_LSD方法不准确性
- Redis通过IO进行序列化+反序列化
热门文章
- SQL:修复脚本的几点注意事项
- java 日历类Calendar用法
- 真爱如血第七季/全集True Blood迅雷下载
- svn导出文件进行比较
- 黑马day17 ajax&;amp;实现username自己主动刷新
- CATEGORICAL, ORDINAL AND INTERVAL VARIABLES
- 7.7 服务远程暴露 - 订阅与通知(TODO)
- go语言之进阶篇借助bufio实现按行读取内容
- High Availability (HA) 和 Disaster Recovery (DR) 的区别
- Word Ladder leetcode java