Reincarnation

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

ZROI - 20连测day3

发表于 分类于 ，
本文字数： 25k 阅读时长 ≈ 23 分钟

在任第一人 ！

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

A. 你

题目简介

给定一个 的矩阵，从 依次标号。即对于 ，现在维护 次操作：

  • 交换第 和第 行；
  • 交换第 和第 列；
  • 交换 和 。

求最后的矩阵，输出形式如 。

数据范围：

考虑对每一行维护 初始为 ，每次交换 和 即可，列同理。

然后你发现这样没法做单点交换，所以我们考虑维护 表示对于 的 与实际值的偏差，三个操作都可以 维护。

时间复杂度 ，好像还有不需要 的做法。

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
// ----- Eternally question-----
// Problem: A. 【noip赛前20天冲刺集训 day3】你
// Contest: ZROI - 23noip赛前20天冲刺 day3
// URL: http://zhengruioi.com/contest/1466/problem/2724
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-11 08:43:57
// ----- 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=5e3+10,MAXQ=1e6+10;
const int Mod=998244353;
int N,M,Q;
uint64_t seed;
char Oper[MAXQ];
uint64_t next()
{
	//xorshift64
    seed^=seed<<13;
    seed^=seed>>7;
    seed^=seed<<17;
    return seed;
}
int Hori[MAXN],Cros[MAXN],val[MAXN][MAXN];
int Pw17[MAXN],Pw19[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M,Q,seed),Pw17[0]=Pw19[0]=1;
	scanf("%s",Oper+1);
	for(int i=0;i<M;++i) Cros[i]=i;
	for(int i=0;i<N;++i) Hori[i]=i;
	for(int i=1;i<=N;++i) Pw17[i]=(ll)Pw17[i-1]*17%Mod;
	for(int i=1;i<=M;++i) Pw19[i]=(ll)Pw19[i-1]*19%Mod;
	for(int i=1;i<=Q;++i)
	{
		
		if(Oper[i]=='r')
		{
			int r1=next()%N,r2=next()%N;
			// write("r:",r1,' ',r2,'\n');
			std::swap(Hori[r1],Hori[r2]);
		}
		else if(Oper[i]=='c')
		{
			int c1=next()%M,c2=next()%M;
			// write("c:",c1,' ',c2,'\n');
			std::swap(Cros[c1],Cros[c2]);
		}
		else
		{
			int sx=next()%N,sy=next()%M,lx=next()%N,ly=next()%M;
			// printf("f:(%d,%d),(%d,%d)\n",sx,sy,lx,ly);
			int val1=Hori[sx]*M+Cros[sy]+val[Hori[sx]][Cros[sy]];
			int val2=Hori[lx]*M+Cros[ly]+val[Hori[lx]][Cros[ly]];
			val[Hori[sx]][Cros[sy]]+=val2-val1;
			val[Hori[lx]][Cros[ly]]+=val1-val2;
		}
		// for(int i=0;i<N;++i,puts(""))
			// for(int j=0;j<M;++j) write(Hori[i]*M+Cros[j]+val[Hori[i]][Cros[j]],' ');
	}
	ll ans=0;
	for(int i=0;i<N;++i)
		for(int j=0;j<M;++j)
		{
			ll v=Hori[i]*M+Cros[j]+val[Hori[i]][Cros[j]];
			ans=(ans+v*Pw17[i]%Mod*Pw19[j]%Mod)%Mod;
		}
	write(ans);
	return 0;
}
/*

*/

B. 有点太

题目简介

原题链接：https://www.luogu.com.cn/problem/P2474

有 个砝码，重量可能为 中的一种，但是你不能确定。给出一个 的图标，其中 表示砝码 与 的重量关系：

  • ?，则无法确定 的大小（指初始不知道，可能可以通过其它信息推断出来其重量关系）；
  • +，则 重于 ；
  • -，则 轻于 ；
  • =，则 与 重量一致。

现在拿出第 个和第 个，要求再拿出另外两个 ，求出有多少种选择的方案，使得通过上述已知信息能够确定 与 的重量关系，分别求出「重于」，「等于」，「轻于」的答案。

数据范围：

首先对于所有相等的信息，我们进行缩点，然后差分约束对 连有向边 ，那么最后会得到一个最长路 的 。

我们枚举 以及 的重量，考虑通过 对其它砝码分配重量，判断是否合法。

我们将没有入度的砝码重量设为 ，没有出度的设为 ，其余设成 。那么这一定是一组优美的合法解。

时间复杂度 。

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
#include<bits/stdc++.h>
using namespace std;
int n;
int fa[55];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
char s[55][55];
vector<int> to[55];
int ok[3],ans[3];
int w[55];
int ind[55],oud[55];
int cmp(int x,int y){
	return x>y?0:x==y?1:2;
}
bool check(){
	for(int i=1;i<=n;++i)if(w[i]){
		if(!w[find(i)])w[find(i)]=w[i];
		else if(w[find(i)]!=w[i])return 0;
	}
	for(int i=1;i<=n;++i)if(find(i)==i && !w[i] && !ind[i])w[i]=1;
	for(int i=1;i<=n;++i)if(find(i)==i && !w[i] && !oud[i])w[i]=3;
	for(int i=1;i<=n;++i)if(find(i)==i && !w[i])w[i]=2;
	for(int i=1;i<=n;++i)for(auto j:to[i])if(w[j]<=w[i])return 0;
	return 1;
}
int main() {
#ifdef QAQAutoMaton
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
#endif
    scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i)fa[i]=i;
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]=='=')fa[find(i)]=find(j);
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(s[i][j]=='+'){
		to[find(j)].emplace_back(find(i));
		++ind[find(i)];++oud[find(j)];
	}
	int x,y;
	scanf("%d%d",&x,&y);
	for(int i=1;i<=n;++i)if(i!=x && i!=y)
		for(int j=i+1;j<=n;++j)if(j!=x && j!=y){
			ok[0]=ok[1]=ok[2]=0;
			for(int a1=1;a1<=3;++a1)for(int a2=1;a2<=3;++a2)
				for(int a3=1;a3<=3;++a3)for(int a4=1;a4<=3;++a4){
					for(int k=1;k<=n;++k)w[k]=0;
					w[x]=a1;w[y]=a2;w[i]=a3;w[j]=a4;
					if(check()){
						ok[cmp(a1+a2,a3+a4)]=1;
					}
				}
			if(ok[0]+ok[1]+ok[2]==1){
				for(int j=0;j<=2;++j)ans[j]+=ok[j];
			}
		}
	for(int i=0;i<=2;++i)printf("%d\n",ans[i]);
	return 0;
}

这是一个差分约束的经典模型，所以我们考虑也这么做。

设 表示 可能的最大值， 表示可能的最小值。

  • ；
  • =，那么 ；
  • +，那么 ；
  • -，那么 ；
  • ?，那么 。

然后你发现这个形式是满足差分和合并性质的，所以我们用 处理一遍得到 的真实极差。

具体维护形式就是：

然后我们考虑枚举 ，然后通过上述条件判断是否合法即可。依然是分类讨论：

  • 如果 分别重于 ，那么总和一定更重；
  • 如果 分别等于 ，那么总和一定相等；
  • 如果 分别轻于 ，那么总和一定更轻。

时间复杂度 。

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
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
// ----- Eternally question-----
// Problem: B. 【noip赛前20天冲刺集训 day3】有点太
// Contest: ZROI - 23noip赛前20天冲刺 day3
// URL: http://zhengruioi.com/contest/1466/problem/2725
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-11 09:56:18
// ----- 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=60;
int N,S1,S2;
char Str[MAXN][MAXN];
namespace Brute
{
	int v[MAXN],val[MAXN][MAXN];
	int ans[4];
	inline void check()
	{
		for(int i=1;i<=N;++i)
			for(int j=1;j<=N;++j)
			{
				if(Str[i][j]=='?') continue;
				if(Str[i][j]=='+'&&v[i]<=v[j]) return ;
				if(Str[i][j]=='='&&v[i]!=v[j]) return ;
				if(Str[i][j]=='-'&&v[i]>=v[j]) return ;
			}
		// for(int i=1;i<=N;++i) write(v[i],' ');
		// puts("");
		int res=v[S1]+v[S2];
		for(int i=1;i<=N;++i)
		{
			if(i==S1||i==S2) continue;
			for(int j=i+1;j<=N;++j)
			{
				if(j==S1||j==S2||j==i) continue;
				if(!~val[i][j]) continue;
				if(v[i]+v[j]<res)
				{
					if(val[i][j]&&val[i][j]!=1){ --ans[val[i][j]],val[i][j]=-1;continue; }
					else if(!val[i][j]) ++ans[1],val[i][j]=1;
				}
				if(v[i]+v[j]==res)
				{
					if(val[i][j]&&val[i][j]!=2){ --ans[val[i][j]],val[i][j]=-1;continue; }
					else if(!val[i][j]) ++ans[2],val[i][j]=2;
				}
				if(v[i]+v[j]>res)
				{
					if(val[i][j]&&val[i][j]!=3){ --ans[val[i][j]],val[i][j]=-1;continue; }
					else if(!val[i][j]) ++ans[3],val[i][j]=3;
				}
			}
		}
	}
	void mixed(int pos)
	{
		for(int j=1;j<pos-1;++j)
		{
			if(Str[pos-1][j]=='?') continue;
			if(Str[pos-1][j]=='+'&&v[pos-1]<=v[j]) return ;
			if(Str[pos-1][j]=='='&&v[pos-1]!=v[j]) return ;
			if(Str[pos-1][j]=='-'&&v[pos-1]>=v[j]) return ;
		}
		if(pos>N) return check();
		v[pos]=1;
		mixed(pos+1);
		v[pos]=2;
		mixed(pos+1);
		v[pos]=3;
		mixed(pos+1);
		return ;
	}
	inline bool main()
	{
		mixed(1);
		write(ans[1],'\n',ans[2],'\n',ans[3]);
		return 0;
	}
};
int Mx[MAXN][MAXN],Mn[MAXN][MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) scanf("%s",Str[i]+1);
	read(S1,S2);
	// if(N<=10) return Brute::main();
	for(int i=1;i<=N;++i)
	{
		Mx[i][i]=Mn[i][i]=0;
		for(int j=1;j<=N;++j)
		{
			if(i==j) continue;
			if(Str[i][j]=='+') Mx[i][j]=2,Mn[i][j]=1;
			if(Str[i][j]=='=') Mx[i][j]=Mn[i][j]=0;
			if(Str[i][j]=='-') Mx[i][j]=-1,Mn[i][j]=-2;
			if(Str[i][j]=='?') Mx[i][j]=2,Mn[i][j]=-2;
		}
	}
	for(int k=1;k<=N;++k)
		for(int i=1;i<=N;++i)
			for(int j=1;j<=N;++j)
				checkMin(Mx[i][j],Mx[i][k]+Mx[k][j]),
				checkMax(Mn[i][j],Mn[i][k]+Mn[k][j]);
	int ans1=0,ans2=0,ans3=0;
	for(int i=1;i<=N;++i)
	{
		if(i==S1||i==S2) continue;
		for(int j=1;j<i;++j)
		{
			if(j==S1||j==S2) continue;
			if(Mn[S1][i]>Mx[j][S2]||Mn[S1][j]>Mx[i][S2]) ++ans1;
			if(Mn[S1][i]==Mx[S1][i]&&Mn[S1][i]==Mn[j][S2]&&Mn[j][S2]==Mx[j][S2]) ++ans2;
			else if(Mn[S2][i]==Mx[S2][i]&&Mn[S2][i]==Mn[j][S1]&&Mn[j][S1]==Mx[j][S1]) ++ans2;
			if(Mx[S1][i]<Mn[j][S2]||Mx[S1][j]<Mn[i][S2]) ++ans3;
		}
	}
	write(ans1,'\n',ans2,'\n',ans3);
	return 0;
}
/*

*/

C. 极端

题目简介

给定 个点分别为 。其中 的权值为 ， 的权值为 。

现在你可以标记一些点，如果你标记了 ，那么你可以获得 的权值，其中 ，但是这些点以及 的权值都会变为 。最大化获得的权值。

数据范围：

你发现标记点实际上是不会存在代价的，所以对于一个没有被标记覆盖的点，我们将其标记后总贡献只会更优不会更劣。所以我们转化题意，标记一些点，代价为 ，使得 个点都被覆盖。那么答案用总权值减去最小代价。

我们考虑设计状态 表示已经覆盖了 的最小代价，那么我们转移：

有 个转移的原因是，如果标记了 ，那么 都会被标记，所以我们需要特判 和 的情况，也就是后两种转移。而当其它情况我们不需要在意 的标记情况的原因是，这个 一定会在之后的覆盖中被重新覆盖，因为 中间存在未被覆盖的点。

时间复杂度 。

80pts
 
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
// ----- Eternally question-----
// Problem: C. 【noip赛前20天冲刺集训 day3】极端
// Contest: undefined - 23noip赛前20天冲刺 day3
// URL: http://zhengruioi.com/contest/1466/problem/2726
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-11 19:24: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=1.5e3+10;
int N,D,a[MAXN],b[MAXN],Sum;
int Dp[MAXN][MAXN];
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,D);
	for(int i=1;i<=N;++i) read(a[i]),Sum+=a[i];
	for(int i=1;i<=N;++i) read(b[i]),Sum+=b[i];
	std::memset(Dp,0x3f,sizeof(Dp));
	Dp[0][0]=0;
	for(int i=0;i<=N;++i)
		for(int j=0;j<=N;++j)
		{
			for(int k=std::max(1,i-D+1);k<=i+D+1&&k<=N;++k)
				checkMin(Dp[std::min(N,k+D)][j],Dp[i][j]+b[k]);
			for(int k=std::max(1,j-D+1);k<=j+D+1&&k<=N;++k)
				checkMin(Dp[i][std::min(N,k+D)],Dp[i][j]+a[k]);
			for(int k=std::max(1,i-D+1);k<=j+1&&k<=N&&k<=i+D+1;++k)
				checkMin(Dp[std::min(N,k+D)][std::max(k,j)],Dp[i][j]+b[k]);
			for(int k=std::max(1,j-D+1);k<=i+1&&k<=N&&k<=j+D+1;++k)
				checkMin(Dp[std::max(k,i)][std::min(N,k+D)],Dp[i][j]+a[k]);
		}
	write(Sum-Dp[N][N]);
	return 0;
}
/*

*/

然后考虑优化。

我们将转移左边全部替换为 进行转移的话，你会发现右边枚举 时则是在寻找一个区间内的最小值，那么可以用区间最小值维护。这里用线段树，但实际上用 的后缀最小值维护也可以（因为再后面是没有转移的 ）。

时间复杂度 。

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
// ----- Eternally question-----
// Problem: C. 【noip赛前20天冲刺集训 day3】极端
// Contest: undefined - 23noip赛前20天冲刺 day3
// URL: http://zhengruioi.com/contest/1466/problem/2726
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-11 19:24: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=1.5e3+10;
const int Inf=0x3f3f3f3f;
int N,D,a[MAXN],b[MAXN],Sum;
int Dp[MAXN][MAXN];
struct Seg_tree
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct Segment
	{ int l,r,val; }Tr[MAXN<<2];
	inline void pushUp(int p)
	{ Tr[p].val=std::min(Tr[ls].val,Tr[rs].val); }
	void build(int p,int l,int r)
	{
		Tr[p].l=l,Tr[p].r=r;
		if(l==r) return Tr[p].val=Inf,void();
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		pushUp(p);
	}
	void modifyX(int p,int x,int v)
	{
		if(Tr[p].l==Tr[p].r) return checkMin(Tr[p].val,v),void();
		int mid=(Tr[p].l+Tr[p].r)>>1;
		x<=mid?modifyX(ls,x,v):modifyX(rs,x,v);
		pushUp(p);
	}
	int queryMin(int p,int l,int r)
	{
		if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
		int mid=(Tr[p].l+Tr[p].r)>>1,res=Inf;
		if(l<=mid) checkMin(res,queryMin(ls,l,r));
		if(mid<r) checkMin(res,queryMin(rs,l,r));
		return res;
	}
	void modify(int x,int v){ modifyX(1,x,v); }
	int query(int l,int r){ return queryMin(1,l,r); }
	#undef ls
	#undef rs
}Tra[MAXN],Trb[MAXN];
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,D);
	for(int i=1;i<=N;++i) read(a[i]),Sum+=a[i];
	for(int i=1;i<=N;++i) read(b[i]),Sum+=b[i];
	std::memset(Dp,0x3f,sizeof(Dp));
	Dp[0][0]=0;
	for(int i=0;i<=N;++i) Tra[i].build(1,0,N),Trb[i].build(1,0,N);
	Tra[0].modify(0,0),Trb[0].modify(0,0);
	for(int i=1;i<=N;++i)
		for(int j=std::max(0,i-D-1);j<=std::min(N,i+D);++j)
		{
			int l=std::max(0,i-D-1),r=std::min(N,i+D),k=j+(j+1==i);
			checkMin(Dp[k][r],Tra[j].query(l,r)+a[i]);
			Tra[k].modify(r,Dp[k][r]),Trb[r].modify(k,Dp[k][r]);
			checkMin(Dp[r][k],Trb[j].query(l,r)+b[i]);
			Trb[k].modify(r,Dp[r][k]),Tra[r].modify(k,Dp[r][k]);
			checkMin(Dp[r][r],Tra[j].query(l,r)+a[i]+b[i]),
			checkMin(Dp[r][r],Trb[j].query(l,r)+a[i]+b[i]);
			Tra[r].modify(r,Dp[r][r]),Trb[r].modify(r,Dp[r][r]);
		}
	write(Sum-Dp[N][N]);
	return 0;
}
/*

*/

D. 了

题目简介

给定 个代码语句，维护 个变量 ，有下列 种形式：

  • ，执行 ，其中 为前面的运算；
  • ，执行 ，与语句 同理，其中 给定。
  • ，将接下来的语句循环 次；
  • ，与 成对出现，封装一个循环。

其中语句 的执行需要消耗 单位的时间。

现在给出 次询问，每次询问给出 ，求出程序运行 单位时间后 的值。

数据范围：

什么大模拟。

按位运算，没有移位操作，所以我们位与位独立计算。

按照代码结构建树，求出子树的 值，询问的时候直接在树上遍历。时间复杂度 ，考场有人过，那是卡常神仙。

考虑优化，首先将循环大小 的全部扔掉，那么树深就不会超过 ，然后倍增处理。时间复杂度 。

出题人代码
 
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int inf=1000000000;
struct obj{
	int op,x,y;	
	// op=0: or 
	// op=1: and 
	// op=2: xor
	// op=3: repeat
	// op=4: end
	// y=-1 -2 -3 -4 : a,b,c,d
	// y=0,1 : val y
};
obj w[9][12005];
char s[15],s1[15],s2[15];
struct Map{
	unsigned char to[16];
	unsigned char &operator [](int x){return to[x];}
	unsigned char operator [](int x)const{return to[x];}
	Map(obj);
	Map(){}
};
Map::Map(obj a){
	for(int i=0;i<16;++i){
		int u=(i>>a.x)&1,v=a.y>=0?a.y:(i>>(-a.y-1))&1;
		if(a.op==0)
			to[i]=(i&(~(1<<a.x)))|(u|v)<<a.x;
		else if(a.op==1)
			to[i]=(i&(~(1<<a.x)))|(u&v)<<a.x;
		else 
			to[i]=(i&(~(1<<a.x)))|(u^v)<<a.x;
	}
}
Map operator +(const Map &a,const Map &b){
	Map c;
	for(int i=0;i<16;++i)c[i]=b[a[i]];
	return c;
}
Map fpm(Map a,int b){
	Map c;
	for(int i=0;i<16;++i)c[i]=i;
	for(;b;b>>=1,a=a+a)if(b&1)c=c+a;
	return c;
}
int stk[12005],tp;
int nx[15][12005],cnt[12005],fs[15][12005];
Map f[9][15][12005],g[9][12005];
pair<Map,int> solve(int id,int l,int r){
	Map res;
	for(int i=0;i<16;++i)res[i]=i;
	int cc=0;
	for(int i=l;i<=r;++i){
		if(w[id][i].op==3){
			nx[0][i]=w[id][i].y+1;
			auto ret=solve(id,i+1,w[id][i].y-1);
			cnt[i]=ret.y;
			g[id][i]=ret.x;
			fs[0][i]=min((long long)cnt[i]*w[id][i].x,inf+1ll);
			f[id][0][i]=fpm(g[id][i],w[id][i].x);
			cc=min(cc+fs[0][i],inf+1);
			res=res+f[id][0][i];
			i=w[id][i].y;
		}
		else{
			nx[0][i]=i+1;
			cnt[i]=1;fs[0][i]=1;
			g[id][i]=f[id][0][i]=Map(w[id][i]);
			res=res+g[id][i];
			++cc;
		}
	}
	return {res,min(cc,inf+1)};
}
void calc(int l,int r,int k,int *x){
	while(k){
		int at=l;
		for(int i=14;~i;--i)if(fs[i][at]<=k){
			for(int j=0;j<8;++j)x[j]=f[j][i][at][x[j]];
			k-=fs[i][at];
			at=nx[i][at];
		}
		if(k){
			int c=min(k/cnt[at],w[0][at].x);

			k-=c*cnt[at];
			for(int i=0;i<8;++i)x[i]=fpm(g[i][at],c)[x[i]];
			if(k){
				l=at+1,r=w[0][at].y-1;			
			}
		}
	}
}
int del[12005];
int nid[12005];
int x[8];
int pre(int l,int r){
	int s=0;
	for(int i=l;i<=r;++i){
		if(w[0][i].op==3){
			int is=pre(i+1,w[0][i].y-1);
			if(is>inf){
				del[i]=del[w[0][i].y]=1;
			}
			else{
				is=min((long long)is*w[0][i].x,inf+1ll);
			}
			s=min(s+is,inf+1);
			i=w[0][i].y;
		}
		else{
			++s;
		}
	}
	return min(s,inf+1);
}
void init(int &n){
	pre(1,n);
	int m=0;
	for(int i=1;i<=n;++i){
		if(!del[i]){
			nid[i]=++m;
			for(int j=0;j<8;++j)w[j][nid[i]]=w[j][i];
		}
	}
	n=m;
	for(int i=1;i<=n;++i)
		for(int j=0;j<8;++j)
			if(w[j][i].op==3)w[j][i].y=nid[w[j][i].y];
			else if(w[j][i].op==4)w[j][i].x=nid[w[j][i].x];
}
int main(){
#ifdef QAQAutoMaton
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
#endif
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%s",s);
		if(s[0]=='r'){
			int k;
			scanf("%d",&k);
			for(int j=0;j<8;++j){
				w[j][i].op=3;
				w[j][i].x=k;
			}
			stk[++tp]=i;
		}
		else if(s[0]=='e'){
			for(int j=0;j<8;++j){
				w[j][stk[tp]].y=i;
				w[j][i].x=stk[tp];
				w[j][i].op=4;
			}
			--tp;
		}
		else {
			scanf("%s",s1);
			if(s[0]=='o')
				for(int j=0;j<8;++j){
					w[j][i].op=0;
				}
			else if(s[0]=='a')
				for(int j=0;j<8;++j){
					w[j][i].op=1;
				}
			else 
				for(int j=0;j<8;++j){
					w[j][i].op=2;
				}
			for(int j=0;j<8;++j){
				w[j][i].x=s1[0]-'a';
			}
			if(s[s[0]=='o'?2:3]=='i'){
				int y=0;
				scanf("%d",&y);
				for(int j=0;j<8;++j)w[j][i].y=(y>>j)&1;
			}
			else{
				scanf("%s",s2);
				for(int j=0;j<8;++j)w[j][i].y=-(s2[0]-'a'+1);
			}
		}
	}
	init(n);
	int cs=0;
	for(int i=0;i<8;++i){
		cs=solve(i,1,n).y;
	}
	for(int i=1;i<=n+1;++i)if(!nx[0][i]){
		nx[0][i]=n+1;fs[0][i]=inf+1;
	}
	for(int k=1;k<=14;++k){
		for(int i=1;i<=n+1;++i){
			nx[k][i]=nx[k-1][nx[k-1][i]];
			fs[k][i]=min(fs[k-1][i]+fs[k-1][nx[k-1][i]],inf);
			for(int j=0;j<8;++j){
				f[j][k][i]=f[j][k-1][i]+f[j][k-1][nx[k-1][i]];
			}
		}
	}
	for(;q;--q){
		int k,a,b,c,d;
		int na=0,nb=0,nc=0,nd=0;
		scanf("%d%d%d%d%d",&k,&a,&b,&c,&d);
		assert(k<=cs);
		for(int i=0;i<8;++i){
			int ax=(a>>i)&1,bx=(b>>i)&1,cx=(c>>i)&1,dx=(d>>i)&1;
			x[i]=dx<<3|cx<<2|bx<<1|ax;
		}
		calc(1,n,k,x);
		for(int i=0;i<8;++i){
			na|=(x[i]&1)<<i;
			nb|=(x[i]>>1&1)<<i;
			nc|=(x[i]>>2&1)<<i;
			nd|=(x[i]>>3&1)<<i;
		}
		printf("%d %d %d %d\n",na,nb,nc,nd);
	}
	
	return 0;	
}
相关文章