CF1229

Posted on | Views:

$Div.1$

A Marcin and Training Camp

有 $n$ 个人,每个人有一个集合,用二进制数 $a_i$ 表示,以及一个能力值 $b_i$ .

现在需要选出一些人形成一个大小 $\ge 2$ 的集合 $S$ ,满足 $\forall i\in S,\exists j\not=i,a_i \& a_j=a_i$ .

需要求出最大的 $\sum_{i\in S}b_i$ ,无解输出 $0$ .

容易发现,选出的人中至少有两个人的 $a_i$ 是相同的,即形成自环.否则就会存在拓扑序,至少存在一个不合法的元素.

可以先将有相同的元素都选上.

对于其他元素,只需要判一下能否被那些有相同的元素限制,即找到 $a_i \& a_j=a_i$ 的 $j$ ,内部不需要判断.

这是因为 $a_i \& a_j=a_i$ 这个关系是可以传递的.

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
#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=7777;
int n,m;
struct node
{
	ll first;
	int second;
	bool operator < (const node &rhs) const
	{
		return first<rhs.first;
	}
	bool operator == (const node &rhs) const
	{
		return first==rhs.first;
	}	
}a[MAXN],p[MAXN],q[MAXN];
unordered_map<ll,bool> vis;
int main()
{
	n=read();
	int t=0;
	if(n==1)
		return puts("0")&0;
	for(int i=1;i<=n;++i)
		a[i].first=read();
	for(int i=1;i<=n;++i)
		a[i].second=read();
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
	{
		if(vis[a[i].first])
			q[++t]=a[i];
		else
			p[++m]=a[i];
		vis[a[i].first]=true;
	}
	for(int i=1;i<=t;++i)
		p[m+i]=q[i];
	ll ans=0;
	for(int i=1;i<=m;++i)
	{
		bool f=false;
		for(int j=m+1;j<=n && !f;++j)
			if((p[i].first&p[j].first)==p[i].first)
				f=true;
		if(f)
			ans+=p[i].second;
	}		
	if(!ans)
		return puts("0")&0;
	for(int i=m+1;i<=n;++i)
		ans+=p[i].second;
	cout<<ans<<endl;
	return 0;
}

B Kamil and Making a Stream

给一棵以 $1$ 为根的有根树,每个点有一个权值 $x_i$ .

设 $f(x,y)$ 表示从 $x$ 到 $y$ 的路径上所有权值的 $\gcd$ .

需要求出$\sum_{\text {u is an ancestor of v}} f(v,u)$ ,答案对 $10^9+7$ 取模.

一个点到根的路径上,不同的 $\gcd$ 最多只有 $\log x$ 种,因为 $\gcd$ 每次改变时至少会 $/2$ .

于是倍增处理每个点向上跳 $2^i$ 步这段的 $\gcd$ 进行处理.

或者 $dfs$ 时直接把 $\gcd$ 的 $vector$ 数组传下来,相同的数合并,只记录次数.

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
#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;
}
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
const int P=1e9+7;
inline int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=1e5+10,L=17;
int n,ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
struct node
{
	ll v;
	int t;
	bool operator < (const node &rhs) const
	{
		return v<rhs.v;		
	}
	node(ll v=0,int t=0):v(v),t(t) {}
};
int ans=0;
ll val[MAXN];
vector<node> G[MAXN],tmp;
void dfs(int u,int f)
{
	G[u].push_back(node(val[u],1));
	for(auto x:G[f])
		G[u].push_back(node(gcd(x.v,val[u]),x.t));
	sort(G[u].begin(),G[u].end());
	ll cv=-1;
	int ct=0;
	for(auto x:G[u])
	{
		if(cv!=x.v)
		{
			if(cv!=-1)
				tmp.push_back(node(cv,ct)),ans=add(ans,mul(cv%P,ct));
			cv=x.v;
			ct=x.t;
		}
		else
			ct+=x.t;
	}
	tmp.push_back(node(cv,ct));
	ans=add(ans,mul(cv%P,ct));
	G[u]=tmp;
	tmp.clear();
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dfs(v,u);
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		val[i]=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}

C Konrad and Company Evaluation

有 $n$ 个人,每个人有一个工资,初始时等于他的编号.

给出一张图,对于一条边 $(u,v)$ ,若 $u$ 的工资比 $v$ 高,则从 $u$ 连向 $v$ ,否则从 $v$ 连向 $u$ .

有 $q$ 次询问,第 $i$ 次询问给出一个 $x$ ,表示将第 $x$ 个人的工资改为 $n+i$ ,再求出图中长度为 $3$ 的链的数目.

将 $a$ 向 $b$ 炫耀看成一条有向边 $a\to b$ .

记录每个点的入度 $indeg_i$ 和出度 $outdeg_i$ ,答案为 $\sum_i indeg_i\cdot outdeg_i$ .

每次将 $v$ 的工资调到最大,就是将所有 $u\to v$ 的边全部反向.

只要将这些边一条条的暴力反向的同时维护答案就可以了.

通过一些势能分析,可以得出每次修改时均摊反向 $O(\sqrt m)$ 条边.

时间复杂度 $O(n+m+q\cdot \sqrt m)$ .

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
#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;
}
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
const int P=1e9+7;
inline int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=1e5+10,L=17;
int n,ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
struct node
{
	ll v;
	int t;
	bool operator < (const node &rhs) const
	{
		return v<rhs.v;		
	}
	node(ll v=0,int t=0):v(v),t(t) {}
};
int ans=0;
ll val[MAXN];
vector<node> G[MAXN],tmp;
void dfs(int u,int f)
{
	G[u].push_back(node(val[u],1));
	for(auto x:G[f])
		G[u].push_back(node(gcd(x.v,val[u]),x.t));
	sort(G[u].begin(),G[u].end());
	ll cv=-1;
	int ct=0;
	for(auto x:G[u])
	{
		if(cv!=x.v)
		{
			if(cv!=-1)
				tmp.push_back(node(cv,ct)),ans=add(ans,mul(cv%P,ct));
			cv=x.v;
			ct=x.t;
		}
		else
			ct+=x.t;
	}
	tmp.push_back(node(cv,ct));
	ans=add(ans,mul(cv%P,ct));
	G[u]=tmp;
	tmp.clear();
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dfs(v,u);
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		val[i]=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}

D Wojtek and Card Tricks

给出 $n$ 个长度为 $k$ 的置换, $n\le 2\times 10^5,k\le 5$ .

定义 $f(l,r)$ 表示只用第 $l$ 个到第 $r$ 个置换对排列 $1,2,3,\dots,k$ 进行若干次操作,最多能得到的排列的数目.

需要求出 $\sum_{l=1}^n \sum_{r=l}^n f(l,r)$ .

对于每个左端点 $l$ ,先预处理出从 $l$ 向后走,哪些置换是第一次出现的,这可以从后往前扫一遍完成.

枚举左端点 $l$ ,只用考虑从 $l$ 开始第一次出现的置换,最多只有 $k!$ 个,其它地方答案不变,可以直接计算.

加入一个新的置换时,如果它能被已经加入的置换组合出,就没有用,直接跳过.

否则,直接大力 $bfs$ 出所有已经加入的有用的置换能操作出的排列,若答案改变,说明这个排列有用.

状态数最多为 $k!$ ,而有用的置换不会超过 $O(\log k!)$ 个,所以每加入一个有用的置换复杂度为 $O(k!\log k!)$ .

时间复杂度 $O((k!)^2+nk!k)$ .

常数没卡过去,不想卡了.

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
//%std
#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,MAXS=120;
typedef vector<int> perm;
map<perm,int> id;
int n,k,idx=0;
int calc(perm p)
{
	if(id.find(p)==id.end())
		id[p]=idx++;
	return id[p];
}
perm p[MAXN];
perm lst,pos[MAXN];
perm rep;
int S,vis[MAXS],tid;
queue<int> Q;
int ts=0,pt;
int G[MAXS][MAXS];
perm p1,p2,p3;
void init()
{
	p1.resize(k),p2.resize(k),p3.resize(k);
	for(int i=0;i<k;++i)
		p1[i]=p2[i]=i;
	for(int i=0;i<S;++i)
	{
		for(int j=0;j<S;++j)
		{
			for(int t=0;t<k;++t)
				p3[t]=p2[p1[t]];
			G[calc(p1)][calc(p2)]=calc(p3);
			next_permutation(p2.begin(),p2.end());
		}
		next_permutation(p1.begin(),p1.end());
	}
}
int bfs()
{
	++tid;
	int res=ts;
	int st,newst;
	if(vis[0]<=pt)
		res++;
	vis[0]=tid;
	Q.push(0);
	int tot=rep.size();
	while(!Q.empty())
	{
		st=Q.front();
		Q.pop();
		if(vis[st]==tid)
		{
			for(auto trans:rep)
			{
				newst=G[st][trans];
				if(vis[newst]<=pt)
				{
					++res;
					vis[newst]=tid;
					Q.push(newst);
				}
			}
		}
		else
		{
			int trans=rep[tot-1];
			newst=G[st][trans];
			if(vis[newst]<=pt)
			{
				++res;
				vis[newst]=tid;
				Q.push(newst);
			}
		}
	}
	return ts=res;
}
int main()
{
	n=read(),k=read();
	for(int i=0; i<n; ++i)
	{
		S=1;
		for(int j=0; j<k; ++j)
			p[i].push_back(read()-1),S*=(j+1);
	}
	init();
	lst.resize(S);
	for(int i=0; i<S; ++i)
		lst[i]=n;
	for(int i=n-1; i>=0; --i)
	{
		int x=calc(p[i]);
		lst[x]=i;
		pos[i]=lst;
		sort(pos[i].begin(),pos[i].end());
	}
	ll ans=0;
	for(int l=0; l<n; ++l)
	{
		rep.clear();
		ts=0;
		pt=tid;
		int tmp=1,head=-1;
		for(auto x:pos[l])
		{
			if(x==n)
				break;
			if(head!=-1)
				ans+=1LL*tmp*(x-head);
			head=x;
			if(vis[calc(p[x])]>pt)
				continue;
			rep.push_back(calc(p[x]));
			int newtmp=bfs();
			if(newtmp==tmp)
				rep.pop_back();
			else
				tmp=newtmp;
		}
		ans+=1LL*tmp*(n-head);
	}
	cout<<ans<<endl;
	return 0;
}