Good Bye 2014 B. New Year Permutation 【传递闭包 贪心】
解题思路:给出一列数an,再给出一个矩阵d[i][j],在满足d[i][j]=1的情况下,称a[i]和a[j]可以交换,问经过交换最后得到字典序最小的数列a[n]
首先是贪心的思想,大的能换就换到后面去,这样尽可能使小的在前面。
然后是判断a[i]和a[j]能不能交换, 如果d[i][j]=1,表示a[i]和a[j]可直接交换 如果d[i][k]=1&&d[k][j]=1,表示a[i]可以通过a[k]和a[j]交换
比如 1 7 3 4 2 5 假如 7能和4交换,4能和2交换,那么7也能和2交换
处理矩阵的时候用到了紫书中的传递闭包
for(k=;k<=n;k++)
for(i=;i<=n;i++)
for(j=;j<=n;j++)
d[i][j]=d[i][j]||(d[i][k]&&d[k][j]);
2 seconds
256 megabytes
standard input
standard output
User ainta has a permutation p1, p2, ..., pn. As the New Year is coming, he wants to make his permutation as pretty as possible.
Permutation a1, a2, ..., an is prettier than permutation b1, b2, ..., bn, if and only if there exists an integer k (1 ≤ k ≤ n) where a1 = b1, a2 = b2, ..., ak - 1 = bk - 1 and ak < bk all holds.
As known, permutation p is so sensitive that it could be only modified by swapping two distinct elements. But swapping two elements is harder than you think. Given an n × n binary matrix A, user ainta can swap the values of pi and pj (1 ≤ i, j ≤ n, i ≠ j) if and only if Ai, j = 1.
Given the permutation p and the matrix A, user ainta wants to know the prettiest permutation that he can obtain.
The first line contains an integer n (1 ≤ n ≤ 300) — the size of the permutation p.
The second line contains n space-separated integers p1, p2, ..., pn — the permutation p that user ainta has. Each integer between 1and n occurs exactly once in the given permutation.
Next n lines describe the matrix A. The i-th line contains n characters '0' or '1' and describes the i-th row of A. The j-th character of thei-th line Ai, j is the element on the intersection of the i-th row and the j-th column of A. It is guaranteed that, for all integers i, j where 1 ≤ i < j ≤ n, Ai, j = Aj, i holds. Also, for all integers i where 1 ≤ i ≤ n, Ai, i = 0 holds.
In the first and only line, print n space-separated integers, describing the prettiest permutation that can be obtained.
7 5 2 4 3 6 7 1 0001001 0000000 0000010 1000001 0000000 0010000 1001000
1 2 4 3 6 7 5
5 4 2 1 5 3 00100 00011 10010 01101 01010
1 2 3 4 5
In the first sample, the swap needed to obtain the prettiest permutation is: (p1, p7).
In the second sample, the swaps needed to obtain the prettiest permutation is (p1, p3), (p4, p5), (p3, p4).
A permutation p is a sequence of integers p1, p2, ..., pn, consisting of n distinct positive integers, each of them doesn't exceed n. Thei-th element of the permutation p is denoted as pi. The size of the permutation p is denoted as n.
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1010],d[1010][1010];
char s[1020];
int main()
{
int n,i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<=n;i++)
{
scanf("%s",&s);
for(j=0;j<n;j++)
{
if(s[j]=='1') d[i][j+1]=1;
else d[i][j+1]=0;
}
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=d[i][j]||(d[i][k]&&d[k][j]); for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(d[i][j]&&a[i]>a[j])
swap(a[i],a[j]);
}
}
for(i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[i]);
}
最新文章
- python---socketserver模块
- SQLMAP使用笔记
- c# 调用分页(控制器端的)与时间的格式
- Oracle11G安装之后
- poj 1654 Area (多边形求面积)
- UIStepper
- Linux下软件安装,卸载,管理
- javascript函数的基础功能
- 关于第一次STM32连接电脑下载程序
- sql server 把数据 复制成脚本文件
- Laravel5中使用阿里大于(鱼)发送短信验证码
- jsp:forward动作功能
- Ubuntu 装机软件
- css 实现的网页布局
- 软件工程作业 - Week 1
- border-color: transparent rgb(255, 48, 48) transparent transparent;
- Linux实验楼学习之二
- linux 的dmesg命令
- JAVA-JSP Scriptlets(JSP小脚本)
- c语言define和typedef区别和使用
热门文章
- P1888 三角函数
- c#将http调用返回额json中的有关中文的unicode转换为中文
- JDBC的总结
- js正则获取html字符串指定的dom元素和内容
- Unity 控制public/private 是否暴露给Inspector面板
- Java基础——Servlet
- luogu 自适应Simpson2
- BZOJ 4044 Virus synthesis (回文自动机+dp)
- 2019-02-25 SQL:cast(itemvalue as decimal(19,4))
- Thunder9(迅雷9)去掉右侧浏览器广告的方法