Atcoder Beginner Contest 133

Posted on | Views:

$F$ 没调出来,炸了.

C Remainder Minimization 2019

  • 可以直接大力枚举两个余数是多少,再判断它们是否合法,合法就计入贡献.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
bool judge(int a,int b,int L,int R)
{
	if(R<a || R<b)
		return false;
	int L1=(L-a+2018)/2019,R1=(R-a)/2019;
	int L2=(L-b+2018)/2019,R2=(R-b)/2019;
	if(L1>R1 || L2>R2)
		return false;
	if(a<b)
		return L1<=R2;
	else
		return L1<R2;
}
int main()
{
	int L=read(),R=read();
	int ans=2019;
	for(int i=0;i<2019;++i)
		for(int j=0;j<2019;++j)
			if(judge(i,j,L,R))
				ans=min(ans,i*j%2019);
	cout<<ans<<endl;
	return 0;
}

D Rain Flows into Dams

  • 设第 $i$ 座山收到的水为 $x_i$ ,可以把题目中所给的条件表示为方程组的形式.

  • 题目保证 $x$ 有唯一的一组合法解,所以直接将这个方程组解出来,得到的就是那组合法解,过程中不必判断.
  • 尝试手动解.首先将所有方程加起来可以得到 $\sum x_i$ .每两个相邻的方程相减可以得到 $x_3-x_1,x_4-x_2,x_5-x_3,x_6-x_4\dots$ 这些值.
  • 求前缀和就可以得到每个奇数位置与 $x_1$ 的差值,每个偶数位置与 $x_2$ 的差值.再根据 $x_n+x_1$ 将 $x_1$ 以及所有奇数位置的 $x$ 解出,用 $\sum x_i$ 减去奇数位置的总和,得到偶数位置的总和,再根据求得的差分解出所有偶数位置 $x$.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n;
ll sum=0,a[MAXN],t[MAXN],x[MAXN];
void pr()
{
	for(int i=1;i<=n;++i)
		printf("%lld ",x[i]);
	puts("");
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		sum+=(a[i]=read());
	for(int i=3;i<=n;i+=2)
	{
		t[i]=a[i-1]-a[i-2];
		t[i]+=t[i-2];
	}
	x[1]=a[n]-t[n];
	for(int i=1;i<=n;i+=2)
		sum-=(x[i]=x[1]+2*(t[i]));
	if(n==3)
	{
		x[2]=sum;
		pr();
		return 0;
	}
	ll tot=0,cnt=1;
	for(int i=4;i<n;i+=2)
	{
		t[i]=2*(a[i-1]-a[i-2]);
		t[i]+=t[i-2];
		tot+=t[i];
		++cnt;
	}
	x[2]=(sum-tot)/(cnt);
	for(int i=4;i<n;i+=2)
		x[i]=x[2]+t[i];
	pr();
	return 0;
}

E Virus Tree 2

  • 只需满足每个点与它的父亲颜色不同,每个点与它父亲的父亲颜色不同,每个点的所有儿子颜色不同.
  • 设 $f(i)$ 表示当节点 $i$ 的颜色已被确定时,子树 $i$ 内染色的方案数,随便 $dfs$ 一下即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int head[MAXN],to[MAXN<<1],nx[MAXN<<1],ecnt=0;
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
const int P=1e9+7;
int add(int a,int b)
{
	return (a + b) % P;
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int fac[MAXN],invfac[MAXN];
int n,k,f[MAXN],Deg[MAXN];
int fa[MAXN];
int A(int N,int M)
{
	if(N>M)
		return 0;
	return mul(fac[M],invfac[M-N]);
}
int dfs(int u,int num,int Fa)
{
	fa[u]=Fa;
	if(num<=0)
		return f[u]=0;
	int deg=(u==1?Deg[u]:Deg[u]-1);
	if(!deg)
		return f[u]=1;
	if(u==1)
		f[u]=A(deg,k-1);
	else
		f[u]=A(deg,k-2);
	if(!f[u])
		return f[u];
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==Fa)
			continue;
		if(u==1)
			dfs(v,k-1,u);
		else
			dfs(v,k-2,u);
		f[u]=mul(f[u],f[v]);
	}
	return f[u];
}
int main()
{
	n=read(),k=read();
	fac[1]=1;
	for(int i=2;i<=k;++i)
		fac[i]=mul(fac[i-1],i);
	invfac[k]=fpow(fac[k],P-2);
	for(int i=k-1;i>=0;--i)
		invfac[i]=mul(invfac[i+1],i+1);
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
		++Deg[u],++Deg[v];
	}
	cout<<mul(dfs(1,k,0),k)<<endl;
	return 0;
}

F Colorful Tree

  • 不难发现对于每个询问 $(x,y,u,v)$ 只需要找出 $u\to v$ 的路径上颜色为 $x$ 的边的数目 $cnt$ 以及这些边的总长度 $sum$ .答案就是 $dist(u,v)-sum+cnt\cdot y$ .
  • 询问一段区间某种颜色的数目/权值和,用主席树进行维护.时间复杂度 $O(n\cdot log^n)$ .

树上的主席树并不需要像线段树那样维护 $dfs$ 序.直接在第一次 $dfs$ 时每个点复制父亲的信息,再修改即可.询问就是 $rt[u]+rt[v]-rt[LCA]-rt[LCA.fa]$ .

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
struct Edge
{
	int nx,to;
}E[MAXN<<1];
int head[MAXN],ecnt=0;
int col[MAXN],val[MAXN];
void addedge(int u,int v)
{
	++ecnt;
	E[ecnt].nx=head[u];
	E[ecnt].to=v;
	head[u]=ecnt;
}
void ins(int u,int v)
{
	addedge(u,v);
	addedge(v,u);
}
int n,m;
int dfn[MAXN],idx=0;
int dep[MAXN],fa[MAXN],top[MAXN];
int siz[MAXN],mxson[MAXN],dist[MAXN];
struct PreSegTree
{
	int nodeidx;
	struct node
	{
		int cnt,sum;
		int ls,rs;
	}Tree[MAXN*30];
	PreSegTree(){nodeidx=0;Tree[0].cnt=Tree[0].sum=0;}
#define root Tree[o]
	void upd(int &o,int pre,int l,int r,int pos,int c)
	{
		o=++nodeidx;
		root=Tree[pre];
		if(!pos)
			return;
		if(l==r)
		{
			root.cnt++;
			root.sum+=c;
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid)
			upd(root.ls,Tree[pre].ls,l,mid,pos,c);
		else
			upd(root.rs,Tree[pre].rs,mid+1,r,pos,c);
	}
	int query_sum(int o,int l,int r,int pos)
	{
		if(!o)
			return root.sum;
		if(l==r)
			return root.sum;
		int mid=(l+r)>>1;
		if(pos<=mid)
			return query_sum(root.ls,l,mid,pos);
		else
			return query_sum(root.rs,mid+1,r,pos);
	}
	int query_cnt(int o,int l,int r,int pos)
	{
		if(!o)
			return root.cnt;
		if(l==r)
			return root.cnt;
		int mid=(l+r)>>1;
		if(pos<=mid)
			return query_cnt(root.ls,l,mid,pos);
		else
			return query_cnt(root.rs,mid+1,r,pos);
	}
}T;
int rt[MAXN];
void dfs1(int u,int Fa)
{
	fa[u]=Fa;
	dep[u]=dep[Fa]+1;
	siz[u]=1;
	T.upd(rt[u],rt[Fa],1,n,col[u],val[u]);
	for(int i=head[u];i;i=E[i].nx)
	{
		int v=E[i].to;
		if(v==Fa)
			continue;
		dist[v]=dist[u]+val[v];
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[mxson[u]])
			mxson[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	if(mxson[u])
		dfs2(mxson[u],tp);
	for(int i=head[u];i;i=E[i].nx)
	{
		int v=E[i].to;
		if(v==fa[u] || v==mxson[u])
			continue;
		dfs2(v,v);
	}
}
void init()
{
	dfs1(1,0);
	dfs2(1,1);
}
int getLCA(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
int Solve(int c,int d,int x,int y)
{
	int LCA=getLCA(x,y);
	int cnt=0,sum=0;
	cnt+=T.query_cnt(rt[x],1,n,c)+T.query_cnt(rt[y],1,n,c);
	cnt-=T.query_cnt(rt[LCA],1,n,c)+T.query_cnt(rt[fa[LCA]],1,n,c);
	sum+=T.query_sum(rt[x],1,n,c)+T.query_sum(rt[y],1,n,c);
	sum-=T.query_sum(rt[LCA],1,n,c)+T.query_sum(rt[fa[LCA]],1,n,c);
	int res=dist[x]+dist[y]-dist[LCA]-dist[fa[LCA]];
	return res-sum+d*cnt;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		col[n+i]=read(),val[n+i]=read();
		ins(u,n+i);
		ins(v,n+i);
	}
	n=2*n-1;
	init();
	while(m--)
	{
		int x=read(),y=read();
		int u=read(),v=read();
		printf("%d\n",Solve(x,y,u,v));
	}
	return 0;
}