2022杭电多校第八场题解

2022杭电多校第八场

Theramore（思维）

题意
给定一个01字符串，每次可以将一个奇数长度的区间翻转，求操作后字典序最小的字符串。

分析
翻转奇数长度的区间，元素位置的奇偶性不变，统计奇数位置和偶数位置1的个数，每次只使用长度为3的区间翻转，贪心的将1放到尽可能靠后的位置。时间复杂度$O(n)$。

AC代码

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		string s;
		cin>>s;
		int a=0,b=0;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='1')
			{
				if(i&1) a++;
				else b++;
			}
		}
		string ans(s.size(),'0');
		for(int i=(int)ans.size()-1;i>=0;i--)
		{
			if(i&1)
			{
				if(a>0)
				{
					ans[i]='1';
					a--;
				}
			}
			else
			{
				if(b>0)
				{
					ans[i]='1';
					b--;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
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

Quel’Thalas（思维）

题意
给定一个二维平面，每个点的横纵坐标范围是$[0,n]$内的整数，输出最少数量的直线，满足直线不经过$(0,0)$且直线经过除$(0,0)$以外所有的点。时间复杂度$O(1)$。

分析
同一条直线最多穿越两个边界上的点，总共有 $4n$ 个边界上的点，所以至少要 $2n$ 条直线。

AC代码

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		cout<<2*n<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

Ironforge（思维 数论）

题意
一条链，每个点上有一个数 $a_i$，每条边上有一个质数 $b_i$。一开始在某个点上，有一个空背包，走到一个点上可以把它的质因子放进背包，一条边如果背包里有那个质数就可以走。多组询问求从 $x$ 出发能否走到 $y$ (即求每个点能走到的最大范围)。

分析
先预处理每个质数在点上出现的位置，通过vector二分可以找到每条边左右两边最近的含有边上质数的位置。接下来需要预处理每个位置左右可以移动的最大范围，暴力扩展的时间复杂度是$O(n^2)$，但实际上如果扩展到之前处理的结点，可以继承它的扩展范围，对于每个点扩展的复杂度均摊是$O(1)$的，预处理的复杂度是$O(n)$，复杂度的瓶颈在于处理质数。时间复杂度$O(nlog(n))$。

AC代码

#include 
#define endl '\n'
using namespace std;
typedef long long ll;
const int N=2e5+10;
int a[N],b[N],vis[N],prime[N];
int L[N],R[N],l[N],r[N];
vector<int> v[N]; //存放每个质数出现的位置 
int n,m,k,cnt;

void get_primes(int n)
{
	for(int i=2;i<=n;i++) {
		if(vis[i]==0) { vis[i]=i; prime[++k]=i; }
		for(int j=1;j<=k;j++) {
			if(prime[j]>vis[i]||prime[j]>n/i) break;
			vis[i*prime[j]]=prime[j];
		}
	}
}

void solve(int &a,int &b)
{
	int x=a,y=b;
	while(true)
	{
		if(x>1)
		{
			if(R[x-1]<=y)
			{
				x--;
				y=max(y,r[x]);
				x=min(x,l[x]);
			}
		}
		if(y<n)
		{
			if(L[y]>=x) y++;
		}
		if(x==a&&y==b) break;
		a=x,b=y;
	}
}

bool check(int a,int b)
{
	if(a<b) return L[a]==a;
	else return R[a-1]==a;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T;
	cin>>T;
	get_primes(200000);
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<n;i++)  cin>>b[i];
		for(int i=1;i<=200000;i++) v[i].clear();
		for(int i=1;i<=n;i++)
		{
			int x=a[i];
			while(x>1)
			{
				v[vis[x]].push_back(i);
				int z=vis[x];
				while(x%z==0) x/=z;
			}
		}
		for(int i=1;i<n;i++)
		{
			int x=b[i];
			if(!v[x].size())
			{
				L[i]=0,R[i]=n+1;
				continue;
			}
			int t=upper_bound(v[x].begin(),v[x].end(),i)-v[x].begin();
			if(t>0) L[i]=v[x][t-1];
			else L[i]=0;
			if(t<v[x].size()) R[i]=v[x][t];
			else R[i]=n+1;
		}
		for(int i=1;i<=n;i++)
		{
			l[i]=r[i]=i;
			if(i==1)
			{
				solve(l[i],r[i]);
			}
			else
			{
				if(!check(i,i-1))
				{
					solve(l[i],r[i]);
				}
				else
				{
					l[i]=l[i-1];
					r[i]=max(r[i],r[i-1]);
					solve(l[i],r[i]);
				}
			}
		}
		while(m--)
		{
			int x,y;
			cin>>x>>y;
			if(x==y) cout<<"Yes"<<endl;
			else if(x<y)
			{
				if(r[x]>=y) cout<<"Yes"<<endl;
				else cout<<"No"<<endl;
			}
			else
			{
				if(l[x]<=y) cout<<"Yes"<<endl;
				else cout<<"No"<<endl;
			}
		}
	}
	return 0;
}
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

Orgrimmar（树形DP）

题意
求一棵树的最大分离集的大小。
分离集(dissociation set)：一个顶点的集合，如果只保留这些顶点之间的边，那么该集合中的每个顶点最多只与一条边相连。

分析
用$f[x][0/1/2]$表示不选$x$、选$x$且选$x$连向子结点的边、选$x$但不选$x$连向子结点的边分离集顶点数的最大值。状态转移方程如下，其中$x$是$y$的父结点。
{ f [ x ] [ 0 ] = ∑ m a x ( f [ y ] [ 0 ] , f [ y ] [ 1 ] , f [ y ] [ 2 ] ) f [ x ] [ 1 ] = 1 + ∑ f [ y ] [ 0 ] + m a x ( 0 , f [ y ] [ 2 ] − f [ y ] [ 0 ] ) f [ x ] [ 2 ] = 1 + ∑ f [ y ] [ 0 ] \left\{

\right. ⎩ ⎨ ⎧​f[x][0]=∑max(f[y][0],f[y][1],f[y][2])f[x][1]=1+∑f[y][0]+max(0,f[y][2]−f[y][0])f[x][2]=1+∑f[y][0]​
对于$f[x][1]$来说，只能由子结点$0/2$两种状态转移而来，且$2$状态最多选一个，因此贪心的选择$f[y][2]-f[y][0]$值最大的结点。

AC代码

const int N=5e5+10;
const int M=2*N;
int head[N],e[M],ne[M],tot;
int f[N][3];

void add(int x,int y)
{
	e[++tot]=y,ne[tot]=head[x],head[x]=tot;
}

void dfs(int x,int p)
{
	int mx=0;
	for(int i=head[x];i;i=ne[i])
	{
		int y=e[i];
		if(y==p) continue;
		dfs(y,x);
		f[x][0]+=max({f[y][0],f[y][1],f[y][2]});
		f[x][2]+=f[y][0];
		f[x][1]+=f[y][0];
		mx=max(mx,f[y][2]-f[y][0]);
	}
	f[x][2]+=1;
	f[x][1]+=mx+1;
}

int main()
{
	int size(512<<20);  // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		//初始化 
		for(int i=1;i<=n;i++) head[i]=0;
		for(int i=1;i<=n;i++) f[i][0]=f[i][1]=f[i][2]=0;
		tot=0;
		for(int i=1;i<n;i++)
		{
			int x,y; cin>>x>>y;
			add(x,y); add(y,x);
		}
		dfs(1,-1);
		cout<<max({f[1][0],f[1][1],f[1][2]})<<endl;
	}
	exit(0);
}
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

注意
本题需要手动开栈，否则会RE

int main() {
    int size(512<<20);  // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    // YOUR CODE
   ...
    exit(0);
}
1
2
3
4
5
6
7

Stormwind（思维）

题意
有一个$n\ast m$的矩形，现在要在这个矩形上画线，要满足以下条件：

• 线的端点在矩形的边界上
• 线至少与矩形的一条边界平行
• 切割后每个小矩形的长和宽都是整数
• 每个矩形的面积最少是$k$
• 两条直线不能重合

求最大画线的数量。

分析
枚举小矩形的长宽，由长宽可以确定两个方向上的直线数量，取最大值即可，枚举的小矩形的面积可以大于$k$。时间复杂度$O(Tk)$。

AC代码

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m,k;
		cin>>n>>m>>k;
		int ans=0;
		for(int i=1;i<=k;i++)
		{
			int j=(k+i-1)/i;
			if(n<i||m<j) continue;
			int x=n/i-1;
			int y=m/j-1;
			ans=max(ans,x+y);
		}
		cout<<ans<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21