Topcoder SRM 638 Div2 T3 CandleTimerEasy 题解

Topcoder Single Round Match 638 Div2 T3 CandleTimerEasy 题解 每天被 XY 题困扰的我们怎么会去做 Topcoder 呢

Translation

你有很多蜡烛，每条蜡烛看成一条边，则构成了一棵树。现在你要点燃所有蜡烛，有两个条件：

• 只能从树的叶节点开始点燃；
• 长度为 len[i] 的蜡烛完全燃烧需要 len[i] 的时间。如果从它的两边同时点燃，则只需要 len[i]/2 的时间。

问你以不同方式从叶节点点燃蜡烛，最后所有蜡烛燃烧完需要消耗的时间有多少种。

给出数据的方式是给你三个 vector：A、B 和 len，对于 i，节点 A[i] 与 B[i] 之间有一条长度为 len[i] 的蜡烛。 数据范围：$1 \leqslant e \leqslant 19$。

• A will contain between 1 and 19 elements, inclusive.
• A, B and len will contain same number of elements.
• Each element in A will be between 0 and |A|, inclusive.
• Each element in B will be between 0 and |A|, inclusive.
• Each element in len will be between 1 and 1000, inclusive.
• A, B and len will describe a tree.
• Time limit (s): 2.000
• Memory limit (MB): 256

Examples

样例零：

{0,1}
{1,2}
{10,1}

Returns: 2

这是一条链，可以看成一条长度为 11 的长蜡烛，从头、尾单独点燃时间 11，同时点燃时间 5.5，一共 2 种。

This tree looks the same as a single candle of length 11. If we light it on one end, we will measure the time 11. If we light it on both ends, we will measure the time 5.5.

样例一：

{0,0,0}
{1,2,3}
{1,1,1}

Returns: 2

这次有 3 个地方可以点燃。如果全部同时点燃，需要消耗 1 的时间，否则消耗 2。

This time we have 3 ends. If we ignite all of them the time is 1, otherwise the time is 2.

样例二：

{0,0,0}
{1,2,3}
{1,2,3}

Returns: 4

We can get 4 different outcomes: 2.5, 3, 4, 5.

Original

You have a lot of candles. The candles burn at a uniform rate: if you ignite a candle of length L, it will burn completely in L units of time. You can also ignite a candle at both ends, which makes it burn twice as fast. You have arranged some candles into the shape of a tree. You want to use the tree to measure time. At the beginning, you will ingite some leaves of the tree (all at the same time). Then you will just wait and watch the flames spread across the entire tree. (Whenever a flame reaches an inner node of the tree, it spreads to all branches that meet at that node.) Note that you are not allowed to light new flames during the process. The time you will measure is the time between the moment when you lighted the fire(s) and the moment when the last part of the tree finished burning. You are given a description of the tree as three vector s: a, b, and len, with N elements each. The nodes of the tree are numbered 0 through N, inclusive. For each valid i, there is a candle between the nodes a[i] and b[i] with length len[i]. Compute and return the number of different times you can measure when following the above procedure.

因为数据非常非常非常小，可以考虑暴枚。暴力枚举每个叶节点点燃或不点燃，则复杂度是 $\Theta (2^{f})$（f 代表叶节点数量）。接下来考虑的就是根据某个叶节点的点集来算出燃烧时间。

因为数据非常非常非常小，可以先直接来一趟 Floyd 算出两两叶节点之间蜡烛长度。假设 t[i] 表示烧到第 i 个节点的最早时间，那么接下来：对所有非点燃处，寻找离它最近的点燃处，两者之间距离即是烧到这个点的最早时间；对所有点燃处，t[i]=0。 但是这不够。你以为处理所有“点燃处”时间的最大值 max(t[i]) 就是当前答案吗？其实即使考虑完所有的点，仍然会有些边没有被考虑到。我们要再枚举所有的边，这时候每条边两个端点的最早烧到的时间都已经得出，我们只需要考虑根据这个算出这条边烧完的时间。 如何根据这条边两个端点 $A_i$ 和 $B_i$ 最早被烧到的时间，算出这条边被烧完的时间？两个端点的最早烧到时间可以看成有先后顺序的，那么分为两种情况：

• 两端点中先烧到的一个，直接把整根蜡烛烧掉了，另一端的小火苗根本没有机会，则时间是：$min(t_{A_i},t_{B_i})+len_i$；

• 两端点中一个先开始烧这根蜡烛，烧了一会儿另外一端开始烧。那么较晚的一端开始烧的时候，剩下蜡烛长度是：$len_i-|t_{A_i}-t_{B_i}|$，这段只需要一半的时间；其余的一段则是需要完整的时间。烧完这根蜡烛总时间就是：max(t[A[i]],t[B[i]])+(len[i]-Abs(t[A[i]]-t[B[i]]))/2.0)。

因为数据非常非常非常小，而且时限 2s，即使上述方法 $\Theta (f^2\ast 2^f)$ 完成，也不会超时……

Codes

#include <bits/stdc++.h>
#define CLEAR(x) memset(x,0,sizeof(x))
#define CLEAR_MAX(x) memset(x,63,sizeof(x))
using namespace std;
const int maxn=25,INF=1e8;
int n,s,ind[maxn];
int dst[maxn][maxn];
double t[maxn];
vector <double> vec;

class CandleTimerEasy {
public:
    int differentTime( vector <int> A, vector <int> B, vector <int> len );
};
inline void init(){
	vec.clear();CLEAR(ind);CLEAR_MAX(dst);
}
inline void Floyd(){
	for (int i=0;i<n;i++) dst[i][i]=0;
	for (int k=0;k<n;k++)
	for (int i=0;i<n;i++) if (i!=k)
	for (int j=0;j<n;j++) if ((j!=k)&&(j!=i))
		dst[i][j]=dst[j][i]=min(dst[i][j],dst[i][k]+dst[k][j]);
}
inline double Abs(double x) {return x<0?-x:x;}
inline double Get(int x,vector <int> A, vector <int> B, vector <int> len){
	double ret=0.0;
	for (int i=0;i<n;i++) if ((ind[i]==1)&&(x&(1<<i))) t[i]=0; else {
		t[i]=(double)INF;
		for (int j=0;j<n;j++) if ((ind[j]==1)&&(x&(1<<j))&&(i!=j)) t[i]=min(t[i],(double)dst[i][j]);
		ret=max(ret,t[i]);
	}
	for (int i=0;i<n-1;i++) ret=max(ret,min(min(t[A[i]],t[B[i]])+len[i],max(t[A[i]],t[B[i]])+(len[i]-Abs(t[A[i]]-t[B[i]]))/2.0));
	return ret;
}
int CandleTimerEasy::differentTime(vector <int> A, vector <int> B, vector <int> len) {
    init();
	n=A.size()+1;s=1<<n;
	for (int i=0;i<n-1;i++){
		dst[A[i]][B[i]]=dst[B[i]][A[i]]=len[i];
		ind[A[i]]++;ind[B[i]]++;
	}
	Floyd();
	for (int i=1;i<s;i++) vec.push_back(Get(i,A,B,len));
	sort(vec.begin(),vec.end());
	int ans=0;
	// for (int i=0;i<vec.size();i++) printf("ANS: %.3lf\n",vec[i]);
	for (int i=0;i<vec.size();i++) if (((i==0)||(vec[i]!=vec[i-1]))&&(vec[i]>0)&&(vec[i]<INF)) ans++;//,printf("%.2f\n",vec[i]);
	return ans;
}