SDOI 2011

发表于 | 更新于

好几天才做完这几道题。。效率贼低。。还有一个插头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;
}