To_Heart—题解——P6234 [eJOI2019] T形覆盖

这篇具有很好参考价值的文章主要介绍了To_Heart—题解——P6234 [eJOI2019] T形覆盖。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

link.

突然很想写这篇题解。虽然题目不算难。

考场只有30分是为什么呢?看来是我没有完全理解这道题目吧!

首先很明显的转换是,把 T 型覆盖看成十字形,再考虑最后减去某一块的贡献。

然后然后直接往原图上面放十字形!对于每一个十字的中心来说,实际上它只需要三个相邻的方块就可以了。而我们发现两个十字重合的部分不会超过两个方块,也就是说把这两个方块任意分配给两个人,就能保证这两个每个人都只会舍弃一个方块。

因为每次两个十字的重合最多只能让每个点丢弃一个方块,并且每次重合至少有一个十字会丢弃掉一个方块,所以惊天的结论是我们可以直接计算整个十字连通块的中心点和非中心点的个数。如果非中心点的个数大于等于中心点的个数的三倍,那么当前连通块一定合法,否则不能保证每个十字的中心点都能分配到刚好三个非中心点,即无解。

但是可能有非中心点的个数大于中心点的个数的三倍。这种情况说明所有的十字都只重合了一个点,那么必须要丢掉一个非中心点。因为要权值最大所以丢掉最小权值的就好了。

其实这个的实现方式有很多,但是我使用了并查集。为什么呢?因为其他题解就是用的并查集啊!

然后并查集需要注意的点就是不能选择中心点啊。中心点的权值设为最大值好不好。文章来源地址https://www.toymoban.com/news/detail-663118.html

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
int a[1000005];
int ID(int x,int y){
	return (x-1)*m+y;
}
int pre[1000005],dp[1000005];
int sz[1000005][2];
long long sum[1000005];

bool vis[1000005];

struct zz{
	int x,y;
}t[1000005];

int Find(int x){
	if(pre[x]!=x) pre[x]=Find(pre[x]);
	return pre[x];
}
void Join(int x,int y){
	int fx=Find(x),fy=Find(y);
	if(fx==fy) return ;
	pre[fy]=fx,sum[fx]+=sum[fy],dp[fx]=min(dp[fx],dp[fy]),sz[fx][0]+=sz[fy][0],sz[fx][1]+=sz[fy][1];
}

int fx[5]={0,1,-1,0,0};
int fy[5]={0,0,0,1,-1};

int main(){
//	freopen("t-covering.in","r",stdin);
//	freopen("t-covering.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[ID(i,j)]);
	cin>>k;
	for(int i=1,x,y;i<=k;i++) scanf("%d%d",&x,&y),t[i]=(zz){x+1,y+1};
	for(int i=1;i<=k;i++) vis[ID(t[i].x,t[i].y)]=1;
	for(int i=1;i<=n*m;i++){
		pre[i]=i,sum[i]=a[i],dp[i]=a[i],sz[i][vis[i]]=1;
		if(vis[i]) dp[i]=0x3f3f3f3f; 
	}
	for(int i=1;i<=k;i++) for(int j=1;j<=4;j++){
		int x=t[i].x,y=t[i].y;int dx=x+fx[j],dy=y+fy[j];
		if(dx<=0||dx>n||dy<=0||dy>m) continue;
		Join(ID(x,y),ID(dx,dy)); 
	}
	long long ans=0;
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		int x=(ID(i,j));int fx=Find(x);
		if(vis[fx]) continue; vis[fx]=1;
		if(sz[fx][0]<sz[fx][1]*3) return printf("No\n"),0;
        else if(sz[fx][0]==sz[fx][1]*3) ans+=sum[fx];
        else ans+=sum[fx]-dp[fx];
	}
	cout<<ans<<endl;
	return 0;
}

到了这里,关于To_Heart—题解——P6234 [eJOI2019] T形覆盖的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论入门题题解

    ✨欢迎来到脑子不好的小菜鸟的文章✨       🎈创作不易,麻烦点点赞哦🎈           所属专栏:刷题_脑子不好的小菜鸟的博客-CSDN博客           我的主页:脑子不好的小菜鸟           文章特点:关键点和步骤讲解放在           代码相应位置 注意:该题用上一

    2024年03月16日
    浏览(35)
  • 密文题解(图论+字典树)

    题目大意 有一段长度为 n n n 的密文,密文的每一位都可以用一个非负整数来描述,并且每一位都有一个权值 a i a_i a i ​ 。你可以操作任意多次,每次操作可以选择任意一段密文,花费选择的所有位上权值的异或和的代价获得这段密文每一位的异或和。求至少需要花费多少代

    2024年02月13日
    浏览(34)
  • 算法题目题单+题解——图论

    本文为自己做的一部分图论题目,作为题单列出,持续更新。 题单由题目链接和题解两部分组成,题解部分提供简洁题意,代码仓库:Kaiser-Yang/OJProblems。 对于同一个一级标题下的题目,题目难度尽可能做到递增。 题目链接:Luogu P3547 [POI2013] CEN-Price List 题解: 题目链接:

    2024年02月19日
    浏览(38)
  • 2019年 团体程序设计天梯赛——题解集

    前言: Hello各位童学大家好!😊😊,茫茫题海你我相遇即是缘分呐,或许日复一日的刷题已经让你感到疲惫甚至厌倦了,但是我们真的真的已经达到了我们自身极限了吗?少一点自我感动,没有结果前别太松懈,请相信 ”一万小时定理“ 。当你迷茫时抬头看看远方回想当初

    2023年04月17日
    浏览(82)
  • 2019 第十届蓝桥杯省赛A组题解

    本次试题难度(对专业算法竞赛选手来说)不大,但是考验基本的编程基本功和数学思维。估计完成80%即可获得省一进入决赛(根据一些公开的反馈,如果有准确数据请告诉我),因此更多的是需要细心。 至于C/C++还是Java我觉得不重要,因为题目除了顺序有点不同,内容是一

    2023年04月09日
    浏览(47)
  • 图论技巧之反向建图 (P1629题解)

    对于单源最短路径无论是迪杰斯特拉还是SPFA,都只可以求出一个点到其他各它n-1个点的最短路径,但是假如现在需要求n-1个点到达某个点的最短路径一般会采用floyd算法,但是floyd算法的复杂度是 O ( n 3 ) O(n^3) O ( n 3 ) 因此很有可能会超时,因此此时可以采用反向建图,即边反

    2024年04月13日
    浏览(27)
  • 第三章 图论 No.11二分图,匈牙利算法与点覆盖

    257. 关押罪犯 - AcWing题库 最大最小问题,一眼二分 答案的范围在 [ 1 , 1 e 9 ] [1, 1e9] [ 1 , 1 e 9 ] 之间,二分答案,check(mid) check:将所有权值大于mid的边进行二分,若能得到二分图,返回true,否则返回false 最终将得到最优解ans,所有大于ans的边组成的图为二分图,若是图中有边

    2024年02月12日
    浏览(42)
  • 2019湖南省大学生程序设计竞赛题解(D)

    很妙的类似区间dp, 我自己是想不到,本题解题思路来自学长的博客: 长沙橘子猫 题意 有一个长度为 n n n 的序列,你可以给每个位置填 0 ∼ 9 0sim9 0 ∼ 9 的一个数,有 m m m 个限制,每个限制 [ l i , r i ] [l_{i}, r_{i}] [ l i ​ , r i ​ ] 要求区间内的数相乘必须为 9 9 9 的倍数,问

    2023年04月15日
    浏览(64)
  • B3610 [图论与代数结构 801] 无向图的块 题解

    2023 2023 2023 ,再见。 2024 2024 2024 ,你好! 其实就是统计点双连通分量的个数。需要注意的是,孤立点在这里不被看作块。本文使用 tarjan 算法来解决这道题。 概念明晰 时间戳:这里记为 d f n i dfn_i df n i ​ ,表示第一次深度优先搜索到节点 i i i 的时间。时间 t i m e ∈ N + t

    2024年02月03日
    浏览(41)
  • 【题解】JZOJ6578 / 洛谷P5201[USACO2019Jan]Shortcut G

    洛谷 P5201 [USACO19JAN] Shortcut G 在一个带权无向连通图上,每个点有 a i a_i a i ​ 只奶牛,奶牛会走最短路径到 1 1 1 ,如果有多条路径,选择字典序最小的,定义移动总时间为所有奶牛走到 1 1 1 的时间之和。你可以修建一条从任意一点到 1 1 1 的边权为 t t t 的边,奶牛只有在平时

    2024年02月11日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包