0%

Camp Day2

发表于 阅读次数：

Camp第二天比赛部分题解。

H.叁佰爱抠的序列

叁佰爱抠的智商有三百，他特别喜欢构造各种各样的序列。

这天他突然想出了这样一个序列：

一个长度为n的序列A，元素的值域是[1,m]。

对于任意x,y∈[1,m],x≠y，序列中存在一个位置p(1≤p<n)，满足A[p]=x,A[p+1]=y或者A[p+1]=x,A[p]=y。

叁佰爱抠很开心地走了。作为他忠实粉丝的你只听清楚了n的大小，那么你好奇了起来，m最大值可以取到多少，并且打算自己动手构造一个这样的序列。

输入格式：

读入一个整数n(1≤n≤1e18)，代表序列的长度。

输出格式

若n>2∗106，请直接输出一个整数m代表最大取值。

若n≤2∗106，请按以下格式输出： 第一行输出一个整数m，代表最大取值。 第二行输出n个整数，代表满足条件的序列。

输入样例：

1
8
1
6

输出样例：

1
2
4
1 2 3 1 4 3 4 2
1
2
3
1 2 3 1 1 1

题解：首先观察序列的含义，每对x,y(x<y) 在序列中至少相邻一次，将x，y相邻看成一条边，对于n个点的完全图(存在自环)来说，该序列的含义为，图上的一条链，该链包含每条边，每条边可以重复出现。对于这样的链，其特殊情况即每条边只出现一次为欧拉通路或者欧拉回路。故对n个点建好完全图，跑出欧拉路即可构造出题目需要的序列。

知道序列为完全图欧拉路之后，可以推出点数n与序列长度m的关系

1.当点数n为奇数时，即每个点的度都为偶数，该图存在欧拉回路，即该图所有的边可以构成满足条件的序列，设边数为m，则n个点最少边数为n(n-1)/2,序列长度至少为n****(n-1)/2+1;

2.当点数n为偶数时，每个点的度都为奇数，不存在欧拉通路，故我们要尝试提出一些边，使得存在欧拉通路，即只存在两奇点(度数为奇数的点),设1和n为奇点，剩下n-2为偶点，任取(n-2)/2对点之间的边即可，跑出欧拉通路后，再把这(n-2)/2条边补在最后面，就能构成满足条件的序列。此时n个点需要最少边数依然是n(n-1)/2，但因为放了（n-2）/2条无公共点的边，导致序列长度增加，最后序列长度至少为n****n/2。

综上 知道序列长度后，可以采用二分法推出最大点数，然后建图跑欧拉路，构造序列即可。

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
#include <bits/stdc++.h>
#define ll long long
#define mk(a,b) make_pair(a, b)
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e6 + 5;
const int maxm = 1e5 + 5;
struct edge{
	int to, next, f;
}e[maxm];
int head[maxn], num;
void add(int u, int v){
	e[num] = (edge){v, head[u], 0}; head[u] = num++;
}
void dfs(int u){
	for(int i=head[u];~i;i=e[i].next){
		if(e[i].f) continue;
		e[i].f = e[i^1].f = 1;
		dfs(e[i].to);
		printf("%d ", e[i].to);
	}
}
int main(){
	ll n;
	memset(head, -1, sizeof head);
	num = 0;
	scanf("%lld",&n);
	if(n > 2000000) {
		//TODO;
		ll m1, m2;
		ll l = 1, r = 1500000000;
		while(l <= r) {
			ll mid = l+r>>1;
			if(mid&1) {
				if(1+(mid-1)/2*mid <= n) l = mid + 1;
				else r = mid - 1;
			}
			else {
				if(mid/2*mid <= n) l = mid + 1;
				else r = mid - 1;
			}
		}
		printf("%lld\n", r);
	}
	else {
		int l = 1, r = 2000;
		while(l <= r) {
			int mid = l+r>>1;
			if(mid&1) {
				if(1+mid*(mid-1)/2 <= n) l = mid + 1;
				else r = mid - 1;
			}
			else {
				if(mid*mid/2 <= n) l = mid + 1;
				else r = mid - 1;
			}
		}
		printf("%d\n", r);
		if(r & 1){
			for(int i=1;i<=r;i++){
				for(int j=1+i;j<=r;j++){
					add(i, j);
					add(j, i);
				}
			}
			dfs(1);
			printf("%d", 1);
			int tmp = n - 1 - r*(r-1)/2; 
			for(int j=0;j<tmp;++j) printf(" %d", 1);
			puts("");
		}
		else {
			
			for(int i=1;i<=r;i++){

				for(int j=i+1;j<=r;j++){
					if(i!=1 && (i&1) && i+1==j) continue;
  					add(i, j);
					add(j, i);
				}
			}

			dfs(1);
			printf("1");
			for(int i=3;i<r;i+=2) printf(" %d %d", i, i+1);
			int tmp = n - r*r/2;
			for(int i=0;i<tmp;i++) printf(" 1");
            puts("");

		}
	}
}

2.邦邦的2-SAT模板

邦邦是图论白痴，他有一天捡到了一份模板，可以解决2-SAT问题并输出方案。

所谓2-SAT问题，指：有n个布尔变量a**、、i，有m个形如xor**y=tru**e的方程，x和y为a**i或者!a**i，求是否存在一组a**i的取值满足所有方程。

戳戳是真正的图论大师，他看了看邦邦的板子，发现这段代码会超时。邦邦不相信，戳戳要赶去约会了，于是希望你构造一个数据让邦邦这段代码超时。

具体地，你需要根据给定的n按如下格式构造：

第一行输出一个整数m(0≤m≤n)，代表有m个方程。

接下来m行，给出两个数x和y(−n≤x,y≤n,x,y≠0)，若数字为负数，代表!a**i，否则代表a**i。

要求保证代码中solve的返回值是true(存在至少一组解)，且CNT的值满足

n2≤2∗CNT

邦邦的2-SAT模板见附录。

输入格式：

读入一个整数n(1≤n≤3000)。

输出格式

按规定格式输出。

输入样例：

1
1

输出样例：

1
0

附录

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
#include<cstdio>
using namespace std;
const int N=3010;
int g[N<<1],nxt[N<<1],v[N<<1],num;
int q[N<<1],t;
bool vis[N<<1];
int CNT;
int n,m;
void add(int x,int y){
	nxt[++num]=g[x];
	v[num]=y;
	g[x]=num;
}
bool dfs(int x){
	CNT++;
	if(vis[x>n?x-n:x+n])return 0;
	if(vis[x])return 1;
	vis[q[++t]=x]=1;
	for(int i=g[x];i;i=nxt[i])if(!dfs(v[i]))return 0;
	return 1;
}
bool solve(){
	for(int i=1;i<=n;i++)if(!vis[i]&&!vis[i+n]){
		t=0;
		if(!dfs(i)){
			while(t)vis[q[t--]]=0;
			if(!dfs(i+n))return 0;
		}
	}
	return 1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		if(x<0)x=n-x;if(y<0)y=n-y;
		add(x>n?x-n:x+n,y);add(y>n?y-n:y+n,x);
	}
	solve();
	return 0;
}

题目给了一个市面上常用的2-SAT模板，复杂度O(n*(n+m))，主要用于求字典序最小的方案，当求通解或判断是否存在解时，可用tarjan缩点的方式在(m+n)的时间内求出。当明白该模板原理后，很容易发现，一条长链就可以吧该模板卡成最坏复杂度。因为只有每次dfs到最深处，才知道该次dfs为假，至于优化，不是很了解…