TopCoder SRM 431 Summary

March 9, 2009 — gnarlycow

LaserShooting
简单概率题
显然本题中target并不阻挡射线，所以各个targe之间互不影响，那么射中个数的数学期望值就是射中各个targe的概率和。值得注意的是C++中求反正切arctan时最好用atan2(y,x)函数，因为它不仅能处理斜率不存在的情况还能正确处理角度符号。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
const double PI=3.1415926535;
 
class LaserShooting
{
public:
	double numberOfHits(vector <int> x, vector <int> y1, vector <int> y2)
	{
		int n=x.size();
		for(int i=0;i<n;++i)
			if(y1[i]>y2[i])
				swap(y1[i],y2[i]);
		double ans=0;
		for(int i=0;i<n;++i) ans+=(atan2(y2[i],x[i])-atan2(y1[i],x[i]))/PI;
		return ans;
	}
};

MegaCoolNumbers

动态规划
首先挖掘一下cool number of power A这个定义的本质：一个N位数如果是cool number of power A（A9时直接返回0，下面我们考虑A<=9的情况。采用动态规划，f[n][i][last][diff]表示所有n位数中最小power值为i且最后一个数字为last且最后一段的公差为diff的mega cool numbers个数（其中0<=diff<=8，用diff=9表示最后一组仅包含last这一个数字的情况，表示此时公差不确定），按照题意容易想出状态转移方法，这里不赘述。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <cmath>
#include <ctime>
#include <iostream>
#include <sstream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
const int MOD=1000000007;
int f[1001][10][10][10];
 
class MegaCoolNumbers
{
public:
	int count(int n,int A)
	{
		if(A>9) return 0;
		memset(f,0,sizeof(f));
		for(int i=1;i<10;++i) f[1][1][i][9]=1;
		for(int i=2;i<=n;++i)
			for(int j=1;j<10;++j)
				for(int last=1;last<10;++last)
				{
					for(int diff=0;diff<last;++diff) f[i][j][last][diff]=(f[i-1][j][last-diff][diff]+f[i-1][j][last-diff][9])%MOD;
					for(int prev=1;prev<=last;++prev)
						for(int diff=0;diff<9;++diff)
							if(diff!=last-prev)
								f[i][j][last][9]=(f[i][j][last][9]+f[i-1][j-1][prev][diff])%MOD;
				}
		int ans=0;
		for(int i=1;i<10;++i)
			for(int j=0;j<10;++j)
				ans=(ans+f[n][A][i][j])%MOD;
		return ans;
	}
};
Posted in SRM, TopCoder. Tags: , , . RSS feed for comments on this post.. TrackBack URL.

No Comments

1 Trackbacks

Leave a comment

«
»