数列
提交文件:sequence.pas/c/cpp
输入文件: sequence.in
输出文件: sequence.out
问题描述:
把一个正整数分成一列连续的正整数之和。这个数列必须包含至少两个正整数。你需要求出这个数列的最小长度。如果这个数列不存在则输出 -1 。
输入格式:
每行包含一个正整数 n 。
每个文件包含多行,读入直到文件结束。
输出格式:
对于每个 n ,输出一行,为这个数列的最小长度。
 

第一行是两个整数N和S,其中N是树的节点数。

第二行是N个正整数,第i个整数表示节点i的正整数。

接下来的N-1行每行是2个整数x和y,表示y是x的儿子。

输出格式:

输出路径节点总和为S的路径数量。

输入样例:

输出样例:

3 3

1 2 3

1 2

1 3

2

数据范围:

对于30%数据,N≤100;

对于60%数据,N≤1000;

对于100%数据,N≤100000,所有权值以及S都不超过1000。

数据范围:
对于所有数据,n≤2 。

这个是JLOI2012的T1,发出来仅为了试题完整

=============================================================================================

在这个问题中,给定一个值S和一棵树。在树的每个节点有一个正整数,问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点,根的深度是0,它的儿子节点的深度为1。路径不必一定从根节点开始。

Input

第一行是两个整数N和S,其中N是树的节点数。

第二行是N个正整数,第i个整数表示节点i的正整数。

接下来的N-1行每行是2个整数x和y,表示y是x的儿子。

Output

输出路径节点总和为S的路径数量。

Sample Input

3 3

1 2 3

1 2

1 3

Sample Output

2

Hint

对于100%数据,N≤100000,所有权值以及S都不超过1000。

题解:
  这个题目看上去是不是要点分,稍微看一下数据范围,S不超过1000,而且所有点权都为正整数,这意味着我们每次枚举一个起点,dfs,层数不会超过1000层,而且因为要保证深度关系,很多节点都远远达不到。这题还是很暴力吧。

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 101000
using namespace std;
int ans=;
int val[MAXN],b[MAXN],dep[MAXN],roof;
struct edge{
int first;
int next;
int to;
}a[MAXN*];
int n,m,num=; void addedge(int from,int to){
a[++num].to=to;
a[num].next=a[from].first;
a[from].first=num;
} void dfs(int now,int fa,int tot){
if(tot==m) ans++;
if(tot>=m) return;
for(int i=a[now].first;i;i=a[i].next){
int to=a[i].to;
if(to==fa) continue;
if(dep[to]<=dep[now]) continue;
dfs(to,now,val[to]+tot);
}
} void pre(int now,int fa){
dep[now]=dep[fa]+;
for(int i=a[now].first;i;i=a[i].next){
int to=a[i].to;if(to==fa) continue;
pre(to,now);
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&val[i]);
for(int i=;i<=n-;i++){
int x,y;scanf("%d%d",&x,&y);
addedge(x,y),addedge(y,x);b[y]=;
}
for(int i=;i<=n;i++) if(!b[i]) roof=i;
pre(roof,);
for(int i=;i<=n;i++) dfs(i,,val[i]);
printf("%d",ans);
return ;
}
05-26 19:21