T1

题目描述

有$n$个物品编号为$1 - n$，现将其重新排列，但要求相邻两物品的编号差值的绝对值不等于1，按字典序输出所有满足要求的方案

输入

每组输入一个整数n
$1 \leq n \leq 10$

输出

对于每组测试数据：按照字典序输出满足要求的序列，若没有满足的，不用输出任何东西

样例输入

4

样例输出

2 4 1 3
3 1 4 2

算法

($DFS$) $O(n!)$

1. 每层搜索需要记录上一层选择的数，用于判断绝对值不等于1的条件
2. $n = 10$超时了，不要用cout和vector

时间复杂度

迭代$k$次，每层迭代会枚举$O(k)$的点，$k = n, …, 1$

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

const int N = 12;
int n;
bool st[N];
int ret[N], cnt;

void dfs(int u, int last) {
    if (u == n) {
        for (int i = 0; i < cnt; i ++ ) printf("%d ", ret[i]);
        printf("\n");

        return;
    }

    for (int i = 1; i <= n; i ++ )
        if (!st[i] && (last == -1 || abs(i - last) != 1)) {
            st[i] = true;
            ret[cnt ++ ] = i;
            dfs(u + 1, i);
            st[i] = false;
            cnt -- ;
        }
}

int main() {
    cin >> n;
    dfs(0, -1);
    return 0;
}

T2

题目描述

小强有一个长度为$n$的数组$a$和正整数$m$。他想请你帮他计算数组$a$中有多少个连续子区间$[l, r]$，其区间内存在某个元素出现的次数不小于$m$次？例如数组$a = [1, 2, 1, 2, 3]$且$m = 2$，那么区间$[1, 3], [1, 4], [1, 5], [2, 4], [2, 5]$都是满足条件的区间，但区间$[3, 4]$等都是不满足条件的。

输入

第一行输入两个正整数$n$和$m$
第二行输入n个正整数$a[i]$
$1 \leq m \leq n \leq 400000$
$1 \leq a[i] \leq n$

输出

输出一个整数表示答案

样例输入

5 2
1 2 1 2 3

样例输出

5

算法

(双指针) $O(n)$

1. 若$[l, r]$满足条件，则$[k, r], 1 \leq k \leq l$也满足条件，共有$l$个
2. 枚举右区间端点$r$，对于每一个$r$，找到满足条件的最大的$l$，这样枚举出的答案不重不漏
3. $r$向右扩张时，当前区间会一直满足条件
4. $pos[i]$记录值为$i$的数出现过的位置，若枚举到位置$p$时$a[p] = i$且出现次数大于等于$m$，则区间$[pos[i].size() - m, p]$为以右端点$i$结尾的最短的满足条件的区间

时间复杂度

数组只会被枚举一遍，时间复杂度为$O(n)$

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

const int N = 4e5 + 10;

int n, m;
int a[N];
vector<int> pos[N];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    int ret = 0, l = 0, r = 1;

    while (r <= n) {
        int c = a[r];
        pos[c].push_back(r ++ );

        int t = pos[c].size();
        if (t >= m) l = max(l, pos[c][t - m]);

        ret += l;
    }

    cout << ret;

    return 0;
}