Blah数集

题意

完整题面见同目录的 problem.md。

思路

解析

经过普通队列输出数据后,发现普通队列不正正确

发现由 $4$ 生成的 $9$ 比较 $3$ 生成的 $10$ 要大,根据做题目的经验,这个题目肯定有数学规律, 进一步输出数据,找规律.

根据数据范围,知道,最终的代码一定是 $O(n)$ 的, $O(nlogn)$ 都不行,所以不能使用优先队列,这暗示我们,产生的数据可以按某种方式有序,不需要进行比较.

每一次产生的两个数 $a < b$ 一定成立
每一次都应该由最小的数首开两个新的数 $a,b$

每一次产生的两新的数,和原来的已经产生的数,有什么关系,

使用数学归纳法证明

设 $x \geqslant a,y \geqslant b$ ,且取 $t = min(a,b)$ ,且 $t \leqslant z$ , $z$ 是生成 $x,y$ 的元素

x = 2 \times z +1 \\ y = 3 \times z +1 \\

现在取 $t$ ,得到 $A = 2 \times t + 1, B = 3\times t +1$ ,显然

A \leqslant x \Rightarrow 2\times t + 1 \leqslant 2\times z +1 \\ B \leqslant y \Rightarrow 3\times t + 1 \leqslant 3\times z +1

显然成立

这就说明如果原来的双队列成立(单个队列都是单调的),则从取双队列头的最小值,产生新的值,然后把值各自加入到队列尾部, 得到的新的双队列也成立.

错误的代码

使用优先队列,超时.

代码

cpp

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#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e5+5;

template<typename T = int,int siz = maxn>
struct myqueue{
    T a[siz+5];
    //tail 指向最后一个元素后面一个位置
    //head 指向第一个元素
    int head = 0,tail=0; 

    void clear() { head =tail = 0;}

    void push(T b) { a[tail++] = b;}

    void pop(){head++;}
    void pop_back(){tail--;}

    T front() { return a[head];}
    T back() { return a[tail-1];}

    bool empty() { return head == tail;}

    int size() { return tail-head;}
};

typedef  long long ll;
myqueue<ll> a;
myqueue<ll> b;
int s,n;


int main() {
    while (cin >> s >> n) {
        //特别的处理第一个元素.
        int cnt = 1;
        a.clear();
        b.clear();
        ll t = s;
        if( cnt >= n) {
            cout << t <<endl;
            continue;
        }
        a.push(2*t+1);
        b.push(3*t+1);
        int pre = t;
        while(1) {
            ll t1 = 0x7f7f7f7f7f7f7f7f;
            ll t2 = 0x7f7f7f7f7f7f7f7f;

            if( !a.empty()) t1=a.front();
            if( !b.empty()) t2=b.front();

            if( t1 <= t2) {
                t = t1;
                a.pop();
            }
            else
            {
                t= t2;
                b.pop();
            }
            //如果和上一个取的数一样大,
            // 根据集合中元素不能一样,所以这个不能计算
            if( t == pre) continue;
            cnt++;
            pre = t;
            // cout << cnt << " " << t<< "\n";
            if( cnt == n) {
                cout << t << endl;
                break;
            }
            if(a.empty() ||2*t+1 != a.back() )
                a.push(2*t+1);
            if(b.empty() ||3*t+1 != b.back() )
                b.push(3*t+1);
        }
    }
    int m = a.tail;
    if( m < b.tail)
        m = b.tail;
        
    // for(int i =0;i<m;i++)
    // {
    //     cout << a.a[i] << " " << b.a[i] << endl;
    // }

    return 0;
}

目录

题意

思路

解析

错误的代码

代码

复杂度

总结