又遭遇了Pascal版AC而翻译成C++则TLE。

Download (sgu122.pdf, 105.51KB)

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

//list版 TLE on test 20
#include <cstdio>
#include <list>
#include <algorithm>
using namespace std;
 
int main() {
    list<int> ninlist,plist;
    bool map[1001][1001]={{0}};
    char rbuf[5001];
    int n;
    gets(rbuf); sscanf(rbuf,"%d",&n);
    for (int i=1;i<=n;++i) {
        ninlist.push_back(i);
        int j=0,pos=0;
        gets(rbuf);
        while (sscanf(rbuf+pos,"%d",&j)!=EOF) {
            map[i][j]=map[j][i]=true;
            while (rbuf[pos]>32) pos++;
            while (rbuf[pos]==32) pos++;
        }
    }
    plist.splice(plist.end(),ninlist,ninlist.begin());
    while (ninlist.size()) {
        for (bool find=true;find;) {
            find=false;
            for (list<int>::iterator i=ninlist.begin();i!=ninlist.end();++i) if (map[*i][plist.front()] || map[*i][plist.back()]) {
                find=true;
                plist.splice(map[*i][plist.front()]?plist.begin():plist.end(),ninlist,i);
                break;
            }
        }
        for (list<int>::iterator j=plist.begin(),i=j++;j!=plist.end();++i,++j) if (map[*i][plist.back()] && map[*j][plist.front()]) {
            reverse(j,plist.end()); break;
        }
        if (ninlist.size()) for (list<int>::iterator i=plist.begin();i!=plist.end();++i) if (map[*i][ninlist.front()]) {
            plist.splice(plist.end(),plist,plist.begin(),i);
            plist.splice(plist.begin(),ninlist,ninlist.begin());
            break;
        }
    }
    plist.splice(plist.end(),plist,plist.begin(),find(plist.begin(),plist.end(),1));
    for (list<int>::iterator i=plist.begin();i!=plist.end();++i) printf("%d ",*i);
    printf("1\n");
    return 0;
}
?View Code DELPHI
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

//pas数组版 AC
program sgu122;
var
    map:array[1..1000,1..1000] of boolean;
    plist,buf:array[1..1000] of longint;
    ninlist:array[1..1000] of boolean;
    n,i,j,base,num:longint;
    find:boolean;
 
procedure reverse(i,j:longint);
var
    k:longint;
begin
    move(plist[i],buf[1],(j-i+1)*sizeof(longint));
    for k:=i to j do plist[k]:=buf[j-k+1];
end;
 
begin
    readln(n);
    fillchar(map,sizeof(map),false);
    fillchar(ninlist,sizeof(ninlist),true);
    for i:=1 to n do begin
        while not eoln do begin
            read(j);
            map[i,j]:=true; map[j,i]:=true;
        end;
        readln;
    end;
    num:=1; plist[1]:=1; ninlist[1]:=false;
    while num<n do begin
        for j:=1 to 2 do begin
            repeat
                find:=false;
                for i:=1 to n do if (ninlist[i] and map[i,plist[num]]) then begin
                    find:=true;
                    inc(num); plist[num]:=i; ninlist[i]:=false;
                    break;
                end;
            until not find;
            reverse(1,num);
        end;
        for i:=1 to num-1 do if (map[plist[i],plist[num]] and map[plist[i+1],plist[1]]) then begin
            reverse(i+1,num);
            break;
        end;
        for i:=1 to n do if ninlist[i] then begin
            for j:=1 to num do if map[i,plist[j]] then begin
                move(plist[1],buf[1],j*sizeof(longint));
                move(plist[j+1],plist[1],(num-j)*sizeof(longint));
                move(buf[1],plist[num-j+1],j*sizeof(longint));
                break;
            end;
            inc(num); plist[num]:=i; ninlist[i]:=false;
            break;
        end;
    end;
    base:=0;
    for i:=1 to n do if plist[i]=1 then begin
        base:=i;
        break;
    end;
    for i:=0 to n-1 do
        write(plist[(base+i-1)mod n+1],' ');
    writeln(1);
end.
?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

//cpp数组版 TLE on test 20
#include <cstdio>
#include <algorithm>
using namespace std;
 
int n,num=0;
int plist[1001]={0},buf[1001];
char rbuf[5001];
bool ninlist[1001];
bool map[1001][1001]={{0}};
 
int main() {
    gets(rbuf); sscanf(rbuf,"%d",&n);
    for (int i=1;i<=n;++i) {
        ninlist[i]=true;
        int j=0,pos=0;
        gets(rbuf);
        while (sscanf(rbuf+pos,"%d",&j)!=EOF) {
            map[i][j]=map[j][i]=true;
            while (rbuf[pos]>32) pos++;
            while (rbuf[pos]==32) pos++;
        }
    }
    plist[++num]=1; ninlist[1]=false;
    while (num<n) {
        for (int i=0;i<2;i++) {
            for (bool find=true;find;) {
                find=false;
                for (int i=1;i<=n;i++) if (ninlist[i] && map[i][plist[num]]) {
                    find=true;
                    plist[++num]=i; ninlist[i]=false;
                    break;
                }
            }
            reverse(plist+1,plist+num+1);
        }
        for (int i=1;i<num;++i) if (map[plist[i]][plist[num]] && map[plist[i+1]][plist[1]]) {
            reverse(plist+i+1,plist+num+1);
            break;
        }
        for (int i=1;i<=n;++i) if (ninlist[i]) {
            for (int j=1;j<=num;++j) if (map[i][plist[j]]) {
                memmove(buf,&plist[1],j*sizeof(int));
                memmove(&plist[1],&plist[j+1],(num-j)*sizeof(int));
                memmove(&plist[num-j+1],buf,j*sizeof(int));
                break;
            }
            plist[++num]=i; ninlist[i]=false;
            break;
        }
    }
    int pos=1;
    for (;pos<=n;++pos) if (plist[pos]==1) break;
    for (int i=0;i<n;++i) printf("%d ",plist[(pos+i-1)%n+1]);
    printf("1\n");
    return 0;
}