/*编写一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。
例如如下的先序遍历字符串: abc##de#g##f### 其中 # 表示的是空格,空格字符代表空树。
建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
输入格式
共一行,包含一个字符串,表示先序遍历字符串。
输出格式
共一行,输出将输入字符串建立二叉树后中序遍历的序列,字符之间用空格隔开。
注意,输出中不用包含 #。
数据范围
输入字符串长度不超过 100
,且只包含小写字母和 #。
输入样例:
abc##de#g##f###
输出样例:
c b e g d f a*/
#include<iostream>
using namespace std;
#include<string>
int k;//此时二叉树所在的位置
string str;
void dfs()
{
if(str[k]=='#')
{
k++;//往后走一个位置
return;//返回上一层递归
}
char r=str[k++];//用r来存一下所在位置的字母
dfs();
cout<<r<<" ";//中序输出
dfs();
}
int main()
{
cin>>str;
dfs();
return 0;
}
/*给定一个长度为 n
的数组 a1,a2,…,an
。
现在,要将该数组从中间截断,得到三个非空子数组。
要求,三个子数组内各元素之和都相等。
请问,共有多少种不同的截断方法?
输入格式
第一行包含整数 n
。
第二行包含 n
个整数 a1,a2,…,an
。
输出格式
输出一个整数,表示截断方法数量。
数据范围
前六个测试点满足 1≤n≤10
。
所有测试点满足 1≤n≤105
,−10000≤ai≤10000
。
输入样例1:
4
1 2 3 3
输出样例1:
1
输入样例2:
5
1 2 3 4 5
输出样例2:
0
输入样例3:
2
0 0
输出样例3:
0*/
~~~c++
#include<iostream>
using namespace std;
const int N=10010;
int a[N],s[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+a[i];
}
long long cnt=0,res=0;
if(s[n]%3)cout<<"0"<<endl;
else{
for(int j=2;j<=n;j++)
{
if(s[j-1]==s[n]/3)cnt++;
if(s[j]==s[n]/3*2)res+=cnt;
}
}
cout<<res<<endl;
}