博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj1147
阅读量:7118 次
发布时间:2019-06-28

本文共 1652 字,大约阅读时间需要 5 分钟。

题意:给定一个长度为n的01序列,作为矩阵的第一行,每次把本行的最后一位挪到第一位,其余各位向后移一位,构成新的序列,作为下一行,最终形成n*n的矩阵。把矩阵各行交换位置,使得从上到下各序列按字典序从小到大排列,又得到了n*n的矩阵。给出矩阵的最后一列,求矩阵的第一行。

分析:我们发现这个矩阵有个特点。将矩阵的每行看作一个01序列,得到一个序列集合A。然后将矩阵的最后一列移到第一列,其余列后移,然后将没行看作一个01序列,得到一个序列集合B。A与B一定是同一个集合。根据这个性质我们可以进一步得知,把后来经过列移动的矩阵按行字典序排序后可得到排序后的原矩阵。在这个排序变换过程中如果我们只关注矩阵的第一列,我们可以发现,相当于原矩阵的最后一列移到前面之后内部经过了一定的变换位置,变成了原矩阵的第一列。而再次进行这个操作(最后一列移到前面,排序)我们会发现原矩阵的第一列移动到了第二列的位置,并经过了相同的变换变为了原矩阵的第二列。也就是说我们只要找到了这个变换规律,那么我们一定可以由最后一列推出第一列、第二列……直到所有列。由于排序的规则是字典序,所以第一列一定是上面全是0,下面全是1。我们根据最后一列的01的个数与第一列相同,可以得知第一列是什么样的。最后一列移到最前面之后,进行排序时,如果两行的第一位(位于原最后一列中)相同,则排序后他们的前后顺序一定是不变的,因为后面的序列为原矩阵的序列,原矩阵是排过序的,所以在之前就排好了。这样规律就出来了,看原最后一列,现在的第一列,先只看为0的,第i个0会被排到第i行,再只看为1的,倒数第i个1会被排到倒数第i行。排序后我们可得知现在的最后一列一定就是排好序的原矩阵的最后一列。所以我们将最后一列填好。这样我们就得到了矩阵的两列,再进行同样的操作(将最后一列串到第一列,其余列后移,按上述方法对各行排序,填写最后一列)可得到矩阵的三列。

有了规律,一直递推即可。

View Code
#include 
#include
#include
#include
usingnamespace std; #define maxn 3004 int n; int f[maxn]; int g[maxn]; int next[maxn]; int cnt, cnt1; int main() {
//freopen("t.txt", "r", stdin); scanf("%d", &n); cnt = cnt1 =0; for (int i =0; i < n; i++) {
scanf("%d", &f[i]); if (f[i] ==0) cnt++; } for (int i =0; i < n; i++) {
if (f[i]) next[i] = cnt + cnt1++; else next[i] = i - cnt1; } memset(f, 0, sizeof(f)); for (int i = cnt; i < n; i++) f[i] =1; printf("%d", f[0]); for (int i =0; i < n -1; i++) {
for (int j =0; j < n; j++) g[next[j]] = f[j]; memcpy(f, g, n *sizeof(int)); printf(" %d", f[0]); } putchar('\n'); return0; }

转载地址:http://lliel.baihongyu.com/

你可能感兴趣的文章
LeetCode: Path Sum 解题报告
查看>>
Struts2之文件上传(单文件/多文件)
查看>>
【AS3 Coder】任务七:初涉PureMVC——天气预报功能实现
查看>>
基于HT for Web的Web SCADA工控移动应用
查看>>
JavaScript-常用正则函数(适合忘记时看)
查看>>
Sphinx-实战
查看>>
窗体之间传递值的几种方法
查看>>
onSingleTapUp()和onSingleTapConfirmed()的区别
查看>>
Android app应用多语言切换功能实现
查看>>
严重: Catalina.stop: java.net.ConnectException: Connection refused: connect
查看>>
几个常用的ps命令
查看>>
java如何获取本机IP
查看>>
gradle入门(1-7)eclipse和gradle集成插件的安装和使用
查看>>
uva 1378 - A Funny Stone Game sg博弈
查看>>
F#试用感受
查看>>
JavaScript继承详解(三)
查看>>
Java/JSP中使用JDBC连接SQL Server 2000/2005
查看>>
SSH框架+mysql+tomcat 服务器 中文乱码解决方案
查看>>
C++ 沉思录——Chap4:设计类的核查表
查看>>
Oracle笔记(一) Oracle简介及安装
查看>>