发表于 | 更新于

Link

什么鬼题，做完了整个人都方了。。 正方形可以斜着！可以斜着！可以斜着！

Solution

容斥自不必说。。。 考虑“太难了”的问题，K=0K=0怎么做？ 对于每个正方形，不管它怎么斜，肯定对应着唯一一个正好套着它的、与坐标轴平行的正方形，称之为框架(Framework)。每个边长为lenlen的框架，肯定包含着恰好lenlen个以它为框架的正方形。所以只要枚举每种长度的框架有几个，就可以得到答案。 那么剩下的，对应着正方形上有几个被删除的点，就有四种情况。 至少删除二三四个的情况，一个O(n2)O(n^2)枚举，都很好说。 只剩下经过至少一个被删除的点的情况。 O(n)O(n)地枚举必然被删除的那个点，剩下的问题就是统计有多少个正方形以这个点为一个角。 然后，由于一个正方形有唯一的框架；一个框架上每个点只是一个正方形的角。所以，以一个点为角的正方形数==经过这个点的框架数 然后问题转化成求经过一个点的、与坐标轴平行的正方形数。 可以把平面分成四个形如阴影的部分，然后把四部分答案相加，再把重合部分的减一下。 现在问题转化为 经过一个数轴上定点，并且处于一段固定长度的区间内，且有边长限制的正方形个数。 先考虑简化的版本：如果没有固定长度的限制怎么做？ 显然，枚举每种长度，并且在数轴上滑一滑，可以得到总和为2+3+4+...+(h+1)2+3+4+...+(h+1)(hh为边长限制) 现在考虑超出数轴边界的。只考虑超出左边界的，右边界差不多。 只有边长超过p−1p-1的才会超出数轴边界，边长为pp，会被截去11个。边长为p+1p+1，会被截去22个。求出有多少种边长超出了限制，就可以用求和公式计算对答案的贡献了。

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
#include "lucida"
typedef unsigned long long qword;
const int MAXN=2000+11,MAXL=1e6+11,P=1e8+7;
const double eps=1e-6;
double fcmp(const double &x) {
	return -eps<x && x<eps?0:(x<0?-1:1);
}
using std::fill;
using std::min;
int64 Sum(int64 n) {
	return (n*(n+1)/2)%P;
}
template <class T>
qword Hash(const T &x) {
	return x;
}
namespace hashset {
	struct Node {
		qword key;
		Node *pre;
		Node(qword key,Node *pre):key(key),pre(pre) {}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN);
			return Me++;
		}
	};
	template <class T,int Modu>
	struct HashSet {
		Node **id;
		HashSet() {
			id=alloc(Node*,Modu);
			memset(id,0,Modu*sizeof(Node*));
		}
		void Insert(const T &x) {
			qword hcode=Hash(x);
			int bucket=hcode%Modu;
			id[bucket]=new Node(hcode,id[bucket]);
		}
		bool Find(const T &x) {
			qword hcode=Hash(x);
			for(Node *p=id[hcode%Modu];p;p=p->pre) {
				if(p->key==hcode) {
					return 1;
				}
			}
			return 0;
		}
	};
}using hashset::HashSet;
int n,m;
struct point {
	int x,y;
	point() {}
	point(int x,int y):x(x),y(y) {}
	bool inside() {
		return 1<=x && x<=n && 1<=y && y<=m;
	}
	friend point operator +(const point &a,const point &b) {
		return point(a.x+b.x,a.y+b.y);
	}
	friend point operator -(const point &a,const point &b) {
		return point(a.x-b.x,a.y-b.y);
	}
};
typedef point vector;
template <>
qword Hash<point>(const point &p) {
	return ((qword)p.x-1)*(1e6+1)+p.y;
}
vector Rotate(const vector &a,const int &dir) {
	return vector(-a.y*dir,a.x*dir);
}
point p[MAXN];
HashSet<point,99929> set;
int64 All() {
	int64 res=0;
	for(int64 i=1,ei=min(n,m);i<=ei;++i) {
		(res+=i*(n-i)*(m-i))%=P;
	}
	return res;
}
int64 SquareCount(int64 p,int64 l,int64 h) {
	chkmn(h,l-1);
	int64 res=(Sum(h+1)-1),c;
	res-=(c=h-p+1)>0?Sum(c):0;
	res-=(c=p+h-l)>0?Sum(c):0;
	return res%P;
}
int64 CoverCount(point p) {
	int64 res=SquareCount(p.y,m,n-p.x)
			 +SquareCount(p.x,n,m-p.y)
			 +SquareCount(p.y,m,p.x-1)
			 +SquareCount(p.x,n,p.y-1)
			 -min(n-p.x,p.y-1)
			 -min(p.y-1,p.x-1)
			 -min(p.x-1,m-p.y)
			 -min(m-p.y,n-p.x);
	return res%P;
}
int Check(point a,point b,int dir) {
	int res=-1;point c(0,0),d(0,0);
	if(dir) {
		c=a+Rotate(b-a,dir),d=b+Rotate(a-b,-dir);
	} else {
		vector normal=Rotate(b-a,1);
		double cx=(a.x+b.x)/2.0,cy=(a.y+b.y)/2.0;
		double dx=normal.x/2.0,dy=normal.y/2.0;
		c=point(cx-dx+0.5,cy-dy+0.5),d=point(cx+dx+0.5,cy+dy+0.5);
		if(fcmp(c.x-(cx-dx)) || fcmp(c.y-(cy-dy))) {//判合法!!
			c=point(0,0);
		}
		if(fcmp(d.x-(cx+dx)) || fcmp(d.y-(cy+dy))) {
			d=point(0,0);
		}
	}
	if(c.inside() && d.inside()) {
		res++;
		res+=set.Find(c);
		res+=set.Find(d);
	}
	return res;
}
int main() {
	freopen("input","r",stdin);
	int K;is>>n>>m>>K;++n,++m;
	for(int i=1;i<=K;++i) {
		is>>p[i].x>>p[i].y;
		p[i].x++,p[i].y++;
		set.Insert(p[i]);
	}
	int64 res[5]={0,0,0,0,0};
	res[0]=All();
	for(int i=1;i<=K;++i) {
		(res[1]+=CoverCount(p[i]))%=P;
		for(int j=1;j<=K;++j) if(i!=j) {
			for(int d=-1;d<=1;++d) {
				int dr=Check(p[i],p[j],d);
				res[2]+=dr>-1;
				res[3]+=dr>0?dr:0;
				res[4]+=dr==2;
			}
		}
	}
	int64 Ans=((res[0]-res[1]+res[2]/2-res[3]/6+res[4]/12)%P+P)%P;
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

震惊！某ZZ OIer此题WA了半天竟是因为点击查看

Solution

感觉第一步是最难想的。。但看了题解之后又觉得是很显然的。。只是不敢想罢了。 因为数字乘积的个数比较少，离散化一下就可以开到一维状态里。 然后一切都明朗了。 然而WA了很长时间，竟然因为

  1. 101210^{12}居然是1313位数？？？？？？
  2. 把数字分解的时候中间变量写成了int？？？？

Tips

数据范围吓人的但是似乎比较显然的算法也不能不想。因为也许吓人的范围后面隐藏着一些可以减小范围的性质。 在可能爆int的题目中WA了，试试 

1
#define int int64

不要数错数字位数。。。23333

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
#include "lucida"
using std::sort;
using std::unique;
using std::lower_bound;
using std::priority_queue;
const int P=1000000007,MAXCOUNT=203491+11,MAXINSCNT=11026+11;
int64 nums[MAXCOUNT];int nc;
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
void DFS(int pos,int maxNumber,int64 prod) {
	if(!pos) {
		nums[++nc]=prod;
	} else {
		for(int d=maxNumber;d<10;++d) {
			DFS(pos-1,d,prod*d);
		}
	}
}
void Prep() {
	nums[nc=1]=0;//数组开小愣是看不着 233
	DFS(13,1,1);
	sort(nums+1,nums+1+nc);
	nc=unique(nums+1,nums+1+nc)-nums-1;
}
struct Node {
	int64 val;
	int id,ext;
	Node(int64 val,int id,int ext):val(val),id(id),ext(ext) {}
	friend bool operator <(const Node &a,const Node &b) {
		return a.val<b.val;
	}
};
int main() {
	freopen("input","r",stdin);
	static int64 f[14][10][2][MAXINSCNT],g[MAXINSCNT];
	Prep();	
	int64 n;int K;is>>n>>K;
	//g[pos] 乘积为pos位置的个数
	int bit[14],len=0;
	for(int64 x=n;x;x/=10) {
		bit[++len]=x%10;
	}
	for(int d=1;d<=bit[len];++d) {
		f[len][d][d==bit[len]][ref(d)]=1;
	}
	for(int i=len-1;i;--i) {
		for(int d=1;d<10;++d) {
			f[i][d][0][ref(d)]=1;
		}
	}
	for(int i=len-1;i;--i) {
		for(int cd=1;cd<10;++cd) {
			for(int pd=1;pd<10;++pd) {
				for(int pu=0;pu<2;++pu) if(!(pu && bit[i]<cd)) {
					for(int prod=1;prod<=nc;++prod) if(f[i+1][pd][pu][prod]) {
						if(nums[ref(nums[prod]*cd)]!=nums[prod]*cd) {
							throw;
						}
						f[i][cd][pu && cd==bit[i]][ref(nums[prod]*cd)]+=f[i+1][pd][pu][prod];
					}
				}
			}
		}
	}
	for(int prod=2;prod<=nc;++prod) {
		for(int d=1;d<10;++d) {
			for(int u=0;u<2;++u) if(!(u && bit[1]<d)) {
				g[prod-1]+=f[1][d][u][prod];
			}
		}
	}
	nc--;
	sort(g+1,g+1+nc);
	priority_queue<Node> Q;
	for(int i=1;i<=nc;++i) {
		Q.push(Node(g[i]*g[nc],i,nc));
	}
	int64 Ans=0;
	for(int i=1;i<=K && !Q.empty();++i) {
		Node cur=Q.top();Q.pop();
		(Ans+=cur.val)%=P;
		if(cur.ext!=1) {
			Q.push(Node(g[cur.id]*g[cur.ext-1],cur.id,cur.ext-1));
		}
	}
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

感觉非常有意思啊

Solution

启发式合并的并查集树高O(logn)O(\log n)，那么直接在树上暴力LCA暴力最值就好啦。。。 之前还没见过这么玩的呢。。

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
#include "lucida"
using std::fill;
using std::swap;
const int MAXN=500000+11;
int fa[MAXN],val[MAXN],sz[MAXN];
int Root(int x) {
	while(fa[x]) {
		x=fa[x];
	}
	return x;
}
void Union(int x,int y,int id) {
	int rx=Root(x),ry=Root(y);
	if(rx!=ry) {
		if(sz[rx]<sz[ry]) {
			swap(rx,ry);
		}
		fa[ry]=rx;val[ry]=id;
		sz[rx]+=sz[ry];
	}
}
int LCA(int x,int y) {
	static int us[MAXN],ut;
	++ut;
	do us[x]=ut;
	while ((x=fa[x]));
	while(us[y]!=ut) {
		y=fa[y];
	}
	return y;
}
int Query(int x,int y) {
	if(Root(x)!=Root(y)) {
		return 0;
	} else {
		int lca=LCA(x,y),res=0;
		for(;x!=lca;x=fa[x]) {
			chkmx(res,val[x]);
		}
		for(;y!=lca;y=fa[y]) {
			chkmx(res,val[y]);
		}
		return res;
	}
}
int main() {
	freopen("input","r",stdin);
	int n,m;is>>n>>m;
	fill(sz+1,sz+1+n,1);
	int last=0,ec=0;
	for(int i=1;i<=m;++i) {
		int opt,u,v;
		is>>opt>>u>>v;
		u^=last;v^=last;
		if(opt==0) {
			Union(u,v,++ec);
		} else {
			last=Query(u,v);
			os<<last<<'\n';
		}
	}
	return 0;
}

发表于 | 更新于

Link

Solution

树的哈希什么的感觉还是很有意思呢 数据太小估计怎么搞搞都能过。。 另外有一个惊人的事实是一个树至多有22个重心。画个图似乎确实是的样子。。

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
#include "lucida"
using std::map;
using std::sort;
using std::pair;
typedef unsigned long long qword;
const int MAXN=60,INF=0x1f1f1f1f;
qword p3[MAXN];
struct _{_() {
	p3[0]=1;
	for(int i=1;i<MAXN;++i) {
		p3[i]=p3[i-1]*3;
	}
}}Auto;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN*MAXN<<1);
		return Me++;
	}
};
struct Tree {
	int n;Edge *G[MAXN];
	void Adde(int f,int t) {
		G[f]=new Edge(t,G[f]);
		G[t]=new Edge(f,G[t]);
	}
	void operator () (int f,int t) {
		Adde(f,t);
	}
	int sz[MAXN],f[MAXN];
	void preDFS(int pos,int from) {
		sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre) {
			if(e->to!=from) {
				int u=e->to;
				preDFS(u,pos);
				chkmx(f[pos],sz[u]);
				sz[pos]+=sz[u];
			}
		}
		chkmx(f[pos],n-sz[pos]);
	}
	pair<qword,int> Pool[MAXN][MAXN];
	qword DFS(int pos,int from) {
		pair<qword,int> *sh=Pool[pos];qword hash=1;
		int sc=0;sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre) {
			if(e->to!=from) {
				int u=e->to;
				sh[++sc]=pair<qword,int>(DFS(u,pos),sz[u]);
				sz[pos]+=sz[u];
			}
		}
		sort(sh+1,sh+1+sc);
		for(int i=1;i<=sc;++i) {
			(hash*=p3[sh[i].second+1])+=sh[i].first;
		}
		(hash*=3)+=2;
		return hash;
	}
	qword Hash() {
		preDFS(1,0);
		static int gc[MAXN],gcc;
		f[gc[gcc=0]=0]=INF;
		for(int i=1;i<=n;++i) {
			if(f[i]<f[gc[1]]) {
				gc[gcc=1]=i;
			} else if(f[i]==f[gc[1]]) {
				gc[++gcc]=i;
			}
		}
		assert(gcc<=2);
		qword res=0;
		for(int i=1;i<=gcc;++i) {
			chkmx(res,DFS(gc[i],0));
		}
		return res;
	}
}tr[MAXN];
int main() {
	freopen("input","r",stdin);		
	map<qword,int> record;
	int m;is>>m;
	for(int i=1;i<=m;++i) {
		is>>tr[i].n;
		for(int j=1;j<=tr[i].n;++j) {
			int fa;is>>fa;
			if(fa) tr[i](fa,j);
		}
		qword hash=tr[i].Hash();
		if(!record.count(hash)) {
			record[hash]=i;
		}
		os<<record[hash]<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

纸张居然连二分答案都搞不对

Solution

atk+k1a+dnf+k2b≤Midatk+k_1a+dnf+k_2b\le Mid dnf−k1b≥0dnf-k_1b\ge 0 atk−k2a≥0atk-k_2a\ge 0 带了一堆变量，然后需要用整体的思想 首先atk+k1aatk+k_1a取最值的时候dnf−k1b==0dnf-k_1b==0。另一个限制也一样。 所以变成了 atk+dnf×ab+dnf+atk×ba≤Midatk+\dfrac {dnf\times a}b+dnf+\dfrac {atk\times b}a\le Mid 然后上二分答案，解不等式。。然后就T了 但是这个思维过程也是必不可少的

能往凸包上想简直太妙了

换个思路。把每个妖怪看成一个点，x0=atk,y0=dnfx_0=atk,y_0=dnf，答案可以写成x0+ay0b+y0+bx0ax_0+\dfrac {ay_0}b+y_0+\dfrac {bx_0}a。 y−y0x−x0=−ba\dfrac {y-y_0}{x-x_0}=-\dfrac ba在横纵轴的截距和！ 这样想想，显然只有在凸包上的点才有可能成为最大值，具体地说，必须在右上凸包 在右上凸包上，对于每条边，代入斜率求一下端点的值，可以保证每个点的取值都是所有点的取值中，当前斜率下的最大值。 然而还可能有些点，把直线的斜率转一转一样是全局最大值，但可以变得更小。根据均值不等式，应该取−y0x0-\sqrt {\dfrac{y_0}{x_0}}。如果这个斜率的直线与凸包是相切的，那么也可以拿来更新答案。

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
#include "lucida"

using std::sort;
using std::swap;
using std::unique;
using std::reverse;
const int MAXN=1e6+11;
const double inf=1e100,eps=1e-7;
int fcmp(const double &x) {
	return -eps<x && x<eps?0:(x<0?-1:1);
}
struct point {
	double x,y;
	point() {}
	point(double x,double y):x(x),y(y) {}
	double slope() const {
		return fcmp(x)?y/x:inf;
	}
	double len() const {
		return sqrt(x*x+y*y);
	}
	friend point operator +(const point &a,const point &b) {
		return point(a.x+b.x,a.y+b.y);
	}
	friend point operator -(const point &a,const point &b) {
		return point(a.x-b.x,a.y-b.y);
	}
	bool operator < (const point &a) const {
		return x!=a.x?x<a.x:y>a.y;
	}
	bool operator ==(const point &a) const {
		return x==a.x && y==a.y;
	}
};
typedef point vector;
double outer(const vector &a,const vector &b) {
	return a.x*b.y-a.y*b.x;
}
double Calc(point p,double k) {
	return p.x+p.y-p.x*k-p.y/k;
}
int main() {
//	freopen("input","r",stdin);
	static point p[MAXN],stack[MAXN];
	static double pk[MAXN];
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		is>>p[i].x>>p[i].y;
	}
	sort(p+1,p+1+n);
	n=unique(p+1,p+1+n)-p-1;
	int top=0;
	for(int i=n;i;--i) {
		while(top>=2 && outer(stack[top]-stack[top-1],p[i]-stack[top])<0) {
			top--;
		}
		stack[++top]=p[i];
	}
	n=0;
	for(int i=1;i<=top;++i) {
		p[++n]=stack[i];
		if((stack[i+1]-stack[i]).slope()>=0) {
			break;
		}
	}
	reverse(p+1,p+1+n);
	for(int i=2;i<=n;++i) {
		pk[i]=(p[i]-p[i-1]).slope();
	}
	pk[1]=-inf;pk[n+1]=inf;
	double Ans=inf;
	for(int i=1;i<=n;++i) {
		double mik=-sqrt(p[i].y/p[i].x);
		if(fcmp(pk[i]-mik)>=0 && fcmp(mik-pk[i+1])>=0) {
			chkmn(Ans,Calc(p[i],mik));
		}
		if(pk[i]!=inf && pk[i]!=-inf) {
			chkmn(Ans,Calc(p[i],pk[i]));
		}
	}
	os.precision(4);
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

线性基学得和没学差不多。。

Solution

倍增维护线性基，需要特判起点和终点相等的情况。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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
#include "lucida"
using std::fill;
using std::swap;
typedef unsigned long long qword;
const int MAXN=20000+11,MAXLOG=16;
int log_2[MAXN];
struct _{_(){
	log_2[0]=-1;
	for(int lg=1;lg<MAXN;++lg) {
		log_2[lg]=log_2[lg>>1]+1;
	}
}}Auto;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
struct Basis {
	qword a[62];
	Basis() {
		fill(a,a+62,0);
	}
	qword &operator [](const int &x) {
		return a[x];
	}
	const qword &operator [](const int &x) const {
		return a[x];
	}
	void Insert(qword x) {
		for(int lg=61;~lg;--lg) {
			if(x>>lg&1) {
				if(a[lg]) {
					x^=a[lg];
				} else {
					a[lg]=x;
					break;
				}
			}
		}
	}
	friend Basis Merge(Basis a,const Basis &b) {
		for(int lg=61;~lg;--lg) {
			if(b[lg]) {//超强的优化！
				a.Insert(b[lg]);
			}
		}
		return a;
	}
	qword Max() {
		qword res=0;
		for(int lg=61;~lg;--lg) {
			chkmx(res,res^a[lg]);
		}
		return res;
	}
};
qword a[MAXN];
int par[MAXN][MAXLOG],dep[MAXN],fa[MAXN];
Basis basis[MAXN][MAXLOG];
void DFS(int pos) {
	dep[pos]=dep[fa[pos]]+1;
	par[pos][0]=fa[pos];
	basis[pos][0].Insert(a[pos]);
	basis[pos][0].Insert(a[fa[pos]]);
	for(int lg=1;lg<=log_2[dep[pos]];++lg) {
		basis[pos][lg]=Merge(basis[pos][lg-1],basis[par[pos][lg-1]][lg-1]);
		par[pos][lg]=par[par[pos][lg-1]][lg-1];
	}
	for(Edge *e=G[pos];e;e=e->pre) {
		if(e->to!=fa[pos]) {
			int u=e->to;
			fa[u]=pos;
			DFS(u);
		}
	}
}
qword Query(int p1,int p2) {
	if(p1==p2) {
		return a[p1];
	} else {
		Basis b;
		if(dep[p1]<dep[p2]) {
			swap(p1,p2);
		}
		for(int len=dep[p1]-dep[p2],lg=log_2[len];~lg;--lg) {
			if(len>>lg&1) {
				b=Merge(b,basis[p1][lg]);
				p1=par[p1][lg];
			}
		}
		if(p1!=p2) {
			for(int lg=log_2[dep[p1]];~lg;--lg) {
				if(par[p1][lg]!=par[p2][lg]) {
					b=Merge(b,Merge(basis[p1][lg],basis[p2][lg]));
					p1=par[p1][lg];p2=par[p2][lg];
				}
			}
			b=Merge(b,Merge(basis[p1][0],basis[p2][0]));
		}
		return b.Max();
	}
}
int main() {
	freopen("input","r",stdin);
	freopen("output","w",stdout);
	int n,Q;is>>n>>Q;
	for(int i=1;i<=n;++i) {
		is>>a[i];
	}
	for(int i=1;i<=n-1;++i) {
		int x,y;is>>x>>y;
		Adde(x,y);
	}
	DFS(1);
	for(int i=1;i<=Q;++i) {
		int x,y;is>>x>>y;
		qword Ans=Query(x,y);
		os<<Ans<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

推导先放一放吧。。 这道题给我的教育很深刻：

  1. 一定要分清循环的是下标还是长度。FFT的lenlen写成了<n< n，查了很长时间
  2. 谨防填错模板函数参数的数据类型。

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
#include "lucida"
using std::swap;
using std::reverse;
const int MAXN=100000+11,P=998244353,MAXL=MAXN<<2,orig=3;
template <class T>
T pow(T base,int index) {
	T res;
	for(res=1;index;base*=base,index>>=1) {
		if(index&1) {
			res*=base;
		}
	}
	return res;
}

namespace modint {
	template <int modu> struct ModInt {
		int64 num;
		ModInt() {}
		ModInt(int64 num):num(num%P) {}
		ModInt inverse() const {
			return pow(*this,modu-2);//modu-1?..	
		}
		friend ModInt operator +(const ModInt &a,const ModInt &b) {
			return ModInt(a.num+b.num);
		}
		friend ModInt operator -(const ModInt &a,const ModInt &b) {
			return ModInt(a.num-b.num);
		}
		friend ModInt operator *(const ModInt &a,const ModInt &b) {
			return ModInt(a.num*b.num);
		}
		friend ModInt operator /(const ModInt &a,const ModInt &b) {
			return a*b.inverse();
		}
	};
}
typedef modint::ModInt<P> ModInt;
ModInt fac[MAXN];
struct _{_(){
	fac[0]=1;
	for(int i=1;i<MAXN;++i) {
		fac[i]=fac[i-1]*i;
	}
}}Auto;
void Trans(ModInt a[],int n,int d) {
	for(int i=1,j=n>>1;i<n-1;++i) {
		if(i<j) swap(a[i],a[j]);
		int k=n>>1;
		while(k<=j) {
			j-=k;
			k>>=1;
		}
		j+=k;
	}
	for(int len=2;len<=n;len<<=1) {//<=n?<n?.
		ModInt rt=pow((ModInt)orig,(P-1)/len);//实例化了int.
		//cos(2*pi*d/len),sin(2*pi*d/len)
		for(int i=0;i<n;i+=len) {
			ModInt w=1;
			for(int j=i;j<i+(len>>1);++j) {
				ModInt u=a[j],t=w*a[j+(len>>1)];
				a[j]=u+t,a[j+(len>>1)]=u-t;
				w*=rt;
			}
		}
	}
	if(d==-1) {
		reverse(a+1,a+n);
		ModInt inv=ModInt(n).inverse();
		for(int i=0;i<n;++i) {
			a[i]*=inv;
		}
	}
}
struct Polynomial {
	int64 a[MAXL],n;
	int64 &operator [](const int &x) {
		return a[x];
	}
	const int64 &operator [](const int &x) const {
		return a[x];
	}
	friend Polynomial operator *(const Polynomial &A,const Polynomial &B) {
		static Polynomial C;
		static ModInt a[MAXL],b[MAXL],c[MAXL];
		int n=1;for(int lim=C.n=A.n+B.n-1;n<lim;n<<=1);
		for(int i=0;i<n;++i) {
			a[i]=i<A.n?A[i]:0;
			b[i]=i<B.n?B[i]:0;
		}
		Trans(a,n,1);Trans(b,n,1);
		for(int i=0;i<n;++i) {
			c[i]=a[i]*b[i];
		}
		Trans(c,n,-1);
		for(int i=0;i<C.n;++i) {
			C[i]=c[i].num;
		}
		return C;
	}
}A,B,C;
int main() {
	freopen("input","r",stdin);
	int n;is>>n;
	A.n=B.n=n+1;
	for(int i=0;i<=n;++i) {
		A[i]=((i&1?-1:1)/fac[i]).num;
	}
	B[0]=1;
	B[1]=n+1;
	for(int i=2;i<=n;++i) {
		B[i]=((1-pow((ModInt)i,n+1))/((1-i)*fac[i])).num;
	}
	C=A*B;
	ModInt res=0;
	for(int i=0;i<=n;++i) {
		res+=pow(ModInt(2),i)*fac[i]*C[i];
	}
	int64 Ans=(res.num+P)%P;
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

3) 当它的所有后缀都被填入表内的情况下，如果 1...x-1的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。

序号就是位置，位置就是序号。呵呵 第一种情况可以避免。 对反串建Trie,就可以DFS贪心地求第二、三种情况的最优解。

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
#include "lucida"
using std::sort;
using std::reverse;
using std::fill;
const int MAXSUM=510000+11,MAXN=100000+11;
namespace trie {
	struct Node {
		Node *son[26];int id;
		Node(int id):id(id) {
			fill(son,son+26,(Node*)0);
		}
		Node *&next(char c) {
			return son[c-'a'];
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXSUM);//static.
			return Me++;
		}
	};
	struct Trie {
		typedef Node *Iter;
		Node *root;
		Trie():root(new Node(0)) {}
		void Insert(char *s,int len,int id) {
			Node *pos=root;
			for(int i=1;i<=len;++i) {
				pos=pos->next(s[i])?pos->next(s[i]):(pos->next(s[i])=new Node(-1));
			}
			pos->id=id;
		}
	};
}using trie::Trie;
int sz[MAXN],fa[MAXN],dc,dfn[MAXN];
array<int> son[MAXN];
bool cmp(const int &a,const int &b) {
	return sz[a]<sz[b];
}
void Build(Trie::Iter pos,int last) {
	if(~pos->id) {
		if(~last) {
			fa[pos->id]=last;
			son[last].push_back(pos->id);
		}
		last=pos->id;
	}
	for(char c='a';c<='z';++c) {
		if(pos->next(c)) {
			Build(pos->next(c),last);
		}
	}
}
void GetSize(int pos) {
	sz[pos]=1;
	for(size_t i=0;i<son[pos].size();++i) {
		int u=son[pos][i];
		GetSize(u);
		sz[pos]+=sz[u];
	}
	sort(son[pos].begin(),son[pos].end(),cmp);
}
int64 DFS(int pos) {
	dfn[pos]=++dc;
	int64 res=dfn[pos]-dfn[fa[pos]];
	for(size_t i=0;i<son[pos].size();++i) {
		int u=son[pos][i];
		res+=DFS(u);
	}
	return res;
}
int main() {
	freopen("input","r",stdin);
	static char s[MAXSUM];
	int n;is>>n;
	Trie tri;
	for(int i=1;i<=n;++i) {
		is>>(s+1);int len=strlen(s+1);
		reverse(s+1,s+1+len);
		tri.Insert(s,len,i);
	}
	Build(tri.root,-1);
	GetSize(0);
	int64 Ans=DFS(0);
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

神了。 暴力并查集，最后看有多少个集合。设个数为xx，那么答案就是9∗10x−19*10^{x-1}，然而明显很多次操作是重复的。 那就考虑区间一下？似乎并不好直接把并查集套到线段树上。 然后就开始高能： 维护倍增的并查集！fa[lg][pos]fa[lg][pos]表示pospos之后2lg2^{lg}长度的区间所属的集合，那么合并就可以拆成O(logn)O(\log 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
#include "lucida"
using std::swap;
const int P=1e9+7,MAXN=1e5+11,MAXLOG=20;
int log_2[MAXN];
struct _{_(){
	log_2[0]=-1;
	for(int i=1;i<MAXN;++i) {
		log_2[i]=log_2[i>>1]+1;
	}
}}Auto;
int fa[MAXLOG][MAXN];
int Root(int lg,int x) {
	return !fa[lg][x]?x:fa[lg][x]=Root(lg,fa[lg][x]);
}
void Union(int lg,int x,int y) {
	if(rand()&1) {
		swap(x,y);
	}
	int rx=Root(lg,x),ry=Root(lg,y);
	if(rx!=ry) {
		fa[lg][rx]=ry;
		if(lg) {
			Union(lg-1,x,y);
			Union(lg-1,x+(1<<(lg-1)),y+(1<<(lg-1)));
		}
	}
}
int main() {
	freopen("input","r",stdin);
	srand(0x1f1f1f1f);
	int n,m;is>>n>>m;
	for(int i=1;i<=m;++i) {
		int l1,r1,l2,r2;is>>l1>>r1>>l2>>r2;
		for(int len=r1-l1+1,lg=log_2[len];~lg;--lg) {
			if(len>>lg&1) {
				Union(lg,l1,l2);
				l1+=1<<lg;
				l2+=1<<lg;
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=n;++i) {
		cnt+=fa[0][i]==0;
	}
	int64 Ans=9;
	for(int i=1;i<=cnt-1;++i) {
		(Ans*=10)%=P;
	}
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

想写一道第KK大XOR的题，找到之后开始写发现，写着写着发现熟悉的触目惊心。。翻提交记录，果然早就把这道题A了。。23333 做法就是处理线性基，然后把KK二进制拆分，在11的位上异或上相应位的线性基。

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define getf(x) scanf("%lf",&x)
#define gets(x) scanf("%s",x)
#define getl(x) scanf("%lld",&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;}
typedef long long LL;
const int MAXN=10000+11,LEN=63;
LL a[MAXN];int n;
using std::find_if;
using std::swap;

int __bit;bool Exist(LL x){return x>>__bit&1;}
bool gotzero;
void Basis()
{
    int p=0;
    for(int j=LEN;~j;j--)
    {
        int l;
        if((l=(__bit=j,find_if(a+1+p,a+1+n,Exist)-a))==n+1) continue;
        swap(a[++p],a[l]);
        for(int i=1;i<=n;i++)
            if(i!=p && (a[i]>>j&1)) a[i]^=a[p];
    }
    gotzero=(p!=n);
    n=p;

}
LL Query(LL k)
{
    if(gotzero) k--;
    LL res=0;
    for(int i=n;i;i--)
    {
        if(k&1) res^=a[i];
        k>>=1;
    }
    if(k) return -1;
    return res;
}
void WORK()
{
    get(n);
    for(int i=1;i<=n;i++) getl(a[i]);
    Basis();
    int Q;get(Q);
    for(int i=1;i<=Q;i++)
    {
        LL k;getl(k);
        printf("%lld\n",Query(k));
    }
}
int main()
{
    int T;get(T);
    for(int t=1;t<=T;++t)
        printf("Case #%d:\n",t),WORK();
    return 0;
}