发表于 | 更新于

Link

Solution

旋转卡壳

Tips

旋转卡壳 刚开始要用第二个点卡第一条边

Code

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//Code by Lucida
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::sort;
using std::swap;
using std::unique;
const int MAXN=50000+1;
typedef double ld;
const ld eps=1e-7;
int fcmp(ld x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
template <class T> T sqr(T a){return a*a;}
template <class T> T abs(T a){return a>0?a:-a;}
struct vec
{
	ld x,y;
	vec(ld _x=0,ld _y=0):x(_x),y(_y){}
	bool operator <(const vec &a) const
	{
		if(x!=a.x) return x<a.x;
		return y<a.y;
	}
	void operator +=(vec a){x+=a.x,y+=a.y;}
	void operator -=(vec a){x-=a.x,y-=a.y;}
	bool operator ==(const vec &a) const{return x==a.x && y==a.y;}
	ld norm(){return sqrt(x*x+y*y);}
};
typedef vec point;
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator *(vec a,ld t){return vec(a.x*t,a.y*t);}
vec operator /(vec a,ld t){return vec(a.x/t,a.y/t);}
ld inner(vec a,vec b){return a.x*b.x+a.y*b.y;}
ld outer(vec a,vec b){return a.x*b.y-a.y*b.x;}
struct line
{
	point a;vec v;
	line(point _a,vec _v):a(_a),v(_v){}
};
bool cmp(vec a,vec b)
{
	if(fcmp(outer(a,b))!=0)
		return fcmp(outer(a,b))>0;
	return inner(a,a)<inner(b,b);
}
void Graham(point *p,int n,point *stack,int &top)
{
	top=0;
	int mi=1;
	for(int i=1;i<=n;i++) if(p[i]<p[mi]) mi=i;
	swap(p[1],p[mi]),p[0]=p[1];
	for(int i=1;i<=n;i++) p[i]-=p[0];
	sort(p+2,p+1+n,cmp);
	n=unique(p+1,p+1+n)-p-1;
	p[n+1]=p[1];
	for(int i=1;i<=n+1;i++) p[i]+=p[0];
	for(int i=1;i<=n+1;i++)
	{
		while(top>=2 && fcmp(outer(p[i]-stack[top],stack[top]-stack[top-1]))>=0) top--;
		stack[++top]=p[i];
	}
	top--;
}
ld dist(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
ld dist(point a,line l){return abs(outer(a-l.a,l.v))/l.v.norm();}
ld dist2(point a,point b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
int main()
{
	freopen("input","r",stdin);
	static point p[MAXN],hull[MAXN];
	int n,nb;red(n);
	for(int i=1;i<=n;i++) fred(p[i].x),fred(p[i].y);
	Graham(p,nb=n,hull,n);
	ld ANS=0;
	if(n==1)
	{
		n=nb;
		sort(p+1,p+1+n);
		ANS=dist2(p[1],p[n]);
	}
	else
	{
		#define suc(i) (i+1>n?1:i+1)
		for(int i=1,cur=2;i<=n;i++)
		{
			line now(hull[i],hull[suc(i)]-hull[i]);
			while(fcmp(dist(hull[cur],now)-dist(hull[suc(cur)],now))<0) 
				cur=suc(cur);
			chkmx(ANS,dist2(hull[i],hull[cur]));
			chkmx(ANS,dist2(hull[suc(i)],hull[cur]));
		}
		#undef suc
	}
	printf("%.0f\n",ANS);
	return 0;
}

发表于 | 更新于

Link

Solution

把多边形画出来，求出凸包。在凸包的角上分别作两边的垂线，所夹角=该角的外角。 外角和=360°，因此答案为凸包的长度加一个圆的周长。

Code

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//Code by Lucida
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef double ld;
using std::sort;
using std::unique;
using std::swap;
const ld pi=acos(-1.0);
const int MAXN=1000+10;
template <class T> inline T sqr(T x){return x*x;}
template <class T> inline T abs(T x){return x>0?x:-x;}
struct vec
{
	int x,y;
	vec(int _x=0,int _y=0):x(_x),y(_y){}
	bool operator <(const vec &a) const
	{
		if(x*a.y-y*a.x!=0)
			return x*a.y-y*a.x>0;
		return x*x+y*y<a.x*a.x+a.y*a.y;
	}
	bool operator ==(const vec &a) const{return x==a.x && y==a.y;}
	void operator -=(vec a){x-=a.x,y-=a.y;}
	void operator +=(vec a){x+=a.x,y+=a.y;}
};
typedef vec point;
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
int outer(vec a,vec b){return a.x*b.y-b.x*a.y;}
ld dist(point A,point B){return sqrt((double)sqr(A.x-B.x)+sqr(A.y-B.y));}
point p[MAXN],stack[MAXN];
int main()
{
	freopen("input","r",stdin);
	int top=0;
	int n,L;red(n),red(L);
	int mi=1;
	for(int i=1;i<=n;i++) 
	{
		red(p[i].x),red(p[i].y);
		if((p[i].x<p[mi].x) || (p[i].x==p[mi].x && p[i].y<p[mi].y)) mi=i;
	}
	swap(p[1],p[mi]);p[0]=p[1];
	for(int i=1;i<=n;i++) p[i]-=p[0];//p[1]。。。De了1h。。。。。。。
	sort(p+2,p+1+n);
	p[n+1]=p[1];
	for(int i=1;i<=n+1;i++)
	{
		while(top>=2 && outer(p[i]-stack[top],stack[top]-stack[top-1])>=0) top--;
		stack[++top]=p[i];
	}
	ld ANS=dist(stack[1],stack[top])+2*L*pi;
	for(int i=1;i<top;i++) ANS+=dist(stack[i],stack[i+1]);
	printf("%.0f\n",ANS);
	return 0;
}

发表于 | 更新于

Link

Solution

简单的枚举

Code

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//Code by Lucida
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=30+10;
typedef double ld;
const ld eps=1e-10;
using std::vector;
int fcmp(ld x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
template <class T> inline T sqr(T a){return a*a;}
template <class T> inline T abs(T x){return x>0?x:-x;}
struct vec
{
	ld x,y;
	vec(ld _x=0,ld _y=0):x(_x),y(_y){}
};
typedef vec point;
typedef vector<point> poly;
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator *(vec a,ld b){return vec(a.x*b,a.y*b);}
vec operator /(vec a,ld b){return vec(a.x/b,a.y/b);}
ld inner(vec a,vec b){return a.x*b.x+a.y*b.y;}
ld outer(vec a,vec b){return a.x*b.y-a.y*b.x;}
/*ld size(const poly& p)
{
	ld res=0;
	int n=p.size();
	for(int i=0;i<n;i++)
		res+=outer(p[i]-p[0],p[(i+1)%n]-p[0]);
	assert(res>=0);
	return res/2;
}*/
ld size(point A,point B,point C,point D){return (abs(outer(B-A,C-A))+abs(outer(C-A,D-A)))/2;}
struct line
{
	point A;vec v;
	line(point _A,vec _v):A(_A),v(_v){}
};
point cross(line l,line r)
{
	vec v=l.A-r.A;
	ld t=outer(v,r.v)/outer(r.v,l.v);
	return l.A+l.v*t;
}
void WORK(int n)
{
	static ld a[MAXN],b[MAXN],c[MAXN],d[MAXN];
	static point mat[MAXN][MAXN];
	for(int i=1;i<=n;i++) fred(a[i]);
	for(int i=1;i<=n;i++) fred(b[i]);
	for(int i=1;i<=n;i++) fred(c[i]);
	for(int i=1;i<=n;i++) fred(d[i]);
	a[n+1]=b[n+1]=c[n+1]=d[n+1]=1;
	for(int hor=0;hor<=n+1;hor++)
	{
		line ho=line(point(0,c[hor]),point(1,d[hor])-point(0,c[hor]));
		for(int ver=0;ver<=n+1;ver++)
		{
			line ve=line(point(a[ver],0),point(b[ver],1)-point(a[ver],0));
			mat[hor][ver]=cross(ho,ve);
		}
	}
	ld ANS=-1;
	for(int hor=0;hor<=n;hor++)
		for(int ver=0;ver<=n;ver++)
			chkmx(ANS,size(mat[hor][ver],mat[hor+1][ver],mat[hor+1][ver+1],mat[hor][ver+1]));
	printf("%.6f\n",ANS);
}
int main()
{
	freopen("input","r",stdin);	
	int n;while(red(n) && n) WORK(n);	
	return 0;
}

发表于 | 更新于

Link

Solution

用叉积判转向判凸多边形 然后是点到直线的距离 和判点在多边形内

Code

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//Code by Lucida
#include<cstdio>
#include<algorithm>
#include<cmath>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef double ld;
const ld eps=1e-10;
const int MAXN=1e5;
const char ILL[]="HOLE IS ILL-FORMED",
		   FIT[]="PEG WILL FIT",
		   NOTFIT[]="PEG WILL NOT FIT";
int fcmp(ld x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
template <class T> T sqr(T x){return x*x;}
template <class T> T abs(T x){return x>0?x:-x;}
struct vec
{
	ld x,y;
	vec(ld _x=0,ld _y=0):x(_x),y(_y){}
	vec operator -(){return vec(x,y);}
	ld norm(){return sqrt(x*x+y*y);}
};
typedef vec point;
vec operator +(vec u,vec v){return vec(u.x+v.x,u.y+v.y);}
vec operator -(vec u,vec v){return vec(u.x-v.x,u.y-v.y);}
vec operator *(vec u,ld t){return vec(u.x*t,u.y*t);}
vec operator /(vec u,ld t){return vec(u.x/t,u.y/t);}
ld outer(vec u,vec v){return u.x*v.y-u.y*v.x;}
ld inner(vec u,vec v){return u.x*v.x+u.y*v.y;}
struct line
{
	point A;vec v;
	line(point _A,vec _v):A(_A),v(_v){}
};
ld dist(point A,line l)
{
	vec AB=l.A-A,BC=l.v;
	return abs(outer(AB,BC))/BC.norm();
}
struct circle
{
	point O;ld r;
	circle(point _O,ld _r):O(_O),r(_r){}
	
};
bool parl(vec u,vec v){return fcmp(outer(u,v))==0;}
bool on(point A,line l){return parl(A-l.A,l.v);}
int relation(circle C,line l)
{
	ld d=dist(C.O,l);
	return fcmp(d-C.r);
}
int relation(point A,point *p,int n)
{
	#define suc(i) (i+1>n ?1:i+1)
	int wn=0;
	for(int i=1;i<=n;i++)
	{
		if(on(A,line(p[i],p[suc(i)]-p[i]))) return 0;
		if(fcmp(outer(A-p[i],p[suc(i)]-p[i]))>0 && fcmp(A.y-p[i].y)>=0 && fcmp(A.y-p[suc(i)].y)<0) wn++;
		if(fcmp(outer(A-p[i],p[suc(i)]-p[i]))<0 && fcmp(A.y-p[i].y)<0 && fcmp(A.y-p[suc(i)].y)>=0) wn--;
	}
	return wn==0?1:-1;
	#undef suc
}
const char *WORK(int n)
{
	ld r,x,y;fred(r),fred(x),fred(y);
	circle C=circle(point(x,y),r);
	static point p[MAXN];
	for(int i=1;i<=n;i++) fred(p[i].x),fred(p[i].y);
	#define pre(i) (i-1==0?n:i-1)
	#define suc(i) (i+1>n ?1:i+1)
	int dir;
	for(int i=1;i<=n;i++)
	{
		dir=fcmp(outer(p[i]-p[pre(i)],p[suc(i)]-p[i]));
		if(dir) break;
		else if(i==n) return ILL;
	}
	for(int i=2;i<=n;i++)
		if(dir*fcmp(outer(p[i]-p[pre(i)],p[suc(i)]-p[i]))<0) return ILL;
	if(relation(C.O,p,n)>0) return NOTFIT;
	for(int i=1;i<=n;i++)
		if(relation(C,line(p[i],p[suc(i)]-p[i]))<0) return NOTFIT;
	return FIT;
	#undef pre
	#undef suc
}
int main()
{
	freopen("input","r",stdin);
	int n;
	while(red(n) && n>=3)
		printf("%s\n",WORK(n));
	return 0;
}

发表于 | 更新于

Link

Solution

受期望的影响，我设计出状态f[i][v][l]f[i][v][l]表示从第ii个开始处理，有剩余空间vv，还需完成ll个任务，能做到的概率。 显然，从后往前DP，f[i][v][l]=p[i]×f[i+1][v+a[i]][l+1]+(1−p[i])×f[i+1][v][l]f[i][v][l]=p[i]\times f[i+1][v+a[i]][l+1]+(1-p[i])\times f[i+1][v][l]。 然后发现DP出的结果上天了——远远超过1。。。 仔细思考，我的边界设置的是所有f[n][v][0]=1f[n][v][0]=1，其实是包含了很多不合法状态的。 我的答案来自∑v+vinit>0f[1][v][0]\sum_{v+v_{init}>0}f[1][v][0]，就是有很多是从不合法的状态转移过来的。 于是Orz Po姐。 从前往后DP。解决。

Tips

一定要从合法状态开始推啊！

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=200+1;
int main()
{
	static double f[MAXN][MAXN<<1][MAXN],p[MAXN];
	static int a[MAXN];
	//freopen("input","r",stdin);
	int n,lim,iv;red(n),red(lim),red(iv);
	for(int i=1;i<=n;i++) scanf("%lf",&p[i]),p[i]/=(double)100;
	for(int i=1;i<=n;i++) red(a[i]);
	#define conv(x) ( x<-n? 0 : (x>n ? 2*n : x+n ) )
	double ANS=0;
	f[0][conv(iv)][0]=1;
	for(int i=1;i<=n;i++)
		for(int v=-n;v<=n;v++)
			for(int l=0;l<=n;l++)
			{
				f[i][conv(v+a[i])][l+1]+=p[i]*f[i-1][conv(v)][l];
				f[i][conv(v)][l]+=(1-p[i])*f[i-1][conv(v)][l];
			}
	for(int v=0;v<=n;v++)
		for(int l=lim;l<=n;l++)
			ANS+=f[n][conv(v)][l];
	printf("%.6lf\n",ANS);
	return 0;
}

发表于 | 更新于

Link

Solution

要求立方和的期望值。 考虑一个新的1对于答案的贡献。 假设前面已经有x个1了 (x+1)3=x3+3x2+3x+1(x+1)^3=x^3+3x^2+3x+1 即，对于期望已经存在xx个1的连续子串，加入一个1对答案的贡献为 Δ=3x2+3x+1\Delta=3x^2+3x+1 所以，需要维护一个x2x^2的期望和一个xx的期望。 而x2x^2的期望也类似。

Tips

E(xn)≠E(x)nE(x^n)\neq E(x)^n，因此要维护一个高次项的期望可以通过多项式展开转化成维护低次式的期望再相加。根据期望的线性性，这样做是正确的。

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100000+1;
typedef long double ld;
int main()
{
	//freopen("input","r",stdin);
	static ld f[MAXN],exsq[MAXN],ex[MAXN];
	//f表示答案 exsq表示连续x^2的EXP ex表示连续x的exp
	int n;red(n);
	double cur;scanf("%lf",&cur);
	exsq[1]=ex[1]=f[1]=cur;
	for(int i=2;i<=n;i++)
	{
		scanf("%lf",&cur);
		//ex[i]=ex[i-1]+cur;
		ex[i]=cur*(ex[i-1]+1);
		//exsq[i]=exsq[i-1]+cur*(2*ex[i]+1);
		exsq[i]=cur*(exsq[i-1]+2*ex[i-1]+1);
		//f[i]=f[i-1]+cur*(3*exsq[i]+3*ex[i]+1);
		f[i]=f[i-1]+cur*(3*exsq[i-1]+3*ex[i-1]+1);
	}
	printf("%.1lf\n",(double)f[n]);
	return 0;
}

发表于 | 更新于

Link

Solution

一开始naive的认为，可以用一遍递推，求出翻到第i张牌，R或者B的期望剩余张数，就可以算出概率了。。 但是怎么想怎么玄，一写果然WA了。 后来想想，期望除了线性性之外好像没有什么好用的性质。我这样用期望算概率，里面有期望除期望，难免有种钦定的感觉。 没什么办法，去看题解。

考虑用f[i][j]表示剩下i张红牌，j张黑牌时的最大期望。 当i=0时，f[i][j]=0; 当j=0时，f[i][j]=i; 其他情况，f[i][j]=max(0,i/(i+j) (f[i-1][j]+1)+j/(i+j) (f[i][j-1]-1)). 于是滚动一下qwq。 ——fqk

好像。。不是很难的样子。。学习了。 发现期望DP有一个特点就是，设计出状态的转移必须符合期望的定义形式（或许是我做题太少？），而概率DP就不一样。 upd:如果期望累加的话也可以不用，但这样的最优期望是必须的。

AND，像期望出现在分母里的这种事就算了吧

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=5000+1;
typedef long double ld;
const ld INF=1e100;
using std::max;
ld P(ld a,ld b){return a/b;}
int main()
{
	//freopen("input","r",stdin);
	static ld f[2][MAXN];
	int R,B;red(R),red(B);
	//f[r][b] 用完r b张牌的时候的期望
	//不行。前面的依赖后面的
	//./
	// \
	// 这样分叉，必须从后往前走，从前往后算不了
	// f[r][b] 还剩r b张牌时候的期望
	for(int r=0;r<=R;r++)
		for(int b=0;b<=B;b++)
		{
			if(!r) f[r&1][b]=0;
			else if(!b) f[r&1][b]=r;
			else f[r&1][b]=max((ld)0,P(r,r+b)*(1+f[r&1^1][b])+P(b,r+b)*(-1+f[r&1][b-1]));
		}
	printf("%.6lf\n",(double)(f[R&1][B]-5e-7));
	return 0;
}

发表于 | 更新于

Link 吃了期望的亏，回来怼期望。 一个随机变量，存在v→+∞v\rightarrow +\infty，但此时P→0P\rightarrow 0，这个变量的期望不会是∞\infty 期望是线性函数，E[aX+bY]=aE[X]+bE[Y]E[aX+bY]=aE[X]+bE[Y] 求一条边的期望值可以转化为求点的

CODE

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
const int INF=522133279,MAXN=500+1,MAXM=MAXN*MAXN;
typedef long double ld;
typedef ld Matrix[MAXN][MAXN];
const ld eps=1e-10;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::max;
using std::min;
using std::swap;
using std::sort;
using std::greater;
using std::cout;
using std::endl;
template <class T> struct List
{
	List<T> *pre;
	T val;
	List(List<T> *_pre=0,T _val=0):pre(_pre),val(_val){}
};
List<int> *ME=new List<int>[MAXM<<1],*G[MAXN];
inline void Add(List<int> *&cur,int val)
{
	cur=new (ME++)List<int>(cur,val);
}
int deg[MAXN];
ld E[MAXN];
inline int fcmp(const ld& x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
template <class T> inline void swap_n(T *a,T *b,int n)
{
	for(int i=1;i<=n;i++) swap(a[i],b[i]);
}
void Gauss(Matrix &A,int n)
{
	for(int i=1;i<=n;i++)
	{
		int mx=i;
		for(int j=i+1;j<=n;j++)
			if(fcmp(fabs(A[j][i])-fabs(A[mx][i]))>0) mx=j;
		if(mx!=i) swap_n(A[i],A[mx],n+1);
		for(int j=i+1;j<=n;j++)
		{
			ld f=A[j][i]/A[i][i];
			for(int k=1;k<=n+1;k++) A[j][k]-=f*A[i][k];
		}
	}
	for(int i=n;i;i--)
	{
		for(int j=i+1;j<=n;j++) A[i][n+1]-=A[i][j]*A[j][n+1];
		A[i][n+1]/=A[i][i];
	}
}
int main()
{
	static Matrix A;
	static ld exp[MAXM];int cexp=0;
	freopen("input","r",stdin);
	int t1,t2,t3,n,m;red(n),red(m);
	for(int i=1;i<=m;i++)
	{
		red(t1),red(t2);
		Add(G[t1],t2);
		Add(G[t2],t1);
		deg[t1]++,deg[t2]++;
	}
	//只有第E[1\N]存在常数项，为1
	for(int i=1;i<n;i++)
	{
		A[i][i]=1;
		for(List<int> *it=G[i];it;it=it->pre)
		{
			int u=it->val;
			if(u==n) continue;
			A[i][u]=(ld)(-1.0/deg[u]);
		}
	}
	A[1][n+1]=A[n][n+1]=A[n][n]=1;
	Gauss(A,n);
	for(int i=1;i<=n;i++) E[i]=A[i][n+1];
	for(int pos=1;pos<=n;pos++)
		for(List<int> *it=G[pos];it;it=it->pre)
		{
			int u=it->val;
			if(pos>u) continue;

			exp[++cexp]=E[pos]/deg[pos];
			if(u!=n)
				exp[cexp]+=E[u]/deg[u];//..

		}
	sort(exp+1,exp+cexp+1,greater<ld>());
	ld ANS=0;
	for(int i=1;i<=m;i++)
		ANS+=exp[i]*i;
	printf("%.3lf\n",(double)ANS);
	return 0;
}

发表于 | 更新于

题目链接

看数据范围是状压，看平均情况是期望，然后就开始了混乱的求索。

f[i][S]f[i][S]是比较显然的，但是发现边界情况无法处理啊。在不可达的状态设置INF？那还怎么累加期望啊。

无奈。看题解。发现一个很神奇的trick——倒着DP。

那么状态f[i][S]f[i][S]表示，从状态[i][S][i][S]开始算，算到最后答案是多少。目标是f[1][0]f[1][0]。

倒推是有效从有效推来，无效随便，因为答案就是一个有效状态；而顺推则可能从无效推到有效。——hzwer

似乎对期望的理解又深了一些。

以后状态转移像一棵树一样的DP，可以试试从叶到根计算，有奇效（见SDOI走迷宫一题）

CODE

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
typedef long double ld;
using std::max;
const int MAXN=100+1,MAXK=15+1,MAXS=1<<MAXK;
const ld INF=1e100;
int main()
{
	freopen("input","r",stdin);
	static ld f[MAXN][MAXS];
	static int de[MAXK],va[MAXK];
	int t1,t2,t3,n,objc;red(n),red(objc);
	for(int i=1;i<=objc;i++)
	{
		red(va[i]);
		while(red(t1) && t1)
			de[i]|=(1<<t1>>1);
	}
	int S=(1<<objc)-1;
	for(int i=n;i;i--)
		for(int s=0;s<=S;s++)
			for(int cur=1;cur<=objc;cur++)
				f[i][s]+=max(f[i+1][s],((de[cur]&s)==de[cur]?f[i+1][s|(1<<cur>>1)]+va[cur]:-INF))/objc;
	printf("%.6lf\n",(double)f[1][0]);
	return 0;
}

发表于 | 更新于

新课学完了，回到微机室开始OI生活。首先当然要把NOIP的题目都A掉。 做完之后才感觉到，这一届NOIP虽然槽点很多，但是题目的质量还是很不错的，解法优美，没有码农题。

Toy

膜拟。 

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#define red(x) scanf("%d",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::max;
using std::min;
const int MAXN=1e5+10;
int stat[MAXN];//0 内 1  外 
char nam[MAXN][20];
int main()
{
	int n,m;red(n),red(m);
	for(int i=1;i<=n;i++)
	{
		red(stat[i]);
		scanf("%s",nam[i]);
	}
	int cur=1,opt,cnt;
	for(int i=1;i<=m;i++)//opt==0 left opt==1 right
	{
		red(opt),red(cnt);
		opt^=stat[cur];
		if(opt==0) cnt*=-1;
		(((cur+=cnt)%=n)+=n)%=n;
		//cur+=cnt;if(cur<=0) cur+=n;
		if(!cur) cur=n;
	}
	printf("%s\n",nam[cur]);
	return 0;
}

Running

对于链，很容易想到使用双指针，扫一遍统计。 想想使用双指针的原因，无非是因为一些runner虽然到某个点ii的距离是wiw_i，但是在此之前就已经走到了终点，要排除这些runner的影响。 由此可以想到，一个runner能起作用的区间只是这个runner的起点到终点，由此可以看出差分的影子。这样，又得出一个不用双指针的在链上的做法：在区间l处+1,r+1处-1，就可以直接统计了。 做法搬到树上，基本差不多。从lca拆成两条链，这样深度是连续的，可以套用链的做法。 一点trick是，统计子树的答案，只需要统计出子树和进子树的答案差。这个还是第一次见。 

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T>
inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T>
inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::swap;
using std::make_pair;
using std::pair;
const int MAXN=3e5;
template <class T> struct List
{
	List<T> *pre;
	T val;
	List(List<T> *_pre,T _val):pre(_pre),val(_val){}
};
template <class T> inline void Add(List<T> *&cur,T val)
{
	cur=new List<T>(cur,val);
}
inline void *operator new(size_t sz)
{
	static const size_t SIZE=536870912;
	static char *ME=(char *)malloc(SIZE),*cur;
	return cur=ME,ME+=sz,(void *)cur;
}
inline void operator delete(void *p){}

List<int> *G[MAXN];
List<pair<int,int> > *mrk1[MAXN],*mrk2[MAXN],*query[MAXN];
struct FUS
{
	int fa[MAXN];
	int Root(int x){return fa[x]?fa[x]=Root(fa[x]):x;}
	void Union(int x,int y)//x为父节点
	{
		x=Root(x),y=Root(y);
		fa[y]=x;
	}
}S;
int qlca[MAXN],dep[MAXN],w[MAXN];
void DFS(int pos)
{
	for(List<int> *it=G[pos];it;it=it->pre)
	{	
		int u=it->val;if(dep[u]) continue;
		dep[u]=dep[pos]+1;
		DFS(u);
		S.Union(pos,u);
	}
	for(List<pair<int,int> > *it=query[pos];it;it=it->pre)
	{
		int u=it->val.first;
		if(dep[u]) qlca[it->val.second]=S.Root(u);
	}
}
int cnt1[MAXN<<1],__cnt2[MAXN<<1],*cnt2=__cnt2+MAXN,ANS[MAXN];
bool ud[MAXN];
void Calc(int pos)
{
	ud[pos]=1;
	ANS[pos]-=cnt1[w[pos]+dep[pos]]+cnt2[w[pos]-dep[pos]];
	for(List<pair<int,int> > *it=mrk1[pos];it;it=it->pre)
		cnt1[it->val.first]+=it->val.second;
	for(List<pair<int,int> > *it=mrk2[pos];it;it=it->pre)
		cnt2[it->val.first]+=it->val.second;
	for(List<int> *it=G[pos];it;it=it->pre)	
		if(!ud[it->val]) Calc(it->val);	
	ANS[pos]+=cnt1[w[pos]+dep[pos]]+cnt2[w[pos]-dep[pos]];
}
int main()
{
	static struct Opt{int s,t;}opt[MAXN];
	int n,Q,t1,t2;red(n),red(Q);
	for(int i=1;i<=n-1;i++)
	{
		red(t1),red(t2);
		Add(G[t1],t2);Add(G[t2],t1);
	}
	for(int i=1;i<=n;i++)
		red(w[i]);
	for(int i=1;i<=Q;i++)
	{
		red(opt[i].s),red(opt[i].t);
		Add(query[opt[i].s],make_pair(opt[i].t,i));
		Add(query[opt[i].t],make_pair(opt[i].s,i));
	}
	dep[1]=1;DFS(1);
	for(int i=1;i<=Q;i++)
	{
		int lca=qlca[i],s=opt[i].s,t=opt[i].t;
		Add(mrk1[lca],make_pair(t1=dep[s],-1));
		Add(mrk1[s],make_pair(t1,1));
		Add(mrk2[lca],make_pair(t1=dep[s]-dep[lca]*2,-1));
		Add(mrk2[t],make_pair(t1,1));
		if(dep[s]-dep[lca]==w[lca]) ANS[lca]++;
	}
	Calc(1);
	for(int i=1;i<=n;i++)
		printf("%d%s",ANS[i],i==n?"\n":" ");
	return 0;
}

Classroom

在考场上想到的就是正解。但是因为不熟悉期望的性质怕有问题不敢写。 

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define dred(x) scanf("%lf",&x)
#define ldred(x) scanf("%Lf",&x)
template <class T>
inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T>
inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long double ld;
using std::min;
using std::max;
const int MAXC=2000+1,MAXN=300+1,INF=522133279;
inline ld E(ld rate,ld v1,ld v2){return rate*v1+(1-rate)*v2;}
int main()
{
	static int loc[MAXC][2],sp[MAXN][MAXN];
	static ld rate[MAXC],f[MAXC][MAXC][2];
	//freopen("input","r",stdin);
	memset(sp,31,sizeof(sp));
	int cac,lim,n,m;red(cac),red(lim),red(n),red(m);
	for(int i=1;i<=cac;i++) red(loc[i][0]);
	for(int i=1;i<=cac;i++) red(loc[i][1]);
	for(int i=1;i<=cac;i++) ldred(rate[i]);
	for(int i=1;i<=n;i++) sp[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int a,b,w;
		red(a),red(b),red(w);
		chkmn(sp[a][b],w);
		chkmn(sp[b][a],w);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
					chkmn(sp[i][j],sp[i][k]+sp[k][j]);
	//f[i][j][0/1] 前i个教室，申请j个，第i间教室申请/不申请的最小期望
	for(int i=1;i<=cac;i++)
			for(int j=0;j<=lim;j++)
				for(int k=0;k<=1;k++)
					f[i][j][k]=INF;
	f[1][0][0]=f[1][1][1]=0;
	for(int i=2;i<=cac;i++)
		for(int j=0;j<=lim;j++)
		{
			f[i][j][0]=min(f[i-1][j][0]+sp[loc[i-1][0]][loc[i][0]],
						   f[i-1][j][1]+E(rate[i-1],sp[loc[i-1][1]][loc[i][0]],sp[loc[i-1][0]][loc[i][0]]));
			if(j==0) continue;
			f[i][j][1]=min(f[i-1][j-1][0]+E(rate[i],sp[loc[i-1][0]][loc[i][1]],sp[loc[i-1][0]][loc[i][0]]),
						   f[i-1][j-1][1]+rate[i-1]*rate[i]*sp[loc[i-1][1]][loc[i][1]]
									   +rate[i-1]*(1-rate[i])*sp[loc[i-1][1]][loc[i][0]]
									   +(1-rate[i-1])*rate[i]*sp[loc[i-1][0]][loc[i][1]]
									   +(1-rate[i-1])*(1-rate[i])*sp[loc[i-1][0]][loc[i][0]]);
		}
	ld ANS=INF;
	for(int i=0;i<=lim;i++) chkmn(ANS,min(f[cac][i][0],f[cac][i][1]));
	printf("%.2Lf\n",ANS);
	return 0;
}

Problem

成了今年决定1=的题目了 

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
40
41
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
#define red(x) scanf("%d",&x)
using std::max;
using std::min;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
typedef unsigned long long ULL;
const int N=2000,MAXN=N+100;
int f[MAXN][MAXN];
int Prep(int K)
{
	f[0][0]=f[1][0]=f[1][1]=1%K;
	for(int i=2;i<=N;i++)
	{
		f[i][0]=f[i][i]=1%K;
		for(int j=1;j<i;j++)
			f[i][j]=(f[i-1][j-1]+f[i-1][j])%K;
	}
	f[0][0]=(f[0][0]==0);
	for(int i=1;i<=N;i++)
		for(int j=0;j<=i;j++)
			f[i][j]=f[i-1][j]+(f[i][j]==0);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=i;j++)
			f[i][j]+=f[i][j-1];
}
int main()
{
	int T,K,n,m;red(T),red(K);
	Prep(K);
	while(T--)
	{
		red(n),red(m);chkmn(m,n);
		printf("%d\n",f[n][m]);
	}
	return 0;
}

Worm

在考场上思路的方向错了

因为⌊mt⌋\lfloor \frac mt\rfloor是1e5级别的，认为时间复杂度应该是个T(mt)T(\frac mt)的。然后毫无头绪。 q=0，每次拿出的长度单调不升，则切出来的长的一段和短的一段也分别单调不上升。维护三个队列：原序列，切出的长的一段，切出的短的一段，则可以直接取得最大值。

q>0，每次除了切的那个，其它的都长了q。即使它们不长q，切出的两端也要短，更别提它们都长了q，而切去的没有长

这个思路难吗？不难。但是这种分析的方式是迫切需要学习的。 

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T>
inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T>
inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e5+7e6+1;
using std::sort;
using std::for_each;
using std::greater;
struct queue
{
	int a[MAXN],head,tail;
	queue(){head=1,tail=0;}
	void push(int x){a[++tail]=x;}
	void pop(){head++;}
	int& front(){return a[head];}
	bool empty(){return head>tail;}
}Q[3];
int Pop()
{
	int res=-1;
	for(int i=0;i<=2;i++)
		if(!Q[i].empty() && (res==-1 || Q[res].front()<Q[i].front()))
			res=i;
	int ans=Q[res].front();Q[res].pop();
	return ans;
}
int main()
{
	static int a[MAXN],outs[MAXN],*op=outs;	
	int n,m,q,u,v,t;
	red(n),red(m),red(q),red(u),red(v),red(t);
	for(int i=1;i<=n;i++) red(a[i]);
	sort(a+1,a+1+n,greater<int>());
	for(int i=1;i<=n;i++) Q[0].push(a[i]);
	int delta=0;
	for(int i=1;i<=m;i++)
	{
		int x=Pop()+delta,px=(int)((long double)u*x/v);
		delta+=q;
		Q[1].push(px-delta);Q[2].push(x-px-delta);
		if(i%t==0) *++op=x;
	}
	for(int *it=outs+1;it<=op;++it)
		printf("%d%s",*it,it==op?"":" ");
	puts("");
	op=outs;
	for(int i=1;i<=n+m;i++)
	{
		int x=Pop()+delta;
		if(i%t==0) *++op=x;
	}
	for(int *it=outs+1;it<=op;++it)
		printf("%d%s",*it,it==op?"":" ");
	puts("");
	return 0;
}

AngryBirds

DFS，状压剪个枝。 

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<cstdio>
#include<cstring>
#include<algorithm>
#define red(x) scanf("%d",&x)
using std::max;
using std::min;
using std::sort;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=20,INF=522133279;
typedef long double ld;
const ld eps=1e-10;
inline int fcmp(const ld &x)
{
	if(-eps<=x && x<=eps) return 0;
	return x<0?-1:1;
}
struct Point
{
	ld x,y;
	bool operator <(const Point &a) const
	{
		if(x!=a.x) return x<a.x;
		return y<a.y;
	}
}p[MAXN];
int ANS,cur,n;
struct Line
{
	ld a,b;
	Line(){a=b=0;}
	ld f(ld x){return a*x*x+b*x;}
	bool On(Point po)
	{
		return fcmp(f(po.x)-po.y)==0;
	}
};
Line equ(Point a,Point b)//a.x !=b.x
{
	Line res;
	ld C1=a.y,A1=a.x*a.x,B1=a.x;
	ld C2=b.y,A2=b.x*b.x,B2=b.x;
	ld a1=A1,a2=A2;
	C1*=a2,A1*=a2,B1*=a2,C2*=a1,A2*=a1,B2*=a1;
	res.b=(C1-C2)/(B1-B2);
	res.a=(C1-res.b*B1)/A1;
	return res;
}
inline int Count(int x)
{
	int res=0;
	while(x) x>>=1,res++;
	return --res;
}
const int SZE=2097152+10;
int rec[SZE],us[SZE],rT;
void DFS(int step)
{
	if(us[cur]!=rT)
	{
		us[cur]=rT;
		rec[cur]=INF;
	}
	if(!cur)
	{
		chkmn(ANS,step);
		return;
	}
	else if(step>ANS)
		return;
	else if(!chkmn(rec[cur],step)) 
		return;
	int bac=cur,pres=Count(cur & -cur);Line eq;
	cur^=(1<<pres);DFS(step+1);cur=bac;
	for(int i=pres+1;i<=n;i++)
	{
		if(p[pres].x!=p[i].x)
		{
			eq=equ(p[pres],p[i]);
			if(fcmp(eq.a)<0)
			{
				for(int j=pres;j<=n;j++)
				{
					if(eq.On(p[j]) && (cur & (1<<j)))
						cur^=(1<<j);
				}
				DFS(step+1);
				cur=bac;
			}
		}
	}
}
int main()
{
	//freopen("input","r",stdin);
	int T,m;red(T);
	while(T--)
	{
		rT++;
		red(n),red(m);
		cur=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%Lf%Lf",&p[i].x,&p[i].y);
			cur|=(1<<i);
		}
		sort(p+1,p+1+n);
		ANS=n;
		if(m==1) ANS=(int)(1.0*n/3+2);
		DFS(0);
		printf("%d\n",ANS);
	}
	
	return 0;
}

对了，Worm和AngryBirds一开始在uoj上都etf了，都是精度问题。 所以，用的起long double，绝不用double