poj 2470 Ambiguous permutations

做到这道题目,我是真的想吐槽有些人了。。。因为本人是一个很喜欢理清思路的人,如果不理清思路,我几乎不能向下走一步,所以吐槽某些思路混乱的人。。。

所以每每看到网上一些刷题的解题报告里面说:迷迷糊糊就AC了,我是坚决不做这种事情的。。。

这道题,英文题目是不太好懂,但是中文该好懂吧,本来可以很简单把题目说清楚的,看了discuss的一些伙计非把题目简单的意思说的很晦涩难懂。。。

真不知道这些哥们的大脑怎么长的,同样的水题,为什么不能搞的不这么“高端”呢。。。

让我想起了有时看解题报告,一些人的代码简直不能入目,完全不知道在想些什么,写的相当晦涩。。我说就不能用用途去命名每个变量吗。。。

进入正题,先放上discuss某哥们的解释:

新的排列中第i个数是旧的排列中数i(在旧的排列中)的位置。比如,新排列中5(第1个数)是旧排列中数1的位置(第5个)。

我看了一下,呵呵了一下,其实完全可以用更简单的表述。。。

下面贴我的解释:

就是新旧位置和数字的互换!比如,原来的数字和位置(位置用[]框起来)是:
 2   3   4   5   1
[1] [2] [3] [4] [5]

-->

 5   1   2   3   4
[1] [2] [3] [4] [5]

原来2在位置[1],现在1在位置[2]。。。以此类推,不知道为什么你们要说得这么麻烦

好了,贴代码:

#include <stdio.h>

int a[100002];
int b[100002]; //a[]的反转序列

int main()
{
	int n;

	int i;
	while(scanf("%d",&n) && n!=0)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);

		for(i=1;i<=n;i++)
			b[a[i]]=i;

		for(i=1;i<=n;i++)
			if(a[i]!=b[i])
				break;

		if(i>=n+1)
			printf("ambiguous\n");

		else
			printf("not ambiguous\n");
	}

	return 0;
}

简化为:

#include <stdio.h>

int a[100002];

int main()
{
	int n;

	int i;
	while(scanf("%d",&n) && n!=0)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);

		for(i=1;i<=n;i++)
			if(a[a[i]]!=i)
				break;

		if(i>=n+1)
			printf("ambiguous\n");

		else
			printf("not ambiguous\n");
	}

	return 0;
}
时间: 2024-12-24 10:55:15

poj 2470 Ambiguous permutations的相关文章

POJ题目分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

poj分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

C++:多重继承(multiple inheritance)歧义(ambiguous)

多重继承, 如果基类(base class)的成员函数名称相同,重载(overload)函数调用, 会忽略public和private, 选取最佳的匹配函数, 匹配度相同, 则会造成歧义, 产出错误:request for member 'xxx' is ambiguous, (GCC) 如需使用, 可以添加具体的域操作符, 指定类("class::method()"). 代码如下: /* * test.cpp * * Created on: 2014.04.14 * Author:

POJ:DNA Sorting 特殊的排序

Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to

POJ 1001 Exponentiation 无限大数的指数乘法 题解

POJ做的很好,本题就是要求一个无限位大的指数乘法结果. 要求基础:无限大数位相乘 额外要求:处理特殊情况的能力 -- 关键是考这个能力了. 所以本题的用例特别重要,再聪明的人也会疏忽某些用例的. 本题对程序健壮性的考查到达了变态级别了. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ 某人贴出的测试用例数据地址: http://poj.org/showmessage?message_id=76017 有

POJ 2240 Arbitrage:最短路 Floyd

Arbitrage:http://poj.org/problem?id=2240 大意: 给你m种货币,给你m种货币兑换规则,问通过这些规则最后能不能盈利.eg:1美元换0.5英镑,1英镑换10法郎,1法郎换0.21美元,这样1美元能换0.5*10*0.21=1.05美元,净赚0.05美元. 思路: 用Floyd找出每两种钱之间的最大兑换关系,遍历一遍,看有没有那种钱币最后能盈利,有就输出Yes,没有就是No.在处理钱币名称与编号之间的关系时,可以用map存(比较好用),当然也可以用字符串比较.

POJ 1860 Currency Exchange:最短路 Bellman-Ford

Currency Exchange:http://poj.org/problem?id=1860 大意:有多种货币,之间可以交换,但是需要手续费,也就是说既有汇率又有手续费.问经过交换之后能不能赚. 思路:Bellman_Ford,因为要求最长路,所以松弛条件改一下就好了. Tips: 3              2                  1                20.0货币的数量   兑换点的数量     主人公拥有的货币量    主人公拥有货币的价值1 2 1.00

POJ 1258 Agri-Net:最小生成树 Prim 模版题

Agri-Net:http://poj.org/problem?id=1258 大意:新镇长竞选宣言就是将网络带到每一个农场,给出农场个数,两两之间建光缆的耗费,求所有都联通的最小耗费. 思路:最小生成树,因为边比较稠密,用Prim做. PS:对于比较稠密的图,用Prim,对于比较稀疏的图,用 Kruskal.Kruskal是找边的过程,稀疏的话会比较快. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

POJ 1789 Truck History:最小生成树 Prim

Truck History:http://poj.org/problem?id=1789 大意:用一个7位的string代表一个编号,两个编号之间的距离代表这两个编号之间不同字母的个数.一个编号只能由另一个编号变化的来,变化的字母的数量就是这两个编号之间相应的距离,现在要找出一个变化方案,使得总代价最小,也就是距离之和最小. 思路:将每个字符串当成一个节点,求出每个节点之间需要变化的次数为边的权值,用Prim建立最小生成树(稠密图). 更多精彩内容:http://www.bianceng.cnh