Reincarnation

正因为梦易碎，才格外美好。

ZROI - 2023csp七连测day3

发表于 更新于 分类于 ，
本文字数： 15k 阅读时长 ≈ 14 分钟

第三题和崩铁无关的原因是临时换题了。

比赛链接：http://zhengruioi.com/contest/1444

A. 杠上开花

题目简介

存在一个长度为 的序列 ，你现在需要选择 或者 并对其进行扩散攻击（详见《崩坏：星穹铁道》），形式化来讲，如果你选择了 ，那么执行 。如果操作结束后存在一个 ，那么删除 ，并将 向前移。即 ，以此类推。求将整个序列全部删除的最少操作次数。

随机数据生成如下：

数据生成器
 
1
2
3
4
5
6
7
8
9
void Gen(int n,unsigned s1,unsigned s2,unsigned s3){
    for(int i=1;i<=n;++i){
        s1^=s3;
        s3+=3055373123u;
        a[i]=(1<<((s1>>s2)&1));
        s2=(s2^s3)&31;
        s3=(s3>>s2)|((s3<<(31^s2))<<1);
    }
}

数据范围：

存在一个长度为 的序列 ，你现在需要选择任意一个 并对其进行扩散攻击（详见《崩坏：星穹铁道》），形式化来讲，如果你选择了 ，那么执行 。如果操作结束后存在一个 ，那么删除 ，并将 向前移。即 ，以此类推。求将整个序列全部删除的最少操作次数。

随机数据生成如下：

数据生成器
 
1
2
3
4
5
6
7
8
9
void Gen(int n,unsigned s1,unsigned s2,unsigned s3){
    for(int i=1;i<=n;++i){
        s1^=s3;
        s3+=3055373123u;
        a[i]=(1<<((s1>>s2)&1));
        s2=(s2^s3)&31;
        s3=(s3>>s2)|((s3<<(31^s2))<<1);
    }
}

数据范围：

原题面不存在 的限制（指的是 的题面），然后成了一个结论题，但是 在写 std 的时候写成了有限制的，所以这道题场上锅了，所以这场变成了 ，然后听说另外一个版本会出在之后的某场加时赛中（赠送的），现在 上也看得到，先鸽会儿，到时候再写另外个版本。

发现无论选 都会对 造成伤害，所以我们根据 分类讨论（观察数据生成器发现 ）：

  • 如果 ，那么显然如果这个时候选中 会溢出 点伤害，所以一定会选中 攻击。那么此时 一定会被消灭，然后考虑 的状态：
    • 如果 ，那么 被消灭， 成为 ；
    • 如果 ，那么 成为 ，且生命为 。
  • 如果 ，那么现在有两种打法：
    • 如果选中 ，那么 会被减 ，这个时候分讨 即可；
    • 如果选中 ，那么 会被消灭，然后我们还需要再打一次新的 （可能是 或者 ），此时 会被消灭，而两次的 也会被消灭，然后分讨剩余的即可。

所以我们考虑设计状态 表示当前的 是原序列的第 个，且这个 是否已经被打过一次了（作为扩散目标），然后按照上述方法转移即可。

AC 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
// ----- Eternally question-----
// Problem: A. [2023CSP七连 Day3] 杠上开花！（1）
// Contest: ZROI - 23csp7连测day3
// URL: http://zhengruioi.com/contest/1444/problem/2674
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-17 15:04:01
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=3e7+10;
const int Inf=0x3f3f3f3f;
int N,Dp[MAXN][2],a[MAXN];
unsigned s1,s2,s3;
inline void Gen(int n,unsigned s1,unsigned s2,unsigned s3)
{
	for(int i=1;i<=n;++i)
	{
		s1^=s3;s3+=3055373123u;
		a[i]=(1<<((s1>>s2)&1));	
		s2=(s2^s3)&31;s3=(s3>>s2)|((s3<<(31^s2))<<1);
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,s1,s2,s3);
	Gen(N,s1,s2,s3);
	std::memset(Dp,0x3f,sizeof(Dp));
	Dp[1][0]=0;
	for(int i=1;i<=N;++i)
	{
		if(a[i]==1)
		{
			checkMin(Dp[i+2][1],Dp[i][0]+1);
			checkMin(Dp[i+1][0],Dp[i][1]);
		}
		else
		{
			checkMin(Dp[i+1][1],Dp[i][0]+1);
			if(a[i+2]==1)
			{
				if(a[i+4]==1) checkMin(Dp[i+5][0],Dp[i][0]+2);
				else checkMin(Dp[i+4][1],Dp[i][0]+2);
			}
			else
			{
				if(a[i+3]==1) checkMin(Dp[i+4][0],Dp[i][0]+2);
				else checkMin(Dp[i+3][1],Dp[i][0]+2);
			}
			checkMin(Dp[i+2][1],Dp[i][1]+1);
		}
	}
	int ans=Inf;
	for(int i=N+1;i<=N+5;++i) checkMin(ans,std::min(Dp[i][0],Dp[i][1]));
	write(ans);
	return 0;
}
/*

*/

还没做，咕了。

B. 公交星槎

题目简介

现在有 个站点，以及 条航线，每条航线长度为 ，起点为 ，路径为：

现在从 开始计时，每过 秒，如果当前时刻 不存在第 条路线上的星槎，则生成一个新的星槎并出发。第 秒时所有航线都会生成一辆新的星槎，保证 。

现在你在 号结点，称作星槎到达航线中的下一个结点需要 个单位的时间，而换乘则需要 个单位的时间，求到达 号结点的最少时间。

数据范围：

考虑这个航线实际上是把单向边变成了一个伪双向边。考虑一个性质是 ，显然这个航线就是一个以 的循环。但实际上，我们同一条航线中到达某一点的代价一定 是一个定值 。

我们考虑对每一条边建点记为 表示第 条航线中从 到 。然后考虑建图：

  • 从 到 连边，记录当前最短路为 ，那么此时该边代价不定，但 会被从 之后第一个驶过 的星槎的时间 更新。
  • 从 连边 ，代价 。
  • 从 到 连边代价 ，其中 航线存在 。

然后你发现这就是一个最短路的格式，所以可以直接跑 。时间复杂度 。

AC 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
// ----- Eternally question-----
// Problem: B. [2023CSP七连 Day3] 公交星槎
// Contest: undefined - 23csp7连测day3
// URL: http://zhengruioi.com/contest/1444/problem/2675
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-17 16:27:12
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=1e5+10,MAXM=2e5+10,MAXV=5e5+10,MAXE=1e6+10;
const int Inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,M,T,Idx;
struct G
{ int next,to,val; }Edge[MAXE<<1];
int Head[MAXV],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
std::vector<int>Edges[MAXN];
std::vector<ll>Dist[MAXN];
std::vector<Pir>Ti[MAXN];
int Mi[MAXN],Gi[MAXN];
struct Node
{
	int ip,id;
	ll val;
	Node(int _p=0,int _d=0,ll _v=0):ip(_p),id(_d),val(_v){}
	bool operator<(const Node &x) const { return val>x.val; }
};
std::priority_queue<Node>Pq;
inline void upDate(int x,int y,ll val)
{
	if(x) val=std::max((ll)y+1,val+((y-(val-1))%Gi[x]+Gi[x])%Gi[x]);
	if(checkMin(Dist[x][y],val)) Pq.push(Node(x,y,Dist[x][y]));
}
inline void Dijkstra()
{
	Pq.push(Node(0,1,0));
	while(!Pq.empty())
	{
		Node u;
		while(!Pq.empty()&&(u=Pq.top(),Dist[u.ip][u.id]!=u.val)) Pq.pop();
		if(Pq.empty()) break;
		Pq.pop();
		if(u.ip)
		{
			upDate(0,u.id<Mi[u.ip]?Edges[u.ip][u.id+1]:Edges[u.ip][(Mi[u.ip]<<1)-u.id-1],u.val+T);
			upDate(u.ip,(u.id+1)%(Mi[u.ip]<<1),u.val+1);
		}
		else for(auto x:Ti[u.id]) upDate(x.fir,x.sec,u.val+1);
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M,T);
	Dist[0].resize(N+1);
	for(int i=1;i<=N;++i) Dist[0][i]=(i==1?0:INF);
	for(int i=1;i<=M;++i)
	{
		read(Mi[i],Gi[i]);
		Edges[i].resize(Mi[i]+1),Dist[i].resize((Mi[i]+1)<<1);
		for(int j=0;j<=Mi[i];++j) read(Edges[i][j]);
		for(int j=0;j<(Mi[i]<<1);++j)
		{
			Dist[i][j]=INF;
			if(j<Mi[i]) Ti[Edges[i][j]].push_back(Mkr(i,j));
			else Ti[Edges[i][(Mi[i]<<1)-j]].push_back(Mkr(i,j));
		}
	}
	Dijkstra();
	write(Dist[0][N]-T);
	return 0;
}
/*

*/

C. 记忆碎片

题目简介

给定一个字符串集合 ，初始为空，每次插入一个字符串，一共两种类型：

  • 匹配串 ；
  • 模式串 。

每次插入一个串后，你需要计算有哪些模式串能够通过若干匹配串通过若干次拼接而成（可以不用也可以用多次），强制在线。

数据范围：

没改，咕了。

D. 金人旧巷

题目简介

给定一个有 个结点的无根树，一共 次操作：

  • ，对距离 为 的结点 （包括 本身）加 。
  • 断边 ，并分别求连通块 的权值和。

数据范围：

幸好这道题没有这个活动一样又臭又长。

考虑上帝造题的衰减势能分析，将 分讨为两种情况：

  • 如果 ，那么这就是个全局加操作，直接维护一个 即可。
  • 如果 ，那么衰减系数为 。我们考虑一种比较暴力的维护方法。

我们记 的 级祖先为 ，其中 。那么对于修改 ，我们视作 ，也就是按照距离差分，这样的差分不会多于 。

然后我们考虑怎么处理询问，显然指定根后可以视作子树查询。然后基于上面的修改，我们的查询也会分为两部分：

  • 如果修改在子树内，可以直接计算修改，然后求子树和。
  • 记录 表示 子树内距离为 的结点个数，记录 表示所有 修改对 子树内距离为 的贡献，那么枚举深度 以及距离 ，得到贡献 。

时间复杂度 。

AC 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
// ----- Eternally question-----
// Problem: D. [2023CSP七连 Day3] 金人旧巷
// Contest: ZROI - 23csp7连测day3
// URL: http://zhengruioi.com/contest/1444/problem/2677
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-17 20:06:35
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXS=50;
const int S=29;
int N,Q;
struct G
{ int next,to; }Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Siz[MAXN],Dfn[MAXN],Num[MAXN][MAXS],Cnt;
void dfsTree(int x,int last)
{
	Fa[x]=last,Siz[x]=1,Dfn[x]=++Cnt;
	Num[x][0]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		for(int s=1;s<=S;++s) Num[x][s]+=Num[v][s-1];
	}
}
ll ans,Asum,Acnt,Val[MAXN][MAXS];
struct BIT
{
	ll Tre[MAXN],Siz;
	inline void build(int n){ Siz=n;for(int i=0;i<=n;++i) Tre[i]=0; }
	inline int lowbit(int x){ return x&(-x); }
	inline void add(int x,ll v){ for(;x<=Siz;x+=lowbit(x)) Tre[x]+=v; }
	inline ll query(int x)
	{
		ll res=0;
		for(;x;x-=lowbit(x)) res+=Tre[x];
		return res;
	}
	inline ll get(int l,int r){ return query(r)-query(l-1); }
}Tre;
inline void modify(int x,int y,ll p)
{
	ll tot=0;
	for(int i=0;y;++i,y/=p) Val[x][i]+=y,tot+=(ll)Num[x][i]*y;
	Tre.add(Dfn[x],tot),Asum+=tot;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);Tre.build(N);
	for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v);
	dfsTree(N,0);
	for(int opt,u,v;Q--;)
	{
		read(opt,u,v);
		if(opt==1)
		{
			ll p;read(p);
			if(p==1) Asum+=(ll)N*v,Acnt+=v;
			else
			{
				modify(u,v,p),v/=p;
				for(int i=Fa[u],lst=u;i&&v>0;i=Fa[i],lst=Fa[lst],v/=p) 
					modify(i,v,p),modify(lst,-(v/p),p);
			}
		}
		else
		{
			bool rev=0;
			if(Fa[v]==u) std::swap(u,v),rev=1;
			ans=Tre.get(Dfn[u],Dfn[u]+Siz[u]-1)+Acnt*Siz[u];
			for(int s=1;s<=S&&v;++s,v=Fa[v])
				for(int t=0;s+t<=S;++t) ans+=(ll)Val[v][s+t]*Num[u][t];
			if(rev) write(Asum-ans,' ',ans,'\n');
			else write(ans,' ',Asum-ans,'\n');
		}
	}
	return 0;
}
/*

*/
相关文章