第二篇题解

· · 题解

首先，本题题意为一个长度为n的有序序列 数值由一递增到n。

其中有两个操作：

  1. 将所保留元素的第奇数个数删除。

  2. 将所保留元素第偶数个数删除。

    首先想到暴力。

首先把这个问题抽象化，假设有一个长度为n的序列。第一次删除奇数个，剩下所有偶数。第二次删除偶数个剩下所有不是4倍数的偶数。

再思考，能不能把每次操作分成多个部分。 按原始序列来算，第一次每两个数中有一个被删除。 第二次每四个数中有一个被删除。 以此类推，到了第\log{n}次就有两部分，一部分是2^{\log { n }} 一部分是n-2^{\log{n}}。

这就是很明显的递推思想，通过长度为一的序列不断递推到长度为2^{\log{n}}的序列。再根据每一次删去奇数还是偶数判断删去该段的前一个数还是后一个数。 由长度为1的序列递推，初始下标为一，每次递归合并两个序列，合并k次为止。

代码实现：dfs三个变量分别为：递归次数，长度，剩余值和所在下标。

若删去奇数个则下次递推坐标为长度+当前位置，否则不变过程中不断合并序列长度。

由于一共递推k次故时间复杂度仅为O(n \times\log{n})。

代码如下

#include<cstdio>
int n,cnt,k,a[70],t;
template<typename T>inline void read(T&x) {
    x = 0;char c;short sign = 1;
    do{
    c = getchar();if(c == '-') sign = -1;
    }while(c < '0' || c > '9');
    do{
    x = x * 10 + c - '0';c = getchar();
    }while(c <= '9' && c >= '0');x *= sign;}
inline long long dg( short cnt , long long l , long long wz ) {
    if( k == cnt ) return  wz ;
    return a[cnt+1] == 1? dg(cnt+1,l<<1,wz+l) : dg(cnt+1,l<<1,wz) ;}
int main(){
    read( t );
    while( t-- ) {
    read( n );read( k );
    for( register short i = 1; i <= k; ++i ) read( a[i] );
    printf("%lld",dg(0,1,1));puts("");}return 0;
}