题目链接：http://codeforces.com/problemset/problem/1166/D
题目大意
给定序列的第一个元素 a 和最后一个元素 b 还有一个限制 m，请构造一个序列，序列的第 i 项 xi 满足 $x_i = sum_{i = 1}^{i - 1} + r_i，1 leq r_i leq m$。
分析
令 ri 分别全 1 和全 m，可以得到$2^{i - 2} * (a + 1) leq x_i leq 2^{i - 2} * (a + m), i geq 2$。
因此，如果以 b 为第 k 个元素能够构成一个序列，那么 b 一定满足$2^{k - 2} * (a + 1) leq b leq 2^{k - 2} * (a + m), k geq 2$。
反过来，如果存在 k 使 b 满足$2^{k - 2} * (a + 1) leq b leq 2^{k - 2} * (a + m), k geq 2$，那么是否一定能构成一个序列呢？其实是可以的，证明如下：
$$
egin{align*}
&∵ x_i = (sum_{j = 1}^{j - 1} x_j) + r_i，1 leq r_i leq m，i geq 2 \
&∵ sum_{j = 1}^{j - 1} x_j = 2 * x_{i - 1} - r_{i - 1} \
&∴ x_i = 2 * x_{i - 1} + r_i - r_{i - 1} \
&∵ x_2 = a + r_2 \
&∴ x_i = 2^{i - 2} * a + 2^{i - 3} * r_2 + 2^{i - 4} * r_3 + dots + 2 * r_{i - 2} + r_{i - 1} + r_i \
&∴ x_i = 2^{i - 2} * a + r_i + (sum_{j = 0}^{i - 3} 2^j * r_{i - j - 1}) \
&设 h = r_k，d_i = r_k - h，1 - m leq d_i leq m - 1，1 leq h leq m \
&∴ x_i = 2^{i - 2} * a + h + (sum_{j = 0}^{i - 3} 2^j * (d_{i - j - 1} + h)) \
&∴ x_i = 2^{i - 2} * (a + h) + (sum_{j = 0}^{i - 3} 2^j * d_{i - j - 1}) \
&令 d_{i - j - 1} = 0 or 1，0 leq j leq i - 3 \
&于是有(sum_{j = 0}^{i - 3} 2^j * d_{i - j - 1}) < 2^{i - 2} \
&∴ x_i = 2^{i - 2} * (a + h) + (sum_{j = 0}^{i - 3} 2^j * d_{i - j - 1}) 满足 2^{i - 2} * (a + 1) leq x_i leq 2^{i - 2} * (a + m), i geq 2
end{align*}
$$
至此我们找到了 $r_i$ 的一种赋值方案，使得 $2^{i - 2} * (a + 1) leq x_i leq 2^{i - 2} * (a + m), i geq 2$。
应用到通项公式后我们发现： $x_{i - 1} = frac{x_i + r_{i - 1} - r_i}{2} = frac{x_i + p_i}{2}，p_i in {-1, 0, 1}$。
pi 的值视 xi 而定，且满足$2 | (x_i + p_i)$。
那么序列 p 中把 0 除外后的序列必然是 -1，1，-1交错的，可以用反证法证明。
如果 pi == pi+1 == 1，那么 ri-1 - ri+1 == 2，与 |rj - ri| == |dj - di| <= 1 矛盾。
据此可以从尾部开始向前构造序列。
代码如下
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 5 #define Rep(i,n) for (int i = 0; i < (n); ++i) 6 #define For(i,s,t) for (int i = (s); i <= (t); ++i) 7 #define rFor(i,t,s) for (int i = (t); i >= (s); --i) 8 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i) 9 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i) 10 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 11 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 12 13 #define pr(x) cout << #x << " = " << x << " " 14 #define prln(x) cout << #x << " = " << x << endl 15 16 #define LOWBIT(x) ((x)&(-x)) 17 18 #define ALL(x) x.begin(),x.end() 19 #define INS(x) inserter(x,x.begin()) 20 21 #define ms0(a) memset(a,0,sizeof(a)) 22 #define msI(a) memset(a,inf,sizeof(a)) 23 #define msM(a) memset(a,-1,sizeof(a)) 24 25 #define MP make_pair 26 #define PB push_back 27 #define ft first 28 #define sd second 29 30 template<typename T1, typename T2> 31 istream &operator>>(istream &in, pair<T1, T2> &p) { 32 in >> p.first >> p.second; 33 return in; 34 } 35 36 template<typename T> 37 istream &operator>>(istream &in, vector<T> &v) { 38 for (auto &x: v) 39 in >> x; 40 return in; 41 } 42 43 template<typename T1, typename T2> 44 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) { 45 out << "[" << p.first << ", " << p.second << "]" << " "; 46 return out; 47 } 48 49 inline int gc(){ 50 static const int BUF = 1e7; 51 static char buf[BUF], *bg = buf + BUF, *ed = bg; 52 53 if(bg == ed) fread(bg = buf, 1, BUF, stdin); 54 return *bg++; 55 } 56 57 inline int ri(){ 58 int x = 0, f = 1, c = gc(); 59 for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); 60 for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); 61 return x*f; 62 } 63 64 typedef long long LL; 65 typedef unsigned long long uLL; 66 typedef pair< double, double > PDD; 67 typedef pair< int, int > PII; 68 typedef pair< string, int > PSI; 69 typedef set< int > SI; 70 typedef vector< int > VI; 71 typedef map< int, int > MII; 72 typedef pair< LL, LL > PLL; 73 typedef vector< LL > VL; 74 typedef vector< VL > VVL; 75 const double EPS = 1e-10; 76 const LL inf = 0x7fffffff; 77 const LL infLL = 0x7fffffffffffffffLL; 78 const LL mod = 1e18 + 7; 79 const int maxN = 2e5 + 7; 80 const LL ONE = 1; 81 const LL evenBits = 0xaaaaaaaaaaaaaaaa; 82 const LL oddBits = 0x5555555555555555; 83 84 int q; 85 LL a, b, m, k; 86 LL x[57]; 87 88 int main(){ 89 INIT(); 90 cin >> q; 91 while(q--) { 92 cin >> a >> b >> m; 93 LL p = 1; 94 k = 2; 95 // 找使得 b <= p * (a + m) 的最小 p 96 while(b > p * (a + m)) { 97 ++k; 98 p <<= 1; 99 } 100 // 在 a != b 的情况下，只要满足 p * (a + 1) <= b <= p * (a + m)，就一定可以构造 101 if(b >= p * (a + 1)) { 102 cout << k << " "; 103 x[1] = a; 104 x[k] = b; 105 int p = 1; 106 rFor(i, k - 1, 2) { 107 if(x[i + 1] % 2 == 0) x[i] = x[i + 1] >> 1; 108 else { 109 x[i] = (x[i + 1] + p) >> 1; 110 p = -p; 111 } 112 } 113 For(i, 1, k) cout << x[i] << " " << endl; 114 cout << endl; 115 } 116 else if(a == b) cout << "1 " << a << endl; 117 else cout << -1 << endl; 118 } 119 return 0; 120 }
大佬代码如下
和我的代码效果是一样的，但我死活推不出原理，只能先搁着里了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 5 #define Rep(i,n) for (int i = 0; i < (n); ++i) 6 #define For(i,s,t) for (int i = (s); i <= (t); ++i) 7 #define rFor(i,t,s) for (int i = (t); i >= (s); --i) 8 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i) 9 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i) 10 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 11 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 12 13 #define pr(x) cout << #x << " = " << x << " " 14 #define prln(x) cout << #x << " = " << x << endl 15 16 #define LOWBIT(x) ((x)&(-x)) 17 18 #define ALL(x) x.begin(),x.end() 19 #define INS(x) inserter(x,x.begin()) 20 21 #define ms0(a) memset(a,0,sizeof(a)) 22 #define msI(a) memset(a,inf,sizeof(a)) 23 #define msM(a) memset(a,-1,sizeof(a)) 24 25 #define MP make_pair 26 #define PB push_back 27 #define ft first 28 #define sd second 29 30 template<typename T1, typename T2> 31 istream &operator>>(istream &in, pair<T1, T2> &p) { 32 in >> p.first >> p.second; 33 return in; 34 } 35 36 template<typename T> 37 istream &operator>>(istream &in, vector<T> &v) { 38 for (auto &x: v) 39 in >> x; 40 return in; 41 } 42 43 template<typename T1, typename T2> 44 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) { 45 out << "[" << p.first << ", " << p.second << "]" << " "; 46 return out; 47 } 48 49 inline int gc(){ 50 static const int BUF = 1e7; 51 static char buf[BUF], *bg = buf + BUF, *ed = bg; 52 53 if(bg == ed) fread(bg = buf, 1, BUF, stdin); 54 return *bg++; 55 } 56 57 inline int ri(){ 58 int x = 0, f = 1, c = gc(); 59 for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); 60 for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); 61 return x*f; 62 } 63 64 typedef long long LL; 65 typedef unsigned long long uLL; 66 typedef pair< double, double > PDD; 67 typedef pair< int, int > PII; 68 typedef pair< string, int > PSI; 69 typedef set< int > SI; 70 typedef vector< int > VI; 71 typedef map< int, int > MII; 72 typedef pair< LL, LL > PLL; 73 typedef vector< LL > VL; 74 typedef vector< VL > VVL; 75 const double EPS = 1e-10; 76 const LL inf = 0x7fffffff; 77 const LL infLL = 0x7fffffffffffffffLL; 78 const LL mod = 1e18 + 7; 79 const int maxN = 2e5 + 7; 80 const LL ONE = 1; 81 const LL evenBits = 0xaaaaaaaaaaaaaaaa; 82 const LL oddBits = 0x5555555555555555; 83 84 int q; 85 LL a, b, m, k; 86 87 int main(){ 88 INIT(); 89 cin >> q; 90 while(q--) { 91 cin >> a >> b >> m; 92 LL p = 1; 93 k = 2; 94 // 找使得 b <= p * (a + m) 的最小 p 95 while(b > p * (a + m)) { 96 ++k; 97 p <<= 1; 98 } 99 // 在 a != b 的情况下，只要满足 p * (a + 1) <= b <= p * (a + m)，就一定可以构造 100 if(b >= p * (a + 1)) { 101 cout << k << " " << a << " "; 102 For(i, 2, k - 1) cout << (((b >> (k - i - 1)) + 1) >> 1) << " "; 103 cout << b << endl; 104 } 105 else if(a == b) cout << "1 " << a << endl; 106 else cout << -1 << endl; 107 } 108 return 0; 109 }