73 条题解
-
2
不退 LV 8 @ 2018-03-14 23:02:38
并没有理解各位大佬的（优秀）做法，于是打了纯模拟……
相信不需要任何注释就能看懂（因为实在是太朴素了……）
代码有点长，效率也不高，最慢一个450ms，但胜在容易理解……
另外膜一下楼下大佬O(10*K)做法，真的是飞速，虽然我不太懂……#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,k,s,e,cr,now; int a[200005],nc[200005]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) a[i]=i; for(int i=1;i<=k;++i) { scanf("%d%d%d",&s,&e,&cr); if(cr<=s-2) { memset(nc,0,sizeof(nc)); now=1; for(int j=s;j<=e;++j) { nc[now]=a[j]; now++; a[j]=0; } for(int j=n;j>=cr+1;--j) a[j+e-s+1]=a[j]; now=1; for(int j=cr+1;j<=cr+1+e-s;++j) { a[j]=nc[now]; now++; } now=1; for(int j=1;j<=n+e-s+1;++j) { if(a[j]!=0) { nc[now]=a[j]; now++; } } memset(a,0,sizeof(a)); for(int j=1;j<=n;++j) a[j]=nc[j]; } if(cr>=s&&cr<e) { memset(nc,0,sizeof(nc)); now=1; for(int j=e+1;j<=e+cr+1-s;++j) { nc[now]=a[j]; now++; a[j]=0; } for(int j=n;j>=s;--j) a[j+cr+1-s]=a[j]; now=1; for(int j=s;j<=cr;++j) { a[j]=nc[now]; now++; } now=1; for(int j=1;j<=n+cr+1-s;++j) { if(a[j]!=0) { nc[now]=a[j]; now++; } } memset(a,0,sizeof(a)); for(int j=1;j<=n;++j) a[j]=nc[j]; } if(cr>=e) { memset(nc,0,sizeof(nc)); now=1; for(int j=e+1;j<=e+cr-s+1;++j) { nc[now]=a[j]; now++; a[j]=0; } for(int j=n;j>=s;--j) a[j+cr-s+1]=a[j]; now=1; for(int j=s;j<=cr;++j) { a[j]=nc[now]; now++; } now=1; for(int j=1;j<=n+cr-s+1;++j) { if(a[j]!=0) { nc[now]=a[j]; now++; } } memset(a,0,sizeof(a)); for(int j=1;j<=n;++j) a[j]=nc[j]; } } for(int i=1;i<=10;++i) cout<<a[i]<<endl; return 0; } -
2
/* 此题神坑啊，一定要注意剪切粘贴的细节；坑啊坑啊 天啊噜啊 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <iomanip> #include <cstdlib> using namespace std; const int maxn=100000+10; int text[maxn],buffer[maxn]; int n,k; int a,b,c; int main() { cin>>n>>k; for(int i=1;i<=n;i++) text[i]=i; while(k--) { cin>>a>>b>>c; int z=b-a+1; memcpy(buffer,text+a,sizeof(int)*z);//将剪切断落复制出来 memmove(text+a,text+b+1,sizeof(int)*(n-b));//将剪切断落后面的部分给弄到剪切断落位置前面来 n-=z;//长度剪掉，到这里为止完成了将剪切断落剪出来的任务 memmove(text+c+z+1,text+c+1,sizeof(int)*(n-c));//将粘贴位置数字后移 memcpy(text+c+1,buffer,sizeof(int)*z);//将断落粘贴进去 n+=z; } for(int i=1;i<=10;i++) cout<<text[i]<<endl; return 0; } -
1
看到各种暴力的，突然醒悟，我想个屁的算法啊。。。强烈要求数据再加强十倍。。。
#1 Accepted 1ms 204.0 KiB
#2 Accepted 1ms 228.0 KiB
#3 Accepted 1ms 220.0 KiB
#4 Accepted 8ms 408.0 KiB
#5 Accepted 2ms 336.0 KiB
#6 Accepted 2ms 336.0 KiB
#7 Accepted 2ms 204.0 KiB
#8 Accepted 8ms 444.0 KiB
#9 Accepted 8ms 432.0 KiB
#10 Accepted 3ms 344.0 KiB这题目第一眼给人感觉像是块状链表，因为涉及到块移动与检索，但仔细看了一下，由于题目不需要查询具体结构，只有修改，所以用链表就够了。
由于初始数据是有序的，这意味着我们只需要一个数字的起点，与数字的长度就能表示一长串数据。而当我们需要进行剪切的时候，则是将链表切开，然后将插入点也切开，然后将切出的链表接到接入点就可以了。
需要注意的是，由于剪切的首位位置可能存在于同一个链表结点中，也可能存在于不同链表结点中，而两者切段的操作细节是不同的，所以最好分类讨论。
（本来还想着考虑链表结点的合并，结果提交上去就过了，然后看了一下题解，诶……不说了）
-
1
这道题给的启示就是好好打暴力，虽然理论上是O(nk)但实际上不可能跑到
粘贴文本可分成五步：
1.切下来的部分放进新数组
2.原文本后面的变到前面
3.将要粘的位置后面的部分取出来
4.切下来的部分粘回去
5.要粘位置后的部分放回去
数组下标可能有些混乱，最好开辅助变量记录一下#include<iostream> using namespace std; int x[100010],lin[100010],e[100010]; int main() { int n,k,i,j,a,b,c,na,nb,nc; cin>>n>>k; for(i=1;i<=n;i++) x[i]=i; for(i=1;i<=k;i++) { cin>>a>>b>>c; na=0; nb=0; //五个循环 nc=0; for(j=a;j<=b;j++) //切 { na++; lin[na]=x[j]; } for(j=b+1;j<=n;j++) //前移 x[j-na]=x[j]; for(j=c+1;j<=n-na;j++) //要粘的位置后面 { nc++; e[nc]=x[j]; } for(j=c+1;j<=c+na;j++) //粘回去 x[j]=lin[j-c]; for(j=n-nc+1;j<=n;j++) //放回去 x[j]=e[j-n+nc]; } for(i=1;i<=10;i++) cout<<x[i]<<endl; return 0; } -
1
cjn7788577 LV 8 @ 2017-11-05 14:12:06
#include <stdio.h> int a[1010],b[1010],c[1010]; int N,K; int get(int n,int k){ if (k==0) return n; if (c[k]+1>a[k]){ if ((n<a[k])||(n>(c[k]+1+b[k]-a[k]))) return get(n,k-1); if (n>=c[k]+1) return get(n+a[k]-c[k]-1,k-1); return get(n+b[k]-a[k]+1,k-1); } if (c[k]+1<a[k]){ if ((n<c[k]+1)||(n>b[k])) return get(n,k-1); if (n<=c[k]+1+b[k]-a[k]) return get(n+a[k]-c[k]-1,k-1); return get(n-b[k]+a[k]-1,k-1); } return get(n,k-1); } int main(){ scanf("%d %d",&N,&K); for (int i=1;i<=K;i++) scanf("%d %d %d",&a[i],&b[i],&c[i]); for (int i=1;i<=10;i++) printf("%d\n",get(i,K)); return 0; }O(10*k)的写法
-
1
用memmove复制就可以了
具体过程见注释
代码如下
#include<iostream> #include<cstdio> #include<map> #include<algorithm> #include<cstring> using namespace std; int n,k,a,b,c; int x[100000],y[100000]; int main(){ scanf("%d%d",&n,&k); for(int i=0;i<n;i++) x[i]=i+1; for(int i=1;i<=k;i++){ scanf("%d%d%d",&a,&b,&c); if(c==a-1) continue;//特判，c==a-1等价于不移 int l=b-a+1; memmove(y,x+a-1,sizeof(int)*l); //把要剪切的东西复制到y上 if(c<a){ memmove(x+l+c,x+c,sizeof(int)*(a-c-1));//前面的往后移 }else{ memmove(x+a-1,x+b,sizeof(int)*(c-a+1));//后面的往前移 } memmove(x+c,y,sizeof(int)*l); //把剪切掉的部分粘贴到正确位置 } for(int i=0;i<=9;i++) printf("%d\n",x[i]); return 0; } -
0
Accepted
状态 耗时 内存占用
#1 Accepted 3ms 256.0KiB
#2 Accepted 2ms 384.0KiB
#3 Accepted 3ms 376.0KiB
#4 Accepted 22ms 256.0KiB
#5 Accepted 21ms 384.0KiB
#6 Accepted 43ms 488.0KiB
#7 Accepted 73ms 512.0KiB
#8 Accepted 167ms 640.0KiB
#9 Accepted 163ms 736.0KiB
#10 Accepted 203ms 768.0KiB
代码#include<iostream> using namespace std; int l[100010],n,k,a,b,c,t,n1,n2,n3,n4,n5,n6; int main() { cin>>n>>k; for(int i=1;i<=n+1;i++) l[i-1]=i; for(int i=1;i<=k;i++) { cin>>a>>b>>c; t=0; for(int j=1;j<=a-1;j++) t=l[t]; n3=t; n4=l[n3]; for(int j=a;j<=b;j++) t=l[t]; n5=t; n6=l[n5]; l[n3]=n6; t=0; for(int j=1;j<=c;j++) t=l[t]; n1=t; n2=l[n1]; l[n1]=n4; l[n5]=n2; } t=0; for(int i=1;i<=10;i++) { t=l[t]; cout<<t<<endl; } return 0; } -
0
#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
Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步 -
0
-
0
数组下标即为该数字，存储数据为下一个数字，恰也为下一个数字的下标，更改链结即可。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
ChinaLover LV 7 @ 2012-07-22 10:00:28
编译通过...
├ 测试数据 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
没秒杀，请大牛指点优化……
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
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.
纯模拟怎么会错???
不退
LV 8
@ 2018-03-14 23:02:38
