「解题报告」Codeforces Round 596 (Div. 2)

又被C题的一些小细节卡死……

A. Forgetting Things

Source

不难发现只有 a+1 = b 或 a = b 时才有解。前一种直接输出 ‘a b’ ，后一种输出 ‘a0 b1’ 。
然后还有一个坑点是 a = 9,b = 1 的情况，此时是有解的，应输出 ‘9 10’。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int a,b;
int main()
{
    scanf("%d%d",&a,&b);
    if(a == b) printf("%d0 %d1",a,b);
    else if(a + 1 == b) printf("%d %d",a,b);
    else if(a == 9 && b == 1) printf("9 10");
    else printf("-1");
    return 0;
}

B. TV Subscriptions

Source (Easy Version)
Source (Hard Version)

区间的长度是固定的，那么只需要开一个桶，维护一下在某段区间内有那些元素。
考虑从一个区间滑动到另一个区间，那么这时候区间内元素个数是可以 O(1) 维护的，然后切了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int CN = 1e6+6;
const int INF = 0x3f3f3f3f;

int read(){
    int s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}

int t,n,k,d,a[CN];
int tot[CN];

int main()
{
    t = read();
    while(t--){
        memset(tot,0,sizeof(tot));
        
        n = read(); k = read(); d = read();
        for(int i=1;i<=n;i++) a[i] = read();
        
        int ans = INF,cnt = 0;
        for(int i=1;i<d;i++) {if(!tot[ a[i] ]) cnt++; tot[ a[i] ]++;}
        for(int i=d;i<=n;i++){
            if(!tot[ a[i] ]) cnt++; tot[ a[i] ]++;
            tot[ a[i-d] ]--; if(!tot[ a[i-d] ]) cnt--;
            ans = min(ans, cnt); 
        }
        
        printf("%d\n",ans);
    }
    
    return 0;
}

C. p-binary

Source

简化一下题意：给定 $p,s$ ，试求得一个最小的 $n$ ，使得存在一组 $\begin{Bmatrix} k_1,k_2,…,k_n \end{Bmatrix}$ ，满足 $\sum\limits_{i=1}^n 2^{k_i} + np = s$ 。

把 $np$ 移到右边去，变形成 $\sum\limits_{i=1}^n 2^{k_i} = s-np$ 。枚举 $n$ 之后， $s-np$ 就变成了一个定值，于是很自然的联想到可以把 $s-np$ 这个数表示成二进制下的和的形式，也就是 $s-np=\sum\limits_{(s-np) \And 2^i} 2^i$ 。
那么这实际上就是一种可行的拆分方案，我们只需要 check 一下 $(s-np) \And 2^i$ 成立的数量是否恰好等于 $n$ 即可，也就是判断 $s-np$ 在二进制下 $1$ 的数量是否恰好等于 $n$ ，这是 $O(\log)$ 的。

但是这并不能涵盖所有的方案。事实上，对于一个正整数 $k$，总有 $2^k=2\times(2^{k-1})=2^{k-1} + 2^{k-1}$ ，也就是说有一些项我们依然可以继续拆分。考虑 $2^k$ 能拆出的项数的范围：最少只有它自己，也就是一项；最多呢？
考虑把上面拆分的过程看作一棵二叉树，不难发先我们总可以拆出两项，三项，…，直到 $k$ 项。那么对于任意的 $2^k$ ，它总可以被拆分一项，两项，…， $k$ 项，也就是说它“能拆出的项数的范围”是 $[1,k]$ 。

考虑 $s-np=\sum\limits_{(s-np) \And 2^i} 2^i$ 中，后面那些部分能变成多少项。显然，任意 $2^i$ 能拆出的项数的范围是 $[1,i]$ ，那么设 $s-np = 2^{i_1}+2^{i_2}+…+2^{i_k} $ ，其中后面那一部分共有 $k$ 项，即可推出 $s-np$ 能拆出的项数的范围就是 $[k,i_1+i_2+…+i_k]$ 。

于是我们要做的就变成了 check 一下 $n\in [k,i_1+i_2+…+i_k]$ 是否成立，若成立则我们找到了一个可行解。这个判断还是 $O(\log)$ 的，那么只需要在 $10^6$ 内枚举 $n$ 就好了。

然后还有一些小细节，比赛的时候把我卡死了。。。具体看代码。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

#define LL long long

const int N = 1e6; // 枚举的边界，实际上还可以更小

LL n,p,ans = -1;
bool checker(LL u,int k){
    if(!u) return false; // 特判 u 为 0 时一定无解
    int lb = 0,rb = 1,i = 0; // rb 一定要初始化为 1, 因为至少有一项
    while(u){
        if(u & 1) lb++,rb += i;
        u >>= 1,i++;
    }
    return lb <= k && k <= rb;
}
 
int main()
{
    scanf("%I64d%I64d",&n,&p);
    for(int k=1;k<=N;k++){
        LL c = n - 1ll * k * p;
        if(c < 0) break;
        if(checker(c,k)){
            ans = 1ll * k;
            break;
        }
    }
    printf("%I64d",ans);
}