荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: [合集]一道题~~~~~~
发信站: 荔园晨风BBS站 (Tue Jul 6 08:16:47 2004), 站内信件
bakey (深海的鱼爱上会潜水的猫) 于Tue Jun 29 20:52:30 2004提到：
Description
Given a permutation of numbers from 1 to n, we can always get the
sequence 1, 2, 3, ..., n by swapping pairs of numbers. For example, if
the initial sequence is 2, 3, 5, 4, 1, we can sort them in the following
way:
2 3 5 4 1
1 3 5 4 2
1 3 2 4 5
1 2 3 4 5
Here three swaps have been used. The problem is, given a specific
permutation, how many swaps we needs to take at least.
Input
The first line contains a single integer t (1 <= t <= 20) that indicates
the number of test cases. Then follow the t cases. Each case contains
two lines. The first line contains the integer n (1 <= n <= 10000),
and the second line gives the initial permutation.
Output
For each test case, the output will be only one integer, which is the
least number of swaps needed to get the sequence 1, 2, 3, ..., n from
the initial permutation.
Sample Input
2
3
1 2 3
5
2 3 5 4 1
Sample Output
0
3
bakey (深海的鱼爱上会潜水的猫) 于Tue Jun 29 20:52:47 2004提到：
alec (AlecMonkeyKing) 于Wed Jun 30 15:46:48 2004提到：
Search......
alec (AlecMonkeyKing) 于Wed Jun 30 15:56:10 2004提到：
in my opinion only search+cut
may be search with A* will be better
bakey (深海的鱼爱上会潜水的猫) 于Wed Jun 30 16:50:30 2004提到：
alec (AlecMonkeyKing) 于Wed Jun 30 17:24:33 2004提到：
e.g.
source: 2 3 5 4 1 ->
target: 1 2 3 4 5
~->this number in the right place, no change
try to change between local 1 2 3 5(number 2 3 5 1)
2 3 5 4 1 may change to after swap once
=3 2 5 4 1 ->the 2 and 4 on the right local now no change any more
=5 3 2 4 1 ->4 no change
=1 3 5 4 2 ->1 4
=2 5 3 4 1 ->4
=2 1 5 4 3 ->4
=2 3 1 4 5 ->4 5
use the BFS .... (it is without any optimal)
alec (AlecMonkeyKing) 于Wed Jun 30 20:10:40 2004提到：
understand?
kaman (天外飞仙) 于Wed Jun 30 20:20:50 2004提到：
n有一万啊～may be too slow~
bakey (深海的鱼爱上会潜水的猫) 于Wed Jun 30 22:39:34 2004提到：
好象还不是很清楚`~~~可能我不大熟BFS~~~~我想的是是不是每个数字
如果不在正确的位置上时每次只要换一次就就可以到正确的位置上了，那么
selahx (MYKERNEL) 于Wed Jun 30 23:01:31 2004提到：
哪里的题啊？写了一下，去验证一下先……
kaman (天外飞仙) 于Wed Jun 30 23:02:52 2004提到：
甘快？真定假啊？
selahx (MYKERNEL) 于Wed Jun 30 23:04:29 2004提到：
^_^乱写的……测一测而已……
bakey (深海的鱼爱上会潜水的猫) 于Wed Jun 30 23:06:09 2004提到：
POJ`~~~~
http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1674
selahx (MYKERNEL) 于Wed Jun 30 23:06:50 2004提到：
好的……
selahx (MYKERNEL) 于Thu Jul 1 10:14:01 2004提到：
是一道简单题来的，最主要的思想就是尽量找出和构造出多点交换一次就有两个数字
回到正确的位置的对来，这个考一点逻辑思维吧，不过其实规律也挺容易找的，我一开始
想错方向也才花了30分钟就想出来了，然后就写了一下提交，第一次就accept了，
我选c编译器的话时间是15ms，平了pku online judge这道题的时间记录了^_^
其实pku的online judge也很不错，测试返回的数据也很全面，不过他的编译器有点古怪
我提交了四次，每次都用不同的编译器，结果如下：
121864 selahx 1674 Accepted 148K 62MS C++(GCC) 1.03K 2004-07-01 05:53:18.0
121863 selahx 1674 Accepted 138K 15MS C 1.03K 2004-07-01 05:22:04.0
121862 selahx 1674 Accepted 148K 62MS C(GCC) 1.03K 2004-07-01 05:21:35.0
121861 selahx 1674 Accepted 140K 31MS C++ 1.03K 2004-07-01 05:13:37.0
我的程序如下（写得比较烦，自己写的时候都差点懵了）：
很难用描述出来具体的方法，要靠你自己去领会咯^_^～
/*
Author: Selahx.BRO
Date: 2004.7.1
Other: PKU1674
*/
#include<stdio.h>
#include<string.h>
int main()
{
int stat[10005],is[10005],stat2[10005],cases,ca,i,n,m,o,tmp;
scanf("%d",&cases);
for(ca=1;ca<=cases;ca++)
{
memset(is,0,sizeof(is));
scanf("%d",&n);
m=n;
o=0;
for(i=1;i<=n;i++)
{
scanf("%d",&stat[i]);
stat2[stat[i]]=i; //建一个反向索引表^_^
if(stat[i]==i)
{
is[i]=1;
m--;
}
}
if(m==0)
{
printf("%d\n",0);
continue;
}
for(i=1;i<=n;i++)
{
if(is[i]==1) continue;
if(stat2[i]==stat[i])
{
stat[stat2[i]]=stat2[i];
is[stat2[i]]=1;
stat[i]=i;
is[i]=1;
o+=1;
m-=2;
continue;
}
if(stat[stat[i]]==stat[stat2[i]])
{
stat[stat2[i]]=stat2[i];
is[stat2[i]]=1;
stat[stat[i]]=stat[i];
is[stat[i]]=1;
stat[i]=i;
is[i]=1;
o+=2;
m-=3;
continue;
}
tmp=stat[i];
stat[i]=i;
stat[stat2[i]]=tmp;
is[i]=1;
stat2[tmp]=stat2[i];
o++;
m--;
}
printf("%d\n",o);
}
return 0;
}
kaman (天外飞仙) 于Thu Jul 1 11:51:15 2004提到：
faint……你唔使睡啊？
selahx (MYKERNEL) 于Thu Jul 1 12:09:18 2004提到：
现在好困啊……
alec (AlecMonkeyKing) 于Thu Jul 1 12:31:38 2004提到：
yep you are right
you can got AC by this way
by i do not think that is a right solution
can you prove it?
selahx (MYKERNEL) 于Thu Jul 1 12:36:47 2004提到：
of course la
Can you give an opposite example?
alec (AlecMonkeyKing) 于Thu Jul 1 12:37:19 2004提到：
not yep but how can you prove it?
selahx (MYKERNEL) 于Thu Jul 1 12:39:19 2004提到：
wait~I forget it~
alec (AlecMonkeyKing) 于Thu Jul 1 12:39:44 2004提到：
i am trying to prove your solution now
selahx (MYKERNEL) 于Thu Jul 1 12:45:57 2004提到：
首先，绝对不需要搜索两层以上，因为如果搜索两层以上能找到目标，那么
目标肯定能转化成几个一层的组合，例子比较烦，自己想象一下就清楚了……
alec (AlecMonkeyKing) 于Thu Jul 1 12:48:30 2004提到：
faint that is not prove~~!!!!!!!!!!!!!!!!!!!!
btw: tell me your answer of 7 8 3 4 2 6 0 9 1 5
selahx (MYKERNEL) 于Thu Jul 1 12:50:46 2004提到：
不会有0的……
selahx (MYKERNEL) 于Thu Jul 1 12:52:26 2004提到：
不会有0，把数据全加1
8 9 4 5 3 7 1 10 2 6
我的结果是7
你的结果是什么/
alec (AlecMonkeyKing) 于Thu Jul 1 12:55:23 2004提到：
ok your solution is ok
but...... need not that trouble
i will show you the proof
wait
alec (AlecMonkeyKing) 于Thu Jul 1 13:12:50 2004提到：
1) every number can be changed at most once
2) there only one local for the number you want to change
(if you want to save time)
e.g
2 3 5 4 1
~->when you want to change this number, it must change to
3 2 5 4 1
3) the only way that we can save the times of change, that is
change something like this 1 5 3 4 2 ->1 2 3 4 5, both
2 and 5 in the right place after change
4) we need more numbers like what i said in the (3)
if there some numbers like that in the list already, what we should
do is change them first, after this, we just follow the numbers
to change it to, we check if there is any numbers like (3) after
change
5) there only one local for the number to change, hence we need not
thought about something like this: 1 3 5 4 2, change the 5<->2 fist
1 3 2 4 5, then 3<->2, a link.
code:
#include <iostream>
using namespace std;
const int maxn=10005;
int save[maxn];
int n,ans;
int main(){
int tt,i,ii,t,l;
cin>>tt;
for (ii=0;ii<tt;ii++){
cin>>n;
ans=0;
for (i=1;i<=n;i++){
cin>>save[i];
if (save[i]==i) save[i]=0;
}
l=n;
for (i=1;i<=n;i++){
if (!l) break;
if (save[i]){
if (save[save[i]]==i){
ans++;
save[save[i]]=0;
save[i]=0;
l-=2;
continue;
}
t=save[save[i]];
save[save[i]]=0;
save[i]=t;
ans++;
l--;
i--;
}
}
cout<<ans<<endl;
}
return 0;
}
selahx (MYKERNEL) 于Thu Jul 1 13:20:07 2004提到：
there is something different thing here.
例如你那个例子
1 3 5 4 2
I will change it like this
1 2 5 4 3
also get the target
and it will save much more time
kaman (天外飞仙) 于Thu Jul 1 13:22:30 2004提到：
yep,need not to search at all
alec (AlecMonkeyKing) 于Thu Jul 1 13:22:44 2004提到：
need not
1 3 5 4 2 -> check the 3 no (3) numbers
1 5 3 4 2 -> check the 5 have (3) numbers
1 2 3 4 5 -> finished
selahx (MYKERNEL) 于Thu Jul 1 13:25:39 2004提到：
什么need not啊？
我觉得我的很方便，只用一个循环就可以了，不用搜……
alec (AlecMonkeyKing) 于Thu Jul 1 13:27:53 2004提到：
ai....
if that is necessity
then your solution is wrong!
because may be 3links 4links 5links ....
alec (AlecMonkeyKing) 于Thu Jul 1 13:28:30 2004提到：
have a look on my code
you will know what i am talking about
selahx (MYKERNEL) 于Thu Jul 1 13:33:58 2004提到：
faint~我只不过判多了一个东西而已……
本质上是一样的……
selahx (MYKERNEL) 于Thu Jul 1 13:34:14 2004提到：
I don't think so……
alec (AlecMonkeyKing) 于Thu Jul 1 13:35:10 2004提到：
you think that is necessity?
selahx (MYKERNEL) 于Thu Jul 1 13:36:13 2004提到：
Not this one~
But the latter sentence~
alec (AlecMonkeyKing) 于Thu Jul 1 13:36:27 2004提到：
totally different
alec (AlecMonkeyKing) 于Thu Jul 1 13:36:46 2004提到：
???
alec (AlecMonkeyKing) 于Thu Jul 1 13:37:20 2004提到：
have a look on my code please
selahx (MYKERNEL) 于Thu Jul 1 13:37:57 2004提到：
还有问题，运行时间，你的应该不会差这么远的……
yours is 2xx
but mine is 1x
selahx (MYKERNEL) 于Thu Jul 1 13:39:18 2004提到：
但我这种办法快很多啊～
alec (AlecMonkeyKing) 于Thu Jul 1 13:40:33 2004提到：
that is because the compiler
have a look on the memory
you use 3 times more
kaman (天外飞仙) 于Thu Jul 1 13:42:05 2004提到：
not really
just 128(your) vs 138(mine)
alec (AlecMonkeyKing) 于Thu Jul 1 13:42:58 2004提到：
have a look on my code
you will know the facts
alec (AlecMonkeyKing) 于Thu Jul 1 13:44:24 2004提到：
that is because the compiler
and that judge system
do not compare in this way
selahx (MYKERNEL) 于Thu Jul 1 13:46:17 2004提到：
faint~~Just a little tip~
But really save much ram~^_^
kaman (天外飞仙) 于Thu Jul 1 13:48:12 2004提到：
路过……
alec (AlecMonkeyKing) 于Thu Jul 1 13:48:50 2004提到：
but if you think
that 3links check is necessity
then you are wrong!!!
alec (AlecMonkeyKing) 于Thu Jul 1 13:49:04 2004提到：
go die!!!!!!!!!!!!!
selahx (MYKERNEL) 于Thu Jul 1 13:53:00 2004提到：
No,never.
前面已经说我我多判了一种啦……
alec (AlecMonkeyKing) 于Thu Jul 1 13:53:38 2004提到：
why add it?
kaman (天外飞仙) 于Thu Jul 1 13:53:40 2004提到：
爆粗？封post……
go to hell!~~~^_^
selahx (MYKERNEL) 于Thu Jul 1 13:54:27 2004提到：
昨晚我都说过随便写了一下，还没想得很透啦……
alec (AlecMonkeyKing) 于Thu Jul 1 13:54:59 2004提到：
-_-~~~~~~########!!!!!!!!!!!!!!!!
(do not like it at all)
alec (AlecMonkeyKing) 于Thu Jul 1 13:55:11 2004提到：
faint
KILLgui (KILL同盟之鬼) 于Thu Jul 1 13:55:56 2004提到：
haha
alec (AlecMonkeyKing) 于Thu Jul 1 13:57:33 2004提到：
who are u?
KILLgui (KILL同盟之鬼) 于Thu Jul 1 13:58:38 2004提到：
FORGET!
HELP~~~!!!!!
WHO AM I?
alec (AlecMonkeyKing) 于Thu Jul 1 13:59:43 2004提到：
this is bbs, many guys like you
always do the stupid things
KILLgui (KILL同盟之鬼) 于Thu Jul 1 14:00:27 2004提到：
What a crazy gay~haha
kaman (天外飞仙) 于Thu Jul 1 14:03:00 2004提到：
又十大了，faint……
-----===== 本日十大热门话题 =====-----
标题 : REACT 改了不少！
标题 : cc可能确实目不斜视阿
标题 : 给大家看看这个cosplay
标题 : [兼职]日语家教
标题 : 找不到好吃的烧鹅
标题 : 鬼笑话
标题 : 谁那里有扫瞄???
标题 : 今天晚上装完一个系统，7分钟
标题 : 一道题~~~~~~
标题 : 7月1日
Kenniel (生命动人因有你) 于Thu Jul 1 14:06:31 2004提到：
selahx这个师弟好强啊
kaman (天外飞仙) 于Thu Jul 1 14:08:03 2004提到：
有D野知道得越少越好的……
alec (AlecMonkeyKing) 于Thu Jul 1 14:08:35 2004提到：
yep i think so,
or you will feel stupid
westship (总怀感恩的心) 于Thu Jul 1 14:09:34 2004提到：
just look at his nickname.haha~~`he is stupid
selahx (MYKERNEL) 于Thu Jul 1 14:09:47 2004提到：
其实他已经知道了，唉，昨天其实不该爆出来的……
alec (AlecMonkeyKing) 于Thu Jul 1 14:10:31 2004提到：
faint, del this account, or do not use it here
selahx (MYKERNEL) 于Thu Jul 1 14:11:39 2004提到：
not need，except you，no one knows the meaning~~~
westship (总怀感恩的心) 于Thu Jul 1 14:12:05 2004提到：
meaning？？
selahx (MYKERNEL) 于Thu Jul 1 14:13:52 2004提到：
那个you是复数形式来的……
kaman (天外飞仙) 于Thu Jul 1 14:14:52 2004提到：
Include me?
Why not I understand the meaning?
kaman (天外飞仙) 于Thu Jul 1 14:15:39 2004提到：
快说！
selahx (MYKERNEL) 于Thu Jul 1 14:17:09 2004提到：
no talking any more la
I must go to review English.I will take the exam tomorrow
KILLgui (KILL同盟之鬼) 于Thu Jul 1 14:17:33 2004提到：
re~~~~
bakey (深海的鱼爱上会潜水的猫) 于Thu Jul 1 17:36:32 2004提到：
--
※ 修改:·kaman 於 Jul 6 10:22:58 修改本文·[FROM: 192.168.111.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店