Post 14

Veröffentlicht am

如果手里捏着属于自己的泥土，看见青禾在晴空下微风里缓缓生长，算计着一年的收获，那份踏实的情绪，才是余生最好的答案。——三毛

今天尽管大概在机房带了6个多小时，却一道题都没有切。。

其实切了一道，只不过是联赛官方数据水才AC的。。其实思路是对的，只不过不知道哪里出了差错。。

NOIP 2018 D2T1 旅行

题目描述

小 Y 是一个爱好旅行的 OIer。她来到 X 国，打算将各个城市都玩一遍。

小Y了解到， X国的 nn 个城市之间有 mm 条双向道路。每条双向道路连接两个城市。 不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且， 从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些 道路从一个城市前往另一个城市。

小 Y 的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可 以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该 城市时经过的道路后退到上一个城市。当小 Y 回到起点时，她可以选择结束这次旅行或 继续旅行。需要注意的是，小 Y 要求在旅行方案中，每个城市都被访问到。

为了让自己的旅行更有意义，小 Y 决定在每到达一个新的城市（包括起点）时，将 它的编号记录下来。她知道这样会形成一个长度为 nn 的序列。她希望这个序列的字典序 最小，你能帮帮她吗？ 对于两个长度均为 nn 的序列 AA 和 BB，当且仅当存在一个正整数 xx，满足以下条件时， 我们说序列 AA 的字典序小于 BB。

  • 对于任意正整数 1 ≤ i < x1≤i<x，序列 AA 的第 ii 个元素 A_iAi 和序列 BB 的第 ii 个元素 B_iBi 相同。
  • 序列 AA 的第 xx 个元素的值小于序列 BB 的第 xx 个元素的值。

输入输出格式

输入格式：

输入文件共 m + 1m+1 行。第一行包含两个整数 n,m(m ≤ n)n,m(m≤n)，中间用一个空格分隔。

接下来 m 行，每行包含两个整数 u,v (1 ≤ u,v ≤ n)u,v(1≤u,v≤n) ，表示编号为 uu 和 vv 的城市之 间有一条道路，两个整数之间用一个空格分隔。

输出格式：

输出文件包含一行，nn 个整数，表示字典序最小的序列。相邻两个整数之间用一个 空格分隔。

输入输出样例

输入样例#1：

复制

1
2
3
4
5
6
6 5 
1 3 
2 3 
2 5 
3 4 
4 6

输出样例#1：

复制

1
1 3 2 5 4 6

输入样例#2：

复制

1
2
3
4
5
6
7
6 6 
1 3 
2 3 
2 5 
3 4 
4 5 
4 6

输出样例#2：

1
1 3 2 4 5 6

说明

【数据规模与约定】

对于 100\%100% 的数据和所有样例， 1 \le n \le 50001≤n≤5000 且 $m = n − 1$ 或 m = nm=n 。

对于不同的测试点， 我们约定数据的规模如下：

img

题解

暴力断边就不说了，主要说说如何线性贪心。

每个点的vector先排序。

考虑到按树的方式贪心，直到第一个环上的点，我们称为根。

这个根显然可以按照环两点大小（小的称为lson，大的称为rson）分成5部分：

  • 比lson小的，直接递归访问即可。
  • lson开始贪心
  • 在lson至rson中间的，找出最小的，全部压进一个队列。
  • rson后面的，最后处理即可。

那么对于环该如何贪心呢？

显然我们可以不断的从lson往环的另一边走，边走边记录假如它回溯第一个节点是什么，如果小于下一个环上的节点，那就回溯（反证贪心）

回来后把队列里的点递归访问子树。

然后从rson开始走，这个就纯模拟了。

走完把大于rson的点及其子树递归访问。然后return，这个环就解决了。

Code（实际上是错误的但AC了。。）：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#define maxn 500005
std::vector<int> g[maxn];
int id[maxn] , n , m , cir[maxn] , cirnum , ct , ans[maxn];
struct Node{
    int u , v;
};
std::stack<Node> p;
std::queue<int> q;
namespace circle
{
    int dfn[maxn] , low[maxn] , idx , tot , sz[maxn];
    std::stack<int> st;
    void Tarjan(int x, int fx)
    {
        dfn[x] = low[x] = ++idx;
        st.push(x);
        for(int i = 0 ; i < (int)g[x].size(); ++i)
        {
            int v = g[x][i];
            if(!dfn[v]) Tarjan(v , x) ,  low[x] = std::min(low[x] , low[v]);
            else if(v != fx) low[x] = std::min(low[x] , dfn[v]);
        }
        if(dfn[x] == low[x])
        {
            ++tot;
            while(st.top() != x)
            {
                cir[st.top()] = tot;
                sz[tot] ++;
                st.pop();
            }
            cir[st.top()] = tot;
            sz[tot] ++ ;
            st.pop();
        }
    }
    inline void pre()
    {
        Tarjan(1,1);
        for(int i = 1 ; i <= tot ; ++i)
            if(sz[i] > 1){
                cirnum = i;
                break;
            }
        for(int i = 1 ; i <= n ; ++i)
            if(cir[i] != cirnum)
                cir[i] = 0;
        for(int i = 1 ; i <= n ; ++i)
            if(g[i].size() > 1)
                std::sort(g[i].begin() , g[i].end());
    //	puts("THE CICLE");
    //	for(int i = 1 ; i <= n ; ++i)
    //		if(cir[i])
    //			printf("%d ",i);
    }

}
void getID(int x, int fx)
{
    //printf("The Visit Tree point:%d %d\n",x,ct+1);
    id[x] = ++ct;
    if(cir[x])
    {
//		printf("The first point on the Circle: %d\n",x);
//		for(int i = 0 ; i < (int)g[x].size() ; ++i)
//			printf("%d ",g[x][i]);
//		putchar(10);
        int lson = 0 ,rson = 0 , stp = -1 , pre = 0x7ffff;
        for(int i = 0 ; i < (int)g[x].size() ; ++i) // find the two adjancent points
        {
            int v = g[x][i];
            if(v == fx) continue;
            if(lson && rson){
                stp = i;
                break;
            }
            if(!cir[v] && lson && v > lson){
                pre = std::min(pre , v);
                q.push(v);
                continue;
            }
            else if(!cir[v] && v < lson){
                getID(v , x);
                continue;
            }
            if(!lson) lson = v;
            else if(lson && !rson) rson = v;
        }
    //	printf("QQQQ%d %d\n",q.size() , pre);
    //	printf("The lson , rson ans the stop points are:%d %d %d\n",lson,rson,stp);
//		puts("While lson process");
        pre = std::min(pre , rson);
        while(lson != rson)
        {
//			printf("The cur lson ans rson:%d %d\n",lson , rson);
            int u = lson;
            id[u] = ++ct;
            bool flag = false;
            for(int i = 0 ; i < (int)g[u].size() ; ++i)
            {
                int v = g[u][i];
                if(id[v]) continue;
                else if(cir[v]){
                    int k = 0;
                    for(int j = i + 1 ; j < (int)g[u].size() ; ++j)
                    {
                        k = g[u][j];
                        if(cir[k]) continue;
                        pre = k;
                        break;
                    }
                    p.push((Node){u ,i + 1});
//					printf("%d %d %d\n",pre,v,lson);
                    if(v > pre){
                        flag = true;
                        break;
                    }
                    lson = v;
                    break;
                }
                else getID(v , u);
            }
            if(flag) break;
        }
        
//		puts("Backforward to visit the lsons tree points");
        while(!p.empty())
        {
    //		printf("Now the tree point source is : %d\n",p.top().u);
            int u = p.top().u , fr = p.top().v;
            p.pop();
            for(int i = fr ; i < (int)g[u].size() ; ++i)
            {
                int v = g[u][i];
                if(cir[v]) continue;
                getID(v , u);
            }
        }
        while(!q.empty())
        {
            int k = q.front();
            q.pop();
            getID(k , x);
        }
    //	printf("for pre : %dVisit from rson:%d\n",pre,rson);
//		puts("Now the rson remain");
        while(lson != rson)
        {
            int next = -1;
//			printf("now the rson is:%d\n",rson);
            int u = rson;
            id[u] = ++ct;
            for(int i = 0 ; i < (int)g[u].size() ; ++i)
            {
                int v =  g[u][i];
                if(id[v]) continue;
                else if(cir[v])
                {
                 	next = v;
                    p.push((Node){u , i + 1});
                    break;
                }
                else getID(v , u);
            }
            if(~next) rson = next;
            else break;
        }
//	 	puts("Backforward to visit the rsons tree points");
        while(!p.empty())
        {
    //		printf("Now the backforward point is:%d\n",p.top().u);
            int u = p.top().u , fr = p.top().v;
            p.pop();
            for(int i = fr ; i < (int)g[u].size() ; ++i)
            {
                int v = g[u][i];
                if(cir[v]) continue;
                getID(v , u);
            }
        }
    //	puts("The remain points of source:");
        if(!(~stp)) return;
        for(int i = stp ; i < (int)g[x].size() ; ++i){ //visit the remain tree points
            int v = g[x][i];
        //	printf("%d\n",v);
            if(v == fx) continue;
            getID(v , x);
        }
//		printf("The last visit:%d\n", ct);
        return;
    }


    for(int i = 0 ; i < (int)g[x].size() ; ++i)
    {
        int v = g[x][i];
        if(v == fx) continue;
        getID(v , x);
    }


}
int main()
{

    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= m ; ++i)
    {
        int x , y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    circle::pre();
    getID(1,1);
    for(int i = 1 ; i <= n ; ++i)
        ans[id[i]] = i;
    for(int i = 1 ; i <= n ; ++i)
        printf("%d ",ans[i]);
}

正确的写法应该是这样的，但是今天一天都没调出来，明天继续加油。。。

Code：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#define maxn 500005
std::vector<int> g[maxn];
int id[maxn] , n , m , cir[maxn] , cirnum , ct , ans[maxn];
struct Node{
	int u , v;
};
std::stack<Node> p;
std::queue<int> q;
namespace circle
{
	int dfn[maxn] , low[maxn] , idx , tot , sz[maxn];
	std::stack<int> st;
	void Tarjan(int x, int fx)
	{
		dfn[x] = low[x] = ++idx;
		st.push(x);
		for(int i = 0 ; i < (int)g[x].size(); ++i)
		{
			int v = g[x][i];
			if(!dfn[v]) Tarjan(v , x) ,  low[x] = std::min(low[x] , low[v]);
			else if(v != fx) low[x] = std::min(low[x] , dfn[v]);
		}
		if(dfn[x] == low[x])
		{
			++tot;
			while(st.top() != x)
			{
				cir[st.top()] = tot;
				sz[tot] ++;
				st.pop();
			}
			cir[st.top()] = tot;
			sz[tot] ++ ;
			st.pop();
		}
	}
	inline void pre()
	{
		Tarjan(1,1);
		for(int i = 1 ; i <= tot ; ++i)
			if(sz[i] > 1){
				cirnum = i;
				break;
			}
		for(int i = 1 ; i <= n ; ++i)
			if(cir[i] != cirnum)
				cir[i] = 0;
		for(int i = 1 ; i <= n ; ++i)
			if(g[i].size() > 1)
				std::sort(g[i].begin() , g[i].end());
	//	puts("THE CICLE");
	//	for(int i = 1 ; i <= n ; ++i)
	//		if(cir[i])
	//			printf("%d ",i);
	}

}
void getID(int x, int fx)
{
	//printf("The Visit Tree point:%d %d\n",x,ct+1);
	id[x] = ++ct;
	if(cir[x])
	{
//		printf("The first point on the Circle: %d\n",x);
//		for(int i = 0 ; i < (int)g[x].size() ; ++i)
//			printf("%d ",g[x][i]);
//		putchar(10);
		int lson = 0 ,rson = 0 , stp = -1 , pre = 0x7ffff;
		for(int i = 0 ; i < (int)g[x].size() ; ++i) // find the two adjancent points
		{
			int v = g[x][i];
			if(v == fx) continue;
			if(lson && rson){
				stp = i;
				break;
			}
			if(!cir[v] && lson && rson && v > lson && v < rson){
				pre = std::min(pre , v);
				q.push(v);
				continue;
			}
			else if(!cir[v] && v < lson){
				getID(v , x);
				continue;
			}
			if(!lson) lson = v;
			else if(lson && !rson) rson = v;
		}
	//	printf("QQQQ%d %d\n",q.size() , pre);
	//	printf("The lson , rson ans the stop points are:%d %d %d\n",lson,rson,stp);
//		puts("While lson process");
		pre = std::min(pre , rson);
        while(lson != rson)
		{
//			printf("The cur lson ans rson:%d %d\n",lson , rson);
			int u = lson , next = -1;
			id[u] = ++ct;
			bool flag = false;
			for(int i = 0 ; i < (int)g[u].size() ; ++i)
			{
				int v = g[u][i];
				if(id[v]) continue;
				else if(cir[v])
				{
					int k = 0;
					for(int j = i + 1 ; j < (int)g[u].size() ; ++j)
					{
					    k = g[u][j];
						if(cir[k]) continue;
						pre = k;
						break;
					}
					p.push((Node){u ,i + 1});
//					printf("%d %d %d\n",pre,v,lson);
					if(v > pre){
						flag = true;
						break;
					}
					next = v;
					break;
				}
				else getID(v , u);
			}
			if(flag) break;
			if(~next) lson = next;
			else break;
		}
		
//		puts("Backforward to visit the lsons tree points");
		while(!p.empty())
		{
	//		printf("Now the tree point source is : %d\n",p.top().u);
			int u = p.top().u , fr = p.top().v;
			p.pop();
			for(int i = fr ; i < (int)g[u].size() ; ++i)
			{
				int v = g[u][i];
				if(cir[v]) continue;
				getID(v , u);
			}
		}
		while(!q.empty())
		{
			int k = q.front();
			q.pop();
			getID(k , x);
		}
	//	printf("for pre : %dVisit from rson:%d\n",pre,rson);
//		puts("Now the rson remain");
		while(lson != rson)
		{
			int next = -1;
//			printf("now the rson is:%d\n",rson);
			int u = rson;
			id[u] = ++ct;
			for(int i = 0 ; i < (int)g[u].size() ; ++i)
			{
				int v =  g[u][i];
				if(id[v]) continue;
				else if(cir[v])
				{
				 	next = v;
					p.push((Node){u , i + 1});
					break;
				}
				else getID(v , u);
			}
			if(~next) rson = next;
			else break;
		}
//	 	puts("Backforward to visit the rsons tree points");
		while(!p.empty())
		{
	//		printf("Now the backforward point is:%d\n",p.top().u);
			int u = p.top().u , fr = p.top().v;
			p.pop();
			for(int i = fr ; i < (int)g[u].size() ; ++i)
			{
				int v = g[u][i];
				if(cir[v]) continue;
				getID(v , u);
			}
		}
	//	puts("The remain points of source:");
		if(!(~stp)) return;
		for(int i = stp ; i < (int)g[x].size() ; ++i){ //visit the remain tree points
			int v = g[x][i];
		//	printf("%d\n",v);
			if(v == fx) continue;
			getID(v , x);
		}
//		printf("The last visit:%d\n", ct);
		return;
	}


	for(int i = 0 ; i < (int)g[x].size() ; ++i)
	{
		int v = g[x][i];
		if(v == fx) continue;
		getID(v , x);
	}


}
int main()
{
	freopen("travel.in","r",stdin);
	freopen("my.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= m ; ++i)
	{
		int x , y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	circle::pre();
	getID(1,1);
	for(int i = 1 ; i <= n ; ++i)
		ans[id[i]] = i;
	for(int i = 1 ; i <= n ; ++i)
		printf("%d ",ans[i]);
}

感觉代码写着写着就又臭又长了啊。。明天重构一下代码吧，把能写成函数的写成函数。

Linux下code真好，超级稳定，从不卡崩溃什么的。

剩下的时间写写数学了