发表于 | 更新于

学了FHQTreap来试试模板，发现就这道题我的代码而言，比Treap和Scp慢，比Splay快。 当然一年过去了代码风格也有变化，等有空把各种平衡树的性能测试一番。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
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+10,P=1e5+7,INF=0x1f1f1f1f;
using std::pair;
using std::make_pair;
struct TreapNode
{
	TreapNode *son[2];
	int py,v,sz;
	void up(){sz=1+son[0]->sz+son[1]->sz;}
	int Rank(int);
	int LowCount(int);
	int Kth(int);
	int Pred(int);
	int Succ(int);
}*null=new TreapNode,*root=null;
typedef pair<TreapNode*,TreapNode*> NodePair;
inline void InitTreap()
{
	null->son[0]=null->son[1]=null;
	null->py=P;null->sz=null->v=0;
}
inline TreapNode *newTreapNode(int v)
{
	static TreapNode *ME=new TreapNode[MAXN],*cur;
	cur=ME++;cur->v=v;cur->son[0]=cur->son[1]=null;
	cur->py=rand()%P;cur->sz=1;
	return cur;
}
TreapNode *Merge(TreapNode *a,TreapNode *b)
{
	if(a==null) return b;
	if(b==null) return a;
	if(a->py<b->py)
	{
		a->son[1]=Merge(a->son[1],b);
		a->up();
		return a;
	}
	else//a->val>b->val
	{
		b->son[0]=Merge(a,b->son[0]);
		b->up();
		return b;
	}
}
NodePair Split(TreapNode *pos,int K)
{
	NodePair cur=make_pair(null,null);
	if(pos==null) return cur;
	if(K<=pos->son[0]->sz)
	{
		cur=Split(pos->son[0],K);
		pos->son[0]=cur.second,pos->up();
		cur.second=pos;
	}
	else
	{
		cur=Split(pos->son[1],K-pos->son[0]->sz-1);
		pos->son[1]=cur.first,pos->up();
		cur.first=pos;
	}
	return cur;
}
void Insert(int x)
{
	NodePair sp=Split(root,root->LowCount(x));
	root=Merge(Merge(sp.first,newTreapNode(x)),sp.second);
}
void Delete(int x)
{
	NodePair sp1=Split(root,root->LowCount(x)),
			 sp2=Split(sp1.second,sp1.second->Rank(x));
	root=Merge(sp1.first,sp2.second);
}
int TreapNode::LowCount(int v)
{
	TreapNode *pos=this;
	int res=0;
	while(pos!=null)
	{
		if(pos->v<v)
		{
			res+=pos->son[0]->sz+1;
			pos=pos->son[1];
		}
		else
			pos=pos->son[0];
	}
	return res;
}
int TreapNode::Rank(int v){return LowCount(v)+1;}
int TreapNode::Kth(int K)
{
	TreapNode *pos=this;
	while(pos!=null)
	{
		if(pos->son[0]->sz+1==K) return pos->v;
		else if(K<pos->son[0]->sz+1) pos=pos->son[0];
		else K-=pos->son[0]->sz+1,pos=pos->son[1];
	}
	return INF;
}
int TreapNode::Pred(int x)
{
	TreapNode *pos=this;
	int res=-INF;
	while(pos!=null)
	{
		if(pos->v<x)
		{
			chkmx(res,pos->v);
			pos=pos->son[1];
		}
		else
			pos=pos->son[0];
	}
	return res;
}
int TreapNode::Succ(int x)
{
	TreapNode *pos=this;
	int res=INF;
	while(pos!=null)
	{
		if(pos->v>x)
		{
			chkmn(res,pos->v);
			pos=pos->son[0];
		}
		else
			pos=pos->son[1];
	}
	return res;
}
int main()
{
	srand(0x1f1f1f1f);
	InitTreap();
	//freopen("input","r",stdin);
	int n;red(n);int g=0;
	for(int i=1;i<=n;i++)
	{
		int opt,x;red(opt),red(x);
		switch(opt)
		{
			case 1:Insert(x);break;
			case 2:Delete(x);break;
			case 3:printf("%d\n",root->Rank(x));break;
			case 4:printf("%d\n",root->Kth(x));break;
			case 5:printf("%d\n",root->Pred(x));break;
			case 6:printf("%d\n",root->Succ(x));break;
		}
	}
	return 0;
}

发表于 | 更新于

好几天才做完这几道题。。效率贼低。。还有一个插头DP和一个大搜索没做。 插头DP学完之后来填，大搜索嘛。。什么时候想练码力了再写吧。 总体感觉不是特别难，没有像今年r2的那种神级毒瘤题。。

R1 day1

shrew

乍一看被唬住了。然后就开始寻找问题性质 看数据范围->一定是枚举r,cr,c啊。。 所有数字的总和一定能整除rcrc 再想了一会儿，发现角上只有一种消法，然后就写了一发纯暴力。

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
//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=100+10;
int a[MAXN][MAXN],b[MAXN][MAXN],n,m,tol;
inline bool flush(int x1,int y1,int x2,int y2,int v)
{
	for(int i=x1;i<=x2;i++)//x1..y1..
		for(int j=y1;j<=y2;j++)
		{
			if(b[i][j]<v || i>n || j>m) 
				return 0;
			b[i][j]-=v;
		}
	return 1;
}
bool check(int r,int c)
{
	memcpy(b,a,sizeof(a));
	int x,y,sum=tol;
	while(sum)
	{
		for(x=1;x<=n;x++)
			for(y=1;y<=m;y++)
				if(b[x][y]) goto out;
		out:
		sum-=r*c*b[x][y];
		if(!flush(x,y,x+r-1,y+c-1,b[x][y])) 
			return 0;
	}
	return 1;
}
int main()
{
	//freopen("input","r",stdin);
	red(n),red(m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			red(a[i][j]),tol+=a[i][j];
	int ANS=tol;
	for(int r=n;r>=1;r--)
		for(int c=m;c>=1;c--)
		{
			if(tol%(r*c)!=0 || ANS<=tol/(r*c)) continue;
			if(check(r,c)) 
				ANS=tol/(r*c);
		}
	printf("%d\n",ANS);
	return 0;
}

calc

之前学BSGS的时候做过，本来想迅速写完，结果写完了pow_mod和exgcd之后就卡住了。。无语啊。想了一会儿，模模糊糊记得好像是个算出P\sqrt P以内的值，hash之后再枚举？总之没回忆起来。 为了防止忘，还是写下来吧。

BSGS

解yx≡z(mod P)y^x\equiv z(mod\ P) 由费马小定理，yP−1≡1(mod P)y^{P-1}\equiv 1(mod\ P)，所以方程左边的值以[0,P−1][0,P-1]为第一个周期，然后开始循环。（好像是P-2？）但是实现的时候感觉算到PP简单一些。 令x=ki−jx=ki-j，则yki−j≡z(mod P)⟺(yi)k≡zyj(mod P)y^{ki-j}\equiv z(mod\ P)\Longleftrightarrow (y^i)^k\equiv zy^j(mod\ P) 固定ii，这样只需枚举kk，看看有没有符合条件的zyjzy^j即可。

  1. 算出a∈[1,P]a\in [1,\sqrt P]的zyazy^a，存在HashSet里面
  2. 枚举k∈[1,P]k\in [1,\sqrt P]，查找zyazy^a。如果找到了就返回。 特殊情况！当y∣Py|P的时候总是无解。。需要特判。

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
106
//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 char *NOTFOUND="Orz, I cannot find x!";
typedef long long LL;
int Pow(LL base,int pv,int P)
{
	LL res=1;
	for(;pv;pv>>=1)
	{
		if(pv&1)
			(res*=base)%=P;
		(base*=base)%=P;
	}
	return res;
}
void solve1(int y,int z,int P){printf("%d\n",Pow(y,z,P));}
int ExGcd(int a,int b,LL &x,LL &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	else
	{
		int d=ExGcd(b,a%b,x,y);
		LL x1=x,y1=y;
		x=y1,y=x1-(a/b)*y1;
		return d;
	}
}
void solve2(int a,int z,int P)
{
	LL x=0,y=0;
	int d=ExGcd(a,P,x,y);//ax+P(-y)=z
	if(z%d) puts(NOTFOUND);
	else
	{
		x*=z/d;
		int k=P/d;
		((x%=k)+=k)%=k;
		printf("%lld\n",x);
	}
}
struct Hash
{
	static const int P=99929;
	static const int MAXSIZE=P<<2;
	struct HashNode{int key,value,pre;}node[MAXSIZE];int id[P],nc;
	void Clear(){nc=0;memset(id,0,sizeof(id));}
	int find(int x)
	{
		for(int i=id[x%P];i;i=node[i].pre)
			if(node[i].key==x) return 1;
		return 0;
	}
	int &operator [](int x)
	{
		for(int i=id[x%P];i;i=node[i].pre)
			if(node[i].key==x) return node[i].value;
		node[++nc].key=x;node[nc].pre=id[x%P];id[x%P]=nc;
		return node[nc].value;
	}
};
void solve3(int y,int z,int P)
{
	static Hash S;
	if(y%P)//....
	{
		S.Clear();
		int B=(int)sqrt(P);
		LL zyi=z;
		for(int i=0;i<=B;i++,(zyi*=y)%=P)
			if(!S.find(zyi)) S[zyi]=i;
		int yb=Pow(y,B,P);
		LL ybi=yb;
		for(int i=1;i<B;i++)
		{
			if(S.find(ybi))
			{
				printf("%d\n",B*i-S[ybi]);
				return;
			}
			(ybi*=yb)%=P;
		}
	}
	puts(NOTFOUND);
}
void (*solve[4])(int,int,int);//=(solve1,solve2,solve3); 
int main()
{
	int T,kind,y,z,P;
	red(T),red(kind);
	solve[1]=solve1;
	solve[2]=solve2;
	solve[3]=solve3;
	while(T--)
	{
		red(y),red(z),red(P);
		solve[kind](y,z,P);
	}
	return 0;
}

paint

太弱了。。这种题想了一中午都没想出来。。 对于每个区间，维护一个左端点颜色，一个右端点颜色，就可以合并了（好像看到了一点捉迷藏括号序列的影子啊。。）

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//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+10;
using std::swap;
struct SplayNode
{
	SplayNode *son[2],*fa;
	int cnt,lc,rc,c,cov;
	bool rev;
	
	void up();//null up的时候会出问题
	void down();
	inline bool isRoot(){return fa->son[0]!=this && fa->son[1]!=this;}
	inline bool isRelated(){return fa->son[0]==this || fa->son[1]==this;}
	inline bool kind(){return fa->son[1]==this;}
	inline void cover(int newc)
	{
		if(!c) return;
		lc=rc=c=cov=newc;
		cnt=1;
	}
	inline void reverse()
	{
		if(!c) return;
		swap(son[0],son[1]);
		swap(lc,rc);
		rev^=1;//=1
	}

}spl[MAXN],*null=spl,*ME=spl,*node[MAXN];
inline void SplayNode::up()
{
	cnt=son[0]->cnt+son[1]->cnt+1;
	if(son[0]->rc==c) cnt--;
	if(son[1]->lc==c) cnt--;
	lc=son[0]==null?c:son[0]->lc;
	rc=son[1]==null?c:son[1]->rc;
}
inline void SplayNode::down()
{
	if(isRelated())//!isRoot()) 
		fa->down();
	if(cov)
	{
		son[0]->cover(cov);
		son[1]->cover(cov);
		cov=0;
	}
	if(rev)
	{
		son[0]->reverse();
		son[1]->reverse();
		rev=0;
	}
}
inline void InitSplay()
{
	null->cnt=null->lc=null->rc=null->c=0;
	null->son[0]=null->son[1]=null->fa=null;
}
inline SplayNode *newSplayNode(int c)
{
	++ME;
	ME->cnt=1;
	ME->lc=ME->rc=ME->c=c;
	ME->cov=ME->rev=0;
	ME->fa=ME->son[0]=ME->son[1]=null;
	return ME;
}
void trans(SplayNode *pos)
{
	static SplayNode *f,*grf;
	static int d;
	f=pos->fa,grf=f->fa,d=pos->kind();
	if(!f->isRoot()) grf->son[f->kind()]=pos;
	pos->fa=grf;
	pos->son[!d]->fa=f;f->son[d]=pos->son[!d];
	pos->son[!d]=f;f->fa=pos;
	f->up(),pos->up();
}
void Splay(SplayNode *pos)
{
	pos->down();
	while(!pos->isRoot())
	{
		static SplayNode *f;
		f=pos->fa;
		if(!f->isRoot())
			trans(pos->kind()==f->kind()?f:pos);
		trans(pos);
	}
}
void Access(SplayNode *pos)
{
	SplayNode *pred=null;
	while(pos!=null)
	{
		Splay(pos);
		pos->son[1]=pred;
		pos->up();
		pred=pos;
		pos=pos->fa;
	}
}
inline void BeRoot(SplayNode *pos)
{
	Access(pos),Splay(pos);
	pos->reverse();
}
inline void Link(SplayNode *p1,SplayNode *p2)
{
	BeRoot(p2);
	p2->fa=p1;
}
inline void Paint(int p1,int p2,int newc)
{
	BeRoot(node[p1]);
	Access(node[p2]),Splay(node[p2]);
	node[p2]->cover(newc);
}
inline int Query(int p1,int p2)
{
	BeRoot(node[p1]);
	Access(node[p2]),Splay(node[p2]);
	return node[p2]->cnt;
}
int main()
{
	InitSplay();
	int n,m;red(n),red(m);
	for(int i=1;i<=n;i++)
	{
		int c;
		red(c);
		node[i]=newSplayNode(c);
	}
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		red(x),red(y);
		Link(node[x],node[y]);
	}
	for(int i=1;i<=m;i++)
	{
		char opt[5];scanf("%s",opt);
		int a,b,c;red(a),red(b);
		if(opt[0]=='C') red(c),Paint(a,b,c);
		else printf("%d\n",Query(a,b));
	}
	return 0;
}

R1 day2

missile

太弱了，被这题从2016克到了2017。 首先第一问，不用说，是CDQ分治。 然后我就WA了好久。因为之前写CDQ分治，虽说也是统计前面对后面的影响，但是要求的是总和之类的问题。所以我就顺手写了 

1
DC(l,mid),DC(mid+1,r);

然后查了很长时间才查出来。 第二问，仍旧CDQ分治，要找出有多少有多少种方案包含某个点，然后除以总方案数就是这个点的概率。 就要记一下一个点前面有多少点可以转移到它，它点可以转移到后面多少个点，相乘就行了。 第一种没问题，第二种就没办法了。最后发现，似乎只能把序列翻转求。 改完之后，还是WA。最后发现，chkmx(pair<int,double>,pair<int,double>)chkmx(pair<int,double>,pair<int,double>)是先按照第一关键字再按第二关键字比较的。所以即使.first.first相同也有可能不累加。惨痛的教训啊！

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
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::copy;
using std::merge;
using std::sort;
using std::pair;
using std::make_pair;
using std::lower_bound;
using std::greater;
const int MAXN=5e4+100;
pair<int,double> f[MAXN][2];
struct Opt
{
	int fst,snd,trd,id;
	bool operator <(const Opt &a) const {return snd<a.snd;}
}p[MAXN],t[MAXN];
void partition(int l,int r,int midv)
{
	int pl=l,pr=(l+r)/2+1;
	for(int i=l;i<=r;i++)
		if(p[i].fst<=midv) t[pl++]=p[i];
		else t[pr++]=p[i];
	copy(t+l,t+r+1,p+l);
}
struct BIT
{
	pair<int,double> a[MAXN];int us[MAXN],T,n;
	void reset(){++T;}
	void add(int pos,pair<int,double> v)
	{
		if(!pos) return;
		for(;pos<=n;pos+=pos & -pos)
		{
			if(us[pos]!=T) us[pos]=T,a[pos]=make_pair(0,0);
			if(a[pos].first<v.first) a[pos]=v;
			else if(a[pos].first==v.first) a[pos].second+=v.second;
		}
	}
	pair<int,double> max(int pos)
	{
		if(!pos) return make_pair(0,0);
		pair<int,double> res=make_pair(0,0);
		for(;pos;pos-=pos & -pos)
		{
			if(us[pos]!=T) us[pos]=T,a[pos]=make_pair(0,0);
			if(res.first<a[pos].first) res=a[pos];
			else if(res.first==a[pos].first) res.second+=a[pos].second;
		}
		return res;
	}
}bit;
void DC(int l,int r,int d)
{
	if(l==r) return;
	int mid=(l+r)/2;
	partition(l,r,mid);
	DC(l,mid,d);
	bit.reset();
	for(int pl=l,pr=mid+1;pr<=r;pr++)
	{
		while(pl<=mid && p[pl].snd<=p[pr].snd)
		{
			bit.add(p[pl].trd,f[p[pl].id][d]);
			pl++;
		}
		pair<int,double> res=bit.max(p[pr].trd);
		if(!res.first) continue;
		res.first++;
		if(f[p[pr].id][d].first<res.first) f[p[pr].id][d]=res,f[p[pr].id][d].first;
		else if(f[p[pr].id][d].first==res.first) f[p[pr].id][d].second+=res.second;
	}
	DC(mid+1,r,d);
	merge(p+l,p+mid+1,p+mid+1,p+r+1,t+l);
	copy(t+l,t+r+1,p+l);
}
int main()
{
	//freopen("input","r",stdin);
	static int snd[MAXN],trd[MAXN];
	int n;red(n),bit.n=n;
	for(int i=1;i<=n;i++)
	{
		red(p[i].snd),red(p[i].trd),p[i].fst=p[i].id=i;
		snd[i]=p[i].snd,trd[i]=p[i].trd;
		f[i][0]=f[i][1]=make_pair(1,1);
	}
	sort(snd+1,snd+1+n,greater<int>()),sort(trd+1,trd+1+n,greater<int>());
	for(int i=1;i<=n;i++)
	{
		p[i].snd=lower_bound(snd+1,snd+1+n,p[i].snd,greater<int>())-snd;
		p[i].trd=lower_bound(trd+1,trd+1+n,p[i].trd,greater<int>())-trd;
	}
	sort(p+1,p+1+n),DC(1,n,0);
	for(int i=1;i<=n;i++)
	{
		p[i].fst=n-p[i].fst+1;
		p[i].snd=n-p[i].snd+1;
		p[i].trd=n-p[i].trd+1;
	}
	sort(p+1,p+1+n),DC(1,n,1);
	int ANS=1;
	for(int i=1;i<=n;i++)
	{
		chkmx(ANS,f[i][0].first+f[i][1].first-1);
		//debug(f[i][0].first),debug(f[i][1].first);
	}
	printf("%d\n",ANS);
	double sum=0;
	for(int i=1;i<=n;i++)
		if(f[i][0].first==ANS) 
			sum+=f[i][0].second;
	for(int i=1;i<=n;i++)
		printf("%.5lf%s",f[i][0].first+f[i][1].first-1==ANS?f[i][0].second*f[i][1].second/sum:0,i==n?"\n":" ");
	return 0;
}

job

费用流直接上，结果因为没用LL，WA了一次，而且还是全WA。 一定要算好一个变量的取值范围！！！ 如果考场上出现这种情况，那就真是>>>>了。

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
using std::queue;
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;
const int MAXN=(250+10)*2,INF=0x1f1f1f1f,MAXM=MAXN*MAXN;
struct Arc
{
	int to,cap,cost,f,pre;
}e[MAXM<<1];int id[MAXN],ec=1,S,T;
void Adde(int from,int to,int cap,int cost)
{
	e[++ec].to=to;e[ec].cap=cap;e[ec].cost=cost;e[ec].f=0;e[ec].pre=id[from];id[from]=ec;
	e[++ec].to=from;e[ec].cap=0;e[ec].cost=-cost;e[ec].f=0;e[ec].pre=id[to];id[to]=ec;
}
int dist[MAXN],pree[MAXN];
bool Find()
{
	static bool inq[MAXN];
	static queue<int> Q;
	memset(inq,0,sizeof(inq));
	memset(dist,31,sizeof(dist));
	dist[S]=0;Q.push(S),inq[S]=1;
	while(!Q.empty())
	{
		int cur=Q.front();Q.pop(),inq[cur]=0;
		for(int i=id[cur];i;i=e[i].pre)
		{
			int u=e[i].to;
			if(e[i].cap>e[i].f && chkmn(dist[u],dist[cur]+e[i].cost))
			{
				pree[u]=i;
				if(!inq[u])
					Q.push(u),inq[u]=1;
			}
		}
	}
	return dist[T]!=INF;
}
int Aug()
{
	int minf=INF;
	for(int i=pree[T];i;i=pree[e[i^1].to])
		chkmn(minf,e[i].cap-e[i].f);
	for(int i=pree[T];i;i=pree[e[i^1].to])
		e[i].f+=minf,e[i^1].f-=minf;
	return minf;
}
LL MCMF()
{
	int f,flow=0;
	LL cost=0;
	while(Find())
	{
		f=Aug();
		flow+=f;
		cost+=(LL)dist[T]*f;
	}
	return cost;
}
int main()
{
	//freopen("input","r",stdin);
	static int c[MAXN],a[MAXN][MAXN],s[MAXN],w[MAXN][MAXN],t[MAXN][MAXN];
	#define obj(i) (i+n)
	#define person(i) (i)
	int n,m;red(n),red(m);
	S=0,T=n+m+1;
	for(int i=1;i<=m;i++) red(c[i]),Adde(obj(i),T,c[i],0);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			red(a[i][j]);
			if(a[i][j]) Adde(person(i),obj(j),INF,0);//obj(i)..
		}
	for(int i=1;i<=n;i++)
	{
		red(s[i]);
		for(int j=1;j<=s[i];j++) red(t[i][j]);
		for(int j=1;j<=s[i]+1;j++) red(w[i][j]);
		for(int j=1;j<=s[i];j++) Adde(S,person(i),t[i][j]-t[i][j-1],w[i][j]);
		Adde(S,person(i),INF,w[i][s[i]+1]);
	}
	printf("%lld\n",MCMF());
	return 0;
}

maze

不会做。。。 用三进制数SS表示对陷阱的了解情况。 状态是f[S][x][y][h]f[S][x][y][h]表示对陷阱的了解情况为SS，在位置(x,y)(x,y)，血量为hh，走出的最大概率。 转移的时候，如果碰到了未知的陷阱，可以根据p[]中目前可能存在的状况求出陷阱两种属性分别的概率。 写完之后90。换个枚举顺序就100了？？why？？

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
106
107
108
109
110
111
112
113
114
115
116
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
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,MAXS=243+10,MAXK=5+3,MAXH=5+3,WALL=-1,EMPTY=-2,EXIT=-3,NOTSURE=2,HARM=1,SAFE=0,
		  dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int n,m,K,p[MAXN],pw3[MAXN],map[MAXN][MAXN];
struct point{int x,y;};
struct bitset
{
	int a[MAXK];
	bitset(int cur)
	{
		memset(a,0,sizeof(a));
		for(int i=1;cur;i++,cur/=3) a[i]=cur%3;
	}
	int &operator [](int x){return a[x];}
	int toint()
	{
		int res=0;
		for(int i=1;i<=K;i++) res+=a[i]*pw3[i-1];
		return res;
	}
};
bool possible(bitset &a,int S)
{
	for(int i=1;i<=K;i++)
		if(a[i]!=NOTSURE && (a[i]!=((S>>(i-1)) & 1)))//S&(1<<i>>1)..
			return 0;
	return 1;
}
double Pharm(int cur,int x)//
{
	static bool vis[MAXS][MAXN];
	static double val[MAXS][MAXN];
	if(vis[cur][x]) return val[cur][x];
	vis[cur][x]=1;
	bitset buf=bitset(cur);
	if(buf[x]==HARM) return val[cur][x]=1;
	else if(buf[x]==SAFE) return val[cur][x]=0;
	else
	{
		int a=0,b=0;
		for(int S=0;S<=(1<<K)-1;S++)
			if(possible(buf,S))
			{
				b+=p[S];
				if((S>>(x-1)) & 1)
					a+=p[S];
			}
		return val[cur][x]=(double)a/b;
	}
}
double DP(int cur,int x,int y,int h)
{
	static bool vis[MAXS][MAXN][MAXN][MAXH];
	static double f[MAXS][MAXN][MAXN][MAXH];
	if(vis[cur][x][y][h]) return f[cur][x][y][h];
	vis[cur][x][y][h]=1;
	if(!h || x==0 || x>n || y==0 || y>m) return f[cur][x][y][h]=0;
	if(map[x][y]==EXIT) return f[cur][x][y][h]=1;
	bitset buf=bitset(cur);
	for(int d=0;d<4;d++)
	{
		int nx=x+dx[d],ny=y+dy[d];
		double res=0;
		switch(map[nx][ny])
		{
			//case EMPTY:
			case EMPTY: res=DP(cur,nx,ny,h);break;
			case EXIT: res=DP(cur,nx,ny,h);break;
			case WALL:break;
			default:
				int num=map[nx][ny];
				if(buf[num]==SAFE) res=DP(cur,nx,ny,h);
				else if(buf[num]==HARM) res=DP(cur,nx,ny,h-1);
				else
				{
					buf[num]=SAFE;res=(1-Pharm(cur,num))*DP(buf.toint(),nx,ny,h);
					buf[num]=HARM;res+=Pharm(cur,num)*DP(buf.toint(),nx,ny,h-1);
					buf[num]=NOTSURE;
				}
				break;
		}
		chkmx(f[cur][x][y][h],res);
	}
	return f[cur][x][y][h];
}
int main()
{
	pw3[0]=1;for(int i=1;i<MAXK;i++) pw3[i]=pw3[i-1]*3;
	//freopen("input","r",stdin);
	static char line[MAXN];
	int H;red(n),red(m),red(K),red(H);
	point start;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",line+1);
		for(int j=1;j<=m;j++)
		{
			switch(line[j])
			{
				case '$':start.x=i,start.y=j;map[i][j]=EMPTY;break;
				case '#':map[i][j]=WALL;break;
				case '.':map[i][j]=EMPTY;break;
				case '@':map[i][j]=EXIT;break;
				default:map[i][j]=line[j]-'A'+1;break;
			}
		}
	}
	for(int i=0;i<(1<<K);i++) red(p[i]);
	printf("%.3lf\n",DP(pw3[K]-1,start.x,start.y,H));
	return 0;
}

R2 day1

game

一开始看错题了。看对了之后又理解错了。 对于一次游戏，终止局面一定是相邻的黑子白子靠在一起，这还是能看出来的。 按照标解，黑子右移或者白子左移都没有意义，因为可以模仿。所以只考虑黑子左移或者白子右移的情况。 把空格看成石子的话，问题就变成了：有k2\frac k2堆石子，一次可以从1∼k1\sim k堆拿走任意多的石子，不能拿的输，问有多少种先手必胜策略。 这种博弈称为Nim-K，结论和Bash博弈类似：当每堆石子的每个二进制位为1的个数都分别能整除k+1k+1，则先手必败。 然后可以根据这个来DP。定义f[i][j]f[i][j]为处理完二进制前ii位，石子总和为jj的必败方案数目（当石子堆顺序不同也算不同），然后枚举k+1k+1的倍数qq转移。 最终必败的方案总和为∑i=0n−Kf[20][i]×C(n−i−K2,K2)\sum_{i=0}^{n-K}f[20][i]\times C(n-i-\frac K2,\frac K2) 乘的那个组合数的含义为： 已经确定了每堆石子的个数，只需确定每堆第一个石子的位置就能确定出一个方案。而共有n−i−K2n-i-\frac K2个位置可供选择，要选K2\frac K2个。

但其实这个转化是有问题的？

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
//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;}
typedef long long LL;
using std::min;
const int P=1000000007;
const int MAXN=10000+10,MAXK=100+10,LOG=20,MAXLOG=20+5;
LL f[MAXLOG][MAXN],C[MAXN][MAXK];
int main()
{
	//freopen("input","r",stdin);
	int n,K,d;red(n),red(K),red(d);
	C[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		C[i][0]=C[i][1]=1;
		for(int j=1;j<=min(i,K);j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
	}
	f[0][0]=1;
	for(int i=0;i<=LOG;i++)
		for(int j=0;j<=n-K;j++)
			for(int q=0;q*(d+1)<=(K>>1) && j+q*(d+1)*(1<<i)<=n-K;q++)
				(f[i+1][j+q*(d+1)*(1<<i)]+=f[i][j]*C[K>>1][q*(d+1)])%=P;
	LL ANS=0;
	for(int i=0;i<=n-K;i++)
		(ANS+=f[LOG][i]*C[n-i-(K>>1)][K>>1])%=P;
	ANS=C[n][K]-ANS;((ANS%=P)+=P)%=P;
	printf("%lld\n",ANS);
	return 0;
}

mindist

树网的核

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
//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=300000+10,INF=0x1f1f1f1f;
using std::make_pair;
using std::pair;
using std::queue;
using std::max;
using std::reverse;
inline int max(const int &a,const int &b,const int &c){return max(max(a,b),c);}
struct Edge{int to,v,pre;}e[MAXN<<1];int id[MAXN],ec=1,n;
void Adde(int from,int to,int v)
{
	e[++ec].to=to;e[ec].v=v;e[ec].pre=id[from];id[from]=ec;
	e[++ec].to=from;e[ec].v=v;e[ec].pre=id[to];id[to]=ec;
}
int dist[MAXN],pree[MAXN],ud[MAXN],T;
int BFS(int s)
{
	queue<int> Q;
	pree[s]=dist[s]=0;ud[s]=T;Q.push(s);
	int res=0;
	while(!Q.empty())
	{
		int cur=Q.front();Q.pop();
		for(int i=id[cur];i;i=e[i].pre)
		{
			int u=e[i].to;
			if(ud[u]==T) continue;
			pree[u]=i;
			dist[u]=dist[cur]+e[i].v;ud[u]=T;Q.push(u);
			chkmx(res,dist[u]);
		}
	}
	return res;
}
pair<int,int> diameter[MAXN];int ds;
int far[MAXN],dl[MAXN],dr[MAXN];
void Prep()
{
	++T;
	BFS(1);
	int mx=0,start=1;
	for(int i=1;i<=n;i++)
		if(chkmx(mx,dist[i])) start=i;
	++T;
	BFS(start);
	mx=0;int dest=start;
	for(int i=1;i<=n;i++)
		if(chkmx(mx,dist[i])) dest=i;
	for(int i=pree[dest];i;i=pree[e[i^1].to]) 
		diameter[++ds]=make_pair(e[i].to,e[i].v);
	diameter[++ds]=make_pair(start,0);
	reverse(diameter+1,diameter+1+ds);	
	++T;
	for(int i=1;i<=ds;i++) ud[diameter[i].first]=T;
	for(int i=1;i<=ds;i++) far[i]=BFS(diameter[i].first);
	for(int i=2;i<=ds;i++) dl[i]=dl[i-1]+diameter[i].second;
	for(int i=ds-1;i;i--) dr[i]=dr[i+1]+diameter[i+1].second;
}
inline int dis(int l,int r){return dl[r]-dl[l];}
int main()
{
	//freopen("input","r",stdin);
	int lim;red(n),red(lim);
	for(int i=1;i<=n-1;i++)
	{
		int u,v,a;
		red(u),red(v),red(a);
		Adde(u,v,a);
	}
	Prep();
	static int Q[MAXN];//如果比ta晚还比ta大，ta就无用了。维护单减队列
	int ANS=INF,l,r,res,h,t;
	for(l=1,r=1,Q[h=t]=1;l<=ds;l++)
	{
		while(h<=t && Q[h]<l) h++;
		res=max(dl[l],dr[r],far[Q[h]]);chkmn(ANS,res);
		while(r<ds && dis(l,r+1)<=lim)
		{
			++r;
			while(h<=t && far[Q[t]]<=far[r]) t--;
			Q[++t]=r;
			res=max(dl[l],dr[r],far[Q[h]]);chkmn(ANS,res);
		}
	}
	printf("%d\n",ANS);
	return 0;
}

mars

R2 day2

snake

the file name has no special meanings

这是个什么梗啊。。然后又不会做 先用分数规划求出到每个出入口的最小危险值。 然后建图，S到奇数点，偶数点到T，流量为最小危险值。 在对应的出入口之间连INF。跑出最小割就是答案。

Tips

实数二分最好记答案，实数二分的range要在合法的情况下尽量小，要么就得调小eps。否则误差会大 对于不可达的奇数点或者偶数点，如果和S,T没有连INF就会WA？

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
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=700+10,MAXM=100000+10,INF=0x1f1f1f1f;
const double eps=1e-8,inf=1e10;
using std::queue;
int fcmp(double x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
struct Edge{int to,u,d,pre;}e[MAXM];int id[MAXN],ec,n;
void Adde(int f,int t,int u,int d){e[++ec].to=t;e[ec].u=u;e[ec].d=d;e[ec].pre=id[f];id[f]=ec;}
double SP(int s,int t,double k)
{
	static int Q[MAXN*MAXN],hd,tl;
	static double dist[MAXN];
	static bool inq[MAXN];
	for(int i=1;i<=n;i++) dist[i]=inf,inq[i]=0;
	dist[s]=0;Q[hd=tl=1]=s,inq[s]=1;
	while(hd<=tl)
	{
		int cur=Q[hd++];inq[cur]=0;
		for(int i=id[cur];i;i=e[i].pre)
		{
			int u=e[i].to;
			if(chkmn(dist[u],dist[cur]+e[i].u-k*e[i].d) && !inq[u])
				Q[++tl]=u,inq[u]=1;
			if(fcmp(dist[t])<0)
				return dist[t];
		}
	}
	return dist[t];
}
double SP01(int s,int t)
{
	double L=0,R=20,A=inf;
	while(R-L>1e-3)
	{
		double MID=(L+R)/2.0;
		if(fcmp(SP(s,t,MID))<0)
			R=A=MID;
		else 
			L=MID;
	}
	return A;
}
struct MaxFlow
{
	struct Arc{int to,pre;double cap,v;}e[MAXM];int id[MAXN],ec,S,T,N;
	MaxFlow(){ec=1;}
	void Adde(int f,int t,double cap)
	{
		e[++ec].to=t;e[ec].cap=cap;e[ec].v=0;e[ec].pre=id[f];id[f]=ec;
		e[++ec].to=f;e[ec].cap=0;  e[ec].v=0;e[ec].pre=id[t];id[t]=ec;
	}
	int pree[MAXN],d[MAXN],num[MAXN],curf[MAXN];
	double Aug()
	{
		double minf=inf;
		for(int i=pree[T];i;i=pree[e[i^1].to])
			chkmn(minf,e[i].cap-e[i].v);
		for(int i=pree[T];i;i=pree[e[i^1].to])
		{
			e[i].v+=minf;
			e[i^1].v-=minf;
		}
		return minf;
	}
	bool BFS()
	{
		queue<int> Q;
		memset(d,31,sizeof(d));
		num[d[T]=0]=1,Q.push(T);
		while(!Q.empty())
		{
			int cur=Q.front();Q.pop();
			for(int i=id[cur];i;i=e[i].pre)
			{
				int u=e[i].to;
				//if(e[i].cap>e[i].v && 
				if(d[u]==INF)
				{
					num[d[u]=d[cur]+1]++;
					Q.push(u);
				}
			}
		}
		return d[S]!=INF;
	}
	double ISAP()
	{
		memcpy(curf,id,sizeof(id));
		if(!BFS()) return 0;
		int cur=S;double flow=0;
		while(d[S]<N)
		{
			if(cur==T)
			{
				flow+=Aug();
				cur=S;
			}
			bool adv=0;
			for(int i=curf[cur];i;i=e[i].pre)
			{
				int u=e[i].to;
				if(e[i].cap>e[i].v && d[u]+1==d[cur])
				{
					adv=1;
					pree[u]=i;
					curf[cur]=i;
					cur=u;
					break;
				}
			}
			if(!adv)
			{
				if(--num[d[cur]]==0) break;
				int mind=N-1;
				for(int i=(curf[cur]=id[cur]);i;i=e[i].pre)
					if(e[i].cap>e[i].v) chkmn(mind,d[e[i].to]);
				num[d[cur]=mind+1]++;
				if(cur!=S)
					cur=e[pree[cur]^1].to;
			}
		}
		return flow;
	}
}flow;
int main()
{
	//freopen("input","r",stdin);
	static double danger[MAXN];
	int m;red(n),red(m);
	for(int i=1;i<=m;i++)
	{
		int a,b,t,s;
		red(a),red(b),red(t),red(s);
		Adde(a,b,t,s);
	}
	int m1,n1;red(m1),red(n1);
	for(int i=1;i<=n1;i++)
		danger[i]=SP01(n,i);
	flow.S=0,flow.T=n1+1,flow.N=n1+1+1;
	for(int i=1;i<=n1;i++) //if(fcmp(danger[i]-inf))
	{
		if(i&1) flow.Adde(flow.S,i,danger[i]);
		else flow.Adde(i,flow.T,danger[i]);
	}
	for(int i=1;i<=m1;i++)
	{
		int u,v;red(u),red(v);
		flow.Adde(u,v,inf);
	}
	double ANS=flow.ISAP();
	if(ANS<inf)
		printf("%.1lf\n",ANS);
	else
		puts("-1");
	return 0;
}

repair

学习了一个虚树。 

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//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::min;
using std::sort;
typedef long long LL;
const int MAXN=250000+10,LOG=21;
const LL INF=1e15;
int n,K,h[MAXN];
struct Graph
{
	private:
	int id[MAXN],ec,us[MAXN],T;
	public:
	struct Edge{int to,v,pre;}e[MAXN<<1];
	void clear(){ec=1,++T;}
	void check(int pos){if(us[pos]!=T) us[pos]=T,id[pos]=0;}
	void Adde(int f,int t,int v)
	{
		check(f),check(t);
		e[++ec].to=t;e[ec].v=v;e[ec].pre=id[f];id[f]=ec;
		e[++ec].to=f;e[ec].v=v;e[ec].pre=id[t];id[t]=ec;
	}
	void Adde(int f,int t)
	{
		check(f),check(t);
		e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;
	}
	int operator [](int x){check(x);return id[x];}
	Edge &operator ()(int i){return e[i];}
	void out()
	{
		for(int i=0;i<=n;i++)
			for(int j=id[i];j;j=e[j].pre)
				printf("%d %d\n",i,e[j].to);
	}
}real,virt;
LL mine[MAXN]/*minedge*/;
int dfs[MAXN<<1],dc,li[MAXN],ro[MAXN],dep[MAXN];
void DFS(int pos)
{
	dfs[++dc]=pos;li[pos]=ro[pos]=dc;
	for(int i=real[pos];i;i=real(i).pre)
	{
		int u=real(i).to;
		if(li[u]) continue;
		dep[u]=dep[pos]+1;
		mine[u]=min(mine[pos],(LL)real(i).v);
		DFS(u);ro[pos]=ro[u];dfs[++dc]=pos;
	}
}
int f[MAXN<<1][LOG],log_2[MAXN<<1];
void ST()
{
	log_2[0]=-1;
	for(int i=1;i<=dc;i++) f[i][0]=dfs[i],log_2[i]=log_2[i>>1]+1;
	for(int j=1;j<=log_2[dc];j++)
		for(int i=1;i<=dc-(1<<j)+1;i++)
		{
			int pl=f[i][j-1],pr=f[i+(1<<(j-1))][j-1];
			f[i][j]=dep[pl]<dep[pr]?pl:pr;
		}
}
int LCA(int p1,int p2)
{
	if(!p1 || !p2) return 0;
	static int i,pl,pr;
	p1=li[p1],p2=li[p2];
	if(p1>p2) swap(p1,p2);
	i=log_2[p2-p1+1],pl=f[p1][i],pr=f[p2-(1<<i)+1][i];
	return dep[pl]<dep[pr]?pl:pr;
}
inline bool cmp(const int &a,const int &b){return li[a]<li[b];}
LL DP(int pos)
{
	if(!virt[pos]) return mine[pos];
	LL res=0;
	for(int i=virt[pos];i;i=virt(i).pre)
	{
		int u=virt(i).to;
		res+=DP(u);
	}
	chkmn(res,mine[pos]);return res;
}
LL solve()
{
	static int stack[MAXN],top;
	sort(h+1,h+1+K,cmp);
	//剪枝
	int hc=0;for(int i=1;i<=K;i++)
		if(!hc || ro[h[hc]]<li[h[i]]) h[++hc]=h[i];
	virt.clear();
	stack[top=0]=0;
	for(int i=1;i<=hc;i++)
	{
		for(int lca=LCA(stack[top],h[i]);stack[top]!=lca;)
		{
			if(dep[lca]>dep[stack[top]])
				stack[++top]=lca;
			else if(dep[lca]<=dep[stack[top]])
			{
				virt.Adde(dep[stack[top-1]]>=dep[lca]?stack[top-1]:lca,stack[top]);
				if(dep[stack[top]]==dep[lca]) stack[top]=lca;
				else top--;
			}
		}
		stack[++top]=h[i];
	}
	for(;top;top--)
		virt.Adde(stack[top-1],stack[top]);
	//virt.out();
	return DP(0);
}
int main()
{
	//freopen("input","r",stdin);
	red(n);real.clear();
	for(int i=1;i<=n-1;i++)
	{
		int u,v,w;
		red(u),red(v),red(w);
		real.Adde(u,v,w);
	}
	mine[0]=mine[1]=INF,dep[1]=1;
	DFS(1);ST();
	int m;red(m);
	for(int i=1;i<=m;i++)
	{
		red(K);
		for(int j=1;j<=K;j++) 
			red(h[j]);//h[i]..
		printf("%lld\n",solve());
	}
	return 0;
}

发表于 | 更新于

Link

Solution

嗯。做法来自Po姐。

紫荆花之恋。我在WC 2014中出的题目，这个题目的核心在于可以意识到替罪羊树这一技巧，能够适用于一切依靠子树大小来维持平衡的结构。那么，它必然也可以被使用于点分治这一结构。那么我们就可以用替罪羊树来维护动态的点分治。当时觉得还挺有意思的，不过现在也已经不怎么研究数据结构了>_>。 --WJMZBMR

支持加点，实时维护dis(i,j)≤ri+rjdis(i,j)\le r_i+r_j的点对数目。 考虑不是动态加点的做法。 （口胡begin） 对树点分治，重心为pp的一层内，问题变成dis(i,p)+dis(j,p)≤ri+rjdis(i,p)+dis(j,p)\le r_i+r_j，即dis(i,p)−ri≤rj−dis(j,p)dis(i,p)-r_i \le r_j-dis(j,p) 维护一个有序的数组a[]={dis(i,p)−ri}a[]=\{dis(i,p)-r_i\}，对于一个新分支，求出b[]={rj−dis(j,p)}b[]=\{r_j-dis(j,p)\}。用双指针统计答案，然后把b[]b[]取反，将两个表std::mergestd::merge。 （如果我说的有问题欢迎指教。。） （口胡end） 加点的话，要想办法统计一个新的点对答案的贡献，即以从它一直到根节点为LCA的所有合法路径。这样，在每个重心处维护一个TreapTreap维护ri−dis(i,p)r_i-dis(i,p)，然后查询值dis(j,p)−rjdis(j,p)-r_j在其中的排名即可。 然后复杂度会爆棚，于是借助替罪羊思想，如果一个点点分出来的某个分支的size过大，就重新点分治这棵子树。

Tips

  • 在以pp为重心的一层统计答案的时候要减去LCA不是pp的点对。一开始想的是减去以pp的子节点为LCA的路径，，然后发现不一定只有这样的不合法。。于是不可避免地要开两棵TreapTreap，设pp分出的一棵子树为uu，uu的另一棵记录的是pp在uu内产生的ri−dis(i,p)r_i-dis(i,p)。由此，统计答案的时候直接减去即可。
  • 在重新分治的时候要把TreapTreap重新赋值，用filltreap()实现。一开始这个函数的Treap::Insert()操作写在了遍历边的循环里，结果最顶上的点的值没有Insert()进去。。
  • TreapNode::cnt++之后，没有立即TreapNode::up()TreapNode::up()
  • 维护点分出来的分支的时候只能用平衡树，因为涉及节点的查找和删除操作。
  • 千万不要把原树的father和点分分支的uplayer混淆。
  • 点分中各种操作都严禁跑出当前一层的点集。
  • 一开始的时候std::queue出了问题，调试的时候在那里挂掉。然后还真的研究了很长时间queue的问题。然而弃疗之后发现某个细节写错了，改了之后立即好了。。由此，崩溃的位置不一定是bug的位置。。
  • 在Rebuild中，一开始我的filltreap(DyNode::anti)是写在遍历边的循环里的，结果和上面的一样，最顶上的点没有把anti赋值。
  • 于是学习Po姐的代码，发现在Rebuild之前可以直接保留这棵子树的anti，因为anti不会随着树的结构改变。于是开心地效仿了，发现立即崩溃。研究了好久才顿悟——在Rebuild之前有垃圾回收，里面的TreapNode等同于已经被析构了，再调用必死啊。还是语言逻辑不好啊。。
  • 于是又把代码改成在每层的一开始处理本层的anti，结果崩。苦想，明白了问题：Rebuild(pos)，pos我传的是替罪羊树中的节点编号。它和它的上一层不一定是父子关系。这样filltreap的值就是错的。所以pos应该传这棵子树在原树上的节点编号。
  • 倍增LCA支持动态加点操作。
  • 替罪羊树只需检测每次加了点的分支。
  • 一开始T了，加了fread优化T的更厉害，然后加了fwrite优化，调整了替罪羊树的α\alpha值，才卡过去。如果看出我的代码复杂度写错，或者有常数的缺陷，欢迎指教。看到BZOJ上%jvcb%跑的那么快简直BUG一样。 upd：发现替罪羊树写错了，改过来之后T飞了，然后有各种卡常数改α\alpha，结果最后发现是点分治写错了。太愚蠢了。

    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
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    336
    337
    338
    339
    340
    341
    342
    343
    344
    345
    346
    347
    //Code by Lucida
    #include<bits/stdc++.h>
    //#define red(x) scanf("%d",&x)
    #define debug(x) printf(#x"=%d\n",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 long LL;
    using std::swap;
    using std::queue;
    using std::set;
    const int MAXN=1e5+100,P=1e7;
    LL last=0;int r[MAXN];
    //IO begin
    const int INBUF=1e7;
    char inbuf[INBUF],*iptr=inbuf,*iptrend=inbuf;
    #define getc() (iptr==iptrend && (iptrend=(iptr=inbuf)+fread(inbuf,1,INBUF,stdin),iptr==iptrend)?EOF:*iptr++)
    inline void red(int &x)
    {
    	static int flag;
    	static char ch;
    	flag=1;
    	while(!isdigit(ch=getc())) if(ch=='-') flag=-1;
    	x=ch-'0';
    	while(isdigit(ch=getc()))
    		(x*=10)+=ch-'0';
    	x*=flag;
    }
    const int OUTBUF=1e7;
    char outbuf[OUTBUF],*optr=outbuf;
    inline void white(LL x)
    {
    	if(x<0) *optr++='-';
    	if(x==0) *optr++='0';
    	if(x)
    	{
    		static char stack[100],*top;
    		for(top=stack;x;x/=10)
    			*top++=(x%10)+'0';
    		while(top!=stack)
    			*optr++=*--top;
    	}
    	*optr++='\n';
    }
    //IO end
    //LCA begin
    namespace fullgraph
    {
    	const int LOG=20;
    	struct Edge{int to,v,pre;}e[MAXN<<1];int id[MAXN],ec=0;
    	inline void Adde(int f,int t,int v)
    	{
    		if(!f || !t) return;//1 0...
    		e[++ec].to=t;e[ec].v=v;e[ec].pre=id[f];id[f]=ec;
    		e[++ec].to=f;e[ec].v=v;e[ec].pre=id[t];id[t]=ec;
    	}
    	int dep[MAXN],dis[MAXN],fa[MAXN][LOG];
    }
    inline void AddNode(int pos,int father,int c)
    {
    	using namespace fullgraph;
    	fa[pos][0]=father;
    	for(int j=1;j<=LOG-1;j++)
    		fa[pos][j]=fa[fa[pos][j-1]][j-1];
    	dep[pos]=dep[father]+1;
    	dis[pos]=dis[father]+c;
    	Adde(pos,father,c);
    }
    inline int LCA(int p1,int p2)
    {
    	using namespace fullgraph;
    	if(dep[p1]<dep[p2]) swap(p1,p2);
    	for(int j=LOG-1;~j;j--)
    		if(dep[fa[p1][j]]>=dep[p2]) p1=fa[p1][j];
    	if(p1==p2) return p1;
    	for(int j=LOG-1;~j;j--)
    		if(fa[p1][j]!=fa[p2][j]) p1=fa[p1][j],p2=fa[p2][j];
    	return fa[p1][0];
    }
    inline int Dist(int p1,int p2)
    {
    	using namespace fullgraph;
    	return dis[p1]+dis[p2]-2*dis[LCA(p1,p2)];
    }
    //LCA END
    //Treap BEGIN
    struct Treap
    {
    	struct TreapNode
    	{
    		TreapNode *son[2];
    		int key,v,sz,cnt;
    		TreapNode(){key=P;}
    		inline void up()
    		{
    			sz=cnt;
    			if(son[0]) sz+=son[0]->sz;
    			if(son[1]) sz+=son[1]->sz;
    		}
    		inline int mkyson()
    		{
    			if(!son[0] && !son[1]) return -1;
    			else return (son[0]?son[0]->key:P)<(son[1]?son[1]->key:P)?0:1;
    		}
    	};
    	static queue<TreapNode*> trash;
    	TreapNode *root;
    	Treap(){root=0;}
    	inline int size(){return root?root->sz:0;}
    	inline TreapNode *newTreapNode(int v)
    	{
    		static TreapNode *cur,*ME=new TreapNode[MAXN<<5],*END=ME+(MAXN<<5);
    		//if(0)
    		if(!trash.empty())
    		{
    			cur=trash.front();
    			trash.pop();
    		}
    		else
    		{
    			if(ME==END)
    				END=(ME=new TreapNode[MAXN<<5])+(MAXN<<5);
    			cur=++ME;
    		}
    		cur->son[0]=cur->son[1]=0;
    		cur->key=rand()%P;cur->v=v;cur->cnt=cur->sz=1;
    		return cur;
    	}
    	inline void deleteTreapNode(TreapNode *cur){trash.push(cur);}
    	inline void trans(TreapNode *&pos,int d)
    	{
    		TreapNode *s=pos->son[d];
    		pos->son[d]=s->son[!d];
    		s->son[!d]=pos;
    		pos->up(),s->up();
    		pos=s;
    	}
    	inline int adjust(TreapNode *&pos)
    	{
    		int mks=pos->mkyson();
    		if((~mks) && pos->key>pos->son[mks]->key)
    		{
    			trans(pos,mks);
    			return !mks;
    		}
    		else return -1;
    	}
    	void Insert(TreapNode *&pos,int v)
    	{
    		if(pos==0) pos=newTreapNode(v);
    		else if(pos->v==v) pos->cnt++,pos->up();//pos->up....??.
    		else
    		{
    			Insert(pos->son[pos->v<v],v),pos->up();
    			adjust(pos);
    		}
    	}
    	inline void Insert(int v){Insert(root,v);}
    	inline int Rnk(int v)//返回不含等于的
    	{
    		TreapNode *pos=root;
    		int res=0;
    		while(pos)
    		{
    			if(pos->v<v)
    			{
    				res+=(pos->son[0]?pos->son[0]->sz:0)+pos->cnt;
    				pos=pos->son[1];
    			}
    			else pos=pos->son[0];
    		}
    		return res;
    	}
    	inline int Access(int v){return size()-Rnk(v);}
    	void clear(TreapNode *&pos)
    	{
    		if(!pos) return;
    		clear(pos->son[0]);
    		clear(pos->son[1]);
    		deleteTreapNode(pos);
    		pos=0;
    	}
    	inline void Clear(){clear(root);}
    };
    queue<Treap::TreapNode*> Treap::trash;
    //Treap END
    //DC BEGIN
    struct DynamicTree
    {
    	static const double lambda=0.88;
    	struct DyNode
    	{
    		Treap rec,anti;
    		set<int> son;
    		int orgroot,node;
    		inline int size(){return rec.size();}
    		//只需检测每次添加了节点的分支。
    	}*tree[MAXN];
    	static queue<DyNode*> recv;
    	inline DyNode *newDyNode(int node,int root)
    	{
    		DyNode *cur;
    		if(!recv.empty()) 
    			cur=recv.front(),recv.pop();
    		else
    		{
    			static DyNode *ME=new DyNode[MAXN<<1];
    			cur=++ME;
    		}
    		cur->node=node;
    		cur->orgroot=root;
    		cur->son.clear();
    		cur->rec.Clear();
    		cur->anti.Clear();
    		return cur;
    	}
    	inline void deleteDyNode(DyNode *cur){recv.push(cur);}

    	int f[MAXN],sz[MAXN],tol,uplayer[MAXN];
    	void calcsize(int pos,int from)
    	{
    		using namespace fullgraph;
    		sz[pos]=1;
    		for(int i=id[pos];i;i=e[i].pre)
    		{
    			int u=e[i].to;
    			if(u==from || tree[u]) continue;
    			calcsize(u,pos);
    			sz[pos]+=sz[u];
    		}
    	}
    	int DP(int pos,int from)
    	{
    		using namespace fullgraph;
    		int rs=pos,mi=-1;f[pos]=0;
    		for(int i=id[pos];i;i=e[i].pre)
    		{
    			int u=e[i].to;
    			if(u==from || tree[u]) continue;
    			rs=DP(u,pos);
    			mi=(mi==-1 || f[mi]>f[rs])?rs:mi;
    			chkmx(f[pos],sz[u]);
    		}
    		chkmx(f[pos],tol-sz[pos]);
    		return (mi==-1 || f[mi]>f[pos])?pos:mi;
    	}
    	inline int GC(int root)
    	{
    		using namespace fullgraph;
    		calcsize(root,0);
    		tol=sz[root];
    		return DP(root,0);
    	}

    	void filltreap(int pos,Treap &cur,int from,int dist)
    	{
    		using namespace fullgraph;
    		cur.Insert(r[pos]-dist);
    		for(int i=id[pos];i;i=e[i].pre)
    		{
    			int u=e[i].to;
    			if(u==from || tree[u]) continue;
    			filltreap(u,cur,pos,dist+e[i].v);
    		}
    	}
    	int DC(int origin,int from)
    	{
    		using namespace fullgraph;
    		Treap temp;
    		if(from) 
    			filltreap(origin,temp,from,Dist(origin,from));//origin and from gotta be father son
    		int gc;DyNode *cur=newDyNode(gc=GC(origin),origin);
    		tree[gc]=cur;
    		uplayer[gc]=from;
    		cur->anti=temp;
    		cur->rec.Insert(r[gc]);
    		for(int i=id[gc];i;i=e[i].pre)
    		{
    			int u=e[i].to;
    			if(u==from || tree[u]) continue;
    			filltreap(u,cur->rec,gc,e[i].v);
    			cur->son.insert(DC(u,gc));
    		}
    		return gc;
    	}
    	void recycle(DyNode *&cur)
    	{
    		for(set<int>::iterator it=cur->son.begin();it!=cur->son.end();++it)
    			recycle(tree[*it]);
    		deleteDyNode(cur);
    		cur=0;
    	}
    	inline int Rebuild(int pos)
    	{
    		int up=uplayer[pos],org=tree[pos]->orgroot;
    		if(up) tree[up]->son.erase(pos);
    		recycle(tree[pos]);
    		int cur=DC(org,up);
    		if(up) tree[up]->son.insert(cur); 
    		return cur;
    	}
    	void Insert(int pos,int father)
    	{
    		DyNode *cur=newDyNode(pos,pos);
    		tree[pos]=cur;
    		if(father)
    			tree[father]->son.insert(pos);
    		uplayer[pos]=father;
    		int reb=0;
    		for(int i=pos,pre=0;i;pre=i,i=uplayer[i])
    		{
    			int d=Dist(pos,i);
    			last+=tree[i]->rec.Access(d-r[pos]);
    			tree[i]->rec.Insert(r[pos]-d);
    			if(pre)
    			{
    				last-=tree[pre]->anti.Access(d-r[pos]);
    				tree[pre]->anti.Insert(r[pos]-d);
    			}
    			if(pre && ( ((double)tree[pre]->size()/tree[i]->size()) >lambda)) 
    				reb=i;
    		}
    		if(reb)
    			Rebuild(reb);
    	}
    }Tree;
    queue<DynamicTree::DyNode*> DynamicTree::recv;
    //DC END
    void Adjust(int pos,int father,int c)
    {
    	AddNode(pos,father,c);
    	Tree.Insert(pos,father);
    }
    int main()
    {
    	srand(0x1f1f1f1f);
    	int n;red(n),red(n);
    	const int P=1e9;
    	for(int i=1;i<=n;i++)
    	{
    		int a,c;red(a),red(c),red(r[i]);
    		a=a^(last%P);
    		Adjust(i,a,c);
    		white(last);
    	}
    	fwrite(outbuf,1,optr-outbuf,stdout);
    	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
//Code by Lucida
#include<bits/stdc++.h>
#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=50000+10;
using std::sort;

typedef double ld;
ld eps=1e-7;
int fcmp(ld x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
struct point
{
	ld x,y;
	point(){}
	point(ld _x,ld _y):x(_x),y(_y){}
};
typedef point vec;
vec operator-(vec a,vec b){return vec(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
{
	ld k,b;int id;
	line(){}
	line(ld _k,ld _b):k(_k),b(_b){}
	bool operator <(const line &a)const
	{
		if(k!=a.k) return k<a.k;
		return b>a.b;
	}
};
bool cmp(const line &a,const line &b){return a.id<b.id;}
bool onleft(point a,line l){return fcmp(outer(a-point(0,l.b),vec(1,l.k)))<0;}
point cross(line a,line b)
{
	point o;o.x=-(a.b-b.b)/(a.k-b.k);
	o.y=a.k*o.x+a.b;
	return o;
}
int main()
{
//freopen("input","r",stdin);
	static line l[MAXN];
	int n;red(n);
	for(int i=1;i<=n;i++)
		fred(l[i].k),fred(l[i].b),l[i].id=i;
	sort(l+1,l+1+n);
	static line S[MAXN];
	int top=0;
	for(int i=1;i<=n;i++)
	{
		if(fcmp(S[top].k-l[i].k)==0) continue;
		while(top>1 && !onleft(cross(S[top-1],S[top]),l[i])) top--;
		S[++top]=l[i];
	}
	sort(S+1,S+1+top,cmp);
	for(int i=1;i<=top;i++) printf("%d ",S[i].id); 
	puts("");
	return 0;
}

套模板

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
//Code by Lucida
#include<bits/stdc++.h>
#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=50000+1;
using std::sort;
 
typedef double ld;
ld eps=1e-7;
int fcmp(ld x)
{
    if(-eps<x && x<eps) return 0;
    return x<0?-1:1;
}
struct point
{
    ld x,y;
    point(){}
    point(ld _x,ld _y):x(_x),y(_y){}
};
typedef point vec;
vec operator-(vec a,vec b){return vec(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
{
    ld k,b;int id;
    line(){}
    line(ld _k,ld _b):k(_k),b(_b){}
    bool operator <(const line &a)const
    {
        if(k!=a.k) return k<a.k;
        return b<a.b;
    }
};
bool cmp(const line &a,const line &b){return a.id<b.id;}
bool onleft(point a,line l){return fcmp(outer(a-point(0,l.b),vec(1,l.k)))<0;}
point cross(line a,line b)
{
    point o;o.x=-(a.b-b.b)/(a.k-b.k);
    o.y=a.k*o.x+a.b;
    return o;
}
int main()
{
    //freopen("input","r",stdin);
    static line l[MAXN];
    int n;red(n);
    for(int i=1;i<=n;i++)
        fred(l[i].k),fred(l[i].b),l[i].id=i;
    sort(l+1,l+1+n);
    static line Ql[MAXN];
    static point Qp[MAXN];
    int head,tail;
    Ql[head=tail=1]=l[1];
    #define count(x,y) (y-x+1)
    for(int i=2;i<=n;i++)
    {
        while(count(head,tail)>=2 && !onleft(Qp[tail-1],l[i])) 
            tail--;
        while(count(head,tail)>=2 && !onleft(Qp[head],l[i])) 
            head++;
        Ql[++tail]=l[i];
        if(fcmp(Ql[tail-1].k-Ql[tail].k)==0)
        {
            tail--;
            if(fcmp(l[i].b-Ql[tail].b)>0) 
                Ql[tail]=l[i];
        }
        if(count(head,tail)>=2) 
            Qp[tail-1]=cross(Ql[tail-1],Ql[tail]);
    }
    while(count(head,tail)>=2 && !onleft(Qp[tail-1],Ql[head])) tail--;
    #undef count
    sort(Ql+head,Ql+tail+1,cmp);
    for(int i=head;i<=tail;i++) printf("%d ",Ql[i].id);
    puts("");
    return 0;
}

发表于 | 更新于

Link

Solution

Simpson积分，拟合二次函数曲线。 公式为(r−l)(f(l)+f(r)+4f(mid))6\frac {(r-l)(f(l)+f(r)+4f(mid))}{6} 涉及圆的公切线的求法，要用到一点点平面几何。

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
106
107
//Code by Lucida
#include<bits/stdc++.h>
#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::swap;
const int MAXN=500+1;
const ld eps=1e-6,pi=acos(-1.0),INF=1e100;
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);}
    void operator +=(vec a){x+=a.x,y+=a.y;}
    void operator -=(vec a){x-=a.x,y-=a.y;}
    void operator /=(ld a){x/=a,y/=a;}
    void operator *=(ld a){x*=a,y*=a;}
    bool operator ==(vec a){return x==a.x && y==a.y;}
	bool operator <(vec a){if(x!=a.x) return x<a.x;return y<a.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 circle
{
	ld x,r;
	circle(){}
	circle(ld _x,ld _r):x(_x),r(_r){}
	bool cover(circle a){return fcmp(abs(x-a.x)+a.r-r)<=0;}
}c[MAXN];
struct line
{
	point a;vec v;
	line(){}
	line(point _a,vec _v):a(_a),v(_v){}
}le[MAXN];
int n;
ld f(ld x)
{
	ld res=0;
	for(int i=1;i<=n;i++)
	{
		if(fcmp(c[i].x-c[i].r-x)<0 && fcmp(c[i].x+c[i].r-x)>0)
			chkmx(res,sqrt(sqr(c[i].r)-sqr(x-c[i].x)));
		point p=le[i].a,q=le[i].a+le[i].v;
		//if(p>q) swap(p,q);
		if(fcmp(p.x-x)<0 && fcmp(x-q.x)<0)
			chkmx(res,p.y+(x-p.x)/(q.x-p.x)*(q.y-p.y));
	}
	return res;
}
ld Simpson(ld l,ld r,ld lv,ld rv,ld mv){return (r-l)*(lv+rv+4*mv)/6;}
ld calc(ld l,ld r,ld lv,ld rv)
{
	ld mid=(l+r)/2,mv=f(mid),res;
	if(fcmp((res=Simpson(l,r,lv,rv,mv))-Simpson(l,mid,lv,mv,f((l+mid)/2))-Simpson(mid,r,mv,rv,f((mid+r)/2))))
		res=calc(l,mid,lv,mv)+calc(mid,r,mv,rv);
	return res;
}

line comtan(circle a,circle b)
{
	if(a.cover(b) || b.cover(a))
		return line(point(0,0),vec(1,0));
	if(a.x>b.x) swap(a,b);//necs
	point p,q;
	p.x=(a.r-b.r)/abs(a.x-b.x)*a.r,p.y=sqrt(sqr(a.r)-sqr(p.x));
	q.x=b.r/a.r*p.x,q.y=b.r/a.r*p.y;
	p.x+=a.x,q.x+=b.x;
	return line(p,q-p);
}
int main()
{
	static ld h[MAXN],ra[MAXN];
	//freopen("input","r",stdin);
	ld alpha;
	red(n),fred(alpha);
	alpha=1.0/tan(alpha);
	n++;
	for(int i=1;i<=n;i++) fred(h[i]),h[i]*=alpha,h[i]+=h[i-1];
	for(int i=1;i<n;i++) fred(ra[i]);ra[n]=0;
	ld l=INF,r=-INF;
	for(int i=1;i<=n;i++)
	{
		c[i]=circle(h[i],ra[i]);
		chkmn(l,h[i]-ra[i]);
		chkmx(r,h[i]+ra[i]);
	}
	for(int i=1;i<n;i++)
		le[i]=comtan(c[i],c[i+1]);
	printf("%.2lf\n",calc(l,r,f(l),f(r))*2);
	return 0;
}

发表于 | 更新于

Link

Notice

如果谁能证明O(N)O(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
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
//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;}
const int MAXN=50000+10;
using std::swap;
using std::sort;
typedef double ld;
const ld eps=1e-7,pi=acos(-1.0);
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);}
    void operator +=(vec a){x+=a.x,y+=a.y;}
    void operator -=(vec a){x-=a.x,y-=a.y;}
    void operator /=(ld a){x/=a,y/=a;}
    void operator *=(ld a){x*=a,y*=a;}
    bool operator ==(vec a){return 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);}
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(const point &a,const point &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)
{
	int mi=1;
	for(int i=1;i<=n;i++)
		if(p[mi].x<p[i].x || (p[mi].x==p[i].x && p[mi].y<p[i].y)) mi=i;
	swap(p[mi],p[1]);p[0]=p[1];
	for(int i=1;i<=n;i++) p[i]-=p[0];
	sort(p+2,p+1+n,cmp);
	for(int i=1;i<=n;i++) p[i]+=p[0];
	static point Sp[MAXN];
	int top=0;
	p[n+1]=p[1];
	for(int i=1;i<=n+1;i++)
	{
		while(top>=2 && fcmp(outer(p[i]-Sp[top],Sp[top]-Sp[top-1]))>=0) top--;
		Sp[++top]=p[i];
	}
	top--;
	for(int i=1;i<=top;i++) p[i]=Sp[i];
	n=top;
}
ld dist(point a,line l){return abs(outer(a-l.a,l.v))/l.v.norm();}
void WORK(int n)
{
	static point p[MAXN];
	for(int i=1;i<=n;i++)
		fred(p[i].x),fred(p[i].y);
	Graham(p,n);
	ld ANS=-1;
	#define suc(x) (x+1>n?1:x+1)
	for(int i=1;i<=n;i++)
		for(int j=suc(i),cur=j;j!=i;j=suc(j))
		{
			line l=line(p[i],p[j]-p[i]);
			while(fcmp(dist(p[suc(cur)],l)-dist(p[cur],l))>0) cur=suc(cur);
			chkmx(ANS,l.v.norm()*dist(p[cur],l));
		}
	#undef suc
	printf("%.2f\n",ANS/2);
}
int main()
{
	freopen("input","r",stdin);
	int n;while(red(n),~n) WORK(n);
	return 0;
}

发表于 | 更新于

Link

Solution

so that the longest distance between xiaomi's home and the other groundhog's home is minimum.

二分答案？然而二分之后有什么用呢？ 注意到，选取一个点，要让平面内所有点到它的距离最近，转化一下，不就是最小覆盖圆吗。。

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
//Code by Lucida
#include<bits/stdc++.h>
#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=1000+10;
using std::max_element;
using std::random_shuffle;

ld dist(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
bool parl(vec a,vec b){return fcmp(outer(a,b))==0;}
struct line
{
	point a;vec v;
	line(point _a,vec _v):a(_a),v(_v){}
};
point cross(line a,line b){return a.a+a.v*outer(a.a-b.a,b.v)/outer(b.v,a.v);}
vec rotate(vec a,ld rad){return vec(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
point excenter(point a,point b,point c)
{
	if(parl(b-a,c-a))
	{
		ld lens[]={dist(a,b),dist(a,c),dist(b,c)};
		switch(max_element(lens,lens+3)-lens)
		{
			case 0:return (a+b)/2;break;
			case 1:return (a+c)/2;break;
			case 2:return (b+c)/2;break;
		}
	}
	else return cross(line((a+b)/2,rotate(b-a,pi/2)),line((a+c)/2,rotate(c-a,pi/2)));
}
void WORK(int n)
{
	static point p[MAXN];
	for(int i=1;i<=n;i++) fred(p[i].x),fred(p[i].y);
	random_shuffle(p+1,p+1+n);
	point O=p[1];ld r=0;
	for(int i=2;i<=n;i++)
	{
		if(fcmp(dist(O,p[i])-r)>0)
		{
			O=p[i],r=0;
			for(int j=1;j<i;j++)
			{
				if(fcmp(dist(O,p[j])-r)>0)
				{
					O=(p[i]+p[j])/2,r=dist(p[i],p[j])/2;
					for(int k=1;k<j;k++)
					{
						if(fcmp(dist(O,p[k])-r)>0)
						{
							O=excenter(p[i],p[j],p[k]);
							r=dist(O,p[i]);
						}
					}
				}
			}
		}
	}
	printf("(%.1lf,%.1lf).\n%.1f\n",O.x,O.y,r);
}
int main()
{
	freopen("input","r",stdin);
	int x,y,n;
	while((~red(x)) && (~red(y)) && (~red(n))) WORK(n);

	return 0;
}

发表于 | 更新于

Link

Solution

要让两个圆覆盖的面积最大，而且不能与边相交。 于是，将凸包上的边内移半径长度，然后求半平面交，得到的区域就是圆心可以存在的区域。 贪心地选择两个最远的点。（在边上肯定不如在点上远？），旋转卡壳。 旋转卡壳比O(n2)O(n^2)枚举慢？？常数大？ 貌似，求单位法向量， 内移求内核是个常见的套路。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//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;}
const int MAXN=100+1;
using std::reverse;
using std::pair;
using std::sort;
using std::make_pair;
typedef double ld;
const ld eps=1e-7,pi=acos(-1.0);
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);}
    bool operator <(vec a)
    {
        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;}
    void operator /=(ld a){x/=a,y/=a;}
    void operator *=(ld a){x*=a,y*=a;}
    bool operator ==(vec a){return x==a.x && y==a.y;}
	vec normal();
};
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;}
vec rotate(vec a,ld rad){return vec(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
vec vec::normal()
{
	vec nm=rotate(*this,pi/2);
	nm/=nm.norm();
	return nm;
}
struct line
{
	point a;vec v;ld angle;
	line(){}
	line(point _a,vec _v):a(_a),v(_v){angle=atan2(v.y,v.x);}
	bool operator <(const line &a)const{return angle<a.angle;}
};
bool parl(line a,line b){return fcmp(outer(a.v,b.v))==0;}
bool onleft(point a,line b){return fcmp(outer(b.v,a-b.a))>=0;}//>=?
point cross(line a,line b){return a.a+a.v*outer(a.a-b.a,b.v)/outer(b.v,a.v);}
int intersect(line *l,int n,point *tio)
{
	sort(l+1,l+1+n);
	static point Qp[MAXN];
	static line Ql[MAXN];
	int head,tail;
	Ql[head=tail=1]=l[1];
	#define count(x,y) (y-x+1)
	for(int i=2;i<=n;i++)
	{
		while(count(head,tail)>=2 && !onleft(Qp[tail-1],l[i])) tail--;
		while(count(head,tail)>=2 && !onleft(Qp[head],l[i])) head++;
		Ql[++tail]=l[i];
		if(parl(Ql[tail-1],Ql[tail]))
		{
			tail--;
			if(onleft(l[i].a,Ql[tail])) Ql[tail]=l[i];
		}
		if(count(head,tail)>=2) Qp[tail-1]=cross(Ql[tail-1],Ql[tail]);
	}
	while(count(head,tail)>=2 && !onleft(Qp[tail-1],Ql[head])) tail--;
	Qp[tail]=cross(Ql[head],Ql[tail]);
	for(int i=head;i<=tail;i++) *++tio=Qp[i]; 
	return count(head,tail);
	#undef count
}
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();}
pair<point,point> caliper(point *p,int n)
{
	pair<point,point> pa;
	ld ANS=-1;
	#define suc(i) (i+1>n?1:i+1)
	for(int i=1,cur=2;i<=n;i++)
	{
		line now=line(p[i],p[suc(i)]-p[i]);
		while(fcmp(dist(p[cur],now)-dist(p[suc(cur)],now))<0) cur=suc(cur);
		if(chkmx(ANS,dist(p[cur],p[i]))) pa=make_pair(p[cur],p[i]);
		if(chkmx(ANS,dist(p[cur],p[suc(i)]))) pa=make_pair(p[cur],p[suc(i)]);
	}
	return pa;
	#undef suc
	/*
	pair<point,point> pa;
	ld res=-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(chkmx(res,dist(p[i],p[j])))
				pa=make_pair(p[i],p[j]);
	return pa;*/
}
int main()
{
	freopen("input","r",stdin);
	static point p[MAXN];
	static line l[MAXN];
	int n;red(n);
	ld r;fred(r);
	for(int i=1;i<=n;i++) fred(p[i].x),fred(p[i].y);
	reverse(p+1,p+1+n);
	for(int i=1;i<=n;i++) l[i]=line(p[i],vec(p[i+1>n?1:i+1]-p[i]));
	for(int i=1;i<=n;i++) l[i].a+=l[i].v.normal()*r;
	n=intersect(l,n,p);
	pair<point,point> ANS=caliper(p,n);
	printf("%.4f %.4f %.4f %.4f",ANS.first.x,ANS.first.y,ANS.second.x,ANS.second.y);
	return 0;
}

发表于 | 更新于

Link

Solution

找一个半径最大的内切圆。 二分r，将凸包上的边向内移动，求半平面交看是否为空。 移动边的时候比较巧妙，用到了单位法向量。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//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;}
const int MAXN=100+1;
typedef double ld;
using std::sort;
const ld eps=1e-7,undefined=1e250,pi=acos(-1.0);
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);}
	bool operator <(vec a)
	{
		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;}
	void operator /=(ld a){x/=a,y/=a;}
	void operator *=(ld a){x*=a,y*=a;}
	bool operator ==(vec a){return 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);}
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;}
vec rotate(vec a,ld rad){return vec(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
struct line
{
	point a;vec v;
	ld angle;
	line(){}
	line(point _a,vec _v):a(_a),v(_v){angle=atan2(v.y,v.x);}
	vec norm()
	{
		vec normal=rotate(v,pi/2);
		normal/=normal.norm();
		return normal;
	}
	bool operator<(const line &a)const {return angle<a.angle;}
}il[MAXN];
bool onleft(point a,line l){return fcmp(outer(l.v,a-l.a))>=0;}//在左或者在上
bool parl(line a,line b){return fcmp(outer(a.v,b.v))==0;}
point cross(line l1,line l2)
{
	vec v=l1.a-l2.a;
	ld t=outer(v,l2.v)/outer(l2.v,l1.v);
	return l1.a+l1.v*t;
}
int n;
int intersect(line *l,point *tio)
{
	sort(l+1,l+1+n);
	static point Qp[MAXN];
	static line Ql[MAXN];
	int head=1,tail=0;
	Ql[++tail]=l[1];
	#define count(x,y) (y-x+1)
	for(int i=2;i<=n;i++)
	{
		while(count(head,tail)>=2 && !onleft(Qp[tail-1],l[i])) tail--;
		while(count(head,tail)>=2 && !onleft(Qp[head],l[i])) head++;
		Ql[++tail]=l[i];
		if(parl(Ql[tail-1],Ql[tail]))
		{
			tail--;
			if(onleft(l[i].a,Ql[tail]))
				Ql[tail]=l[i];
		}
		if(count(head,tail)>=2) Qp[tail-1]=cross(Ql[tail-1],Ql[tail]);
	}
	while(count(head,tail)>=2 && !onleft(Qp[tail-1],Ql[head])) tail--;
	if(count(head,tail)<2) return 0;
	Qp[tail]=cross(Ql[head],Ql[tail]);
	int tol=0;
	for(int i=head;i<=tail;i++) tio[++tol]=Qp[i];
	return tol;
	#undef count
}
bool check(ld r)
{
	static line tr[MAXN];
	for(int i=1;i<=n;i++) tr[i]=il[i];
	for(int i=1;i<=n;i++)
		tr[i].a+=tr[i].norm()*r;
	static point tio[MAXN];
	int tol=intersect(tr,tio);
	return tol>2;
}
void WORK()
{
	static point p[MAXN];
	for(int i=1;i<=n;i++)
		fred(p[i].x),fred(p[i].y);
	for(int i=1;i<=n;i++)
		il[i]=line(p[i],p[i+1>n?1:i+1]-p[i]);
	ld L=0,R=1e10;
	while(fcmp(R-L))
	{
		ld MID=(L+R)/2;
		if(check(MID))
			L=MID;
		else
			R=MID;
	}
	printf("%.7lf\n",L);
}
int main()
{
	freopen("input","r",stdin);
	while(red(n),n) WORK();
	return 0;
}

发表于 | 更新于

Link

Solution

旋转卡壳

Tips

注意判断的条件和卡的时候的逻辑。 按照DavidLee的这种写法必须要正卡再反卡。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
//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;}
const int MAXN=10000+10;
typedef double ld;
const ld eps=1e-7,INF=1e100;
using std::unique;
using std::sort;
using std::swap;
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);}
	bool operator <(vec a)
	{
		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 ==(vec a){return 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);}
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;}
ld dist(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.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,AC=l.a+l.v-a,BC=l.v;
	point A=a,B=l.a,C=l.a+l.v;
	if(fcmp(inner(BC,-AB))<0) return dist(A,B);
	else if(fcmp(inner(-AC,-BC))<0) return dist(A,C);
	else return abs(outer(AB,BC))/BC.norm();
}
ld caliper(point *p1,int n1,point *p2,int n2)
{
	int c1=1,c2=1;
	for(int i=1;i<=n1;i++) if(p1[i].y<p1[c1].y) c1=i;
	for(int i=1;i<=n2;i++) if(p2[i].y<p2[c2].y) c2=i;
	#define suc(x,n) (x+1>n?1:x+1)
	ld res=INF;
	for(int loop=1;loop<=n1;loop++,c1=suc(c1,n1))
	{
		while(fcmp(outer(p1[suc(c1,n1)]-p1[c1],p2[suc(c2,n2)]-p2[c2]))>0)
			c2=suc(c2,n2);
		line now=line(p1[c1],p1[suc(c1,n1)]-p1[c1]);
		chkmn(res,dist(p2[c2],now));
		chkmn(res,dist(p2[suc(c2,n2)],now));
	}
	#undef suc
	return res;
}
bool cmp(vec a,vec b)
{
	if(outer(a,b)!=0)
		return outer(a,b)>0;
	return inner(a,a)<inner(b,b);
}
void Graham(point *p,int n)
{
	static point stack[MAXN];int top=0;
	int mi=1;
	for(int i=1;i<=n;i++)
		if(p[i]<p[mi]) mi=i;
	p[0]=p[mi];swap(p[mi],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;
	for(int i=1;i<=n;i++) p[i]+=p[0];
	p[n+1]=p[1];
	for(int i=1;i<=n+1;i++)
	{
		while(top>=2 && fcmp(outer(p[i]-stack[i],stack[i]-stack[i-1]))>=0) top--;
		stack[++top]=p[i];
	}
	n=top-1;
	for(int i=1;i<=n;i++) p[i]=stack[i];
}
void WORK(int n1,int n2)
{
	static point p1[MAXN],p2[MAXN];
	for(int i=1;i<=n1;i++) fred(p1[i].x),fred(p1[i].y);
	for(int i=1;i<=n2;i++) fred(p2[i].x),fred(p2[i].y);
	Graham(p1,n1);
	Graham(p2,n2);
	ld ANS=INF;
	chkmn(ANS,caliper(p1,n1,p2,n2));
	chkmn(ANS,caliper(p2,n2,p1,n1));
	printf("%.5lf\n",ANS);
}
int main()
{
	freopen("input","r",stdin);
	int n1,n2;
	while(red(n1),red(n2),n1 && n2)
		WORK(n1,n2);
	return 0;
}