Educational Codeforces Round 106部分题解

119 阅读 0 评论 79 点赞

我是靠谱客的博主过时柠檬，这篇文章主要介绍Educational Codeforces Round 106部分题解，现在分享给大家，希望可以做个参考。

A. Domino on Windowsill
题意：
给定 $2 * n$ 的方格，第一行有k1个白格，第二行有k2个白格。且白格是连续且从1开始。其他位置为黑格。问能否放下w个白色骨牌和b个黑色骨牌 $（ 1 * 2 ）$
思路：
显然我们可以直接算出两种骨牌放置个数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int _;
int n,k1,k2,w,b;
int main() {
for(_=rd();_;_--){
n=rd();k1=rd();k2=rd();
w=rd();b=rd();
int ans1=min(k1,k2)+abs(k1-k2)/2;
k1=n-k1;k2=n-k2;
int ans2=min(k1,k2)+abs(k1-k2)/2;
if (ans1>=w&&ans2>=b)puts("YES");
else puts("NO");
}
return 0;
}

B. Binary Removals
题意：
给定一个01串，你可以选择一个子序列删除，子序列需满足不能取相邻元素。
问是否可以将01串变成升序排列即0…01…1或全0/1.

思路：
我们可以发现两个连续的0/1是不能同时删去的。
所以我们就找到最后一个00的位置和11的位置。判断一下前后关系即可

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int _,n;
char s[maxn];
int main() {
for(scanf("%d",&_);_;_--){
scanf("%s",s+1);
n=strlen(s+1);
int pos1=0,pos2=n+1;
for (int i=1;i<n;i++){
if (s[i]=='0'&&s[i+1]=='0')pos1=i;
}
for (int i=n;i>1;i--){
if (s[i]=='1'&&s[i-1]=='1')pos2=i;
}
if (pos1<=pos2)puts("YES");
else puts("NO");
}
return 0;
}

C. Minimum Grid Path
题意：你有一个 $n * n$ 的棋盘，初始你在 $（ 0, 0)$ 想要到达 $（ n * n)$
每一次你可以选择水平或者竖直走任意距离。
题目限制你最多拐弯n-1次即最多有n次走。
先给定每次走每一格的代价，求最小代价到达终点。

思路：
假如我们知道了走几步，那么我们让其中水平走的非最小花费的次数都只走1，最小花费的次数走掉剩下的。
这样显然是最优的，是贪心的策略。
那么我们不知道要走几步，就去枚举了，对于第x步都算出来最小代价，取个min即可

复制代码

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
const int maxn=1e5+5;
const ll mod=998244353;
int _;
ll n,a[maxn];
ll calc(ll *sum,ll *mn,int p){
int len1=p/2;
int len2=p-len1;
ll ans=0;
ans+=(sum[0]-mn[0]);
ans+=(n-len1+1)*mn[0];
ans+=(sum[1]-mn[1]);
ans+=(n-len2+1)*mn[1];
//printf("%d %dn",len1,len2);
return ans;
}
int main() {
for(_=rd();_;_--){
n=rd();
for (int i=1;i<=n;i++)a[i]=rd();
ll ans=1e18;
ll sum[2]={0},mn[2]={0};
mn[1]=a[1];sum[1]=a[1];
mn[0]=1e18;
for (int i=2;i<=n;i++){
mn[i%2]=min(mn[i%2],a[i]);
sum[i%2]+=a[i];
ans=min(ans,calc(sum,mn,i));
}
printf("%lldn",ans);
}
return 0;
}

D. The Number of Pairs
题意：给定c,d,x(1<=c,d,x<=1e7),求点对 $(a, b)$ 的数量使得 $c * l c m (a, b) - d * g c d (a, b) = x$
思路：
首先我们考虑假如我们知道lcm和gcd的值，那么点对 $(a, b)$ 会有多少种呢。
稍微在质因数分解的角度思考一会，就会发现取决于lcm/gcd的质因数个数。设lcm/gcd的值的质因数个数为c，点对数量= $2^c$ 。
那我们就可以对原式进行操作=> $l c m g c d frac{lcm}{gcd}$ = $x g c d + d c frac{frac{x}{gcd}+d}{c}$
那么我们就可以枚举x的因数，来得到每一个 $l c m g c d frac{lcm}{gcd}$ 加上它的贡献。
对于x的质因数个数我们可以预处理出来
时间复杂度 $O (n l o g n + T * 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
35
const int maxn=2e7+5;
const ll mod=998244353;
int _;
ll c,d,x;
int num[maxn],f[100],cnt1;
void init(){
for (int i=2;i<=20000000;i++){
if (num[i])continue;
num[i]=1;
for (int j=i*2;j<=20000000;j+=i)num[j]+=1;
}
}
int main() {
init();
for (int i=0;i<=30;i++)f[i]=1<<i;
for(_=rd();_;_--){
c=rd();d=rd();x=rd();
ll ans=0;
for (int i=1;i*i<=x;i++){
if (x%i)continue;
cnt1=i;
if ((cnt1+d)%c==0){
ans+=f[num[(cnt1+d)/c]];
}
if (i==(x/i))continue;
cnt1=x/i;
if ((cnt1+d)%c==0){
ans+=f[num[(cnt1+d)/c]];
}
}
printf("%lldn",ans);
}
return 0;
}