BZOJ 4725 Reprezentacje różnicowe

发表于 | 更新于

Link

搜到了波兰人的题解！！还有视频！！

Solution

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
  1:                   1
  2:                   2
  3:                   4
  4:                   8
  5:                  16
  6:                  21
  7:                  42
  8:                  51
  9:                 102
 10:                 112
 11:                 224
 12:                 235
 13:                 470
 14:                 486
 15:                 972
 16:                 990
 17:                1980
 18:                2002
 19:                4004
 20:                4027
 21:                8054
 22:                8078
 23:               16156
 24:               16181
 25:               32362
 26:               32389
 27:               64778
 28:               64806
 29:              129612
 30:              129641
 31:              259282
 32:              259313
 33:              518626
 34:              518658
 35:             1037316
 36:             1037349
 37:             2074698
 38:             2074734
 39:             4149468
 40:             4149505
 41:             8299010
 42:             8299049
 43:            16598098
 44:            16598140
 45:            33196280
 46:            33196324
 47:            66392648
 48:            66392693
 49:           132785386
 50:           132785432
 51:           265570864
 52:           265570912
 53:           531141824
 54:           531141876
 55:          1062283752
 56:          1062283805
 57:          2124567610
 58:          2124567664
 59:          4249135328
 60:          4249135383
 61:          8498270766
 62:          8498270822
 63:         16996541644
 64:         16996541701
 65:         33993083402
 66:         33993083460
 67:         67986166920
 68:         67986166979
 69:        135972333958
 70:        135972334020
 71:        271944668040
 72:        271944668103
 73:        543889336206
 74:        543889336270
 75:       1087778672540
 76:       1087778672605
 77:       2175557345210
 78:       2175557345276
 79:       4351114690552
 80:       4351114690619
 81:       8702229381238
 82:       8702229381306
 83:      17404458762612
 84:      17404458762681
 85:      34808917525362
 86:      34808917525433
 87:      69617835050866
 88:      69617835050938
 89:     139235670101876
 90:     139235670101949
 91:     278471340203898
 92:     278471340203972
 93:     556942680407944
 94:     556942680408019
 95:    1113885360816038
 96:    1113885360816114
 97:    2227770721632228
 98:    2227770721632305
 99:    4455541443264610
100:    4455541443264688

打表发现，50来项之后就有 ，而a[2i+1]=2a[2i]a[2i+1]=2a[2i]，所以差值要 ，只能是一个偶数项和它的前一项，也就是a[2i]−a[2i−1]=r[2i−1]a[2i]-a[2i-1]=r[2i-1]。 这些a[2i]a[2i]只能让集合SS增加一个 的数字，即r[2i−1]r[2i-1]，所以数组r[]r[]在a[i]>1e9a[i]> 1e9之后是连续变化，每次增加11。 所以把小范围的答案算出来存进 ，也把SS存起来； 大范围xx的在SS中二分找到最后一个小于xx的pp，也就是说在预处理的这些项之外，要找到第x−px-p对数字。然后再算一下就可以得到答案了。 比较好理解，但我太jiruo，想了很长时间。

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
//Code by Lucida
#include<bits/stdtr1c++.h>
typedef long long int64;
namespace IO
{
	template <class T> inline void get(T &x) {
		static bool f;static char ch;
		for(f=0,ch=0;ch<'0' || '9'<ch;ch=getchar()) f|=ch=='-';
		for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
		x=f?-x:x;
	}
	template <> inline void get<char>(char &x) {
		while(x=getchar(),((x<'0' || '9'<x) && (x<'a' || 'z'<x) && (x<'A' || 'Z'<x)));
	}
	template <> inline void get<char*>(char *&x) {
		char *cp=x;
		while(*cp++=getchar(),(*cp!=' ' && *cp!='\r' && *cp!='\n' && *cp!=EOF));
		*--cp=0;
	}

	template <class T> inline void put(T x) {
		if(!x)
			putchar('0');
		else {
			if(x<0) {
				putchar('-');
				x=-x;
			}
			static char stack[30]={0};
			char *top=stack;
			for(;x;x/=10) *++top=x%10+'0';
			while(*top) putchar(*top--);
		}
	}
	template <> inline void put<char>(char x) {
		putchar(x);
	}
	template <> inline void put<const char*>(const char* x) {
		while(*x)
			putchar(*x++);
	}

}

template <class T> inline bool chkmx(T &a,const T &b) {
	return a<b?a=b,1:0;
}
template <class T> inline bool chkmn(T &a,const T &b) {
	return a>b?a=b,1:0;
}

using std::swap;
using std::max;
using std::min;
using IO::get;
using IO::put;


using std::set;
using std::pair;
using std::make_pair;
using std::map;
using std::upper_bound;
const int N=57,MAXN=N+5;
struct Solver {
	map<int,pair<int,int> > rec;
	int64 a[MAXN],d[N*N];
	int dcnt;
	Solver() {
		a[0]=0,a[1]=1,a[2]=2;
		rec[1]=make_pair(2,1);
		for(int i=3;i<=N;++i) {
			if(i&1) {
				a[i]=a[i-1]*2;
			} else {
				int mex=1;
				while(rec.count(mex)) mex++;
				a[i]=a[i-1]+mex;
			}
			for(int j=1;j<i;++j) {
				rec[a[i]-a[j]]=make_pair(i,j);
			}
		}
		dcnt=0;
		for(map<int,pair<int,int> >::iterator it=rec.begin();it!=rec.end();++it) {
			d[++dcnt]=it->first;
		}
	}
	pair<int,int> operator ()(int x) {
		if(rec.count(x))
			return rec[x];
		else {
			int p=upper_bound(d+1,d+1+dcnt,x)-d-1;
			return make_pair(N+(x-p)*2-1,N+(x-p)*2-2);
		}
	}
}Cal;
int main() {
	//naive哈哈哈
//	freopen("input","r",stdin);
	int n;get(n);
	for(int i=1;i<=n;++i) {
		int x;get(x);
		pair<int,int> Ans=Cal(x);
		put(Ans.first),put(' '),put(Ans.second),put('\n');
	}
	return 0;
}