九度oj 王道论坛研究生机试练习赛第三场

首先是要靠你一步一步推出公式

假设半径为R，比例为f

S为圆的面积

q为切线交点和圆心的连线的角度的一半

然后可知切割后的一部分面积为x = （f*S）/（f+1）

然后R^2*q - R^2*sin(2*q)/2 = x

对于这条方程最主要就是求出q的值，但是~~我不会

所以我就用最简单的方法求：二分求值

然后ans = 2.0*R*sin(mid)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<math.h>

using namespace std;
#define pi 3.1415926
int main()
{
    int n,i,j;
    int sum;
    double R,f;
	while(~scanf("%lf%lf",&R,&f))
	{
		double S = R*R*pi;
		if(f>1.0)
		f = 1.0/f;
		double var = (f*S)/(f+1.0)/(R*R) ;
		double l = 0,r = pi/2.0,mid;
		while(1)
		{
			mid = (l+r)/2.0;
			if(mid-sin(2.0*mid)*0.5>var)
			r = mid;
			else
			l = mid;
			if(r-l<0.00000001)
			break;
		}
		
		printf("%0.2f\n",2.0*R*sin(mid));
	}
    return 0;
	
}

————————————————————————————————————————————————————————————

不过哥状态方程我也想了很久，丢脸！~~~

dp[i][j]表示第i个放男和女的个数（j为0是男，j为1是女）

然后很容易dp[i][0] = dp[i-1][0]+dp[i-1][1];

关键就是dp[i][1]这么表示

其实dp[i][1] = sum(dp[k][0])(k = 0~i-2)

其实意思就是最后一个放女的那倒数第二个就一定也是女的但是男的最后一个放在那里呢

就是枚举最后一个男的位置

把所有的情况都考虑了一遍

这个操作可以用单调队列来实现

最后时间复杂度就变成里O（n）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<math.h>
 
using namespace std;
#define MOD 1000000007
int dp[1005][3];
void Init()
{
    int i,j;
    memset(dp,0,sizeof(dp));
    dp[1][0] = 1;
    dp[1][1] = 0;
    dp[0][0] = 1;
    //dp[2][]
    int sum = 0;
    for(i=2;i<1003;i++)
    {
        dp[i][0] = (dp[i-1][0]+dp[i-1][1])%MOD;
        sum = (sum+dp[i-2][0])%MOD;
        dp[i][1]=(dp[i][1]+sum)%MOD;
        
    }
     
}
int main()
{
    int n,i,j;
    Init();
    while(~scanf("%d",&n))
    {   
        printf("%d\n",(dp[n][0]+dp[n][1])%MOD);
    }
    return 0;
     
}