《挑战程序设计竞赛》3.2.2 常用技巧-反转 POJ3276 3279 3185 1222

本文主要是介绍《挑战程序设计竞赛》3.2.2 常用技巧-反转 POJ3276 3279 3185 1222,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

POJ3276

http://poj.org/problem?id=3276

题意

N头牛排成一列1<=N<=5000。每头牛或者向前(表示为F)或者向后(表示为B)。为了让所有牛都面向前方,农夫每次可以将K头连续的牛转向1<=K<=N,求操作的最少次数M和对应的最小K。

思路

所有情况穷举O(2^N)肯定超时。
顺序考虑每头牛的反转方向能不能行呢?因为想改变一头牛的方向就必定影响k头牛,但再思考一下,当一头牛被反转2的倍数次时,与初始方向相同,可视为无反转,所以对于每头牛来说,只有被反转和未反转两种操作。
但我们要枚举的是大小为K的区间的反转,顺序考虑时每个区间的反转状态可以被前面的状态所确定,这时候最坏情况下复杂度O(N^3)。这里可以用sum来记录前面的反转状态和,从而将复杂度降到O(N^2),具体见代码。
此题值得注意的地方:
(1)判断条件很容易出错,需要考虑清楚n和k的所有情况,我因为没写好判断,WA了两次。
(2)这个题中二进制的妙用可在代码中细细体会。
(3)用bool存储似乎能进一步缩减内存使用,当然代码需要同步优化。

代码

Source CodeProblem: 3276       User: liangrx06
Memory: 276K        Time: 360MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;const int N = 5000;int main(void)
{int n;int f[N], t[N];cin >> n;char c[2];for (int i = 0; i < n; i ++) {scanf("%s", c);if (c[0] == 'F')f[i] = 0;elsef[i] = 1;}int ansm = n, ansk = 1;for (int k = 1; k <= n; k ++) {int m = 0;int sum = 0;for (int i = 0; i <= n-k; i ++) {t[i] = (f[i] + sum)&1;m += t[i];sum += t[i];if (i-k+1 >= 0) sum += t[i-k+1];}int flag = 1;for (int i = n-k+1; i < n; i ++) {if ( ((f[i] + sum)&1) == 1)flag = 0;if (i-k+1 >= 0) sum += t[i-k+1];}if (flag == 1 && m < ansm) {ansm = m;ansk = k;}}printf("%d %d\n", ansk, ansm);return 0;
}

POJ3279

http://poj.org/problem?id=3279

题意

一个m*n的01矩阵,每次点击(x,y),那么她的上下左右以及本身就会0变1,1变0,问把矩阵变成全0的,最小需要点击多少步。如果有多个符合条件,求字典序最小的。

思路

枚举第一行翻转情况,2^m,然后验证,由于第一行确定了,后面就可以跟着确定了。
这个题看似思路清晰,实际做的过程中却出了不少错误,比如:
(1)字典序弄反了;
(2)应该验证最后一行,结果想错了;
(3)最优解首先要求的是最小步数,而不是字典序最小,我把顺序弄反了。
代码最终基本和书中例题一样了。

代码

Source CodeProblem: 3279       User: liangrx06
Memory: 248K        Time: 547MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;const int N = 15;int m, n;
int f0[N][N], f[N][N], t[N][N], opt[N][N];
int d[5][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {0, 0}};void flip(int i, int j)
{if (t[i][j] == 0) return;for (int k = 0; k < 5; k ++) {int ii = i+d[k][0];int jj = j+d[k][1];if (0 <= ii && ii < m && 0 <= jj && jj < n)f[ii][jj] = (f[ii][jj]+1) & 1;}
}int main(void)
{cin >> m >> n;for (int i = 0; i < m; i ++)for (int j = 0; j < n; j ++)scanf("%d", &f0[i][j]);int minfcount = n*m+1;for (int r = 0; r < (1<<n); r ++) {int fcount = 0;memcpy(f, f0, sizeof(f));for (int j = 0; j < n; j ++) {t[0][n-1-j] = (r>>j)&1;fcount += t[0][n-1-j];flip(0, n-1-j);}for (int i = 1; i < m; i ++) {for (int j = 0; j < n; j ++) {t[i][j] = f[i-1][j];fcount += t[i][j];flip(i, j);/*printf("i=%d, j=%d==========\n", i, j);if (t[i][j]) {for (int ii = 0; ii < m; ii ++)for (int jj = 0; jj < n; jj ++)printf("%d%c", f[ii][jj], (jj == n-1) ? '\n' : ' ');}*/}}bool flag = true;for (int j = 0; j < n; j ++) {if (f[m-1][j] == 1) {flag = false; break;}}if (flag == true && fcount < minfcount) {minfcount = fcount;memcpy(opt, t, sizeof(t));}}if (minfcount == n*m+1)printf("IMPOSSIBLE\n");else {for (int i = 0; i < m; i ++)for (int j = 0; j < n; j ++)printf("%d%c", opt[i][j], (j == n-1) ? '\n' : ' ');}return 0;
}

POJ3185

http://poj.org/problem?id=3185

题意

将一列碗(20个)翻成口朝上,一把下去可能同时反转3个或2个(首尾),求最小翻转次数。

思路

应该说是3276题的简单版,只有两种情况需要考虑:以第一个为中心的反转是否做。后续的反转据此可以确定,然后检验是否符合条件即可。

代码

Source CodeProblem: 3185       User: liangrx06
Memory: 164K        Time: 0MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int n = 20;
int f0[n], f[n], t[n];void flip(int x)
{if (!t[x]) return;f[x] = (f[x]+1)&1;if (x > 0) f[x-1] = (f[x-1]+1)&1;if (x < n-1) f[x+1] = (f[x+1]+1)&1;
}int main(void)
{for (int i = 0; i < n; i ++)scanf("%d", &f0[i]);int best = n;for (int k = 0; k < 2; k ++) {memcpy(f, f0, sizeof(f));t[0] = k;int cnt = t[0];flip(0);for (int i = 1; i < n; i ++) {t[i] = f[i-1];cnt += t[i];flip(i);}if (f[n-1] == 0) {best = min(cnt, best);}}printf("%d\n", best);return 0;
}

POJ1222

http://poj.org/problem?id=1222

题意

poj3279的简单版,详见上文。
这个题固定了行列,而且只需要任意求一个答案就可以。

思路

直接把3279代码拿过来稍作修改即可。

代码

Source CodeProblem: 1222       User: liangrx06
Memory: 244K        Time: 16MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 6;int m = 5, n = 6;
int f0[N][N], f[N][N], t[N][N], opt[N][N];
int d[5][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {0, 0}};void flip(int i, int j)
{if (t[i][j] == 0) return;for (int k = 0; k < 5; k ++) {int ii = i+d[k][0];int jj = j+d[k][1];if (0 <= ii && ii < m && 0 <= jj && jj < n)f[ii][jj] = (f[ii][jj]+1) & 1;}
}int main(void)
{int casecount;cin >> casecount;for (int puzzle = 1; puzzle <= casecount; puzzle ++) {for (int i = 0; i < m; i ++)for (int j = 0; j < n; j ++)scanf("%d", &f0[i][j]);int minfcount = n*m+1;for (int r = 0; r < (1<<n); r ++) {int fcount = 0;memcpy(f, f0, sizeof(f));for (int j = 0; j < n; j ++) {t[0][n-1-j] = (r>>j)&1;fcount += t[0][n-1-j];flip(0, n-1-j);}for (int i = 1; i < m; i ++) {for (int j = 0; j < n; j ++) {t[i][j] = f[i-1][j];fcount += t[i][j];flip(i, j);}}bool flag = true;for (int j = 0; j < n; j ++) {if (f[m-1][j] == 1) {flag = false; break;}}if (flag == true && fcount < minfcount) {minfcount = fcount;memcpy(opt, t, sizeof(t));break;}}printf("PUZZLE #%d\n", puzzle);for (int i = 0; i < m; i ++)for (int j = 0; j < n; j ++)printf("%d%c", opt[i][j], (j == n-1) ? '\n' : ' ');}return 0;
}

这篇关于《挑战程序设计竞赛》3.2.2 常用技巧-反转 POJ3276 3279 3185 1222的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/868683

相关文章

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Linux上设置Ollama服务配置(常用环境变量)

《Linux上设置Ollama服务配置(常用环境变量)》本文主要介绍了Linux上设置Ollama服务配置(常用环境变量),Ollama提供了多种环境变量供配置,如调试模式、模型目录等,下面就来介绍一... 目录在 linux 上设置环境变量配置 OllamPOgxSRJfa手动安装安装特定版本查看日志在

电脑win32spl.dll文件丢失咋办? win32spl.dll丢失无法连接打印机修复技巧

《电脑win32spl.dll文件丢失咋办?win32spl.dll丢失无法连接打印机修复技巧》电脑突然提示win32spl.dll文件丢失,打印机死活连不上,今天就来给大家详细讲解一下这个问题的解... 不知道大家在使用电脑的时候是否遇到过关于win32spl.dll文件丢失的问题,win32spl.dl

Java常用注解扩展对比举例详解

《Java常用注解扩展对比举例详解》:本文主要介绍Java常用注解扩展对比的相关资料,提供了丰富的代码示例,并总结了最佳实践建议,帮助开发者更好地理解和应用这些注解,需要的朋友可以参考下... 目录一、@Controller 与 @RestController 对比二、使用 @Data 与 不使用 @Dat

Mysql中深分页的五种常用方法整理

《Mysql中深分页的五种常用方法整理》在数据量非常大的情况下,深分页查询则变得很常见,这篇文章为大家整理了5个常用的方法,文中的示例代码讲解详细,大家可以根据自己的需求进行选择... 目录方案一:延迟关联 (Deferred Join)方案二:有序唯一键分页 (Cursor-based Paginatio

Python实现常用文本内容提取

《Python实现常用文本内容提取》在日常工作和学习中,我们经常需要从PDF、Word文档中提取文本,本文将介绍如何使用Python编写一个文本内容提取工具,有需要的小伙伴可以参考下... 目录一、引言二、文本内容提取的原理三、文本内容提取的设计四、文本内容提取的实现五、完整代码示例一、引言在日常工作和学

Redis中的常用的五种数据类型详解

《Redis中的常用的五种数据类型详解》:本文主要介绍Redis中的常用的五种数据类型详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Redis常用的五种数据类型一、字符串(String)简介常用命令应用场景二、哈希(Hash)简介常用命令应用场景三、列表(L

python中time模块的常用方法及应用详解

《python中time模块的常用方法及应用详解》在Python开发中,时间处理是绕不开的刚需场景,从性能计时到定时任务,从日志记录到数据同步,时间模块始终是开发者最得力的工具之一,本文将通过真实案例... 目录一、时间基石:time.time()典型场景:程序性能分析进阶技巧:结合上下文管理器实现自动计时