头像

垫底抽风

yxc的忠实粉丝


访客:4923

离线:11小时前



$$\displaystyle x\ XOR\ x ^ 2 = x ^ 3(x \in Z), 求证:该方程唯一解为 x = 0$$




题目描述

一列火车 $n$ 节车厢,依次编号为 $1, 2, 3, \cdots , n$。

每节车厢有两种运动方式,进栈出栈,问 $n$ 节车厢出栈的可能排列方式有多少种。

输入格式

输入一个整数 $n$,代表火车的车厢数。

输出格式

输出一个整数 $s$ 表示 $n$ 节车厢出栈的可能排列方式数量。

数据范围

$1 \leq n \leq 60000$

输入样例:

3

输出样例:

5

算法

(暴力 卡特兰数 + 压位高精) $O(n^2)$

做这道题之前,建议先做一下 AcWing 129. 火车进栈AcWing 889.满足条件的$01$序列 这两题。

看到数据范围,知道这题肯定是不能用暴力来做。
那么我们就需要先转化一下题目意思。

首先规定 $1$ 表示栈中进入一节车厢,$0$ 表示栈中弹出一节车厢,那么每种火车进出栈方案都能用一串 $01$ 序列来表示。
由于每节车厢都要进栈一次出栈一次,所以每种方案所对应的 $01$ 序列的长度都是 $2n$。
那么火车进出栈方案的总数量就可以看成是所有合法的 $01$ 串的个数。

那咋算是合法的嘞?
要有车厢出栈,那么栈中就必须要有车厢。
在 $01$ 序列中,就对应了在任意位置,其前面的 $1$ 的个数大于等于其前面 $0$ 的个数
所以这题就变成了 AcWing 889.满足条件的$01$序列

我们只需求卡特兰数即可。

但高精和卡时让这题恶心了很多。

首先我们要求高精的 $\displaystyle \frac{C _ {2n} ^ n}{n + 1}$,也就是高精的 $\displaystyle \frac{(2n)!}{(n!)(n!)(n + 1)}$
最快的办法是求出这玩意所有的质因数及其次数,然后求所有数乘积即可。
求出它所有的质数的方法可以参考 AcWing 197. 阶乘分解 这题的做法。
我这里是直接在筛质数的时候处理,更好写一些,且效率更高。
然后在乘所有数的乘积的时候,注意到每个数字的次数都不会太多,可以先求出 $primes[i] ^ {primes[i]的次数}\ \ $ 的结果,再乘到答案里面去,效率更高。

看y总视频里面调代码好辛苦,这里给出一份跑的超快的代码,最快一次 $315ms$ 跑完所有数据

C++ 代码

#include <stdio.h>

const int N = 11311;
const int base = 1e9;  // 压 9 位
const int basebit = 9;

int n;
int sum[N];             // 存筛出的质数及其次数的结果
long long res[4500];    // 存答案,res[0] 存 res 的位数
int primes[N], cnt;     // 存筛的质数
bool st[120001];        // 筛质数用的 bool 数组

inline void init()      // 线性筛质数 + 求分解质因数的结果
{
    for (register int i = 2; i <= n << 1; i ++ )
    {
        if (!st[i])     // 如果 st[i] == false,说明该数 i 是质数
        {
            primes[ ++ cnt] = i; // 先把它存进 primes
            for (register int j = (n << 1) / i; j; j /= i) // 加上 (2n)! 含有 i 的数量。
                sum[cnt] += j;
            for (register int j = n / i; j; j /= i) // 减去 (n!)^2 含有 i 的数量。
                sum[cnt] -= j << 1; // (n!)^2 含有 i 的数量即两倍的 n! 所含有的 i 的数量,所以只用处理 n!,然后减去其所含数量两倍即可
            for (register int j = n + 1; j % i == 0; j /= i) // 减去 n + 1 含有 i 的数量
                sum[cnt] -- ;
        }
        for (register int j = 1; primes[j] <= (n << 1) / i; j ++ ) // 线性筛的板子
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break ;
        }
    }
}

inline int qmi(int a, int b) // 快速幂(其实并没有卵用。。大部分调用都会进到那个 if (b == 1) 里面去。。所以加了个特判,效率会更高一点)
{
    if (b == 1) return a;
    int res = 1;
    for (; b; a *= a, b >>= 1)
        if (b & 1) res *= a;
    return res;
}

inline void multi(int b)     // 将 res 乘 b
{
    register long long t = 0;
    for (register int i = 1; i <= res[0]; i ++ )
    {
        res[i] = res[i] * b + t;
        t = res[i] / base;
        res[i] %= base;
    }
    while (t) res[ ++ res[0]] = t % base, t /= base;
}

void print(int x, int i = basebit) // 快速输出 9 位
{
    if (!i) return ;
    print(x / 10, i - 1);
    putchar(x % 10 ^ 48);
}

int main()
{
    scanf("%d",&n);
    init();              // 初始化 primes + 初始化 sum
    res[0] = res[1] = 1; // 出初始化 res,res 的长度制为 1,res 的值制成 1
    for (register int i = 1; i <= cnt; i ++ ) // 枚举一遍分解出来的所有的质数
        if (sum[i]) multi(qmi(primes[i], sum[i]));
    printf("%lld", res[res[0]]);              // 第一位不用输出 9 位
    if (res[0] > 1)      // 如果 res 的位数大于一的话,那么输出后面的
        for (register int i = res[0] - 1; i; i -- )
            print(res[i]);
    return 0;
}


新鲜事 原文

吐槽页面不能刷屏了,想刷屏的可以在这里刷屏鸭(逃
图片



虽然位运算一共就那么几种,但是学的时候的确不是很好学(至少对我来说,神犇跳过)

$C++$ 几种常用位运算简介

  1. 按位与 a & b
    法则:两者相同位都为 $1$,则结果中该位为 $1$;否则结果中该位为 $0$

    • 例:12 & 6 = 4
      12:1 1 0 0
      $\ \ $6:0 1 1 0
      $\ \ $4:0 1 0 0
  2. 按位或 a | b
    法则:两者相同位中有一个为 $1$,则结果中该位为 $1$;否则结果中该位为 $0$

    • 例:12 & 6 = 14
      12:1 1 0 0
      $\ \ $6:0 1 1 0
      14:1 1 1 0
  3. 按位亦或 a ^ b
    法则:两者相同位的值若不同,则结果中该位为 $1$;否则结果中该位为 $0$

    • 例:12 ^ 6 = 10
      12:1 1 0 0
      $\ \ $6:0 1 1 0
      10:1 0 1 0
  4. 按位取反 ~a
    法则:该数中 $0$ 的位置变为 $1$;$1$ 的位置变为 $0$
    (这个涉及二进制补码,先不例)

  5. 按位左移 a << b
    法则:将该数 $a$ 左移 $b$ 位,正数左移后为正数,负数左移后为负数

    • 例:3 << 2 = 12
      $\ \ $3:0 0 1 1
      12:1 1 0 0
      $a << b = a \times 2 ^ b$
  6. 按位右移 a >> b
    法则:将该数 $a$ 右移 $b$ 位,正数右移后为正数,负数右移后为负数。不论正负,都下取整

    • 例:13 >> 2 = 3
      13:1 1 0 1
      $\ \ $3:0 0 1 1
      $a >> b = a / 2 ^ b$
  7. !a
    法则:该数是 $0$ 则为 $1$;否则为 $0$

    • 例:!0 = 1
      $\ \ \ \ \ \ \ $!1 = 0
      $\ \ \ \ \ \ \ $!2 = 0

各种运算符优先级

-,!,~ $>$ *,/,% $>$ >>,<< $>$ >,<,>=,<= $>$ ==,!= $>$ & $>$ ^ $>$ | $>$ && $>$ || $>$ 问号表达式 $>$ 赋值语句

负数表示

用补码表示负数:

  • $\because -1 = 0 - 1$
    $\ \ \ \ \ \ \ 0 = 000 \cdots 00$
    $\ \ \ \ \ \ \ 1 = 000 \cdots 01$
    $\therefore -1 = 111 \cdots 11$

同理:

  • $-2 = 111 \cdots 110$
    $-3 = 111 \cdots 101$
    $-4 = 111 \cdots 100$
    $\cdots$
    -x = ~x + 1
算补上上面那个例了8

八进制与十六进制

八进制数每一位用 $0 \sim 7$ 表示,每一位占二进制中的 $3$ 位
在 $C++$ 中,前面加 0 表示八进制数,例:

printf("%d\n", 015);
// 输出:13

十六进制数每一位用 $0 \sim f$ 表示($a \sim f$ 分别表示 $10 \sim 15$),每一位占二进制中的 $4$ 位
在 $C++$ 中,前面加 0x 表示十六进制数,例:

printf("%d\n", 0xd);
// 输出:13

字节

一个字节为 $8$ 位二进制数,也是$2$ 位十六进制数,即 $00000000 \sim 11111111$
一个 int 占 $4$ 个字节,即 $32$ 位二进制数
一个 long long 占 $8$ 个字节,即 $64$ 位二进制数
memset 按字节赋值,故当 fint 型数组时, memset(f, 0x3f, sizeof f) 是将 f 赋值为 0x3f3f3f3f

位运算常用技巧

(多用于状压 $DP$)

将 $x$ 第 $i$ 位取反:x ^= 1 << i
将 $x$ 第 $i$ 位制成 $1$:x |= 1 << i
将 $x$ 第 $i$ 位制成 $0$:x &= -1 ^ 1 << ix &= ~(1 << i)
取 $x$ 对 $2$ 取模的结果:x & 1
取 $x$ 的第 $i$ 位是否为 $1$:x & 1 << ix >> i & 1
取 $x$ 的最后一位:x & -x
取 $x$ 的绝对值:(x ^ x >> 31) - (x >> 31) (int 型)
判断 $x$ 是否不为 $2$ 的整次方幂:x & x - 1
判断 $a$ 是否不等于 $b$:a != b,a - b,a ^ b
判断 $x$ 是否不等于 $-1$:x != -1,x ^ -1,x + 1,~x

应用

交换两个数字

void swap(int &a, int &b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

求二进制中数字 $1$ 的个数

int count(int x)
{
    int res = 0;
    while (x) x &= x - 1, res ++ ;
    return res;
}

求 $\log _ 2 x$

  • 暴力 $O(\log x)$
int log_2(int x)
{
    int res = 0;
    while (x >> 1) res ++ , x >>= 1;
    return res;
}
  • 二分 $O(\log\log x)$
int log_2(int x)
{
    int l = 0, r = 31, mid;
    while (l < r)
    {
        mid = l + r + 1 >> 1;
        if (x >> mid) l = mid;
        else    r = mid - 1;
    }
}
  • 位运算(二分展开)$O(\log\log x)$
int log_2(int x)
{
    int res = 0;
    if (x & 0xffff0000) res += 16, x >>= 16;
    if (x & 0xff00) res += 8, x >>= 8;
    if (x & 0xf0) res += 4, x >>= 4;
    if (x & 0xc) res += 2, x >>= 2;
    if (x & 2) res ++ ;
    return res;
}

求一遍从 $1$ 到 $10 ^ 7$ 的 $\log _ 2 x$,暴力要 $470ms$,二分要 $177ms$,位运算要 $70ms$,<cmath> 库的那个要 $307ms$当然人家那是带精度的咱不能跟它比

预处理 $1 \sim n$ 中所有数 $\log$ 后的结果 $O(n)$

int log_2[N];   // 存 log2(i) 的结果
void init(int n)
{
    for (int i = 0; 1 << i <= n; i ++ )
        log_2[1 << i] = i;
    for (int i = 1; i <= n; i ++ )
        if (!log_2[i])
            log_2[i] = log_2[i - 1];
}

快读优化

inline int read()
{
   int x = 0; bool f = false; char ch = getchar();
   while (ch < 48 || ch > 57) {f |= (ch == 45); ch = getchar();}
   while (ch > 47 && ch < 58) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
   return f ? ~x + 1 : x;
}

龟速加

int add(int a, int b)
{
    while (b)
    {
        int x = a ^ b;
        b = (a & b) << 1;
        a = x;
    }
    return a;
}

例题

状态压缩$DP$$\ \ \ \ $AcWing 91. 最短$Hamilton$路径$\ \ \ \ $题解
位运算性质$\ \ \ \ $AcWing 998. 起床困难综合征$\ \ \ \ $题解
二进制枚举$\ \ \ \ $AcWing 116. 飞行员兄弟$\ \ \ \ $题解(挂份秦大佬的先)




题目描述

给定一个整数 $M$,对于任意一个整数集合 $S$,定义“校验值”如下:

从集合 $S$ 中取出 $M$ 对数(即 $2 \times M$ 个数,不能重复使用集合中的数,如果 $S$ 中的整数不够 $M$ 对,则取到不能取为止),使得“每对数的差的平方”之和最大,这个最大值就称为集合 $S$ 的“校验值”。

现在给定一个长度为 $N$ 的数列 $A$ 以及一个整数 $T$。

我们要把 $A$ 分成若干段,使得每一段的“校验值”都不超过 $T$。

求最少需要分成几段。

输入格式

第一行输入整数 $K$,代表有 $K$ 组测试数据。

对于每组测试数据,第一行包含三个整数 $N,M,T$ 。

第二行包含 $N$ 个整数,表示数列 $A _ 1, A _ 2 \cdots A _ N$。

输出格式

对于每组测试数据,输出其答案,每个答案占一行。

数据范围

$1 \leq K \leq 12,$
$1 \leq N,M \leq 500000,$
$0 \leq T \leq 10 ^ {18},$
$0 \leq A _ i \leq 2 ^ {20}$

输入样例:

2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9

输出样例:

2
1

算法1

(贪心 $+$ 二分) $\mathcal O(n \log ^ 2 n)$

首先,根据校验值的定义,要快速求出校验值,首先想到的办法肯定是爆搜贪心。

结论:将 $S$ 排序,每次取到 $S$ 中的最大值和最小值,最后计算出来的结果即为 $S$ 的校验值

证明:
这里只证明三个数的情况,多个数字同理。
设这三个数分别为 $A, B, C, D$,且 $0 < A \leq B \leq C \leq D$
那么只要证明 $(D - A) ^ 2 + (C - B) ^ 2 \geq (C - A) ^ 2 + (D - B) ^ 2$ 即可
$\because A \leq B$ 且 $C \leq D$
$\therefore (B - A) D \geq (B - A) C$
$\therefore BD - AD \geq BC - AC$
$\therefore BD + AC \geq BC + AD$
$\therefore -2BC - 2AD \geq -2BD - 2AC$
$\therefore A ^ 2 + B ^ 2 + C ^ 2 + D ^ 2 - 2 BC - 2 AD \geq A ^ 2 + B ^ 2 + C ^ 2 + D ^ 2 - 2 BD - 2 AC$
$\therefore (D - A)^ 2 + (C - B) ^ 2 \geq (C - A) ^ 2 + (D - B) ^ 2$
同理可证 $(D - A) ^ 2 + (C - B) ^ 2 \geq (B - A) ^ 2 + (D - C) ^ 2$

那么可以求出每段区间的校验值之后,如何找到一种划分区间最少的划分方案呢?
因为我们要划分的区间最少,所以要每次划分的区间尽可能长。
那么我们就可以每次划分区间的时候,用二分求出当前能划分的最长的区间。

时间复杂度

每次二分的check中,要拍一遍序,时间复杂度为 $\mathcal O(len \log len)$,其中 $len$ 是当前划分的区间长度。
假设第 $i$ 次二分划分的区间长度为 $len _ i$,一共划分了 $k$ 次,那么有 $len _ 1 + len _ 2 + \cdots + len _ k = n$
所以 $len _ 1 \log len _ 1 + len _ 2 \log len _ 2 + \cdots + len _ k \log len _ k \leq n \log n$
那么再算上二分要跑 $log n$ 次,总的时间复杂度就是 $\mathcal O(n \log ^ 2 n)$,会 TLE。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 500005;

int n, m;
int ans;              // 存答案
ll T;                 // 题目中的 T
ll w[N], t[N];        // w 是输入的数组,t 是用于求校验值的数组

ll sq(ll x)           // 返回 x 的平方
{
    return x * x;
}

ll get(int l, int r)  // 求原数组区间 [l, r] 的校验值
{
    int k = 0;        // 要先把 w 的 [l, r] 这段复制到 t 中,用 k 记录 t 的长度。
    for (int i = l; i <= r; i ++ ) // 从 l 到 r 枚举一遍,将 w 数组复制到 t 数组中
        t[k ++ ] = w[i];
    sort(t, t + k);   // 将复制过来的数排序
    ll sum = 0;       // 存返回的校验值
    for (int i = 0; i < m && i < k; i ++ , k -- )
        sum += sq(t[i] - t[k - 1]); // 双指针,i 指向当前集合中剩余的最小数,k 指向当前集合中剩余的最大数
    return sum;
}

int main()
{
    int K;            // 测试数据组数
    cin >> K;
    while (K -- )     // 不写奇怪的 for 循环了qwq
    {
        cin >> n >> m >> T;
        for (int i = 0; i < n; i ++ ) cin >> w[i];
        ans = 0;      // 答案归零
        int start = 0;    // start 记录当前剩余的区间左端点
        while (start < n) // start < n 说明当前数组还有值,需要继续划分。结束时 start 应等于 n 
        {
            int l = start, r = n, mid; // 二分求出当前能划分的最长的区间
            while (l < r) // 二分板子
            {
                mid = l + r >> 1;
                if (get(start, mid) > T) r = mid;
                else    l = mid + 1;
            }
            start = r;    // 二分完后,r 即当前可划分的最长区间的下一个位置,将 start 制为 r。
            ans ++ ;      // 每次划分完一个区间,ans ++ 
        }
        printf("%d\n", ans);
    }
    return 0;
}

算法2

(倍增) $O(n \log ^ 2 n)$

二分虽然已经是 $\mathcal O(\log n)$ 了,但是常数较大(对于这题来说),因为每次都会跑满 $\log$
一种比较好的优化方式是倍增,每次将当前剩余区间的长度 $\times 2$,大部分情况不会跑满 $\log$
具体做法:(设当前划分区间起点为 $start$)

  1. 让 $len = 1, end = start$
  2. 每次判断区间 $[start, end + len)$ 的校验值是否合法(注意:区间左闭右开)
  3. 如果合法,那么让 $end + len$,然后 $len \times 2$,重复 2
  4. 如果不合法,那么 $len \div 2$。
    • 如果 $len = 0$,那么跳出。
    • 否则重复 2

每次跳出后,由于区间 $[start, end)$ 是左闭右开的,直接让 $start = end$,$ans ++ $ 即可

时间复杂度

虽然是倍增,但时间复杂度和二分一样,都是 $\mathcal O(n \log ^ 2 n)$
但是倍增能过,是因为倍增常数极小,每次可能只找两三次就找到了。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 500005;

int n, m;
int ans;
ll T;
ll w[N], t[N];

ll sq(ll x)
{
    return x * x;
}

ll get(int l, int r)  // 计算原数组左闭右开区间 [l, r) 的校验值
{
    int k = 0;
    for (int i = l; i < r; i ++ )
        t[k ++ ] = w[i];
    sort(t, t + k);
    ll sum = 0;
    for (int i = 0; i < m && i < k; i ++ , k -- )
        sum += sq(t[i] - t[k - 1]);
    return sum;
}

int main()
{
    int K;
    scanf("%d", &K);
    while (K -- )
    {
        scanf("%d %d %lld\n", &n, &m, &T); // 不用 scanf 的话,这么做有一个点会 TLE
        for (int i = 0; i < n; i ++ )
            scanf("%lld", &w[i]);
        ans = 0;
        int start = 0, end = 0;            // start 记录剩余区间开头节点,end 记录当前考虑区间的尾结点(左闭右开)
        while (end < n)
        {
            int len = 1;                   // len 初始化为 1
            while (len)                    // len 为 0 自动跳出
            {
                if (end + len <= n && get(start, end + len) <= T) // 如果说 len + end 还在 n 以内,且区间 [start, end + len) 的校验值不大于 T
                    end += len, len <<= 1; // 那么 end += len,len *= 2
                else    len >>= 1;         // 否则 len /= 2
            }
            start = end;                   // 让 start 指向当前区间末尾结点的下一个位置,由于区间是左闭右开的,所以直接指向 end 就可以了
            ans ++ ;                       // 每次循环都找到了一个区间,所以让 ans ++ 
        }
        printf("%d\n", ans);
    }
    return 0;
}
// 偷个懒,少写点注释 (  ̄▽ ̄)σ

算法3

(倍增 $+$ 归并) $\mathcal O(n \log n)$

上述代码中,在处理 [start, end) 的时候,已经将 [start, end) 排好序了,所以不需要在处理 [start, end + len) 时再排序。
处理 [start, end + len) 时,只需要将 [end, end + len) 排序,然后将 [start, end) 与 [end, end + len) 这两段区间进行归并即可。
详见代码注释。

时间复杂度

假设一共将数组划分成了 $k$ 个区间(这里的区间指的是每次二分里面check的区间总和,并非题目中所指的区间),每个区间的长度分别为 $len _ 1, len _ 2, \cdots, len _ k$。
那么按上述方法只需要将每个区间排序一遍,所以时间复杂度为 $\mathcal O(len _ 1 \log len _ 1 + len _ 2 \log len _ 2 + \cdots + len _ k \log len _ k) = \mathcal O(n \log n)$
加上每次归并的时间复杂度为 $O(n)$,总的时间复杂度为 $\mathcal O(n + n \log n) = \mathcal O(n \log n)$

C++代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 500005;

int n, m;
int ans;
ll T;
ll w[N], t[N];
ll tmp[N];

ll sq(ll x)
{
    return x * x;
}

bool check(int l, int mid, int r)           // 判断区间 [l, r) 是否合法,并将 t 中的 [l, mid) 区间和 [mid, r) 区间合并到 tmp 中
{
    for (int i = mid; i < r; i ++ )         // 将 w 数组的 [l, r) 区间复制到 t 的 [l, r) 区间中
        t[i] = w[i];
    sort(t + mid, t + r);                   // 将 t 的 [mid, r) 排序
    int i = l, j = mid, k = 0;              // 双指针进行区间合并
    while (i != mid && j != r)              // 当 i 不到 mid 且 j 不到 r 时,执行循环
        if (t[i] < t[j])                    // 如果 t[i] 比 t[j] 小,那么将 t[i] 放入 tmp 中
            tmp[k ++ ] = t[i ++ ]; 
        else                                // 否则将 t[j] 放入 tmp 中
            tmp[k ++ ] = t[j ++ ];
    while (i != mid) tmp[k ++ ] = t[i ++ ]; // 处理剩下的元素
    while (j != r) tmp[k ++ ] = t[j ++ ];
    ll sum = 0;                             // 计算校验值
    for (i = 0; i < m && i < k; i ++ , k -- )
        sum += sq(tmp[i] - tmp[k - 1]);
    return sum <= T;                        // 返回当前区间 [l, r) 是否合法
}

int main()
{
    int K;
    scanf("%d", &K);
    while (K -- )
    {
        scanf("%d %d %lld\n", &n, &m, &T);
        for (int i = 0; i < n; i ++ )
            scanf("%lld", &w[i]);
        ans = 0;
        int len;
        int start = 0, end = 0;
        while (end < n)
        {
            len = 1;
            while (len)
            {
                if (end + len <= n && check(start, end, end + len)) // 如果 w 的 [start, end + len) 区间合法
                {
                    end += len, len <<= 1;
                    if (end >= n) break ;               // 一个小剪枝,如果 end >= n,那么直接跳出
                    for (int i = start; i < end; i ++ ) // 在 check 时,已经将 t 数组的 [start, end + len) 这段区间归并在 tmp 中了。现在只需要将 tmp 中的有序数组复制到 t 中即可
                        t[i] = tmp[i - start];          // 复制的时候注意下标变换,tmp 是从 0 开始存的,t 是从 start 开始存的
                }
                else    len >>= 1;
            }
            start = end;
            ans ++ ;
        }
        printf("%d\n", ans);
    }
    return 0;
}


新鲜事 原文

数学渣去世
图片 图片



题目描述

这就不说原题目描述了,又长又不好懂
题意:给定 $n, m$ 以及 $n$ 个数和该数所对应的运算,其中运算有 与、或、异或 三种,问在所有不大于 $m$ 的非负整数中,对给定的 $n$ 个数都按该数所对应的运算运算一遍后,能得到得最大的值是多少。

  • AND 表示按位与,OR 表示按位或,XOR 表示按位异或

输入样例:

3 10
AND 5
OR 6
XOR 7

输出样例:

1

算法

(按位枚举) $\mathcal O(n \log t)$

注意到 按位与、按位或、按位异或 共有的一个性质:每次运算只有关该位上的数,不影响其它位上的数
所以我们可以像最大异或对这题一样,从高位到第位来确定数的每一位。
如果该位可以填 $u$,并且填 $u$ 之后答案的该位是 $1$,那么在该位填 $u$,否则填 $!u$
那么如何判断该位能填几呢?

  • 如果该位填 $1$ 后,所得到的数大于 $m$,那么该位填 $!u$
  • 否则如果该位填 $1$ 后,所得到的数对 $n$ 个数都运算之后,结果小于等于该位填 $0$ 后得到的结果,那么为了让剩下能填的数更大,该位填 $0$
  • 否则该位填 $1$

由于我们只需要得到填出来的数对所有数运算后的结果,而并不需要输出填出来的数,所以在写代码的时候并不需要真正的把数填出来,只需要确定是否能将答案的该位填成 $1$ 即可

时间复杂度

一共要判断 $\log m$ 次,每次判断是 $\mathcal O(n)$ 的,所以总的时间复杂度是 $\mathcal O(n \log m)$

参考文献

C++ 代码

#include <stdio.h>

const int N = 100005;

int n, m;             // n, m 即题目描述中 n, m
int ans;              // ans 存我们能得到的最大的答案
int t[N];             // t 存输入的 $n$ 个数
short op[N];          // op 存 n 个数对应的操作,1 表示按位或,2 表示按位异或,3 表示与
char str[4];          // str 用于读入操作

bool calc(bool x, int j)                         // calc 用于计算 x 经过所有数的第 j 位操作后所得到的结果
{
    for (int i = 0; i < n; i ++ )                // 从 0 到 n 枚举所有读入的数与其对应操作
        if (op[i] == 1) x |= t[i] >> j & 1;      // 如果 op[i] 为 1,说明该数所对应的运算为按位或
        else if (op[i] == 2) x ^= t[i] >> j & 1; // 如果 op[i] 为 2,说明该数所对应的运算为按位亦或
        else    x &= t[i] >> j & 1;              // 如果 op[i] 为 3,说明该数所对应的运算为按位与
    return x;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        scanf("\n%s %d", str, t + i);
        if (*str == 'O') op[i] = 1;              // 如果该操作为 OR ,那么 op[i] 制为 1
        else if (*str == 'X') op[i] = 2;         // 如果该操作为 XOR,那么 op[i] 制为 2
        else    op[i] = 3;                       // 否则该操作为 AND,那么 op[i] 制为 3
    }

    for (int i = 29; ~i; i -- )                  // 因为本题中 m 最大是 10 ^ 9,log2(10 ^ 9) = 3log2(10 ^ 3) < 3 * 10 = 30,所以每次 i 从 29 往后枚举就可以了
        if (m >> i)                              // 如果说 m 右移 i 位仍不为 0,说明该位填 1 后小于 m,要看填完后对答案的影响来填
        {
            bool x = calc(0, i), y = calc(1, i); // 先分别处理出该位填 0 的结果和该位填易得结果
            if (x >= y) ans|= x << i;            // 如果该位填 1 并不比该位填 0 更优,那么为了让剩下能填的数更大,在该位填 0
            else ans |= y << i, m -= 1 << i;     // 否则在该位填 1,填完后让 m 减去该位填 1 的结果,这样在后面填数的时候只用考虑是否大于 m 就可以了
        }
        else ans |= calc(0, i) << i;             // 否则该位只能填 0,

    printf("%d\n", ans);
    return 0;
}



题目描述

给定一张 $n$ 个点的带权无向图,点从 $0 \sim n-1$ 标号,求起点 $0$ 到终点 $n-1$ 的最短 $Hamilton$ 路径。 $Hamilton$ 路径的定义是从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 $n$。

接下来 $n$ 行每行 $n$ 个整数,其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离(记为 $a[i, j]$)。

对于任意的 $x, y, z$,数据保证 $a[x, x] = 0$,$a[x, y] = a[y, x]$ 并且 $a[x, y] + a[y, z] >= a[x, z]$。

输出格式

输出一个整数,表示最短 $Hamilton$ 路径的长度。

数据范围

$1 \leq n \leq 20$
$0 \leq a[i, j] \leq 10 ^ 7$

输入样例:

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例:

18

算法

(状态压缩DP) $O(n^2)$

首先想下暴力算法,这里直接给出一个例子。
比如数据有 $5$ 个点,分别是 $0, 1, 2, 3, 4$
那么在爆搜的时候,会枚举一下六种路径情况(只算对答案有贡献的情况的话):

  • $case\ 1:\ 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4$
  • $case\ 2:\ 0 \rightarrow 1 \rightarrow 3 \rightarrow 2 \rightarrow 4$
  • $case\ 3:\ 0 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$
  • $case\ 4:\ 0 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 4$
  • $case\ 5:\ 0 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$
  • $case\ 6:\ 0 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$

那么观察一下 $case\ 1$ 和 $case\ 3$,可以发现,我们在计算从点 $0$ 到点 $3$ 的路径时,其实并不关心这两中路径经过的点的顺序,而是只需要这两种路径中的较小值,因为只有较小值可能对答案有贡献。
所以,我们在枚举路径的时候,只需要记录两个属性:当前经过的点集,当前到了哪个点。
而当前经过的点集不是一个数。观察到数据中点数不会超过 $20$,我们可以用一个二进制数表示当前经过的点集。其中第 $i$ 位为 1/0 表示是/否经过了点 $i$。
然后用闫式 dp 分析法考虑 dp
状态表示:$f[state][j]$。其中 $state$ 是一个二进制数,表示点集的方法如上述所示。

  • 集合:经过的点集为 $state$,且当前到了点 $j$ 上的所有路径。
  • 属性:路径总长度的最小值

状态计算:假设当前要从点 $k$ 转移到 $j$。那么根据 $Hamilton$ 路径的定义,走到点 $k$ 的路径就不能经过点 $j$,所以就可以推出状态转移方程f[state][j] = min{f[state ^ (1 << j)][k] + w[k][j]}
其中w[k][j]表示从点 $k$ 到点 $j$ 的距离,^表示异或运算。
state ^ (1 << j)是将 $state$ 的第 $j$ 位改变后的值,即

  • 如果 $state$ 的第 $j$ 位是 $1$ 那么将其改为 $0$
  • 否则将 $state$ 的第 $j$ 位改为 $1$

由于到达点 $j$ 的路径一定经过点 $j$,也就是说当 $state$ 的第 $j$ 位为 $1$ 的时候,$f[state][j]$ 才可以被转移,所以 state ^ (1 << j) 其实就是将 $state$ 的第 $j$ 位改为 $0$,这样也就符合了 走到点 $k$ 的路径就不能经过点 $j$ 这个条件。

所有状态转移完后,根据 $f[state][j]$ 的定义,要输出 $f[111\cdots 11 ((n-1)个1)][n - 1]$。
那么怎么构造 n - 1 个 1 呢,可以直接通过 1 << n 求出 $100 \cdots 0((n - 1)个0)$,然后减一即可。

时间复杂度

枚举所有 $state$ 的时间复杂度是 $\mathcal O(2 ^ n)$
枚举 $j$ 的时间复杂读是 $\mathcal O(n)$
枚举 $k$ 的时间复杂度是 $\mathcal O(n)$
所以总的时间复杂度是 $\mathcal O(n ^ 2 2 ^ n)$

参考文献

C++ 代码

#include <stdio.h>
#include <string.h>

const int N = 20;
const int M = 1 << 20; // 一共最多有 20 个 1 种状态

int n;
int w[N][N];           // 存每两个点之间的距离
int f[M][N];           // 上述 f[state][j]

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &w[i][j]);
    memset(f, 0x3f, sizeof f); // 由于要求最小值,所以这里将 f 初始化为正无穷会更好处理一些
    f[1][0] = 0;               // 因为题目要求从点 0 出发,所以这里要将 经过点集为 1,当前到达第 0 个点 的最短路径初始化为 0
    for (int state = 0; state < 1 << n; state ++ )   // 从 0 到 111...11 枚举所有 state
        if (state & 1)                               // state 必须要包含起点 1
            for (int j = 0; j < n; j ++ )            // 枚举所有 state 到达的点
                if (state >> j & 1)                  // 如果当前点集包含点 j,那么进行状态转移
                    for (int k = 0; k < n; k ++ )    // 枚举所有 k
                        if (state ^ 1 << j >> k & 1) // 如果从当前状态经过点集 state 中,去掉点 j 后,state 仍然包含点 k,那么才能从点 k 转移到点 j。当然这个 if 也可以不加,因为如果 state 去掉第 j 个点后,state 不包含点 k 了,那么 f[state ^ 1 << j][k] 必然为正无穷,也就必然不会更新 f[state][j],所以去掉也可以 AC。
                            if (f[state ^ 1 << j][k] + w[k][j] < f[state][j]) // 由于 >> 和 << 的优先级要比 ^ 的优先级高,所以这里可以将 state ^ (1 << j) 去掉括号。
                                f[state][j] = f[state ^ 1 << j][k] + w[k][j];
    printf("%d\n", f[(1 << n) - 1][n - 1]);        // 最后输出 f[111...11][n-1]
    return 0;
}



如题



活动打卡代码 AcWing 106. 动态中位数

快速选择$\ \ \ 47$行$\ \ \ 105ms$

#include <stdio.h>

typedef long long ll;

const int N=10005;

int test,n;
int a[N];
ll ans[N>>1],size;

template<typename T>
T quick_search(T *begin,T *end,int k)
{
    if(begin==end-1)return *begin;
    T pivot=*(begin+(end-begin>>1));
    T *i=begin-1,*j=end;
    while(i!=j)
    {
        while(i!=j&&*++i<pivot);
        while(i!=j&&*--j>pivot);
        if(i!=j)*i^=*j,*j^=*i,*i^=*j;
    }
    if(k<=j-begin)return quick_search(begin,j,k);
    else    return quick_search(j,end,k-(j-begin));
}

int main()
{
    int T;
    for(scanf("%d",&T);T--;putchar('\n'))
    {
        size=0;
        scanf("%d%d",&test,&n);
        printf("%d %d\n",test,n+1>>1);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
            if(i&1)ans[size++]=quick_search(a+1,a+i+1,i+1>>1);
        }
        for(int i=0;i<size;i++)
        {
            if(i&&i%10==0)putchar('\n');
            printf("%d ",ans[i]);
        }
    }
    return 0;
}

对顶堆$\ \ \ 148$行$\ \ \ 5ms$

#include <stdio.h>

typedef long long ll;

const int N=10005;

int test,n;
ll heap1[N],size_heap1; // 大根堆
ll heap2[N],size_heap2; // 小根堆
ll ans[N],size_ans;

void down_heap1(int u)
{
    int t=u;
    if(u<<1<=size_heap1&&heap1[t]<heap1[u<<1])t=u<<1;
    if((u<<1|1)<=size_heap1&&heap1[t]<heap1[u<<1|1])t=u<<1|1;
    if(u!=t)
    {
        heap1[u]^=heap1[t];
        heap1[t]^=heap1[u];
        heap1[u]^=heap1[t];
        down_heap1(t);
    }
}

void up_heap1(int u)
{
    while(u>>1&&heap1[u]>heap1[u>>1])
    {
        heap1[u]^=heap1[u>>1];
        heap1[u>>1]^=heap1[u];
        heap1[u]^=heap1[u>>1];
        u>>=1;
    }
}

void insert_heap1(int x)
{
    heap1[++size_heap1]=x;
    up_heap1(size_heap1);
}

void erase_heap1(int u)
{
    if(u!=size_heap1)
    {
        heap1[u]^=heap1[size_heap1];
        heap1[size_heap1]^=heap1[u];
        heap1[u]^=heap1[size_heap1];
    }
    size_heap1--;
    down_heap1(u);
    up_heap1(u);
}

void down_heap2(int u)
{
    int t=u;
    if(u<<1<=size_heap2&&heap2[u<<1]<heap2[t])t=u<<1;
    if((u<<1|1)<=size_heap2&&heap2[u<<1|1]<heap2[t])t=u<<1|1;
    if(t!=u)
    {
        heap2[u]^=heap2[t];
        heap2[t]^=heap2[u];
        heap2[u]^=heap2[t];
        down_heap2(t);
    }
}

void up_heap2(int u)
{
    while(u>>1&&heap2[u>>1]>heap2[u])
    {
        heap2[u]^=heap2[u>>1];
        heap2[u>>1]^=heap2[u];
        heap2[u]^=heap2[u>>1];
        u>>=1;
    }
}

void insert_heap2(int x)
{
    heap2[++size_heap2]=x;
    up_heap2(size_heap2);
}

void erase_heap2(int u)
{
    if(u!=size_heap2)
    {
        heap2[u]^=heap2[size_heap2];
        heap2[size_heap2]^=heap2[u];
        heap2[u]^=heap2[size_heap2];
    }
    size_heap2--;
    down_heap2(u);
    up_heap2(u);
}

int main()
{
    int T;
    for(scanf("%d",&T);T--;putchar('\n'))
    {
        size_ans=0;
        size_heap1=0;
        size_heap2=0;
        scanf("%d %d",&test,&n);
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            if(i&1)
                if(x<=heap1[1])
                {
                    insert_heap1(x);
                    ans[size_ans++]=heap1[1];
                }
                else
                {
                    insert_heap2(x);
                    ans[size_ans++]=heap2[1];
                }
            else
            {
                if(size_heap1>size_heap2)insert_heap1(x);
                else    insert_heap2(x);
                if(size_heap1>size_heap2)
                {
                    insert_heap2(heap1[1]);
                    erase_heap1(1);
                }
                else if(size_heap1<size_heap2)
                {
                    insert_heap1(heap2[1]);
                    erase_heap2(1);
                }
            }
        }
        printf("%d %d\n",test,size_ans);
        for(int i=0;i<size_ans;i++)
        {
            if(i&&i%10==0)putchar('\n');
            printf("%d ",ans[i]);
        }
    }
    return 0;
}

线段树$\ \ \ 135$行$\ \ \ 17ms$

#include <stdio.h>

typedef long long ll;

const int N=10005;
const int M=40005;

int test,n;
struct point
{
    int l,r;
    ll sum;
}tr[M];
ll alls[N],size_alls;
ll ans[N],size_ans;
ll a[N];

template<typename T>
void sort(T *begin,T *end)
{
    if(begin==end-1)return;
    T pivot=*(begin+(end-begin>>1));
    T *i=begin-1,*j=end;
    while(i!=j)
    {
        while(i!=j&&*++i<pivot);
        while(i!=j&&*--j>pivot);
        if(i!=j)*i^=*j,*j^=*i,*i^=*j;
    }
    sort(begin,j),sort(j,end);
}

template<typename T>
int unique(T *begin,T *end)
{
    T *pivot1,*pivot2;
    pivot1=pivot2=begin;
    while(pivot1!=end)
    {
        while(pivot1!=end&&*pivot1==*pivot2)pivot1++;
        if(pivot1!=end)*++pivot2=*pivot1;
    }
    return pivot2-begin+1;
}

int find(int x)
{
    int l=1,r=size_alls;
    while(l<r)
    {
        int mid=l+r>>1;
        if(alls[mid]>=x)r=mid;
        else    l=mid+1;
    }
    return r;
}

void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r;
    tr[u].sum=0;
    if(l==r)return;
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}

void modify(int u,int x,int c)
{
    if(tr[u].l==tr[u].r)tr[u].sum+=c;
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid)modify(u<<1,x,c);
        else    modify(u<<1|1,x,c);
        pushup(u);
    }
}

ll query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
    ll sum=0,mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)sum+=query(u<<1,l,r);
    if(mid<r)sum+=query(u<<1|1,l,r);
    return sum;
}

int get_kth(int k)
{
    int l=1,r=size_alls;
    while(l<r)
    {
        int mid=l+r>>1;
        if(query(1,1,mid)>=k)r=mid;
        else    l=mid+1;
    }
    return alls[r];
}

int main()
{
    int T;
    for(scanf("%d",&T);T--;putchar('\n'))
    {
        size_alls=0;
        size_ans=0;
        scanf("%d%d",&test,&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",a+i);
            alls[++size_alls]=a[i];
        }
        sort(alls+1,alls+size_alls+1);
        size_alls=unique(alls+1,alls+size_alls+1);
        build(1,1,n);
        for(int i=1;i<=n;i++)
        {
            modify(1,find(a[i]),1);
            if(i&1)ans[size_ans++]=get_kth(i+1>>1);
        }
        printf("%d %d\n",test,size_ans);
        for(int i=0;i<size_ans;i++)
        {
            if(i&&i%10==0)putchar('\n');
            printf("%d ",ans[i]);
        }
    }
    return 0;
}

线段树$(lazytag)\ \ \ 153$行$\ \ \ 27ms$

#include <stdio.h>

typedef long long ll;

const int N=10005;
const int M=40005;

int test,n;
struct point
{
    int l,r;
    ll sum;
    ll lazytag;
}tr[M];
ll alls[N],size_alls;
ll ans[N],size_ans;
ll a[N];

template<typename T>
void sort(T *begin,T *end)
{
    if(begin==end-1)return;
    T pivot=*(begin+(end-begin>>1));
    T *i=begin-1,*j=end;
    while(i!=j)
    {
        while(i!=j&&*++i<pivot);
        while(i!=j&&*--j>pivot);
        if(i!=j)*i^=*j,*j^=*i,*i^=*j;
    }
    sort(begin,j),sort(j,end);
}

template<typename T>
int unique(T *begin,T *end)
{
    T *pivot1,*pivot2;
    pivot1=pivot2=begin;
    while(pivot1!=end)
    {
        while(pivot1!=end&&*pivot1==*pivot2)pivot1++;
        if(pivot1!=end)*++pivot2=*pivot1;
    }
    return pivot2-begin+1;
}

int find(int x)
{
    int l=1,r=size_alls;
    while(l<r)
    {
        int mid=l+r>>1;
        if(alls[mid]>=x)r=mid;
        else    l=mid+1;
    }
    return r;
}

void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u)
{
    if(tr[u].lazytag)
    {
        tr[u<<1].lazytag+=tr[u].lazytag;
        tr[u<<1|1].lazytag+=tr[u].lazytag;
        tr[u<<1].sum+=tr[u].lazytag*(tr[u<<1].r-tr[u<<1].l+1);
        tr[u<<1|1].sum+=tr[u].lazytag*(tr[u<<1|1].r-tr[u<<1|1].l+1);
        tr[u].lazytag=0;
    }
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r;
    tr[u].sum=0;
    tr[u].lazytag=0;
    if(l==r)return;
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}

void modify(int u,int l,int r,ll c)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        tr[u].sum+=c*(tr[u].r-tr[u].l+1);
        tr[u].lazytag+=c;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)modify(u<<1,l,r,c);
    if(mid<r)modify(u<<1|1,l,r,c);
    pushup(u);
}

ll query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
    pushdown(u);
    ll sum=0,mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)sum+=query(u<<1,l,r);
    if(mid<r)sum+=query(u<<1|1,l,r);
    return sum;
}

int get_kth(int k)
{
    int l=1,r=size_alls;
    while(l<r)
    {
        int mid=l+r>>1;
        if(query(1,mid,mid)>=k)r=mid;
        else    l=mid+1;
    }
    return alls[r];
}

int main()
{
    int T;
    for(scanf("%d",&T);T--;putchar('\n'))
    {
        size_alls=0;
        size_ans=0;
        scanf("%d%d",&test,&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",a+i);
            alls[++size_alls]=a[i];
        }
        sort(alls+1,alls+size_alls+1);
        size_alls=unique(alls+1,alls+size_alls+1);
        build(1,1,n);
        for(int i=1;i<=n;i++)
        {
            modify(1,find(a[i]),n,1);
            if(i&1)ans[size_ans++]=get_kth(i+1>>1);
        }
        printf("%d %d\n",test,size_ans);
        for(int i=0;i<size_ans;i++)
        {
            if(i&&i%10==0)putchar('\n');
            printf("%d ",ans[i]);
        }
    }
    return 0;
}

树状数组$\ \ \ 114$行$\ \ \ 9ms$

#include <stdio.h>
#include <string.h>

typedef long long ll;

const int N=10005;

int test,n;
ll a[N];
ll tr[N];
ll alls[N],size_alls;
ll ans[N],size_ans;

template<typename T>
void sort(T *begin,T *end)
{
    if(begin==end-1)return;
    T pivot=*(begin+(end-begin>>1));
    T *i=begin-1,*j=end;
    while(i!=j)
    {
        while(i!=j&&*++i<pivot);
        while(i!=j&&*--j>pivot);
        if(i!=j)*i^=*j,*j^=*i,*i^=*j;
    }
    sort(begin,j),sort(j,end);
}

template<typename T>
int unique(T *begin,T *end)
{
    T *pivot1,*pivot2;
    pivot1=pivot2=begin;
    while(pivot1!=end)
    {
        while(pivot1!=end&&*pivot1==*pivot2)pivot1++;
        if(pivot1!=end)*++pivot2=*pivot1;
    }
    return pivot2-begin+1;
}

template<typename T>
int find(T x)
{
    int l=1,r=size_alls;
    while(l<r)
    {
        int mid=l+r>>1;
        if(alls[mid]>=x)r=mid;
        else    l=mid+1;
    }
    return r;
}

ll lowbit(ll x)
{
    return x&-x;
}

void modify(int x,ll c)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tr[i]+=c;
}

ll query(int x)
{
    ll res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=tr[i];
    return res;
}

int get_kth(ll k)
{
    int l=1,r=size_alls;
    while(l<r)
    {
        int mid=l+r>>1;
        if(query(mid)>=k)r=mid;
        else    l=mid+1;
    }
    return alls[r];
}

int main()
{
    int T;
    for(scanf("%d",&T);T--;putchar('\n'))
    {
        size_alls=size_ans=0;
        memset(tr,0,sizeof tr);
        scanf("%d%d",&test,&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",a+i);
            alls[++size_alls]=a[i];
        }
        sort(alls+1,alls+size_alls+1);
        size_alls=unique(alls+1,alls+size_alls+1);
        for(int i=1;i<=n;i++)
        {
            modify(find(a[i]),1);
            if(i&1)ans[size_ans++]=get_kth(i+1>>1);
        }
        printf("%d %d\n",test,size_ans);
        for(int i=0;i<size_ans;i++)
        {
            if(i&&i%10==0)putchar('\n');
            printf("%d ",ans[i]);
        }
    }
    return 0;
}