Educational Codeforces Round 23(A/B/C)

A Treasure Hunt

题目传送门

$$
(a,b)\rightarrow (a+x,b+y),
(a,b)\rightarrow (a-x,b+y),
(a,b)\rightarrow (a+x,b-y),
(a,b)\rightarrow (a-x,b-y),
$$

对任何$x=0$和$y=0$的情况特判,当没有这些特殊情况时我们就看起点与终点横纵坐标的差是否分别为每次移动的$x$,$y$的倍数,如果不是直接$NO$,如果是的话就判断他们是否同为$x,y$的奇数倍或者偶数倍。
代码:

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
#include <bits/stdc++.h>
using namespace std;
int x_1,y_1,x_2,y_2;
int x,y;
int myabs(int x){return x<0?-x:x;}
int main()
{
scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
scanf("%d%d",&x,&y);
if(x==0){
if(myabs(x_2-x_1)!=0) {printf("NO\n");}
else{
if(y==0 && myabs(y_2-y_1)!=0) {printf("NO\n");}
else if(y!=0 && myabs(y_2-y_1)%myabs(y)!=0)
{printf("NO\n");}
printf("YES\n");
}
}else if(y==0){
if(myabs(y_2-y_1)!=0) {printf("NO\n");}
else{
if(x==0 && myabs(x_2-x_1)!=0) {printf("NO\n");}
else if(x!=0 && myabs(x_2-x_1)%myabs(x)!=0)
{printf("NO\n");}
printf("YES\n");
}
}
else{
if(myabs(x_2-x_1)%myabs(x)!=0 || myabs(y_2-y_1)%myabs(y)!=0)
{printf("NO\n");exit(0);}
else{
int k1=myabs(x_2-x_1)/myabs(x);
int k2=myabs(y_2-y_1)/myabs(y);
k1=k1%2;k2=k2%2;
if(k1==k2) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}

B Makes And The Product

传送门
由于$a$的范围很大,我们考虑离散处理$a$的值(其实根本不用离散,你们当我练一下离散好了),然后我们对$a$排序,最后记录下最小的三个数分别有多少个,然后按照情况去计数就好啦。
代码

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
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int n;
vector<int > a;
ll clt(int n,int m){
ll res=1;
for(int i=n-m+1;i<=n;i++) res=res*i;
for(int i=1;i<=m;i++) res=res/i;
return res;
}
int main()
{
scanf("%d",&n);a.clear();
for(int i=0;i<n;i++){
int num;scanf("%d",&num);a.push_back(num);
}
vector<int > b;b.clear();
for(int i=0;i<n;i++) b.push_back(a[i]);
sort(b.begin(),b.end());
b.erase(unique(b.begin(),b.end()),b.end());
for(int i=0;i<n;i++) a[i]=upper_bound(b.begin(),b.end(),a[i])-b.begin();
sort(a.begin(),a.end());
int tmp=-1,cnt=0;
int cou=0;
int res[4];memset(res,0,sizeof(res));
for(int i=0;i<(int)a.size();i++){
if(tmp!=a[i]) {if(cnt>=1)res[++cou]=cnt;tmp=a[i];cnt=1;}
else cnt++;
if(cou==3) break;
}if(cnt>=1 && cou<3) res[++cou]=cnt;
if(res[1]>=3){
printf("%llu\n",clt(res[1],3));
}else if(res[1]+res[2]>=3){
printf("%llu\n",clt(res[2],3-res[1]));
}else{
printf("%llu\n",(ll)(res[1]*(ll)(res[2]*res[3])));
}
return 0;
}

C Really Big Numbers

传送门

考完了才发现有结论…

对于此题的一个结论是,若$x$是$really ~big ~number$,那么$x+1$也一定是。怎么证明呢?

我们设一个数$x$的每位数字之和为$sumd$,

我们要证明如下的式子:
$$ x+1-sumd(x+1) \ge x-sumd(x)$$

消去$x$后我们得到$-sumd(x+1) \ge -sumd(x)-1$

即我们要证$sumd(x+1) \leq sumd(x)+1$

这个怎么来的呢…?首先如果$x$的末尾不是$9$,那么$sumd(x)=sumd(x+1)$,若$x$末尾为$9$且要进位,那么肯定对于$sumd(x+1)$,相对$sumd(x)$经过的是一个不断$+1$和$-9$的过程,那么$sumd(x+1) \leq sumd(x)+1$,结论成立。

那么对于整个区间$[1,n]$,只要我们找到最小的$x$使得$x$为一个$big number$,那么我们就可以知道$n-x+1$即为需求的个数。至于求解这个$x$,二分答案即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,s;
ll myabs(ll x){return x<0?-x:x;}
ll getsum(ll x)
{
ll res=0;
while(x>0){res+=x%10;x/=10;}
return res;
}
bool cal(ll x)
{
ll tmp=getsum(x);
return myabs(x-tmp)>=s;
}
int main()
{
scanf("%lld%lld",&n,&s);
ll l=1,r=n+1;
while(r-l>1){
ll mid=l+(r-l+1)/2;
if(cal(mid)) r=mid;
else l=mid;
}
printf("%lld\n",n-r+1);
return 0;
}