首页 / HTML / CodeforcesRound#243(Div.2)??SerejaandTable_html/css_WEB-ITnose

CodeforcesRound#243(Div.2)??SerejaandTable_html/css_WEB-ITnose

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#243(Div.2)??SerejaandTable_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1849字，纯文字阅读大概需要3分钟。

内容图文

codeforces.com/contest/426/problem/D

  • 题意：
    首先给出联通块的定义：对于相邻（上下和左右）的相同的数字视为一个联通块
    现给一个n*m的只有0和1的矩形和数字k，求出最小反转个数使得整体包括若干个矩形联通块（即每个联通块均是矩形）(1?≤?n,?m?≤?100; 1?≤?k?≤?10)
    如果最小次数比k大，输出-1
  • 分析：
    题目的特点是k比较小，也就是说反转的次数比较少，所以可以从这里入手。直接枚举所有的位置肯定是不行了，那么可以这样考虑：（不妨设n>=m）如果n比k大，那么肯定有一些行是不会有反转的数字的，那么我们可以枚举每一行来处理；如果k比n大，这个时候n小于10，所以这时候我们就可以暴力枚举每一行的所有状态，然后处理。
    以上两种方法处理的时候均依据下边的图形特点，只知道一行的时候就可以求出最小的总反转数

    • 最终只能是
    01010...
    10101...
    ...
    的形状（其中一个字符代表一个矩形） 

    const int MAXN = 110;int ipt[MAXN][MAXN];int main(){//    freopen("in.txt", "r", stdin);	int n, m, k;	while (~RIII(n, m, k))	{		REP(i, n) REP(j, m) RI(ipt[i][j]);		if (n < m)		{			REP(i, n) FF(j, i + 1, m) swap(ipt[i][j], ipt[j][i]);			swap(n, m);		}		if (n > k)		{			int ans = INF;			REP(i, n)			{				int tans = 0;				REP(j, n)				{					int cnt = 0;					if (i == j) continue;					REP(k, m)					{						if (ipt[i][k] != ipt[j][k]) cnt++;					}					tans += min(cnt, m - cnt);				}				ans = min(ans, tans);			}			printf("%d\n", ans <= k ? ans: -1);		}		else		{			int ans = INF;			REP(i, n)			{				int all = 1 << m;				for (int q = 0; q < all; q++)				{					int diff = 0;					for (int t = 0, l = 1; t < m; l <<= 1, t++) if (((q & l) != 0) != ipt[i][t]) diff++;					if (diff > k) continue;					int tans = 0;					REP(j, n)					{						if (i == j) continue;						int cnt = 0;						for (int t = 0, l = 1; t < m; t++, l <<= 1) if (((q & l) != 0) != ipt[j][t]) cnt++;						tans += min(cnt, m - cnt);					}					ans = min(ans, diff + tans);				}			}			printf("%d\n", ans <= k ? ans: -1);		}	}	return 0;}

    内容总结

    以上是互联网集市为您收集整理的CodeforcesRound#243(Div.2)??SerejaandTable_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#243(Div.2)??SerejaandTable_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

    内容备注

    版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

    内容手机端

    扫描二维码推送至手机访问。

    本文链接：https://qyyshop.com/info/397957.html

    来源：【匿名】