T20201117

Posted on Edited on In Word count in article: 571 Reading time ≈ 2 mins.
大东辰的测试

T1

Subtask 1 & 2

\(O(nk)\) 的暴力，对于 \(f_m(n)\) 有： \[ f_m(n)= \begin{cases} f_m(n-1)&m\not\mid n\\ f_m(n-1)+f(\frac mn) &m\mid n \end{cases} \] 然后就暂时没有下文了

T2

还是暴力。。。

T3

做法

考虑分治，就是模拟归并排序的运算流程。

归并的思想，就是不断的把子区间变得有序，然后再来合并这些有序的子区间。

但是，利用归并的思想，还要考虑如何使用区间翻转操作合并两个区间。

然后又是两个子段的合并，所以合并也是一个 \(O(\log n)\) 的时间复杂度。

那么总时间复杂度就应该是 \(O(n\log ^2n)\) 的时间复杂度。

证明

感觉这其实也是算一种构造的，就是构造了一种排序的方式，似乎有些抽象。

考虑对于每一次的合并操作，最坏最坏的情况就是蓝色的操作刚好取到中点，然后合并黑色和绿色的区间递归下去的时候又是刚好取到中点，所以，这样的一个区间的花费就是 \(len\log len\)，所以最后的总花费就应该是： \[ ans=\sum_{i=0}len_i\log len_i \] 然后把那个\(32000\) 带进去算，得到的答案竟然只有 \(3821617\)，真的是远远小于 \(4\times10^6\)，所以这个算法就是对的了。

Code

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n,a[N];
vector < pair <int,int> > ans;

void update (int l, int r) 
{
	if (l == r) return ;
	ans.push_back(make_pair(l, r));
    for (int i = 0; i < (r - l + 1) / 2; i++)
		swap(a[l + i], a[r - i]);
}

void merge(int l0, int r0, int l1, int r1) 
{
    if (l0 > r0 || l1 > r1) return;
    int l = min (r0 - l0, r1 - l1), pt = 0;

    while (pt <= l) 
		if (a[r0 - pt] > a[l1 + pt]) pt++; 
		else break;

    if (!pt) return;

    update(r0 - pt + 1, r0);
    update(l1 , l1 + pt - 1);
    update(r0 - pt + 1, l1 + pt - 1);
    merge(l0, r0 - pt, r0 - pt + 1, r0);
    merge(l1, l1 + pt - 1, l1 + pt, r1); 
}

void solve(int l, int r) 
{
    if (l >= r) return;
    int mid = (l + r) >> 1;
    solve(l, mid); 
	solve(mid + 1, r);
    merge(l, mid, mid + 1, r);
}

int main()
{
	freopen ("rev.in", "r", stdin);
	freopen ("rev.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    solve(1, n);
    printf("%lu\n",ans.size());
    for (int i = 0; i < ans.size(); i++) printf("%d %d\n", ans[i].first, ans[i].second);
}

T4

广义后缀自动机模板题，不说了。。。