语言漩涡

thirtiseven 的博客

0%

ONTAK 2007 Hyperclock

Posted on Edited on

Hyperclock

题意

个时钟构成了一个超时钟，其中第 个时钟的钟面上写着 从 1 到 共计 个数字，每个时钟有一个指针，一开始，所有的指针都指向数字 1。你可以进行若干次操作，每次操作你可以选择一个时钟将它的指针往顺时针或逆时针移动一格。在执行完最后一次操作后，超时钟的每一种外形都应当被显示正好一次，并且每个指针回到初始位置。求一种合法的操作方案。

输入

第一行为 ，第二行包含 个数字 .

超时钟所有的形状 的大小不超过

输出

如果没有合法的操作方案，输出 NIE。

否则，输出 行。每行包含两个数字：第一个数字表示当前操作的时钟，第二个数字为旋转指针的方向（1表示顺时针，-1表示逆时针）

样例

1
2
3
4
3
2
2
3
1
2
3
4
5
6
7
8
9
10
11
12
1 1
2 1
1 -1
3 1
1 1
2 -1
3 1
2 1
1 -1
2 -1
3 -1
3 -1

解法

一个超时钟的形状可以形式化地表示为 表示当前每个时钟的指针当前直线的方向。于是我们可以很自然地用图来表示这个问题。每个节点是一个超时钟的状态而如果两种状态可以在一步之内互相转化，就连一条边。问题转化为一个哈密顿回路问题，它是一个 NP 完全问题。显然这样的复杂度不能被接受。但是其实这个问题的图有一个特殊的结构，使得我们可以在线性时间内完成求解。

考虑如果这个超时钟是由两个小时钟组成的，那么我们可以将它们的状态填进一个 的方格中。根据边的奇偶性分类讨论，我们可以得到如下的解决方案：

Hyperclock_s

然后我们就可以很容易地将问题扩展到一般情况。如果两个时钟版本的问题可以解决，那么就可以将这两个时钟看成一个有 种状态的大时钟，进而与第三个时钟结合解决三个时钟的问题。由于两个时钟的版本总是可以解决，所以 n 个时钟的版本也总是可以解决。

为了实现这种想法，首先要决定的是如果存储这些时钟。我们其实并不真的需要每一个钟面上的数字，只需要知道哪一步应该移动它的指针。所以可以每个时钟可以表示为一个长度为 k 的数组，每个元素是一个 pair (a, b) ，表示这一步第 a 个时钟顺时针旋转 b 格 。

由于我们可以在线性时间对两个时钟进行合并，那么总的复杂度就为(设 ) 时间复杂度为 ，空间复杂度为

代码

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

namespace fastIO{
	#define BUF_SIZE 100000
	#define OUT_SIZE 100000
	#define ll long long
	//fread->read
	bool IOerror=0;
//	inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;} 
	inline char nc(){
		static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
		if(p1==pend){
			p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);
			if(pend==p1){IOerror=1;return -1;}
		}
		return *p1++;
	}
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
	template<class T> inline bool read(T &x){
		bool sign=0;char ch=nc();x=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		if(ch=='-')sign=1,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(sign)x=-x;
		return true;
	}
	inline bool read(double &x){
		bool sign=0;char ch=nc();x=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		if(ch=='-')sign=1,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(ch=='.'){
			double tmp=1; ch=nc();
			for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
		}
		if(sign)x=-x;
		return true;
	}
	inline bool read(char *s){
		char ch=nc();
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
		*s=0;
		return true;
	}
	inline bool read(char &c){
		for(c=nc();blank(c);c=nc());
		if(IOerror){c=-1;return false;}
		return true; 
	}
	template<class T,class... U>bool read(T& h,U&... t){return read(h)&&read(t...);}
	//fwrite->print
	struct Ostream_fwrite{
		char *buf,*p1,*pend;
		Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
//		void out(char ch){putchar(ch);}
		void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
		template<class T>void print(T x){
			static char s[33],*s1;s1=s;
			if(!x)*s1++='0';if(x<0)out('-'),x=-x;
			while(x)*s1++=x%10+'0',x/=10;
			while(s1--!=s)out(*s1);
		}
		void print(double x,int y){
			static ll mul[]=
			{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,
			10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
			100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
			if(x<-1e-12)out('-'),x=-x;
			ll x2=(ll)floor(x);if(!y&&x-x2>=0.5)++x2;x-=x2;x*=mul[y];
			ll x3=(ll)floor(x);if(y&&x-x3>=0.5)++x3;print(x2);
			if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}
		}
		void print(char *s){while(*s)out(*s++);}
		void print(const char *s){while(*s)out(*s++);}
		void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
		~Ostream_fwrite(){flush();}
	}Ostream;
	template<class T>void print(T x){Ostream.print(x);}
	inline void print(char x){Ostream.out(x);}
	inline void print(char *s){Ostream.print(s);}
	inline void print(std::string s){Ostream.print(s.c_str());}
	inline void print(const char *s){Ostream.print(s);}
	inline void print(double x,int y){Ostream.print(x,y);}
	template<class T,class... U>void print(const T& h,const U&... t){print(h);print(t...);}
	void println(){print('\n');}
	template<class T,class... U>void println(const T& h,const U&... t){print(h);println(t...);}
	inline void flush(){Ostream.flush();}
	#undef ll
	#undef OUT_SIZE
	#undef BUF_SIZE
};
using namespace fastIO;

int n;
int k[100];
std::pair<int, int> ans[1000007], tmp[1000007];
int ans_siz = 0;

void merge_odd(int idx) {
	int cur = 0;
	for (int i = 0; i < k[idx]-1; i+=2) {
		for(int i = 0; i < ans_siz-2; i++) {
			tmp[cur++] = ans[i];
		}
		tmp[cur++] = std::make_pair(idx,1);
		for (int i = ans_siz-3; i >= 0; i--) {
			tmp[cur++] = std::make_pair(ans[i].first,-ans[i].second);
		}
		tmp[cur++] = std::make_pair(idx,1);
	}
	for (int i = 0; i < ans_siz-1; i++) {
		tmp[cur++] = ans[i];
	}
	for (int i = 0; i < k[idx]-1; i++) {
		tmp[cur++] = std::make_pair(idx,-1);
	}
	tmp[cur++] = ans[ans_siz-1];
	ans_siz *= k[idx];
	for (int i = 0; i < ans_siz; i++) {
		ans[i] = tmp[i];
	}
}

void merge_eve(int idx) {
	int cur = 0;
	for (int i = 0; i < k[idx]; i+=2) {
		for(int i = 0; i < ans_siz-1; i++) {
			tmp[cur++] = ans[i];
		}
		tmp[cur++] = std::make_pair(idx,1);
		for (int i = ans_siz-2; i >= 0; i--) {
			tmp[cur++] = std::make_pair(ans[i].first,-ans[i].second);
		}
		tmp[cur++] = std::make_pair(idx,1);
	}
	ans_siz *= k[idx];
	for (int i = 0; i < ans_siz; i++) {
		ans[i] = tmp[i];
	}
}

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	read(n);
	for (int i = 0; i < n; i++) {
		read(k[i]);
	}
	for (int i = 0; i < k[0]; i++) {
		ans[ans_siz++] = std::make_pair(0, 1);
	}
	for (int i = 1; i < n; i++) {
		if (k[i] % 2 == 0) {
			merge_eve(i);
		} else {
			merge_odd(i);
		}
	}
	for (int i = 0; i < ans_siz; i++) {
		print(ans[i].first+1);
		print(' ');
		print(ans[i].second);
		print('\n');
	}
}

吐槽

一个显然错误的直觉是可以把超时钟看成一个每位进制都不同的数字然后+1+1+1，但是我拿到这个题竟然就直接按照这种幻觉想开始写代码..

然后正常人一旦从这个错误中跳出来是不是都会想着推出一个类似格雷码形式的、看上去非常优雅的东西... 然后一下子推不出来，就感觉人生无望，自己好菜，这个东西怎么这么难（（（

这个题想法确实很妙吧，而且也不是很难写，是那种“如果我再聪明一点就能做出来了”的题目。

有一个笑话，找不到了，大意是说为了防止大家数学学不下去跳楼，数学系楼顶上立了一块牌子：“你考虑二维的情况了吗？”，非常好，我要把这句话打印出来贴在墙上。

就是卡了我输入输出...

我一开始一堆 vector 一堆 resize 就往上交，真是勇气可嘉（

贴了个丑陋的一百行快读上去就过了

感觉自己与其学新语言不如去重修 cpp 啊？