【TCO2016 Round 1B Div1 1000】SettingShield

【SRM635】Div2 900 TreeAndPathLength2

Zarxdy34 posted @ 2015年12月11日 14:28 in TopCoder with tags 计数 , 346 阅读

    题目大意:求是否存在这样的一棵树,有n个节点和s条长度为2的简单路径,其中A->B->C和C->B->A算同一种。

    分析:随便找一个点为根root,那么路径有两种,一种是一个点到其父亲再到其父亲的父亲,第二种是一点到其父亲再到其兄弟节点。

    设节点x的儿子节点数为sons[x],则第一种路径的条数为n-1-sons[root],第二种路径的条数为所有sons[x]*(sons[x]-1)/2之和。

    设f[i][j],i表示除root外所有节点的sons之和为i,j表示这些节点有j条长度为2的路径,f[i][j]=1表示这样的图存在。

    最后枚举sons[root],判断是否存在这样的图即可。

 

 

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;


class TreeAndPathLength2 {
public:
	string possible(int n, int s) {
		int arr[55][1010];
		memset(arr,0,sizeof(arr));
		arr[0][0]=1;
		for (int i=1;i<=n;i++)
		for (int j=0;j<i;j++)
		for (int k=0;k<=s && k+(i-j)*(i-j-1)/2<=s;k++) if (arr[j][k])
			arr[i][k+(i-j)*(i-j-1)/2]=1;
		int flag=0;
		for (int i=1;i<n;i++) if (i*(i-1)/2+n-i-1<=s) if (arr[n-1-i][s-(i*(i-1)/2+n-i-1)]) flag=1;
		if (flag) return "Possible";else return "Impossible";
	}
};

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter