闲扯

今天的 $T1$ 想的太复杂了，结果直接暴毙。

$T2,T3$ 由于去体检，没时间写，只打了两个最简单的暴力上去。。

还有 $OI$ 中可能用到的数学知识，我觉得应该补一下？（感觉没时间了啊） $T2$ 的用叉积求面积我是真的服，没见过，乘热学了一下。

题面

$T1$

Solution

我们如果考虑小 $Y$ 怎么赢可能有点过于复杂了，所以我们考虑小 $D$ 的必胜策略。

我们设 $f_u$ 表示考虑以 $u$ 为根结点的子树中，小 $D$ 需要额外的几次操作才能赢。

显然，对于叶子节点，我们有 $f_u=1$ 。

那么对于非叶节点，我们有 $f_u=\min(\sum f_v-1,0)$ 。

表示所有的子树都需要满足，但是由于当前节点可以先走一步，所以需要的额外次数减少 $1$ 。

那么最后小 $D$ 能获胜的条件是 $f_1=0$ 。

Code

#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 1e5+5;
int n,fa[MAXN],f[MAXN];
vector<int> G[MAXN];
il DFS(int u){
	if(!G[u].size()) return f[u]=1,void();
	for(ri i=0;i<(int)G[u].size();++i)
		DFS(G[u][i]),f[u]+=f[G[u][i]];
	if(f[u]) --f[u];
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);
	for(ri i=2;i<=n;++i) read(fa[i]),G[fa[i]].push_back(i);
	DFS(1);
	if(f[1]) puts("Y");
	else puts("D");
	return 0;
}

$T2$

Solution

如果直接计算每一个可能的情况的面积，显然不好算，我们考虑计算每一块被删除的期望。

我们假定在 $[l,r]$ 之间的端点，除了 $l,r$ 都没选，那么这一块被删除的概率就为 $P=\frac{C_{n-(r-l+1)}^{k-2}}{C_n^k}$ ，那么相应的，我们要在答案中减去 $S\cdot P$ 。

对于 $l,r$ 我们可以 $O(n^2)$ 枚举，这样我们就只需要算出每一块的面积即可。

这里介绍一种计算面积的方法：向量叉积。

我们假定一个 $n$ 边形，它的定点按照顺时针排序依次为 $P_1,P_2,\cdots,P_n$ 。

那么它的面积就为 $\sum_{i=1}^{n-1}\vec{OP_{i+1}}\times\vec{OP_i}+\vec{OP_1}\times\vec{OP_n}$ 。

其中 $\vec{a}\times\vec{b}$ 表示向量叉积。

对于 $\vec{a}=(a_x,a_y),\vec{b}=(b_x,b_y)$ ，我们有 $\vec{a}\times\vec{b}=a_xb_y-a_yb_x$ 。

然后这道题就可以 $O(n^2)$ 做出来了。

Code

#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define ld long double
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 25e2+2;
int n,k;
ld ans,sum,C[MAXN][MAXN];//C(n,m)
struct Node{
	ld x,y;
}node[MAXN];
il init(){
	for(ri i=0;i<=n;++i) C[i][0]=1;
	for(ri i=1;i<=n;++i)
		for(ri j=1;j<=i;++j)
			C[i][j]=C[i-1][j-1]+C[i-1][j];
}
ld calc(int x,int y){return node[x].x*node[y].y-node[x].y*node[y].x;}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(k),init();
	for(ri i=1;i<=n;++i)
		scanf("%Lf%Lf",&node[i].x,&node[i].y);
	for(ri i=2;i<=n;++i) ans+=calc(i,i-1);
	ans+=calc(1,n);sum=ans;
	for(ri i=1;i<n;++i){
		ld area=0;
		for(ri j=i+1;j<=n;++j){
			area+=calc(j,j-1);
			ans-=(area+calc(i,j))*C[n-(j-i+1)][k-2]/C[n][k];
			ans-=(sum-area-calc(i,j))*C[j-i-1][k-2]/C[n][k];
		}
	}
	ans=ans/2.;
	printf("%.7Lf",ans);
	return 0;
}