Editorial for Kruska
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include<iostream> #include<algorithm> #define maxm 10010 #define fr(a,b,c) for (a=b;a<=c;a++) using namespace std; struct rec { int x,y,z,d,k; }; int n,k,m,nq,a[222][222],b[maxm][7],dx[4],dy[4],d[222][222][4][7]; rec q[1200000]; long long re; void push(int i,int x,int y,int z,int day,int turn) { q[i].x=x; q[i].y=y; q[i].z=z; q[i].d=day; q[i].k=turn; } int main() { dx[0]=-1; dx[1]=0; dx[2]=1; dx[3]=0; dy[0]=0; dy[1]=1; dy[2]=0; dy[3]=-1; int i,x,j,y,day=0,z=1,turn=0; char ch; cin >> n >> k >> m; fr(j,1,m) { scanf("%d%d%c",&x,&y,&ch); a[x][y]=j; fr(i,0,6) { scanf("%c",&ch); if (ch=='R') b[j][i]=1; if (ch=='L') b[j][i]=3; } scanf("\n"); } d[1][1][1][0]=1; i=1; x=1; y=1; push(1,1,1,1,0,0); while (1) { if (a[x][y]) { int w=a[x][y]; if (b[w][day%7]) { turn++; z=(z+b[w][day%7])%4; } } if (!(x+dx[z] && y+dy[z] && x+dx[z]<=n && y+dy[z]<=n)) { z=(z+2)%4; turn++; } if (turn>=k) { re=day; break; } x+=dx[z]; y+=dy[z]; day++; i++; if (d[x][y][z][day%7]) { int t=d[x][y][z][day%7],u=i-t,v=turn-q[t].k; long long vv; re=q[t].d; k-=q[t].k; vv=k/v; k%=v; re+=vv*u; k+=q[t].k; if (k>q[t].k) { fr(j,t+1,i) if (q[j].k>=k) break; re+=j-t-1; } break; } d[x][y][z][day%7]=i; push(i,x,y,z,day,turn); } cout << re << endl; return 0; }
Code mẫu của RR
//Written by Nguyen Thanh Trung {$R+,Q+} {$Mode objFPC} uses math; const FINP = ''; FOUT = ''; MAXN = 222; MAXM = 10111; di : array[1..4] of longint=(0,0,-1,1); dj : array[1..4] of longint=(1,-1,0,0); turnl : array[1..4] of longint=(3,4,2,1); turnr : array[1..4] of longint=(4,3,1,2); turnb : array[1..4] of longint=(2,1,4,3); var f1,f2 : text; n,m,k : longint; kq : int64; wizard : array[1..MAXM] of string[7]; desert : array[1..MAXN,1..MAXN] of longint; day,turned : array[1..MAXN,1..MAXN,1..7,1..4] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i,u,v:longint; ch:char; begin readln(f1,n,k); readln(f1,m); for i:=1 to m do begin read(f1,u,v); desert[u,v]:=i; read(f1,ch); readln(f1,wizard[i]); end; end; function outside(u,v:longint):boolean; inline; begin exit( (u<1) or (v<1) or (u>n) or (v>n) ); end; procedure solve; var count,turn,u,v,d,h,uu,vv,dd,hh,dir:longint; chuky:int64; begin fillchar(day,sizeof(day),0); u:=1; v:=1; d:=1; h:=1; count:=0; turn:=0; while day[u,v,d,h]=0 do begin count+=1; day[u,v,d,h]:=count; turned[u,v,d,h]:=turn; uu:=u+di[h]; vv:=v+dj[h]; dd:=d+1; if dd=8 then dd:=1; hh:=h; if desert[uu,vv]<>0 then case wizard[desert[uu,vv]][dd] of 'L': begin hh:=turnl[h]; inc(turn); end; 'R': begin hh:=turnr[h]; inc(turn); end; end; if outside(uu+di[hh],vv+dj[hh]) then begin hh:=turnb[hh]; inc(turn); end; u:=uu; v:=vv; d:=dd; h:=hh; if turn>=k then begin writeln(f2,kq+count); closeF; halt; end; end; chuky:=(k-turned[u,v,d,h]) div (turn-turned[u,v,d,h]); kq:=chuky*(count-day[u,v,d,h]+1); k-=chuky*(turn-turned[u,v,d,h]); end; begin openF; inp; solve; solve; end.
Code mẫu của hieult
#include <cstdio> #include <cstring> //#include <conio.h> const int hr[4] = {0, 1, 0, -1}; const int hc[4] = {1, 0, -1, 0}; int N,K,M; char a[220][220][8]; long long tg[220][220][4][8]; int lan[220][220][4][8]; int main() { // freopen("kruska.in.1","r",stdin); scanf("%d %d %d",&N,&K,&M); memset(a,'S',sizeof(a)); for(int i = 0;i<M;i++) { int r,c; scanf("%d %d",&r,&c); r--; c--; scanf("%s",a[r][c]); } long long kq = 0; int r = 0, c = 0, h = 0, t = 0, k = 0; while(true) { if(a[r][c][t] == 'R') { h = (h+1)%4; k++;} if(a[r][c][t] == 'L') { h = (h+3)%4; k++;} if( r+hr[h] < 0 || r+hr[h] >= N || c+hc[h] < 0 || c+hc[h] >= N) { h = (h+2)%4; k++;} if(tg[r][c][h][t]>0) { int qua = k - lan[r][c][h][t]; int con = K-k; kq += (con/qua)*(kq - tg[r][c][h][t]); k += (con/qua) * qua; } tg[r][c][h][t] = kq; lan[r][c][h][t] = k; if(k>=K) break; r += hr[h]; c += hc[h]; kq++; t = (t+1)%7; } printf("%lld",kq); //getch(); }
Code mẫu của ll931110
program KRUS; const input = ''; output = ''; maxn = 200; maxm = 10000; dx: array[1..4] of integer = (-1,0,1,0); dy: array[1..4] of integer = (0,1,0,-1); l: array[1..4] of integer = (4,1,2,3); r: array[1..4] of integer = (2,3,4,1); o: array[1..4] of integer = (3,4,1,2); var pos: array[1..maxn,1..maxn] of integer; ac: array[1..maxm] of string[8]; Fd,Fk: array[1..maxn,1..maxn,1..7,1..4] of longint; n,m: integer; k,nd: longint; res: int64; u,v,md,way,nturn: longint; procedure init; var fi: text; i,x,y: integer; begin assign(fi, input); reset(fi); readln(fi, n, k); readln(fi, m); for i := 1 to m do begin read(fi, x, y); readln(fi, ac[i]); delete(ac[i],1,1); pos[x,y] := i; end; close(fi); end; function outside(way: integer): boolean; begin if (way = 1) and (u = 1) then exit(true); if (way = 2) and (v = n) then exit(true); if (way = 3) and (u = n) then exit(true); if (way = 4) and (v = 1) then exit(true); outside := false; end; procedure update; begin if Fd[u,v,md,way] = 0 then begin Fd[u,v,md,way] := nd; Fk[u,v,md,way] := nturn; end; end; procedure cycle; var cday,td: int64; tt,cturn: longint; begin td := Fd[u,v,md,way]; tt := Fk[u,v,md,way]; cday := nd - td; cturn := nturn - tt; k := k - tt; cday := int64(cday * (k div cturn)); k := k mod cturn; res := td + cday; md := (res mod 7) + 1; nturn := 0; end; procedure solve; var tmp: integer; begin u := 1; v := 1; way := 2; nturn := 0; nd := 0; md := 1; while nturn < k do begin if pos[u,v] <> 0 then begin tmp := pos[u,v]; if ac[tmp][md] = 'L' then begin inc(nturn); way := l[way]; update; end else if ac[tmp][md] = 'R' then begin inc(nturn); way := r[way]; update; end; end; if outside(way) then begin way := o[way]; inc(nturn); update; end; if nturn >= k then begin res := nd; exit; end; if (Fd[u,v,md,way] <> 0) and (Fd[u,v,md,way] <> nd) then begin cycle; u := u + dx[way]; v := v + dy[way]; inc(res); inc(md); if md = 8 then md := 1; break; end; u := u + dx[way]; v := v + dy[way]; inc(nd); inc(md); if md = 8 then md := 1; end; nturn := 0; while nturn < k do begin if pos[u,v] <> 0 then begin tmp := pos[u,v]; if ac[tmp][md] = 'L' then begin inc(nturn); way := l[way]; end else if ac[tmp][md] = 'R' then begin inc(nturn); way := r[way]; end; end; if outside(way) then begin way := o[way]; inc(nturn); end; if nturn >= k then exit; u := u + dx[way]; v := v + dy[way]; inc(res); inc(md); if md = 8 then md := 1; end; end; procedure printresult; var fo: text; begin assign(fo, output); rewrite(fo); writeln(fo, res); close(fo); end; begin init; solve; printresult; end.
Code mẫu của khuc_tuan
#include <iostream> using namespace std; const int MAX = 1120000 * 2; int dx[] = {-1,0,1,0}; int dy[] = {0,1,0,-1}; int n, K; int w; char a[10010][10]; int pt[202][202]; int st[MAX]; int F[202][202][4][7]; bool inside(int x, int y) { return 0 <= x && x < n && 0 <= y && y < n; } int main() { scanf("%d%d%d", &n, &K, &w); memset( pt, -1, sizeof(pt)); for(int i=0;i<w;++i) { int u, v; scanf("%d%d%s", &u, &v, a[i]); pt[u-1][v-1] = i; } int x, y, h; int turn = 0; x = y = 0; h = 1; memset( F, -1, sizeof(F)); F[x][y][h][0] = 0; for(int z=0;;++z) { int quanh = 0; if(pt[x][y]!=-1) { char c = a[pt[x][y]][z%7]; if(c=='L') { h = (h+3) % 4; ++ quanh; ++ turn; } else if(c=='R') { h = (h+1) % 4; ++ quanh; ++ turn; } } if(turn>=K) { cout << z << endl; return 0; } int nx = x + dx[h]; int ny = y + dy[h]; if(!inside(nx,ny)) { h = (h+2)%4; ++turn; ++quanh; if(turn>=K) { cout << z << endl; return 0; } nx = x + dx[h]; ny = y + dy[h]; } x = nx; y = ny; st[z] = quanh; int & ff = F[x][y][h][(z+1) % 7]; if( ff != -1 ) { int ct = z - ff + 1; int need = K - turn; int total = 0; for(int i=ff;i<=z;++i) total += st[i]; long long kq = z + need / total * 1LL * ct; need %= total; if(need == 0) { kq -= ct; need = total; } for(int i=ff;i<=z;++i) { ++ kq; need -= st[i]; if(need <= 0) { cout << kq << endl; return 0; } } } else ff = z + 1; } return 0; }
Comments