[传智杯 #5 初赛] E-梅莉的市场经济学

题目背景
梅莉这个学期选修了经济学。但是主修心理学的她实在不擅长经济领域的分析，为此她时常抱怨自己学不会，想退课。
但是如果现在退掉的话这学期的学分就不够啦，因此她根据“梦中”的经历，“胡诌”了一个简单到不现实的市场模型，并依据这个模型编起了 essay。为了方便地编出图表，她需要写一个程序来查询每个时刻的市场贸易差。
题目描述
市场每一天的贸易差可以视为一个有周期性规律的数列a:$\color{red}[0],\color{blue}[0, 1, 0, -1, 0],\color{red}[0, 1, 2, 1, 0, -1, -2, -1, 0], \color{blue}[0, 1, 2,3, 2, 1, 0, -1, -2, -3, -2, -1, 0]\dots$。具体而言，a 可以被分为无穷段，第 i 段的内容为 $\{0, 1,\cdots,i,i-1, \cdots,0, -1, \cdots,-i, -i+1,\cdots 0\}$如下图所示，是将a数列内的前一些点绘制在坐标轴上的情况：

现在梅莉对市场发起了 q次询问，每次她会给定一个 k，希望求出 $a_k$是多少。
输入格式

  • 第一行有一个正整数 q，表示询问次数。
  • 接下来 q 行，每行一个正整数 k，描述每次询问。

输出格式

  • 输出共 q行。对于每次询问，输出对应的结果。

样例 #1
样例输入 #1

1
2
3
4
5
6
7
8
9
10
9
1
10
100
1000
10000
100000
1000000
10000000
100000000

样例输出 #1
1
2
3
4
5
6
7
8
9
0
1
6
-9
-11
-128
406
1629
5154

提示
对于所有数据，有$1 \leq q \leq 10^5，1 \leq k \leq 4\times 10^{18}$。

题解：

对于这个数据规模，显然询问的次数是没有办法优化的，这就表明考虑最多的循环的次数至少有10^5。那么就算每次询问使用常数复杂度的方式也会超时，因为这个是一个一个区间的形式，每一个区间的长度是按照规律递增的，那么就可以考虑在最大和最小的区间内二分找。算上查询的O(n)复杂度为O(nlogn)左右，可以通过这个数据范围。
比较头疼的是这个规律以及他的上限应该定在哪一个位置比较合适。

峰值 0 1 2 3 4
长度 1 6 15 28 45
规律1 1 6 6+9 6+9+13 6+9+13+17
规律2 1 1+5 1+5+9 1+5+9+13 1+5+9+13+17
规律3
（等差求和，an = 1+4n=4n+1
=>
sn=(5+4n+1)n/2+1=2n^2+3n+1）
 1 21+31+1 24+32+1 29+33+1 216+34+1

从表中不难得出规律：2n^2+3n+1,但是在比赛的时候由于没有画表格，所以就只看出了递推关系：an-an-1 =4n+1,然后利用累加法（累加的时候一定要注意初始条件和结束条件以及一共累加了多少次），最后得出2 (2 + n) * (n - 1) + n + 5;这个式子的右边最大要特别的考虑，因为

因为是这个数据，可以计算出二分右边界要开到1.5*1e9左右，不然会出现死循环过不了最后几个点：

define MAX 1000000000时的情况:

image _2_.png

但是MAX改到1500000000时就能ac

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 1500000000

ll q, k, lb, n;
ll pren;

ll getnum(ll n) {
	return 2 * (2 + n) * (n - 1) + n + 5;//其实也可以写这个：2*n*n+3*n+1
}


//二分找区间
ll getindex() {
	cin >> k;
	lb = 0;
	ll ub = MAX;
	ll ubnum = getnum(ub);
	ll lbnum = getnum(lb);
	while (!(lbnum <= k && k <= getnum(lb + 1))) {//如果二分右边界不对的话这里就会死循环
		ll mid = (lb + ub) / 2;
		if (getnum(mid) >= k) {
			ub = mid;
		} else {
			lb = mid;
		}
		ubnum = getnum(ub);
		lbnum = getnum(lb);
	}
	pren = getnum(lb);
	n = getnum(lb + 1);
	return lb + 1;
}

int main() {
	ll ans = 0;
	cin.tie(0), cout.tie(0);
	ios::sync_with_stdio(false);
	cin >> q;
	while (q--) {
        //包括首尾的话每个区间一共有6个特殊点
		ll top = getindex();
		ll bottom = -top;
		ll zeroindex2 = (pren + n + 1) >> 1;
		ll zeroindex1 = pren + 1;
		ll topindex = (zeroindex1 + zeroindex2) >> 1;
		ll bottomindex = (zeroindex2 + n) >> 1;
        //k位于不同特殊点之间都有不一样的结果
		if (zeroindex1 < k && k < topindex) {
			ans = k - zeroindex1;
			cout << ans  << endl;
		} else if (topindex <= k && k < zeroindex2) {
			ans = top - (k - topindex);
			cout << ans  << endl;
		} else if (zeroindex2 < k && k < bottomindex) {
			ans =  zeroindex2 - k;
			cout <<  ans << endl;
		} else if (bottomindex <= k && k < n) {
			ans = bottom + (k - bottomindex);
			cout << ans  << endl;
		} else {
			cout << 0 << endl;
		}
	}
	return 0;
}

其实这道题目的难点有三：求通项公式，二分的右边界以及一堆条件分支。
求通项因为当时没有想到用表格的形式找规律，就只找到了递推关系式，并且在累加的时候没有考虑好累加的次数导致算错了好几次，如果用表格的话或许就能减少很多时间的浪费。
递增序列很容易想到二分，但是这道题要特别考虑右边界，这里也花了不少时间。
一堆条件分支删删改改了好久，如果在纸上先分析也可以省下调试的时间。