【解题报告】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’。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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) 维护的,然后切了。

代码:

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
#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$ 就好了。

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

代码:

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
#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);
}

$$ - - - - \mathcal{End} - - - - $$


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×