错了两次，第三次中。。。。。。。。。。。。

没看见先剪再贴．．．结果白交了Ｎ次

NOIP模拟题。。。

倒推吧！

zhymaojing大牛的 10k 算法果然厉害..PF..

O(10*k)

O(10*k)

O(10*k)

O(10*k)

O(10*k)

O(10*k)

O(10*k)

O(10*k)

O(10*k)

O(10*k)

O(10*k)

O(10k)

反正只要输前10个,我就只算前10个....

感谢上面大牛们的点拨

鄙人的题解http://blog.sina.com.cn/u/477bbca90100044i

晕死~~调到凌晨2点的链表没搞出来，今天上午上课突然想到了15行代码难度为1的超级弱智算法——O(10*k)

嘿嘿......我也想出来了O(10k)的方法

简单，倒着推1..10的关于移动方案i(1

splay树的几个基本操作即可快速解决

#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;
#define N 100010
struct P{
    int a,b,c;
};

int n,k;
P p[N];
//倒推 只记录 前10行更新的下标 

/*
插入前 
-----------------------------------------
               a|            b|
插入后 
-----------------------------------------
     c|  ~ b-a+1 ~  |
     
     case :1  now在这段 
      |_____________|    
     case :2  now在这段 
                    |___________________|
     case: 3 now 在这段 且now>=a 
 ____|                 
     你自己想象一下上面[a,b]区间移动吧 
*/

int main() {
    ios::sync_with_stdio(false);
    
    #define a p[i].a
    #define b p[i].b
    #define c p[i].c
    
    cin>>n>>k;
    int i,j;
    for(i=1;i<=k;i++)
        cin>>a>>b>>c;
     for(j=1;j<=10;j++)
     {
        int now=j;
        for(i=k;i>=1;i--)//倒推求值 
        {
            if(c+1<=now)//当前下标在插入点后 
            {
                if( c+1+b-a>= now ) //在插入的步数之中 
                    now=now-c-1+a;
                else if( b>=now ) //不再步数中,在b的后面 
                    now=now-c-(b-a+1)+c;    
             }
             else if(a<=now) //下标在插入点前且是往前面插入 
                now= now+(b-a+1);
        }
        cout<<now<<endl;
     }
    
    
    return 0;
}

梦幻空城1686

当前位置：/home/题库/P1058 粘贴文本/题解个人通过/递交:96/225(43%)
未递交
粘贴文本
发表题解

需要更丰富的内容输出？编辑器快速入门 | Markdown详细帮助[Ctrl+Enter] 预览

0

回复 wangyang发表于2014-11-06 16:37
wangyang0 当前没有新消息我的资料 用户中心 设置 我的应用 登出 当前位置：/home/题库/P1058 粘贴文本/题解个人通过/递交:13/19(68%) ​未递交 粘贴文本
发表题解
需要更丰富的内容输出？编辑器快速入门 | Markdown详细帮助
[Ctrl+Enter] 预览取消
0 回复 wuyifan发表于2014-07-09 11:29
include <iostream> include <cstdlib> include <cstdio> include <cstring> define N 100001
using namespace std;
int tmp[N],f[N];
long long shark,n,k,a,c,b;
void zzjdmt1()
{
for(int i=1;i<=N;i++) tmp[i]=f[i];
for(int i=1;i<=a-c-1;i++) f[c+shark+i]=tmp[c+i];
for(int i=1;i<=shark;i++) f[c+i]=tmp[a+i-1];
}
void zzjdmt2()
{
for(int i=1;i<=N;i++) tmp[i]=f[i];
for(int i=1;i<=c-a+1;i++) f[a+i-1]=tmp[b+i];
for(int i=1;i<=shark;i++) f[c+i]=tmp[a+i-1];
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=k;i++){
cin>>a>>b>>c;
shark=b-a+1;
if(c+shark<a) zzjdmt1(); if(c+1==a) continue; if(c+1<a && c+shark>=a) zzjdmt1();
if(c>=b) zzjdmt2();
if(c<b && c+1>a) zzjdmt2();
}
for(int i=1;i<=10;i++) cout<<f[i]<<endl;
//system("pause");
return 0;
}
做自己的明天吧
0 回复 940254533发表于2014-01-01 11:59
Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步
0 回复 SEX丶Elope发表于2013-02-16 10:17
点击查看程序源码+详细题解
0 回复 绵狼发表于2012-10-11 17:21
数组下标即为该数字，存储数据为下一个数字，恰也为下一个数字的下标，更改链结即可。0ms
var
n,k,a,b,c,i,ii,c1,c2,c3,c4:longint;
nex:array[-1..100001] of longint;
function pos(x:longint):longint;
var
i,j:longint;
begin
j:=0;
for i:=1 to x do
j:=nex[j];
exit(j);
end;
begin
readln(n,k);
for i:=0 to n-1 do nex[i]:=i+1;
nex[n]:=0; nex[-1]:=0;
for i:=1 to k do
begin
readln(a,b,c);
c1:=pos(a-1);
c2:=pos(b);
c4:=nex[c1];
nex[c1]:=nex[c2];
c3:=pos(c);
nex[c2]:=nex[c3];
nex[c3]:=c4;
end;
i:=0;
k:=0;
repeat
writeln(nex[i]);
i:=nex[i];
inc(k);
until k=10;
end.
0 回复 FHBPYP发表于2012-08-05 22:08
模拟水过
include <cstdio># include <iostream>using namespace std;int n;void paste(int num[],int a,int b,int c){ int result[n2+1]; int i; for (i=a;i<=n;i++) { result[i]=num[i]; num[i]=num; } for (i=n;i>=c+1;i--)num[i]=num; for (i=1;i<=(b-a)+1;i++)num[c+i]=result[a+i-1]; }int main() { int k,a,b,c; scanf("%d %d",&n,&k); int ans[n2+1]; for (int i=1;i<=n;i++)ans[i]=i; for (int i=1;i<=k;i++) { scanf("%d %d %d",&a,&b,&c); paste(ans,a,b,c); } for (int i=1;i<=10;i++)cout<<ans[i]<<endl; //system("pause"); return 0;}
0 回复 ChinaLover发表于2012-07-22 10:00
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 9ms
├ 测试数据 06：答案正确... 119ms
├ 测试数据 07：答案正确... 103ms
├ 测试数据 08：答案正确... 603ms
├ 测试数据 09：答案正确... 603ms
├ 测试数据 10：答案正确... 478ms
Accepted 有效得分：100 有效耗时：1915ms
TNND 数据需要很大。。。
0 回复 雨，纷飞发表于2012-08-02 10:10
点击这里查看
0 回复 yuu_we发表于2010-07-16 20:14
move！！！！！！！！！！
太神了！！
傻瓜式模拟，不用任何优化~~~~
0 回复 zhh1993发表于2010-04-13 17:42
没天理啊,两次60分,莫名其妙的255错误,居然是数组开小了？
0 回复 习5之人发表于2010-04-04 11:13
谁有c++的题解
0 回复 jiayu888发表于2009-11-07 11:19
没秒杀，请大牛指点优化……
var
a,b:array[1..100000]of longint;
i,j,k,n,x,y,c:longint;
begin
readln(n,k);
for i:=1 to n do
a[i]:=i;
for i:=1 to k do
begin
readln(x,y,c);
b:=a;
move(b[y+1],b[x],4(n-y));
move(a[x],a[c+1],4(y-x+1));
for j:=1 to c do
a[j]:=b[j];
for j:=y-x+c+2 to n do
a[j]:=b[j-y+x-1];
end;
for i:=1 to 10 do writeln(a[i]);
end.
0 回复 zyh0402发表于2009-11-04 11:44
var n,m,a,b,tmp,c,i,j:longint;
e,d:array[1..100000]of longint;
begin
readln(m,n);
for i:=1 to m do d[i]:=i;
for i:=1 to n do begin
read(a,b,c);
tmp:=b-a+1;
for j:=a to b do
e[j-a+1]:=d[j];
for j:=b+1 to m do
d[j-tmp]:=d[j];
for j:=m downto c+1 do
d[j+tmp]:=d[j];
for j:=c+1 to tmp+c do d[j]:=e[j-c];
end;
for i:=1 to 10 do writeln(d[i]);
end.
纯模拟怎么会错???
0 回复 qinhang3发表于2009-10-31 19:11
program vijos_p1058;
var
s,ss:ansistring;
n,ni,l,il,k,ik,a,b,c:longint;
begin
assign(input,'p1058.txt'); reset(input);
readln(n,k);
str(n,ss);
l:=length(ss);
for ni:=1 to n do
begin
str(ni,ss);
if length(ss)<l then
repeat
ss:='0'+ss;
until length(ss)=l;
s:=s+ss;
end ;
for ik:=1 to k do
begin
readln(a,b,c);
ss:=copy(s,(a-1)l+1,(b-a+1)l);
delete(s,(a-1)l+1,(b-a+1)l);
insert(ss,s,cl+1);
end ;
//writeln(s);
ss:='';
for il:=1 to 10l do
begin
ss:=ss+s[il];
if il mod l=0 then
begin
val(ss,ni,ik);
writeln(ni);
ss:='';
end ;
end ;
end .
贴个程序
字符串处理ING。。
0 回复 永恒888发表于2009-10-30 23:24
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
Accepted 有效得分：100 有效耗时：0ms
0 回复 球球4号发表于2009-10-26 23:14
水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水
题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题
0 回复 laiyinan发表于2009-10-12 13:23
AC！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！A啦！！！！！！！
program p1058;
var s:string;
n,k,i,j,temp,a,b,c,no:integer;
w,pos:array[1..100000] of integer;
begin
readln(n,k);
temp:=0;
for i:=1 to n do
w[i]:=i;
for i:=1 to k do
begin
readln(a,b,c);
temp:=b-a+1;
for j:=1 to temp do
pos[j]:=w[j+a-1];
{for no:=1 to temp do
begin
writeln(pos[no]);
writeln;
end;}
for j:=b+1 to n do
w[j-temp]:=w[j];
for j:=(n-temp) downto (c+1) do
w[j+temp]:=w[j];
for j:=1 to temp do
w[c+j]:=pos[j];
end;
for i:=1 to 10 do
writeln(w[i]);
end.
0 回复 zsy90943发表于2009-09-09 23:20
懒了、、没办法
0 回复 wuqinghua068发表于2009-09-05 19:51
program p1058;
var a,b,c:array[1..100000] of longint;
x,w,n,i,j,m,k,p,q:longint;
begin
readln(n,k);
for i:=1 to n do a[i]:=i;
for i:=1 to k do
begin
readln(p,q,m);
for j:=1 to p-1 do b[j]:=a[j];
w:=j;
for j:=q+1 to n do
begin
inc(w);
b[w]:=a[j];
end;
x:=0;
for j:=p to q do
begin
inc(x);
c[x]:=a[j];
end;
for j:=1 to m do a[j]:=b[j];
x:=1;
for j:=m+1 to m+q-p+1 do
begin
a[j]:=c[x];
inc(x);
end;
w:=m+1;
for j:=m+q-p+2 to n do
begin a[j]:=b[w]; inc(w); end;
end;
for i:=1 to 10 do writeln(a[i]);
end.
直接模拟一个不对
0 回复 notblack发表于2009-08-29 16:42
膜拜O(10*k) 的大牛们！
方法大致是这样的，因为只要输出前十位。
所以我们单独考虑这十位。
对于每个操作我们逆序向前查找，比如说某位i,我们对操作进行判断，计算出操作之前这个数是由哪里转移过来的，反复进行k次，便得解。
那么关键问题就是怎么判断了，我们需要分类讨论。
其中有三种情况会造成该位数字的移动，具体大家就自己想啦。
0 回复 yxy发表于2009-08-19 20:59
Accepted 有效得分：100 有效耗时：0ms
类型是：模拟，很明显应该用Splay
0 回复 peng7621260发表于2009-08-19 10:16
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 150ms
├ 测试数据 07：答案正确... 197ms
├ 测试数据 08：答案正确... 822ms
├ 测试数据 09：答案正确... 838ms
├ 测试数据 10：答案正确... 681ms
Accepted 有效得分：100 有效耗时：2688ms
直接模拟还真慢。39行代码
0 回复 shimingxin发表于2009-08-17 16:35
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 103ms
├ 测试数据 07：答案正确... 243ms
├ 测试数据 08：答案正确... 696ms
├ 测试数据 09：答案正确... 696ms
├ 测试数据 10：答案正确... 836ms
Accepted 有效得分：100 有效耗时：2574ms
模拟!
写的有点懒!
就是这个结果!
0 回复 yangbei发表于2009-08-14 18:09
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
Accepted 有效得分：100 有效耗时：0ms
感谢各位大牛，o(10*k)真的很强大
0 回复 1s发表于2009-08-12 10:50
如对本题有疑问可以参看我的题解：
http://xujieqi.blog.hexun.com/35722312_d.html
0 回复 Crash发表于2009-08-08 10:49
用SplayAC了，程序也就140行左右……
0 回复 gsrq发表于2009-08-06 10:41
var
tmp,f:array[0..100000]of longint;
long,n,k,i,ii,a,c,b:longint;
procedure make1;
var i:longint;
begin
tmp:=f;
for i:=1 to a-c-1 do f[c+long+i]:=tmp[c+i];
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
procedure make3;
var i:longint;
begin
tmp:=f;
for i:=1 to c-a+1 do f[a+i-1]:=tmp;
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
begin
readln(n,k);
for i:=1 to n do f[i]:=i;
for ii:=1 to k do
begin
readln(a,b,c);
long:=b-a+1;
if c+long<a then make1; if(c+1=a)then continue; if(c+1<a)and(c+long>=a)then make1;
if c>=b then make3;
if(c<b)and(c+1>a)then make3;
end;
for i:=1 to 10 do writeln(f[i]);
end.
0 回复 RayXie发表于2009-08-01 22:19
为什么我用链表会存取非法呢？
0 回复 TLD发表于2009-07-23 13:25
其实链表模拟完全可以
0 回复 FenXy发表于2009-07-20 17:57
好像全是倒推的啊.我来个模拟法的程序.
var tmp,f:array[0..100000]of longint;
long,n,k,i,ii,a,c,b:longint;
procedure make1;
var i:longint;
begin
tmp:=f;
for i:=1 to a-c-1 do f[c+long+i]:=tmp[c+i];
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
procedure make3;
var i:longint;
begin
tmp:=f;
for i:=1 to c-a+1 do f[a+i-1]:=tmp;
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
begin
readln(n,k);
for i:=1 to n do f[i]:=i;
for ii:=1 to k do
begin
readln(a,b,c);
long:=b-a+1;
if c+long<a then make1; if(c+1=a)then continue; if(c+1<a)and(c+long>=a)then make1;
if c>=b then make3;
if(c<b)and(c+1>a)then make3;
end;
for i:=1 to 10 do writeln(f[i]);
end.
0 回复 oimaster发表于2009-07-13 14:06
今天没事干么，写了一个Splay来AC此题……
然后在6k上秒闪了……Orz
0 回复 怪盗~基德发表于2009-05-15 23:49
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 72ms
├ 测试数据 08：答案正确... 338ms
├ 测试数据 09：答案正确... 353ms
├ 测试数据 10：答案正确... 369ms
Accepted 有效得分：100 有效耗时：1141ms
0 回复 复活者发表于2009-02-26 23:05
Just so so.
0 回复 luyifan发表于2009-02-26 18:14
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
终于ac,看了俩天O(10*k)算法,上数学课突然understand, 建议看zhymaoiing解题报告
0 回复 飞翔发表于2008-12-22 16:28
谁讲讲O（10*K）算法啊
0 回复 Bobby_Z发表于2008-12-16 23:27
SPLAY SPLAY!
0 回复 道不完的忧愁发表于2008-11-22 14:40
jefflepad跟我一开始错的一样，c是指把从a到b剪切之后的行数，所以应该先把a到b剪切出去
0 回复 pmq20发表于2008-11-05 14:51
include<stdio.h> include<string.h> define maxn 100000
long text[maxn+10],buffer[maxn+10],n,k;
int main()
{
long i,a,b,c,sz;
scanf("%ld%ld",&n,&k);
for(i=1;i<=n;++i) text=i;
for(i=1;i<=k;++i)
{
scanf("%ld%ld%ld",&a,&b,&c);
sz=b-a+1;
memcpy(buffer,text+a-1,sizeof(long)sz);
memmove(text+a-1,text+b,sizeof(long)(n-b));
n-=sz;
memmove(text+c+sz,text+c,sizeof(long)(n-c));
memcpy(text+c,buffer,sizeof(long)sz);
n+=sz;
}
for(i=0;i<10;++i)
printf("%ld\n",text[i]);
return 0;
}
0 回复 jefflepad发表于2008-11-03 23:24
请教各位大牛
这个问题有点奇怪
用链表直接模拟全部出现如此奇怪结果
编译通过...
├ 测试数据 01：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 03：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法
Unaccepted 有效得分：0 有效耗时：0ms
原因未知
我自己编了记住评测数据都不故障
用它提供的范例也不故障
程序如下
type point=^node;
node=record
int:longint;
next:point;
end;
var head,a,b,c,d,e,f:point;
i,j,l,m,n,k,fr,en,into:longint;
begin new(head);head^.int:=0;head^.next:=nil;
readln(n,k);
a:=head;
for i:=1 to n do
begin new(b);b^.int:=i;b^.next:=nil;a^.next:=b;a:=b;end;
for i:=1 to k do
begin readln(fr,en,into);
if into=0 then begin a:=head;for j:=1 to (fr-1) do a:=a^.next;{a待求前驱}
e:=a^.next;{e待求}
b:=e;for j:=1 to (en-fr) do b:=b^.next;{b待求}
f:=b^.next;{f待求后驱}
c:=head^.next;
head^.next:=e;
b^.next:=c;
a^.next:=f;
end
else begin a:=head;for j:=1 to (fr-1) do a:=a^.next;
e:=a^.next;
b:=e;for j:=1 to (en-fr) do b:=b^.next;
f:=b^.next;
c:=head;for j:=1 to into do c:=c^.next;
d:=c^.next;
c^.next:=e;
b^.next:=d;
a^.next:=f;
end;
end;
a:=head^.next;for i:=1 to 10 do
begin writeln(a^.int);
a:=a^.next;
end;
End.
0 回复 xbb发表于2008-10-26 18:06
O(10k)是个好东西
{for j:=1 to 10 do
begin
k:=j;
for i:=m downto 1 do
if (k>=c[i]+1)and(k<=c[i]+r[i]-l[i]+1)then k:=k+l[i]-c[i]-1
else begin
if k>c[i]+r[i]-l[i]+1 then k:=k-(r[i]-l[i]+1);
if k>=l[i] then k:=k+r[i]-l[i]+1;
end;
writeln(k);
end;}
//orz j
0 回复 linshutan发表于2008-10-21 09:39
MOVE王道..靠!!
我同样的程序..要交两遍..
0 回复 graylucky发表于2008-10-14 12:36
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 56ms
├ 测试数据 09：答案正确... 72ms
├ 测试数据 10：答案正确... 56ms
Accepted 有效得分：100 有效耗时：184ms
居然……小号过了大号居然没AC……一样的程序第一个点超时………………
人生不得志，十有八九…………
做3个ansistring，用256进制存每个数。
这样再过不了就是RP问题了。
感谢Minus Zero.Albert Thomas的算法启示。
0 回复 K-Boy发表于2008-10-11 21:46
src250/hitman47 在我的指点/帮助下过了...............
我在zhymaoiing大牛的题解下过了（思路基本一样，删了2行错误判定）......
关于解决此题过程总结成一句话:顶歇！（底歇的终极版）...... 此题解对理解力要求很高，还是建议去看楼上zhymaoiing的吧，人家才是真大牛~
主思想：反推模拟
实现过程：
初始化，B数组中每个元素代表最后一轮中的数所在的位置，注意，是位置！！！！
那么恢复到初始时则即为解.
m downto 1 ------a[j,1],a[j,2],a[j,3]
然后就开始处理，分3段：
在移动的范围内，
判定：(a[j,3]+1<=b[i]) and (a[j,2]+a[j,3]-a[j,1]+1>=b[i])
恢复执行：b[i]:=b[i]+a[j,1]-a[j,3]-1;
在左边，即比移动的小，判定：(a[j,2]+a[j,3]-a[j,1]+1<b[i]) 是否要恢复（即在要向左移的范围）：a[j,2]>=b[i]
移动：b[i]:=b[i]-a[j,2]+a[j,1]-1;
在右边，即比移动的小，判定：if (b[i]<a[j,3]+1)
是否要恢复（即在要向右移的范围）：if a[j,1]<=b[i] then
移动：b[i]:=b[i]+a[j,2]-a[j,1]+1;
差不多和楼上一样
看src250的吧
严重同意hitman47与src250的见解~删了得了
0 回复 src250发表于2008-10-11 20:46
让我顶歇 让我囧
10遍提交啊~
var i,j,k,l,m,n,p:longint;
a:array[1..100000,1..3] of longint;
long:array[1..100000] of longint;
begin
read(n,m);
for i:=m downto 1 do
begin
read(a,a,a);
long[i]:=a-a+1;
end;
for i:=1 to 10 do
begin
p:=i;
for j:=1 to m do
if (a[j,3]<p-long[j]) and (p<=a[j,2]) then dec(p,long[j]) else if (p>=a[j,1]) and (p<a[j,3]+1) then inc(p,long[j])
else if (a[j,3]<p) and (p<=a[j,3]+long[j]) then p:=p+a[j,1]-a[j,3]-1;
writeln(p);
end;
end.
0 回复 hitman47发表于2008-10-11 20:21
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
我快被它逼疯了！
强烈建议将这道迫害OIer大脑的题删掉
（疯癫中…………………………）
0 回复 lemon_cn发表于2008-10-10 17:39
我受不了了......此题我足足困了3天终于AC了...
0 回复 天￠殇发表于2008-10-10 17:18
这题用字符串做可以吗？
program p1058;
var s,s1,s2,s3,s4:ansistring;
i,j,l,a,b,c,k,n:longint;
begin
readln(n,k);
s:='';
for i:=1 to n do
s:=s+chr(i+48);
l:=length(s);
for i:=1 to k do
begin
readln(a,b,c);
if c=0 then s1:=''
else s1:=copy(s,1,c);
s2:=copy(s,b+1,l-b);
s3:=copy(s,a,b-a+1);
s4:=copy(s,c+1,a-c-1);
s:=s1+s3+s4+s2;
end;
for i:=1 to 10 do
writeln(ord(s[i])-48);
end.
哪个大牛看下这个程序 为什么一个点也过不去 全部是答案错误？
0 回复 fjxmlhx发表于2008-12-13 13:16
用了MOVE..直接模拟..ac
move(p[a],s[1],(b-a+1)4);
move(p,p[a],(n-b+1)4);
move(p[c+1],s,(n-c)4);
move(s[1],p[c+1],((b-a+1)+(n-c))4);
对内存操作就是快
块状链表
0 回复 DFS发表于2008-09-29 20:00
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
Accepted 有效得分：100 有效耗时：0ms
同上.
0 回复 332404521发表于2008-09-15 17:24
编译通过...
0 回复 失落只为你发表于2008-09-13 18:53
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 56ms
├ 测试数据 08：答案正确... 322ms
├ 测试数据 09：答案正确... 275ms
├ 测试数据 10：答案正确... 416ms
Accepted 有效得分：100 有效耗时：1078ms
直接模拟ac。静态链表
0 回复 mingmingsky发表于2007-12-24 20:33
move函数怎么用呢　大牛能教一下么
0 回复 1898098发表于2007-09-16 20:16
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 9ms
├ 测试数据 08：答案正确... 181ms
├ 测试数据 09：答案正确... 181ms
├ 测试数据 10：答案正确... 150ms
Accepted 有效得分：100 有效耗时：521ms
0 回复 奶嘴发表于2007-09-14 20:40
错了两次，第三次中。。。。。。。。。。。。
0 回复 fengyi发表于2007-08-06 14:31
没看见先剪再贴．．．结果白交了Ｎ次
0 回复 ljj5112898发表于2007-08-02 19:52
NOIP模拟题。。。
倒推吧！
0 回复 Star_Gym发表于2007-04-17 19:22
zhymaojing大牛的 10k 算法果然厉害..PF..
0 回复 WindyPeng发表于2006-10-03 22:41
O(10k)
O(10k)
O(10k)
O(10k)
O(10k)
O(10k)
O(10k)
O(10k)
O(10k)
O(10k)
O(10*k)
0 回复 西门吹牛发表于2006-08-16 22:00
O(10k)
反正只要输前10个,我就只算前10个....
感谢上面大牛们的点拨
0 回复 zhymaoiing发表于2006-06-01 14:03
鄙人的题解http://blog.sina.com.cn/u/477bbca90100044i
0 回复 matrix67发表于2006-04-13 13:09
晕死~~调到凌晨2点的链表没搞出来，今天上午上课突然想到了15行代码难度为1的超级弱智算法——O(10*k)
0 回复 永恒の灵魂发表于2006-04-22 11:11
嘿嘿......我也想出来了O(10k)的方法
简单，倒着推1..10的关于移动方案i(1<=i<=k)的前驱
0 回复 Coldwings发表于2006-01-26 09:54
splay树的几个基本操作即可快速解决
加载更多题解评测机们
◦Jtwd2
◦树形图设计者
◦上海红茶馆
◦VijosEx
Vijos 2.0 动态
◦2014-8-31 微小更新
◦2014-9-16 网络维护
◦2014-9-25 备案完毕
◦2014-9-28 更换服务器
实验室 | API | 博客 | 帮助 | 隐私 | 联系 | 关于 | 沪ICP备14040537号
© Copyright Vijos, r2824 beta, in 254.75907 ms

0

回复 wuyifan发表于2014-07-09 11:29
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define N 100001
using namespace std;
int tmp[N],f[N];
long long shark,n,k,a,c,b;
void zzjdmt1()
{
for(int i=1;i<=N;i++) tmp[i]=f[i];
for(int i=1;i<=a-c-1;i++) f[c+shark+i]=tmp[c+i];
for(int i=1;i<=shark;i++) f[c+i]=tmp[a+i-1];
}
void zzjdmt2()
{
for(int i=1;i<=N;i++) tmp[i]=f[i];
for(int i=1;i<=c-a+1;i++) f[a+i-1]=tmp[b+i];
for(int i=1;i<=shark;i++) f[c+i]=tmp[a+i-1];
}
int main()
{

cin>>n>>k;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=k;i++){
cin>>a>>b>>c;
shark=b-a+1;
if(c+shark<a) zzjdmt1();
if(c+1==a) continue;
if(c+1<a && c+shark>=a) zzjdmt1();
if(c>=b) zzjdmt2();
if(c<b && c+1>a) zzjdmt2();
}
for(int i=1;i<=10;i++) cout<<f[i]<<endl;
//system("pause");
return 0;
}
做自己的明天吧

0

回复 940254533发表于2014-01-01 11:59
Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

0

回复 SEX丶Elope发表于2013-02-16 10:17
点击查看程序源码+详细题解

0

回复 绵狼发表于2012-10-11 17:21
数组下标即为该数字，存储数据为下一个数字，恰也为下一个数字的下标，更改链结即可。0ms
var
n,k,a,b,c,i,ii,c1,c2,c3,c4:longint;
nex:array[-1..100001] of longint;

function pos(x:longint):longint;
var
i,j:longint;
begin
j:=0;
for i:=1 to x do
j:=nex[j];
exit(j);
end;

begin
readln(n,k);
for i:=0 to n-1 do nex[i]:=i+1;
nex[n]:=0; nex[-1]:=0;
for i:=1 to k do
begin
readln(a,b,c);
c1:=pos(a-1);
c2:=pos(b);
c4:=nex[c1];
nex[c1]:=nex[c2];
c3:=pos(c);
nex[c2]:=nex[c3];
nex[c3]:=c4;
end;
i:=0;
k:=0;
repeat
writeln(nex[i]);
i:=nex[i];
inc(k);
until k=10;
end.

0

回复 FHBPYP发表于2012-08-05 22:08
模拟水过

include <cstdio># include <iostream>using namespace std;int n;void paste(int num[],int a,int b,int c){ int result[n*2+1]; int i; for (i=a;i<=n;i++) { result[i]=num[i]; num[i]=num; } for (i=n;i>=c+1;i--)num[i]=num; for (i=1;i<=(b-a)+1;i++)num[c+i]=result[a+i-1]; }int main() { int k,a,b,c; scanf("%d %d",&n,&k); int ans[n*2+1]; for (int i=1;i<=n;i++)ans[i]=i; for (int i=1;i<=k;i++) { scanf("%d %d %d",&a,&b,&c); paste(ans,a,b,c); } for (int i=1;i<=10;i++)cout<<ans[i]<<endl; //system("pause"); return 0;}

0

回复 ChinaLover发表于2012-07-22 10:00
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 9ms
├ 测试数据 06：答案正确... 119ms
├ 测试数据 07：答案正确... 103ms
├ 测试数据 08：答案正确... 603ms
├ 测试数据 09：答案正确... 603ms

├ 测试数据 10：答案正确... 478ms

Accepted 有效得分：100 有效耗时：1915ms
TNND 数据需要很大。。。

0

回复 雨，纷飞发表于2012-08-02 10:10
点击这里查看

0

回复 yuu_we发表于2010-07-16 20:14
move！！！！！！！！！！
太神了！！
傻瓜式模拟，不用任何优化~~~~

0

回复 zhh1993发表于2010-04-13 17:42
没天理啊,两次60分,莫名其妙的255错误,居然是数组开小了？

0

回复 习5之人发表于2010-04-04 11:13
谁有c++的题解

0

回复 jiayu888发表于2009-11-07 11:19
没秒杀，请大牛指点优化……
var
a,b:array[1..100000]of longint;
i,j,k,n,x,y,c:longint;
begin
readln(n,k);
for i:=1 to n do
a[i]:=i;
for i:=1 to k do
begin
readln(x,y,c);
b:=a;
move(b[y+1],b[x],4*(n-y));
move(a[x],a[c+1],4*(y-x+1));
for j:=1 to c do
a[j]:=b[j];
for j:=y-x+c+2 to n do
a[j]:=b[j-y+x-1];
end;
for i:=1 to 10 do writeln(a[i]);
end.

0

回复 zyh0402发表于2009-11-04 11:44
var n,m,a,b,tmp,c,i,j:longint;
e,d:array[1..100000]of longint;
begin
readln(m,n);
for i:=1 to m do d[i]:=i;
for i:=1 to n do begin
read(a,b,c);
tmp:=b-a+1;
for j:=a to b do
e[j-a+1]:=d[j];
for j:=b+1 to m do
d[j-tmp]:=d[j];
for j:=m downto c+1 do
d[j+tmp]:=d[j];
for j:=c+1 to tmp+c do d[j]:=e[j-c];
end;
for i:=1 to 10 do writeln(d[i]);
end.
纯模拟怎么会错???

0

回复 qinhang3发表于2009-10-31 19:11
program vijos_p1058;
var
s,ss:ansistring;
n,ni,l,il,k,ik,a,b,c:longint;
begin
assign(input,'p1058.txt'); reset(input);
readln(n,k);
str(n,ss);
l:=length(ss);
for ni:=1 to n do
begin
str(ni,ss);
if length(ss)<l then
repeat
ss:='0'+ss;
until length(ss)=l;
s:=s+ss;
end ;
for ik:=1 to k do
begin
readln(a,b,c);
ss:=copy(s,(a-1)*l+1,(b-a+1)*l);
delete(s,(a-1)*l+1,(b-a+1)*l);
insert(ss,s,c*l+1);
end ;
//writeln(s);
ss:='';
for il:=1 to 10*l do
begin
ss:=ss+s[il];
if il mod l=0 then
begin
val(ss,ni,ik);
writeln(ni);
ss:='';
end ;
end ;
end .

贴个程序
字符串处理ING。。

0

回复 永恒888发表于2009-10-30 23:24
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

Accepted 有效得分：100 有效耗时：0ms

0

回复 球球4号发表于2009-10-26 23:14
水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水
题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题

0

回复 laiyinan发表于2009-10-12 13:23
AC！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！A啦！！！！！！！
program p1058;
var s:string;
n,k,i,j,temp,a,b,c,no:integer;
w,pos:array[1..100000] of integer;
begin
readln(n,k);
temp:=0;
for i:=1 to n do
w[i]:=i;
for i:=1 to k do
begin
readln(a,b,c);
temp:=b-a+1;
for j:=1 to temp do
pos[j]:=w[j+a-1];
{for no:=1 to temp do
begin
writeln(pos[no]);
writeln;
end;}
for j:=b+1 to n do
w[j-temp]:=w[j];
for j:=(n-temp) downto (c+1) do
w[j+temp]:=w[j];
for j:=1 to temp do
w[c+j]:=pos[j];
end;
for i:=1 to 10 do
writeln(w[i]);
end.

0

回复 zsy90943发表于2009-09-09 23:20
懒了、、没办法

0

回复 wuqinghua068发表于2009-09-05 19:51
program p1058;
var a,b,c:array[1..100000] of longint;
x,w,n,i,j,m,k,p,q:longint;
begin
readln(n,k);
for i:=1 to n do a[i]:=i;
for i:=1 to k do
begin
readln(p,q,m);
for j:=1 to p-1 do b[j]:=a[j];
w:=j;
for j:=q+1 to n do
begin
inc(w);
b[w]:=a[j];
end;
x:=0;
for j:=p to q do
begin
inc(x);
c[x]:=a[j];
end;
for j:=1 to m do a[j]:=b[j];
x:=1;
for j:=m+1 to m+q-p+1 do
begin
a[j]:=c[x];
inc(x);
end;
w:=m+1;
for j:=m+q-p+2 to n do
begin a[j]:=b[w]; inc(w); end;
end;
for i:=1 to 10 do writeln(a[i]);
end.

直接模拟一个不对

0

回复 notblack发表于2009-08-29 16:42
膜拜O(10*k) 的大牛们！

方法大致是这样的，因为只要输出前十位。
所以我们单独考虑这十位。

对于每个操作我们逆序向前查找，比如说某位i,我们对操作进行判断，计算出操作之前这个数是由哪里转移过来的，反复进行k次，便得解。

那么关键问题就是怎么判断了，我们需要分类讨论。

其中有三种情况会造成该位数字的移动，具体大家就自己想啦。

0

回复 yxy发表于2009-08-19 20:59
Accepted 有效得分：100 有效耗时：0ms
类型是：模拟，很明显应该用Splay

0

回复 peng7621260发表于2009-08-19 10:16
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 150ms
├ 测试数据 07：答案正确... 197ms
├ 测试数据 08：答案正确... 822ms
├ 测试数据 09：答案正确... 838ms

├ 测试数据 10：答案正确... 681ms

Accepted 有效得分：100 有效耗时：2688ms

直接模拟还真慢。39行代码

0

回复 shimingxin发表于2009-08-17 16:35
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 103ms
├ 测试数据 07：答案正确... 243ms
├ 测试数据 08：答案正确... 696ms
├ 测试数据 09：答案正确... 696ms

├ 测试数据 10：答案正确... 836ms

Accepted 有效得分：100 有效耗时：2574ms
模拟!
写的有点懒!
就是这个结果!

0

回复 yangbei发表于2009-08-14 18:09
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

Accepted 有效得分：100 有效耗时：0ms

感谢各位大牛，o(10*k)真的很强大

0

回复 1s发表于2009-08-12 10:50

如对本题有疑问可以参看我的题解：
http://xujieqi.blog.hexun.com/35722312_d.html

0

回复 Crash发表于2009-08-08 10:49
用SplayAC了，程序也就140行左右……

0

回复 gsrq发表于2009-08-06 10:41
var
tmp,f:array[0..100000]of longint;
long,n,k,i,ii,a,c,b:longint;
procedure make1;
var i:longint;
begin
tmp:=f;
for i:=1 to a-c-1 do f[c+long+i]:=tmp[c+i];
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
procedure make3;
var i:longint;
begin
tmp:=f;
for i:=1 to c-a+1 do f[a+i-1]:=tmp;
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
begin
readln(n,k);
for i:=1 to n do f[i]:=i;
for ii:=1 to k do
begin
readln(a,b,c);
long:=b-a+1;
if c+long<a then make1;
if(c+1=a)then continue;
if(c+1<a)and(c+long>=a)then make1;
if c>=b then make3;
if(c<b)and(c+1>a)then make3;
end;
for i:=1 to 10 do writeln(f[i]);
end.

0

回复 RayXie发表于2009-08-01 22:19
为什么我用链表会存取非法呢？

0

回复 TLD发表于2009-07-23 13:25
其实链表模拟完全可以

0

回复 FenXy发表于2009-07-20 17:57
好像全是倒推的啊.我来个模拟法的程序.
var tmp,f:array[0..100000]of longint;
long,n,k,i,ii,a,c,b:longint;
procedure make1;
var i:longint;
begin
tmp:=f;
for i:=1 to a-c-1 do f[c+long+i]:=tmp[c+i];
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
procedure make3;
var i:longint;
begin
tmp:=f;
for i:=1 to c-a+1 do f[a+i-1]:=tmp;
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
begin
readln(n,k);
for i:=1 to n do f[i]:=i;
for ii:=1 to k do
begin
readln(a,b,c);
long:=b-a+1;
if c+long<a then make1;
if(c+1=a)then continue;
if(c+1<a)and(c+long>=a)then make1;
if c>=b then make3;
if(c<b)and(c+1>a)then make3;
end;
for i:=1 to 10 do writeln(f[i]);
end.

0

回复 oimaster发表于2009-07-13 14:06
今天没事干么，写了一个Splay来AC此题……
然后在6k上秒闪了……Orz

0

回复 怪盗~基德发表于2009-05-15 23:49
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 72ms
├ 测试数据 08：答案正确... 338ms
├ 测试数据 09：答案正确... 353ms

├ 测试数据 10：答案正确... 369ms

Accepted 有效得分：100 有效耗时：1141ms

0

回复 复活者发表于2009-02-26 23:05
Just so so.

0

回复 luyifan发表于2009-02-26 18:14
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
终于ac,看了俩天O(10*k)算法,上数学课突然understand, 建议看zhymaoiing解题报告

0

回复 飞翔发表于2008-12-22 16:28
谁讲讲O（10*K）算法啊

0

回复 Bobby_Z发表于2008-12-16 23:27
SPLAY SPLAY!

0

回复 道不完的忧愁发表于2008-11-22 14:40
jefflepad跟我一开始错的一样，c是指把从a到b剪切之后的行数，所以应该先把a到b剪切出去

0

回复 pmq20发表于2008-11-05 14:51
#include<stdio.h>
#include<string.h>
#define maxn 100000
long text[maxn+10],buffer[maxn+10],n,k;
int main()
{
long i,a,b,c,sz;
scanf("%ld%ld",&n,&k);
for(i=1;i<=n;++i) text=i;
for(i=1;i<=k;++i)
{
scanf("%ld%ld%ld",&a,&b,&c);
sz=b-a+1;
memcpy(buffer,text+a-1,sizeof(long)*sz);
memmove(text+a-1,text+b,sizeof(long)*(n-b));
n-=sz;
memmove(text+c+sz,text+c,sizeof(long)*(n-c));
memcpy(text+c,buffer,sizeof(long)*sz);
n+=sz;
}
for(i=0;i<10;++i)
printf("%ld\n",text[i]);
return 0;
}

0

回复 jefflepad发表于2008-11-03 23:24
请教各位大牛
这个问题有点奇怪
用链表直接模拟全部出现如此奇怪结果
编译通过...
├ 测试数据 01：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 03：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法

Unaccepted 有效得分：0 有效耗时：0ms
原因未知
我自己编了记住评测数据都不故障
用它提供的范例也不故障
程序如下
type point=^node;
node=record
int:longint;
next:point;
end;
var head,a,b,c,d,e,f:point;
i,j,l,m,n,k,fr,en,into:longint;
begin new(head);head^.int:=0;head^.next:=nil;
readln(n,k);
a:=head;
for i:=1 to n do
begin new(b);b^.int:=i;b^.next:=nil;a^.next:=b;a:=b;end;
for i:=1 to k do
begin readln(fr,en,into);
if into=0 then begin a:=head;for j:=1 to (fr-1) do a:=a^.next;{a待求前驱}
e:=a^.next;{e待求}
b:=e;for j:=1 to (en-fr) do b:=b^.next;{b待求}
f:=b^.next;{f待求后驱}
c:=head^.next;
head^.next:=e;
b^.next:=c;
a^.next:=f;
end
else begin a:=head;for j:=1 to (fr-1) do a:=a^.next;
e:=a^.next;
b:=e;for j:=1 to (en-fr) do b:=b^.next;
f:=b^.next;
c:=head;for j:=1 to into do c:=c^.next;
d:=c^.next;
c^.next:=e;
b^.next:=d;
a^.next:=f;
end;
end;
a:=head^.next;for i:=1 to 10 do
begin writeln(a^.int);
a:=a^.next;
end;
End.

0

回复 xbb发表于2008-10-26 18:06
O(10*k)是个好东西
{for j:=1 to 10 do
begin
k:=j;
for i:=m downto 1 do
if (k>=c[i]+1)and(k<=c[i]+r[i]-l[i]+1)then k:=k+l[i]-c[i]-1
else begin
if k>c[i]+r[i]-l[i]+1 then k:=k-(r[i]-l[i]+1);
if k>=l[i] then k:=k+r[i]-l[i]+1;
end;
writeln(k);
end;}
//orz j*

0

回复 linshutan发表于2008-10-21 09:39
MOVE王道..靠!!
我同样的程序..要交两遍..

0

回复 graylucky发表于2008-10-14 12:36
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 56ms
├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 56ms

Accepted 有效得分：100 有效耗时：184ms

居然……小号过了大号居然没AC……一样的程序第一个点超时………………
人生不得志，十有八九…………
做3个ansistring，用256进制存每个数。
这样再过不了就是RP问题了。
感谢Minus Zero.Albert Thomas的算法启示。

0

回复 K-Boy发表于2008-10-11 21:46
src250/hitman47 在我的指点/帮助下过了...............
我在zhymaoiing大牛的题解下过了（思路基本一样，删了2行错误判定）......

关于解决此题过程总结成一句话:顶歇！（底歇的终极版）......

此题解对理解力要求很高，还是建议去看楼上zhymaoiing的吧，人家才是真大牛~

主思想：反推模拟
实现过程：
初始化，B数组中每个元素代表最后一轮中的数所在的位置，注意，是位置！！！！
那么恢复到初始时则即为解.
m downto 1 ------a[j,1],a[j,2],a[j,3]
然后就开始处理，分3段：

在移动的范围内，
判定：(a[j,3]+1<=b[i]) and (a[j,2]+a[j,3]-a[j,1]+1>=b[i])
恢复执行：b[i]:=b[i]+a[j,1]-a[j,3]-1;

在左边，即比移动的小，判定：(a[j,2]+a[j,3]-a[j,1]+1<b[i])
是否要恢复（即在要向左移的范围）：a[j,2]>=b[i]
移动：b[i]:=b[i]-a[j,2]+a[j,1]-1;

在右边，即比移动的小，判定：if (b[i]<a[j,3]+1)
是否要恢复（即在要向右移的范围）：if a[j,1]<=b[i] then
移动：b[i]:=b[i]+a[j,2]-a[j,1]+1;

差不多和楼上一样

看src250的吧

严重同意hitman47与src250的见解~删了得了

0

回复 src250发表于2008-10-11 20:46
让我顶歇 让我囧
10遍提交啊~~~~~
var i,j,k,l,m,n,p:longint;
a:array[1..100000,1..3] of longint;
long:array[1..100000] of longint;
begin
read(n,m);
for i:=m downto 1 do
begin
read(a,a,a);
long[i]:=a-a+1;
end;
for i:=1 to 10 do
begin
p:=i;
for j:=1 to m do
if (a[j,3]<p-long[j]) and (p<=a[j,2]) then dec(p,long[j])
else if (p>=a[j,1]) and (p<a[j,3]+1) then inc(p,long[j])
else if (a[j,3]<p) and (p<=a[j,3]+long[j]) then p:=p+a[j,1]-a[j,3]-1;
writeln(p);
end;
end.

0

回复 hitman47发表于2008-10-11 20:21
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
我快被它逼疯了！
强烈建议将这道迫害OIer大脑的题删掉
（疯癫中…………………………）

0

回复 lemon_cn发表于2008-10-10 17:39
我受不了了......此题我足足困了3天终于AC了...

0

回复 天￠殇发表于2008-10-10 17:18
这题用字符串做可以吗？
program p1058;
var s,s1,s2,s3,s4:ansistring;
i,j,l,a,b,c,k,n:longint;
begin
readln(n,k);
s:='';
for i:=1 to n do
s:=s+chr(i+48);
l:=length(s);
for i:=1 to k do
begin
readln(a,b,c);
if c=0 then s1:=''
else s1:=copy(s,1,c);
s2:=copy(s,b+1,l-b);
s3:=copy(s,a,b-a+1);
s4:=copy(s,c+1,a-c-1);
s:=s1+s3+s4+s2;
end;
for i:=1 to 10 do
writeln(ord(s[i])-48);
end.
哪个大牛看下这个程序 为什么一个点也过不去 全部是答案错误？

0

回复 fjxmlhx发表于2008-12-13 13:16
用了MOVE..直接模拟..ac
move(p[a],s[1],(b-a+1)*4);
move(p,p[a],(n-b+1)*4);
move(p[c+1],s,(n-c)*4);
move(s[1],p[c+1],((b-a+1)+(n-c))*4);

对内存操作就是快

块状链表

0

回复 DFS发表于2008-09-29 20:00
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

Accepted 有效得分：100 有效耗时：0ms

同上.

0

回复 332404521发表于2008-09-15 17:24
编译通过...

0

回复 失落只为你发表于2008-09-13 18:53
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 56ms
├ 测试数据 08：答案正确... 322ms
├ 测试数据 09：答案正确... 275ms

├ 测试数据 10：答案正确... 416ms

Accepted 有效得分：100 有效耗时：1078ms

直接模拟ac。静态链表

0

回复 mingmingsky发表于2007-12-24 20:33
move函数怎么用呢　大牛能教一下么

0

回复 1898098发表于2007-09-16 20:16
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 9ms
├ 测试数据 08：答案正确... 181ms
├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 150ms

Accepted 有效得分：100 有效耗时：521ms

0

回复 奶嘴发表于2007-09-14 20:40
错了两次，第三次中。。。。。。。。。。。。

0

回复 fengyi发表于2007-08-06 14:31
没看见先剪再贴．．．结果白交了Ｎ次

0

回复 ljj5112898发表于2007-08-02 19:52
NOIP模拟题。。。
倒推吧！

0

回复 Star_Gym发表于2007-04-17 19:22
zhymaojing大牛的 10k 算法果然厉害..PF..

0

回复 WindyPeng发表于2006-10-03 22:41
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)

0

回复 西门吹牛发表于2006-08-16 22:00
O(10k)

反正只要输前10个,我就只算前10个....
感谢上面大牛们的点拨

0

回复 zhymaoiing发表于2006-06-01 14:03
鄙人的题解http://blog.sina.com.cn/u/477bbca90100044i

0

回复 matrix67发表于2006-04-13 13:09
晕死~~调到凌晨2点的链表没搞出来，今天上午上课突然想到了15行代码难度为1的超级弱智算法——O(10*k)

0

回复 永恒の灵魂发表于2006-04-22 11:11
嘿嘿......我也想出来了O(10k)的方法

简单，倒着推1..10的关于移动方案i(1<=i<=k)的前驱

0

回复 Coldwings发表于2006-01-26 09:54
splay树的几个基本操作即可快速解决
加载更多题解
UPYUN
评测机们

Jtwd2
树形图设计者
上海红茶馆
VijosEx
Vijos 2.0 动态

2014-9-16 网络维护
2014-9-25 备案完毕
2014-9-28 更换服务器
2014-11-28 微小更新
实验室 | API | 博客 | 帮助 | 隐私 | 联系 | 关于 | 沪ICP备14040537号
© Copyright Vijos, r2873 beta, in 268.12696 ms

wangyang0 当前没有新消息我的资料 用户中心 设置 我的应用 登出 当前位置：/home/题库/P1058 粘贴文本/题解个人通过/递交:13/19(68%) ​未递交 粘贴文本
发表题解

需要更丰富的内容输出？编辑器快速入门 | Markdown详细帮助
[Ctrl+Enter] 预览取消

0 回复 wuyifan发表于2014-07-09 11:29
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define N 100001
using namespace std;
int tmp[N],f[N];
long long shark,n,k,a,c,b;
void zzjdmt1()
{
for(int i=1;i<=N;i++) tmp[i]=f[i];
for(int i=1;i<=a-c-1;i++) f[c+shark+i]=tmp[c+i];
for(int i=1;i<=shark;i++) f[c+i]=tmp[a+i-1];
}
void zzjdmt2()
{
for(int i=1;i<=N;i++) tmp[i]=f[i];
for(int i=1;i<=c-a+1;i++) f[a+i-1]=tmp[b+i];
for(int i=1;i<=shark;i++) f[c+i]=tmp[a+i-1];
}
int main()
{

cin>>n>>k;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=k;i++){
cin>>a>>b>>c;
shark=b-a+1;
if(c+shark<a) zzjdmt1();
if(c+1==a) continue;
if(c+1<a && c+shark>=a) zzjdmt1();
if(c>=b) zzjdmt2();
if(c<b && c+1>a) zzjdmt2();
}
for(int i=1;i<=10;i++) cout<<f[i]<<endl;
//system("pause");
return 0;
}
做自己的明天吧

0 回复 940254533发表于2014-01-01 11:59
Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

0 回复 SEX丶Elope发表于2013-02-16 10:17
点击查看程序源码+详细题解

0 回复 绵狼发表于2012-10-11 17:21
数组下标即为该数字，存储数据为下一个数字，恰也为下一个数字的下标，更改链结即可。0ms
var
n,k,a,b,c,i,ii,c1,c2,c3,c4:longint;
nex:array[-1..100001] of longint;

function pos(x:longint):longint;
var
i,j:longint;
begin
j:=0;
for i:=1 to x do
j:=nex[j];
exit(j);
end;

begin
readln(n,k);
for i:=0 to n-1 do nex[i]:=i+1;
nex[n]:=0; nex[-1]:=0;
for i:=1 to k do
begin
readln(a,b,c);
c1:=pos(a-1);
c2:=pos(b);
c4:=nex[c1];
nex[c1]:=nex[c2];
c3:=pos(c);
nex[c2]:=nex[c3];
nex[c3]:=c4;
end;
i:=0;
k:=0;
repeat
writeln(nex[i]);
i:=nex[i];
inc(k);
until k=10;
end.

0 回复 FHBPYP发表于2012-08-05 22:08
模拟水过

include <cstdio># include <iostream>using namespace std;int n;void paste(int num[],int a,int b,int c){ int result[n*2+1]; int i; for (i=a;i<=n;i++) { result[i]=num[i]; num[i]=num; } for (i=n;i>=c+1;i--)num[i]=num; for (i=1;i<=(b-a)+1;i++)num[c+i]=result[a+i-1]; }int main() { int k,a,b,c; scanf("%d %d",&n,&k); int ans[n*2+1]; for (int i=1;i<=n;i++)ans[i]=i; for (int i=1;i<=k;i++) { scanf("%d %d %d",&a,&b,&c); paste(ans,a,b,c); } for (int i=1;i<=10;i++)cout<<ans[i]<<endl; //system("pause"); return 0;}

0 回复 ChinaLover发表于2012-07-22 10:00
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 9ms
├ 测试数据 06：答案正确... 119ms
├ 测试数据 07：答案正确... 103ms
├ 测试数据 08：答案正确... 603ms
├ 测试数据 09：答案正确... 603ms

├ 测试数据 10：答案正确... 478ms

Accepted 有效得分：100 有效耗时：1915ms
TNND 数据需要很大。。。

0 回复 雨，纷飞发表于2012-08-02 10:10
点击这里查看

0 回复 yuu_we发表于2010-07-16 20:14
move！！！！！！！！！！
太神了！！
傻瓜式模拟，不用任何优化~~~~

0 回复 zhh1993发表于2010-04-13 17:42
没天理啊,两次60分,莫名其妙的255错误,居然是数组开小了？

0 回复 习5之人发表于2010-04-04 11:13
谁有c++的题解

0 回复 jiayu888发表于2009-11-07 11:19
没秒杀，请大牛指点优化……
var
a,b:array[1..100000]of longint;
i,j,k,n,x,y,c:longint;
begin
readln(n,k);
for i:=1 to n do
a[i]:=i;
for i:=1 to k do
begin
readln(x,y,c);
b:=a;
move(b[y+1],b[x],4*(n-y));
move(a[x],a[c+1],4*(y-x+1));
for j:=1 to c do
a[j]:=b[j];
for j:=y-x+c+2 to n do
a[j]:=b[j-y+x-1];
end;
for i:=1 to 10 do writeln(a[i]);
end.

0 回复 zyh0402发表于2009-11-04 11:44
var n,m,a,b,tmp,c,i,j:longint;
e,d:array[1..100000]of longint;
begin
readln(m,n);
for i:=1 to m do d[i]:=i;
for i:=1 to n do begin
read(a,b,c);
tmp:=b-a+1;
for j:=a to b do
e[j-a+1]:=d[j];
for j:=b+1 to m do
d[j-tmp]:=d[j];
for j:=m downto c+1 do
d[j+tmp]:=d[j];
for j:=c+1 to tmp+c do d[j]:=e[j-c];
end;
for i:=1 to 10 do writeln(d[i]);
end.
纯模拟怎么会错???

0 回复 qinhang3发表于2009-10-31 19:11
program vijos_p1058;
var
s,ss:ansistring;
n,ni,l,il,k,ik,a,b,c:longint;
begin
assign(input,'p1058.txt'); reset(input);
readln(n,k);
str(n,ss);
l:=length(ss);
for ni:=1 to n do
begin
str(ni,ss);
if length(ss)<l then
repeat
ss:='0'+ss;
until length(ss)=l;
s:=s+ss;
end ;
for ik:=1 to k do
begin
readln(a,b,c);
ss:=copy(s,(a-1)*l+1,(b-a+1)*l);
delete(s,(a-1)*l+1,(b-a+1)*l);
insert(ss,s,c*l+1);
end ;
//writeln(s);
ss:='';
for il:=1 to 10*l do
begin
ss:=ss+s[il];
if il mod l=0 then
begin
val(ss,ni,ik);
writeln(ni);
ss:='';
end ;
end ;
end .

贴个程序
字符串处理ING。。

0 回复 永恒888发表于2009-10-30 23:24
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

Accepted 有效得分：100 有效耗时：0ms

0 回复 球球4号发表于2009-10-26 23:14
水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水
题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题

0 回复 laiyinan发表于2009-10-12 13:23
AC！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！A啦！！！！！！！
program p1058;
var s:string;
n,k,i,j,temp,a,b,c,no:integer;
w,pos:array[1..100000] of integer;
begin
readln(n,k);
temp:=0;
for i:=1 to n do
w[i]:=i;
for i:=1 to k do
begin
readln(a,b,c);
temp:=b-a+1;
for j:=1 to temp do
pos[j]:=w[j+a-1];
{for no:=1 to temp do
begin
writeln(pos[no]);
writeln;
end;}
for j:=b+1 to n do
w[j-temp]:=w[j];
for j:=(n-temp) downto (c+1) do
w[j+temp]:=w[j];
for j:=1 to temp do
w[c+j]:=pos[j];
end;
for i:=1 to 10 do
writeln(w[i]);
end.

0 回复 zsy90943发表于2009-09-09 23:20
懒了、、没办法

0 回复 wuqinghua068发表于2009-09-05 19:51
program p1058;
var a,b,c:array[1..100000] of longint;
x,w,n,i,j,m,k,p,q:longint;
begin
readln(n,k);
for i:=1 to n do a[i]:=i;
for i:=1 to k do
begin
readln(p,q,m);
for j:=1 to p-1 do b[j]:=a[j];
w:=j;
for j:=q+1 to n do
begin
inc(w);
b[w]:=a[j];
end;
x:=0;
for j:=p to q do
begin
inc(x);
c[x]:=a[j];
end;
for j:=1 to m do a[j]:=b[j];
x:=1;
for j:=m+1 to m+q-p+1 do
begin
a[j]:=c[x];
inc(x);
end;
w:=m+1;
for j:=m+q-p+2 to n do
begin a[j]:=b[w]; inc(w); end;
end;
for i:=1 to 10 do writeln(a[i]);
end.

直接模拟一个不对

0 回复 notblack发表于2009-08-29 16:42
膜拜O(10*k) 的大牛们！

方法大致是这样的，因为只要输出前十位。
所以我们单独考虑这十位。

对于每个操作我们逆序向前查找，比如说某位i,我们对操作进行判断，计算出操作之前这个数是由哪里转移过来的，反复进行k次，便得解。

那么关键问题就是怎么判断了，我们需要分类讨论。

其中有三种情况会造成该位数字的移动，具体大家就自己想啦。

0 回复 yxy发表于2009-08-19 20:59
Accepted 有效得分：100 有效耗时：0ms
类型是：模拟，很明显应该用Splay

0 回复 peng7621260发表于2009-08-19 10:16
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 150ms
├ 测试数据 07：答案正确... 197ms
├ 测试数据 08：答案正确... 822ms
├ 测试数据 09：答案正确... 838ms

├ 测试数据 10：答案正确... 681ms

Accepted 有效得分：100 有效耗时：2688ms

直接模拟还真慢。39行代码

0 回复 shimingxin发表于2009-08-17 16:35
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 103ms
├ 测试数据 07：答案正确... 243ms
├ 测试数据 08：答案正确... 696ms
├ 测试数据 09：答案正确... 696ms

├ 测试数据 10：答案正确... 836ms

Accepted 有效得分：100 有效耗时：2574ms
模拟!
写的有点懒!
就是这个结果!

0 回复 yangbei发表于2009-08-14 18:09
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

Accepted 有效得分：100 有效耗时：0ms

感谢各位大牛，o(10*k)真的很强大

0 回复 1s发表于2009-08-12 10:50

如对本题有疑问可以参看我的题解：
http://xujieqi.blog.hexun.com/35722312_d.html

0 回复 Crash发表于2009-08-08 10:49
用SplayAC了，程序也就140行左右……

0 回复 gsrq发表于2009-08-06 10:41
var
tmp,f:array[0..100000]of longint;
long,n,k,i,ii,a,c,b:longint;
procedure make1;
var i:longint;
begin
tmp:=f;
for i:=1 to a-c-1 do f[c+long+i]:=tmp[c+i];
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
procedure make3;
var i:longint;
begin
tmp:=f;
for i:=1 to c-a+1 do f[a+i-1]:=tmp;
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
begin
readln(n,k);
for i:=1 to n do f[i]:=i;
for ii:=1 to k do
begin
readln(a,b,c);
long:=b-a+1;
if c+long<a then make1;
if(c+1=a)then continue;
if(c+1<a)and(c+long>=a)then make1;
if c>=b then make3;
if(c<b)and(c+1>a)then make3;
end;
for i:=1 to 10 do writeln(f[i]);
end.

0 回复 RayXie发表于2009-08-01 22:19
为什么我用链表会存取非法呢？

0 回复 TLD发表于2009-07-23 13:25
其实链表模拟完全可以

0 回复 FenXy发表于2009-07-20 17:57
好像全是倒推的啊.我来个模拟法的程序.
var tmp,f:array[0..100000]of longint;
long,n,k,i,ii,a,c,b:longint;
procedure make1;
var i:longint;
begin
tmp:=f;
for i:=1 to a-c-1 do f[c+long+i]:=tmp[c+i];
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
procedure make3;
var i:longint;
begin
tmp:=f;
for i:=1 to c-a+1 do f[a+i-1]:=tmp;
for i:=1 to long do f[c+i]:=tmp[a+i-1];
end;
begin
readln(n,k);
for i:=1 to n do f[i]:=i;
for ii:=1 to k do
begin
readln(a,b,c);
long:=b-a+1;
if c+long<a then make1;
if(c+1=a)then continue;
if(c+1<a)and(c+long>=a)then make1;
if c>=b then make3;
if(c<b)and(c+1>a)then make3;
end;
for i:=1 to 10 do writeln(f[i]);
end.

0 回复 oimaster发表于2009-07-13 14:06
今天没事干么，写了一个Splay来AC此题……
然后在6k上秒闪了……Orz

0 回复 怪盗~基德发表于2009-05-15 23:49
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 72ms
├ 测试数据 08：答案正确... 338ms
├ 测试数据 09：答案正确... 353ms

├ 测试数据 10：答案正确... 369ms

Accepted 有效得分：100 有效耗时：1141ms

0 回复 复活者发表于2009-02-26 23:05
Just so so.

0 回复 luyifan发表于2009-02-26 18:14
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
终于ac,看了俩天O(10*k)算法,上数学课突然understand, 建议看zhymaoiing解题报告

0 回复 飞翔发表于2008-12-22 16:28
谁讲讲O（10*K）算法啊

0 回复 Bobby_Z发表于2008-12-16 23:27
SPLAY SPLAY!

0 回复 道不完的忧愁发表于2008-11-22 14:40
jefflepad跟我一开始错的一样，c是指把从a到b剪切之后的行数，所以应该先把a到b剪切出去

0 回复 pmq20发表于2008-11-05 14:51
#include<stdio.h>
#include<string.h>
#define maxn 100000
long text[maxn+10],buffer[maxn+10],n,k;
int main()
{
long i,a,b,c,sz;
scanf("%ld%ld",&n,&k);
for(i=1;i<=n;++i) text=i;
for(i=1;i<=k;++i)
{
scanf("%ld%ld%ld",&a,&b,&c);
sz=b-a+1;
memcpy(buffer,text+a-1,sizeof(long)*sz);
memmove(text+a-1,text+b,sizeof(long)*(n-b));
n-=sz;
memmove(text+c+sz,text+c,sizeof(long)*(n-c));
memcpy(text+c,buffer,sizeof(long)*sz);
n+=sz;
}
for(i=0;i<10;++i)
printf("%ld\n",text[i]);
return 0;
}

0 回复 jefflepad发表于2008-11-03 23:24
请教各位大牛
这个问题有点奇怪
用链表直接模拟全部出现如此奇怪结果
编译通过...
├ 测试数据 01：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 03：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法
├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法

Unaccepted 有效得分：0 有效耗时：0ms
原因未知
我自己编了记住评测数据都不故障
用它提供的范例也不故障
程序如下
type point=^node;
node=record
int:longint;
next:point;
end;
var head,a,b,c,d,e,f:point;
i,j,l,m,n,k,fr,en,into:longint;
begin new(head);head^.int:=0;head^.next:=nil;
readln(n,k);
a:=head;
for i:=1 to n do
begin new(b);b^.int:=i;b^.next:=nil;a^.next:=b;a:=b;end;
for i:=1 to k do
begin readln(fr,en,into);
if into=0 then begin a:=head;for j:=1 to (fr-1) do a:=a^.next;{a待求前驱}
e:=a^.next;{e待求}
b:=e;for j:=1 to (en-fr) do b:=b^.next;{b待求}
f:=b^.next;{f待求后驱}
c:=head^.next;
head^.next:=e;
b^.next:=c;
a^.next:=f;
end
else begin a:=head;for j:=1 to (fr-1) do a:=a^.next;
e:=a^.next;
b:=e;for j:=1 to (en-fr) do b:=b^.next;
f:=b^.next;
c:=head;for j:=1 to into do c:=c^.next;
d:=c^.next;
c^.next:=e;
b^.next:=d;
a^.next:=f;
end;
end;
a:=head^.next;for i:=1 to 10 do
begin writeln(a^.int);
a:=a^.next;
end;
End.

0 回复 xbb发表于2008-10-26 18:06
O(10*k)是个好东西
{for j:=1 to 10 do
begin
k:=j;
for i:=m downto 1 do
if (k>=c[i]+1)and(k<=c[i]+r[i]-l[i]+1)then k:=k+l[i]-c[i]-1
else begin
if k>c[i]+r[i]-l[i]+1 then k:=k-(r[i]-l[i]+1);
if k>=l[i] then k:=k+r[i]-l[i]+1;
end;
writeln(k);
end;}
//orz j*

0 回复 linshutan发表于2008-10-21 09:39
MOVE王道..靠!!
我同样的程序..要交两遍..

0 回复 graylucky发表于2008-10-14 12:36
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 56ms
├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 56ms

Accepted 有效得分：100 有效耗时：184ms

居然……小号过了大号居然没AC……一样的程序第一个点超时………………
人生不得志，十有八九…………
做3个ansistring，用256进制存每个数。
这样再过不了就是RP问题了。
感谢Minus Zero.Albert Thomas的算法启示。

0 回复 K-Boy发表于2008-10-11 21:46
src250/hitman47 在我的指点/帮助下过了...............
我在zhymaoiing大牛的题解下过了（思路基本一样，删了2行错误判定）......

关于解决此题过程总结成一句话:顶歇！（底歇的终极版）......

此题解对理解力要求很高，还是建议去看楼上zhymaoiing的吧，人家才是真大牛~

主思想：反推模拟
实现过程：
初始化，B数组中每个元素代表最后一轮中的数所在的位置，注意，是位置！！！！
那么恢复到初始时则即为解.
m downto 1 ------a[j,1],a[j,2],a[j,3]
然后就开始处理，分3段：

在移动的范围内，
判定：(a[j,3]+1<=b[i]) and (a[j,2]+a[j,3]-a[j,1]+1>=b[i])
恢复执行：b[i]:=b[i]+a[j,1]-a[j,3]-1;

在左边，即比移动的小，判定：(a[j,2]+a[j,3]-a[j,1]+1<b[i])
是否要恢复（即在要向左移的范围）：a[j,2]>=b[i]
移动：b[i]:=b[i]-a[j,2]+a[j,1]-1;

在右边，即比移动的小，判定：if (b[i]<a[j,3]+1)
是否要恢复（即在要向右移的范围）：if a[j,1]<=b[i] then
移动：b[i]:=b[i]+a[j,2]-a[j,1]+1;

差不多和楼上一样

看src250的吧

严重同意hitman47与src250的见解~删了得了

0 回复 src250发表于2008-10-11 20:46
让我顶歇 让我囧
10遍提交啊~~~~~
var i,j,k,l,m,n,p:longint;
a:array[1..100000,1..3] of longint;
long:array[1..100000] of longint;
begin
read(n,m);
for i:=m downto 1 do
begin
read(a,a,a);
long[i]:=a-a+1;
end;
for i:=1 to 10 do
begin
p:=i;
for j:=1 to m do
if (a[j,3]<p-long[j]) and (p<=a[j,2]) then dec(p,long[j])
else if (p>=a[j,1]) and (p<a[j,3]+1) then inc(p,long[j])
else if (a[j,3]<p) and (p<=a[j,3]+long[j]) then p:=p+a[j,1]-a[j,3]-1;
writeln(p);
end;
end.

0 回复 hitman47发表于2008-10-11 20:21
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
我快被它逼疯了！
强烈建议将这道迫害OIer大脑的题删掉
（疯癫中…………………………）

0 回复 lemon_cn发表于2008-10-10 17:39
我受不了了......此题我足足困了3天终于AC了...

0 回复 天￠殇发表于2008-10-10 17:18
这题用字符串做可以吗？
program p1058;
var s,s1,s2,s3,s4:ansistring;
i,j,l,a,b,c,k,n:longint;
begin
readln(n,k);
s:='';
for i:=1 to n do
s:=s+chr(i+48);
l:=length(s);
for i:=1 to k do
begin
readln(a,b,c);
if c=0 then s1:=''
else s1:=copy(s,1,c);
s2:=copy(s,b+1,l-b);
s3:=copy(s,a,b-a+1);
s4:=copy(s,c+1,a-c-1);
s:=s1+s3+s4+s2;
end;
for i:=1 to 10 do
writeln(ord(s[i])-48);
end.
哪个大牛看下这个程序 为什么一个点也过不去 全部是答案错误？

0 回复 fjxmlhx发表于2008-12-13 13:16
用了MOVE..直接模拟..ac
move(p[a],s[1],(b-a+1)*4);
move(p,p[a],(n-b+1)*4);
move(p[c+1],s,(n-c)*4);
move(s[1],p[c+1],((b-a+1)+(n-c))*4);

对内存操作就是快

块状链表

0 回复 DFS发表于2008-09-29 20:00
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

Accepted 有效得分：100 有效耗时：0ms

同上.

0 回复 332404521发表于2008-09-15 17:24
编译通过...

0 回复 失落只为你发表于2008-09-13 18:53
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 56ms
├ 测试数据 08：答案正确... 322ms
├ 测试数据 09：答案正确... 275ms

├ 测试数据 10：答案正确... 416ms

Accepted 有效得分：100 有效耗时：1078ms

直接模拟ac。静态链表

0 回复 mingmingsky发表于2007-12-24 20:33
move函数怎么用呢　大牛能教一下么

0 回复 1898098发表于2007-09-16 20:16
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 9ms
├ 测试数据 08：答案正确... 181ms
├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 150ms

Accepted 有效得分：100 有效耗时：521ms

0 回复 奶嘴发表于2007-09-14 20:40
错了两次，第三次中。。。。。。。。。。。。

0 回复 fengyi发表于2007-08-06 14:31
没看见先剪再贴．．．结果白交了Ｎ次

0 回复 ljj5112898发表于2007-08-02 19:52
NOIP模拟题。。。
倒推吧！

0 回复 Star_Gym发表于2007-04-17 19:22
zhymaojing大牛的 10k 算法果然厉害..PF..

0 回复 WindyPeng发表于2006-10-03 22:41
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)
O(10*k)

0 回复 西门吹牛发表于2006-08-16 22:00
O(10k)

反正只要输前10个,我就只算前10个....
感谢上面大牛们的点拨

0 回复 zhymaoiing发表于2006-06-01 14:03
鄙人的题解http://blog.sina.com.cn/u/477bbca90100044i

0 回复 matrix67发表于2006-04-13 13:09
晕死~~调到凌晨2点的链表没搞出来，今天上午上课突然想到了15行代码难度为1的超级弱智算法——O(10*k)

0 回复 永恒の灵魂发表于2006-04-22 11:11
嘿嘿......我也想出来了O(10k)的方法

简单，倒着推1..10的关于移动方案i(1<=i<=k)的前驱

0 回复 Coldwings发表于2006-01-26 09:54
splay树的几个基本操作即可快速解决

加载更多题解评测机们
◦Jtwd2
◦树形图设计者
◦上海红茶馆
◦VijosEx
Vijos 2.0 动态
◦2014-8-31 微小更新
◦2014-9-16 网络维护
◦2014-9-25 备案完毕
◦2014-9-28 更换服务器
实验室 | API | 博客 | 帮助 | 隐私 | 联系 | 关于 | 沪ICP备14040537号
© Copyright Vijos, r2824 beta, in 254.75907 ms