-
2022杭电多校赛第八场
2022杭电多校赛第八场
1004.Quel’Thalas
-
题意
- 在二维坐标系上，给一个长度为n左下角为0的正方形
- 现在要求划线，这些线要经过所有正方形覆盖的点，除去(0,0)点
- 问最少需要画多少条线
-
题解
- 横着+竖着划线就是最优解之一，以n=2为例，如图[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6SLyHNCp-1660229480541)(https://s3.bmp.ovh/imgs/2022/08/11/720fc784efe4d33d.png)]
- 证明上述做法是最优解之一：
-
代码
#includeusing namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; cout<<2*n<<'\n'; } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
1001.Theramore
-
题意
- 给一个只含01的字符串s，可以进行操作：对任意的奇数长度区间翻转
- 操作可任意次数，输出s能变成的字典序最小的字符串
-
题解
- 贪心看，希望把所有0放在最前，把所有1放在最后。只交换长度为3的区间，那么索引同奇(偶)的可以任意交换，所以可以把奇数下标元素拉出来前面放0后面放1，偶数下标元素同理，最后再拼凑回去就是答案
-
代码
#include#include using namespace std; void solve() { string s; cin>>s; int len=s.size(); int odd_zeros=0,zeros=0; for(int i=0;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
1011.Stormwind
-
题意
- 给一个n*m的矩形，只能横着与竖着切，并且切下去一定贯穿了矩形
- 问最多可以切多少刀，使得所有切成的小矩形面积不小于k
-
题解
- 枚举方法：枚举小长方形。以枚举出来的小长方形为最小切割，计算大长方形最多能切几刀。计算这里注意如果枚举的如果就是小长方形的宽，那么需要再考虑一下n,m互换的结果。如果枚举的就是小长方形的一条边，那么不需要互换n,m
- 贪心策略：假设固定一边不切，让某一边切的次数尽可能多，然后计算切另一边。一样需要考虑n,m互换对答案的影响
-
代码
#includeusing namespace std; int t,n,m,k; int main() { cin>>t; while(t--) { cin>>n>>m>>k; int ans=0; for(int x=1;x*x<=k;x++) { int y=(k-1)/x+1;//向上取整 if(x<=n&&y<=m) ans=max(ans,(n/x-1)+(m/y-1));//两种切割方式取最大值 if(x<=m&&y<=n) ans=max(ans,(m/x-1)+(n/y-1)); } cout< - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
第二种枚举
#includeusing namespace std; int t,n,m,k; int main() { cin>>t; while(t--) { cin>>n>>m>>k; int res=0; for(int d=1;d<=m;d++) { int h=(k-1)/d+1; if(h>n) continue; res=max(res,(m/d-1)+(n/h-1)); } cout< - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
贪心
#includeusing namespace std; int t,n,m,k; int main() { cin>>t; while(t--) { cin>>n>>m>>k; int res=0; if(n>=k) {//大长方形宽够，那么切成长条形，即让大长方形的长且切足够多次，最多切成1间隔 int ans=m-1;//竖着切m-1条 ans+=n/k-1;//横着切的条数 res=max(res,ans); } else {//宽不够宽肯定不切，找最小的竖着切的间隔 int d=(k-1)/n+1;//间隔 int ans=m/d-1;//竖着切条数为总条数，而横着不切 res=max(res,ans); } swap(n,m);//n,m互换，再来一遍 if(n>=k) { int ans=m-1; ans+=n/k-1; res=max(res,ans); } else { int d=(k-1)/n+1; int ans=m/d-1; res=max(res,ans); } cout< -
- 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
1008.Orgrimmar
-
题意
- 给一颗以1为根的树，从中选择x个点，使得所有这些点的度数<=1
- 求出x的最大值
-
题解
- 容易看出是树形dp，涉及到一棵树中选或者不选某些点，同时父子节点还有相互限制
- 状态定义：
f[u,0]:以u为根的子树中，不选u，符合条件的最大点数量 f[u,1]:以u为根的子树中，选择u但不选择子节点连接，符合要求的最大点数量 f[u,2]:以u为根的子树中，选择u同时选择某一个子节点连接，符合要求的最大点数量- 1
- 2
- 3
- 状态转移：
f[u,0]:根节点u不选，那么对于任意的u的子节点都没有限制，对于某一个子节点选择其最大值max(f[v,0],f[v,1],f[v,2])，f[u,0]就是这些子节点最大值的总和 f[u,1]:根节点u选择，且不选任意一个子节点，所以从子节点转移过来的话，符合要求的只有所有子节点不选的情况，即f[u,1]=sum(f[v,0])，同时加上自己+1 f[u,2]:在选择u的情况下，加上只选某一个子节点连接的限制，先假设点vv是选择连接的那个点，那么壮医过来就是f[u,2]=f[u,1](选择u的情况下)-f[vv,0](vv必选，减去前面加上的f[vv,0])+f[vv,1](选择点vv,同时vv点不能再选择vv的子节点相连接了)+1(同时加上自己)。由式子可得，我们应该找一个f[v,1]-f[v,0]最大的点才会使得f[u,2]最大- 1
- 2
- 3
- 4
- 5
f [ u , 0 ] = ∑ v ∈ c h i l d u m a x ( f [ v , 0 ] , f [ v , 1 ] , f [ v , 2 ] ) f [ u , 1 ] = ∑ v ∈ c h i l d u f [ v , 0 ] + 1 f [ u , 2 ] = ∑ v ∈ c h i l d u f [ v , 0 ] − m a x ( f [ v , 1 ] − f [ v , 0 ] ) + 1
f[u,0]=v∈childu∑max(f[v,0],f[v,1],f[v,2])f[u,1]=v∈childu∑f[v,0]+1f[u,2]=v∈childu∑f[v,0]−max(f[v,1]−f[v,0])+1f [ u , 0 ] = ∑ v ∈ c h i l d u m a x ( f [ v , 0 ] , f [ v , 1 ] , f [ v , 2 ] ) f [ u , 1 ] = ∑ v ∈ c h i l d u f [ v , 0 ] + 1 f [ u , 2 ] = ∑ v ∈ c h i l d u f [ v , 0 ] − m a x ( f [ v , 1 ] − f [ v , 0 ] ) + 1 -
代码
#include
using namespace std;
const int N=5e5+10;
int t,n;
int h[N],e[2*N],ne[2*N],idx;//无向边，开两倍
int f[N][3];
void add(int a,int b) {//加边
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa) {//找到以u为根的，所求的三种情况的最值
int mx0=0,mx1=0,mx2=0;
for(int i=h[u];~i;i=ne[i]) {
int j=e[i];
if(j==fa) continue;//链的是父节点跳过
dfs(j,u);//递归计算子节点
mx0+=max(max(f[j][0],f[j][1]),f[j][2]);//状态转移
mx1+=f[j][0];
mx2=max(mx2,f[j][1]-f[j][0]);
}
f[u][0]=mx0;
f[u][1]=mx1+1;
f[u][2]=mx1+mx2+1;
}
void solve() {
cin>>n;
idx=0;//清空初始化
for(int i=1;i<=n;i++) h[i]=-1,f[i][0]=0,f[i][1]=0,f[i][2]=0;//清空初始化，谨防memset超时
for(int i=1;i>a>>b;
add(a,b);add(b,a);//无向边
}
dfs(1,0);
cout<>t;
while(t--) solve();
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
- 52
- 53
- 54
1005.Ironforge
-
题意
-
题解
* -
代码
- 1