Shelter
0%

2022杭电杯超级联赛08

发表于 更新于
详细题解 我与队友一起在比赛 2022杭电杯超级联赛08 完成的题目

1001-Theramore

来源: 杭电杯超级联赛8 算法: 贪心 题目链接: https://acm.dingbacode.com/contest/problem?cid=1051&pid=1001 补完: Yes 完成时间: August 11, 2022

题意

给定一个只含有‘0’和‘1’的字符串，有无数次机会可以选择长度为奇数的任意间隔并将其反转，输出能得到的字典序最小的字符串。

解法

因为只能选择长度为奇数的任意间隔，所以奇数位置上的字符只能移动到奇数位置，偶数位置上的字符只能移动到偶数位置上。例如：位置5上的’0‘是可以被移到位置1上的。

我们可以分别计算出奇数位置上和偶数位置上‘0’的个数，然后从前往后对应奇偶位置地放置这些’0‘（原来奇数位置上的’0‘还是要放在奇数位置上），放完’0‘后，就可以开始放’1‘，这样的字符串就是能得到的字典序最小的字符串。

完整代码

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
#include<iostream>
#include<stdio.h> 
using namespace std;
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(i%2==0&&s[i]=='0')a++;
			if(i%2==1&&s[i]=='0')b++;
		}
		for(int i=0;i<s.size();i++){
			if(i%2==0){
				if(a>0){
					putchar('0');
					a--;
				}
				else putchar('1');
			}
			else{
				if(b>0){
					putchar('0');
					b--;
				}
				else putchar('1');
			}
		}
		putchar('\n');
	}
	return 0;
	
}

1004-Quel'Thalas

来源: 杭电杯超级联赛8 算法: 模拟 题目链接: https://acm.dingbacode.com/contest/problem?cid=1051&pid=1004 补完: Yes 完成时间: August 11, 2022

题解

问使用几条线可以覆盖\([0,0]\sim[n,n]\)且不包括\([0,0]\)的所有点, 以\(n\)条竖线和\(n\)条横线即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin>>n;
    cout<<2*n<<endl;
}

int main() {
    int T = 1;
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

1008-Orgrimmar

来源: 杭电杯超级联赛8 算法: 动态规划, 树形DP 题目链接: https://acm.dingbacode.com/contest/problem?cid=1051&pid=1008 补完: Yes 完成时间: August 11, 2022

题目链接

题意简述

给一个有\(n\)个节点，\(n-1\)条边的无向连通图（树），任意删除一些点（以及连接它的边），使得剩下的点构成若干个离散集，其中离散集的定义是每个点至多连接了一条边。

求最多剩下多少点。

题目分析

——题意理解——

要让剩下的点满足这个离散集的定义，那么点要么干脆是孤立的点，要么是两个点由一条边相连。超过三个点相连就必定有一个点和另外两点相连，连接了至少两条边。

——初步思路——

首先我们考虑把树切割成链。

删除若干个点之后树变成了若干条链，那么对一条链，每三个点删除一个点，就能让所有的点都满足定义。

但是好难噢，树链剖分也不是删点剖的，连板子都没有。

构造一些样例尝试之后，也很容易发现删除点是有后效性的，贪心这条路可能也走不通。

具体表现在一个节点被删除之后，它的子树的状态会收到影响。

这么一看好像DP噢，试试，试试。

——经典引入——

本题的要求和一种经典的树形DP非常吻合——求树的最大独立集

独立集：图的一个顶点子集，该子集中的任意两个项点在图中不相邻。

首先，和大部分树形DP相同，整体上使用类似后序遍历的DFS跑，也就是先求子树的最优解，再合并求出亲节点的最优解，最后询问根节点的最优解。

再确定我们需要的变量。首先，必不可少的一个变量表示当前的节点编号；接着，在这个情景里，每个节点有两种选择：选入集合/不选入集合。

我们用\(f[i][0]\)表示不选i节点，用\(f[i][1]\)表示选\(i\)节点。DP函数\(f\)的值是以\(i\)为根节点的子树中的最大独立集节点数（如果点有权值，则是最大点权和）。

如果我们不选\(i\)节点，那么它所有的子节点都是可选择的。用\(j\)表示\(i\)的子节点，那么就有：

\(f[i][0]=\sum max(f[j][0],f[j][1])\) ;

如果我们选了\(i\)节点，那么它的所有子节点都不能选择，否则i就不是独立的点了。

\(f[i][1]=\sum f[j][0];\)

——迁移使用——

本题和求树的最大独立集的问题的差别在于，不要求选取的点集中所有的点都是独立的点，还可以有若干个两个节点相连的点对。

我们还是先试着用\(f[i][0]\)表示不选i节点，用\(f[i][1]\)表示选\(i\)节点。

如果我们不选\(i\)节点，那么它所有的子节点仍然都是可选择的。用\(j\)表示\(i\)的子节点，那么同样有：

\(f[i][0]=\sum max(f[j][0],f[j][1])\) ;

但是，如果我们选了i节点，并不是所有的子节点都不能选择。i可以不是独立的点，它可以和其中一个子节点连接成一个点对。

如果它和一个子节点连接成了一个点对，那么这个子节点的所有子节点，也就是i的孙辈节点都不能再选择了，否则就会形成一个三个点相连的链，不符合题目要求。

当然，也可以一个子节点都不选。这样i的孙辈节点仍然可以自由选择。

既然出现了分异，那么一个\(f[i][1]\)就不够用了。

我们使用\(f[i][1]\)表示和之前一样的，不选择任何子节点的情况。那么状态转移方程显然还是那个样子：

\(f[i][1]=\sum f[j][0];\)

另外加一个\(f[i][2]\)表示选了一个子节点的情况。

具体选哪个子节点，当然贪心地选择选了之后贡献最多的那个。记住选择这个点之后，孙辈的点不能选，所以选择的状态是\(f[j][1]\)而不可以是\(f[j][2]\)。

也就是\(max(f[j][1]-f[j][0])\)对应的点。

处理的时候让\(f[i][2]\)和\(f[i][1\)]先一起累计\(\sum f[j][0]\)，最后\(f[i][2]\)加上选择的子节点多出来的贡献就行。

完整代码

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
#include<iostream>
#include<vector> 
using namespace std; 
const int N = 5e5 + 10;
vector<int> tr[N];
int f[N][3],n;
void dfs(int u,int k) {
  f[u][0]=0;
	f[u][1]=1;
	f[u][2]=1;
	int d=0;
    for (int i=0;i<tr[u].size();i++) {
    	int v=tr[u][i];
        if(v==k)continue;//双向连边的情况下要防止搜回亲节点
        dfs(v,u);
        f[u][0]+=max(max(f[v][0], f[v][1]),f[v][2]);
        f[u][1]+=f[v][0];
        f[u][2]+=f[v][0];
        d=max(d,f[v][1]-f[v][0]);
    }
    f[u][2]+=d;
}
int main() {
		//题目给的建议加入的代码
		int size(512<<20);  // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
		//
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
    	for(int i=1;i<=N;i++)tr[i].clear();
    	cin >> n;
    	for (int i=0;i<n-1;i++) {
    		int x,y;
    	    cin >>x>>y;
    	    tr[y].push_back(x);
    	    tr[x].push_back(y);
    	}
    	dfs(1,0);
    	cout <<max(max(f[1][0], f[1][1]),f[1][2])<<'\n';
    }
    //return 0;  //加上会re 
    exit(0); 
}

1011-Stormwind

来源: 杭电杯超级联赛8 算法: 枚举, 贪心 题目链接: https://acm.dingbacode.com/contest/problem?cid=1051&pid=1011 补完: Yes 完成时间: August 11, 2022

题目链接

题意简述

给一个边长\(n*m\)的矩形，\(n\)和\(m\)是整数。平行矩形边切割这个矩形，把它分成若干的小矩形。每次切割都贯穿矩形，也就是切割线一定要交于原矩形的两边。要求每个小矩形边长是整数且面积不小于k。

求最多切割次数。

题目分析

切割欸，乍一看好像不能贪心。

但由于本题切割要求的特殊性：每一次切割都贯穿矩形，也就是不会有呈T型或者L型镶嵌的矩形存在，小矩形一定是规规整整，每行每列固定数量整齐排列的。

其实也就是确定一个横着切几刀和纵着切几刀的方案。

那么我们是可以贪心的：显然每个矩形在满足面积大于k的情况下应该尽量小，这样才可能切出更多矩形，在这样规整的切割里也就是切更多次了。

也就是对于一个一边长为\(i\)的小矩形，我们找到最小的\(j\)作为另一个边长，满足\(i*j≥k\)。

那么\(j\)就是\(k/i\)向上取整。也就是确定\(i\)之后，\(j\)跟着确定了。

确定了小矩形的长和宽之后，我们可以直接计算出大矩形能切出几个小矩形来。

比如大矩形一边长为\(n\)，对应小矩形的边长为\(i\)，\(n/i\)向下取整就是分割数量，切割次数比这个值小1。

另一边同理。

这样以来，我们只要确定一个小矩形边长之一的\(i\)，这个方案对应的答案就能计算出来了。

本题保证大矩形边长在\(1e5\)以内，显然遍历枚举\(1e5\)范围内的整数\(i\)是可以接受的。

甚至因为只需要满足\(i*j≥k\)，所以i遍历到\(sqrt（k）\)就可以结束，再之后的\(ij\)数对是重复的（比如25和52）。

需要注意，如果计算出来一边切不出哪怕一个小矩形，也就是形如\(n<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
#include<iostream>
#include<cmath> 
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,m,k;
		cin>>n>>m>>k;
		int ans=0;
		for(int i=1;i<=sqrt(k);i++){//枚举矩形的一个变成i 
			int j=k/i;
			if(i*j<k)j++;//找到满足i*j>=k的最小的j 
			//n边切i 
			int a=n/i;//n边可以分出几个i长度的段 
			int b=m/j;
			if(a!=0&&b!=0)//有一边一段都分不出来，答案无效 
			ans=max(ans,a+b-2);//否则更新答案 
			//n边切j 
			a=n/j;
			b=m/i;
			if(a!=0&&b!=0)
			ans=max(ans,a+b-2);
		}
		cout<<ans<<'\n';
	} 
}