Codeforces Round #691 (Div. 2)

A. Red-Blue Shuffle

题意：有两个长度为n的数组，数组a和数组b，问那个数组中的数字相比之下比另一个数组中相应位置的元素值更大一些，如果数组a大就输出RED，如果数组b大就输出BLUE，否则就输出EQUAL

思路：直接进行分开两个数组，然后%1d读入，再直接进行比较即可

代码:

 1 #include<iostream>

 2 #include<algorithm>

 3 #include<cstdio>

 4 #include<cmath>

 5 #include<cstring>

 6 using namespace std;

 7 int main(){

 8     //int r=0,b=0;

 9     int t;

10     scanf("%d",&t);

11     while(t--){

12         int n;

13         int r=0,b=0;

14         scanf("%d",&n);

15         int a[n+1],bb[n+1];

16         for(int i=0;i<n;i++){

17             scanf("%1d",&a[i]);

18         }

19         for(int i=0;i<n;i++){

20             scanf("%1d",&bb[i]);

21         }

22         for(int i=0;i<n;i++){

23             if(a[i]>bb[i]){

24                 r++;

25             }

26             if(a[i]<bb[i]){

27                 b++;

28             }

29         }

30         if(r>b){

31             printf("RED\n");

32         }else if(r<b){

33             printf("BLUE\n");

34         }else{

35             printf("EQUAL\n");

36         }

37     }

38 }

B.Move and Turn

题目：有一个无限大的二维平面，现在有个机器人在上面走动，走动的规则是：当走动一个单位时，机器人就要顺时针或者逆时针旋转90°，问现在要走n步，走到的不同的位置有多少个

思路：直接进行规律寻找，如果步数是偶数的话，就直接输出(n/2+1)*(n/2+1)，如果步数是奇数的话，就输出(1+k)*k*2，并且k=(n+1)/2

想不通的地方：当时觉得可能是个组合数学的题，然后就在纸上画来画去试图找到里面的规律，后来发现这样太混乱了，然后敲打代码，发现dfs也不是很好写，然后就看了看一些关于这个题的证明发现其实那些证明还是很含糊的

启示：以后这种找规律的题，可以先写一个代码dfs一下，然后再试图找找里面的规律性，就是用你知道的会TLE掉的代码，进行实验找到里面的规律

代码：

 1 #include<iostream>

 2 #include<algorithm>

 3 #include<cstdio>

 4 #include<cstring>

 5 #include<cmath>

 6 using namespace std;

 7 int main(){

 8     int n;

 9     scanf("%d",&n);

10     if(n%2==0){

11         printf("%d\n",(n/2+1)*(n/2+1));

12     }else{

13         int k=(n+1)/2;

14         printf("%d\n",(1+k)*k*2);

15     }

16 }

C.Row GCD

题意:看公式就是进行两个数组，然后第一个数组的所有数第一次加上第二个数组的第一个数，然后数组第一个数组的最大公约数，以此类推再是原来的第一个数组加上第二个数组的第二个元素，然后输出现在这个数组中最大的公约数

思路:其实跟直接计算没有什么差别，就是巧用了下

1、gcd(a₁,a₂,a₃,a₄……)=gcd(a₁,gcd(a₂,a₃,a₄……))

2、gcd(a₁,a₂) = gcd(a₁ , a₂-a₁)

然后就可以推导题目所求
gcd(a₁+d , a₂+d , a₃+d , a₄+d)=gcd(a₁+d , a₂ - a₁ , a₃ - a₂ , a₄ - a₃ ) = gcd(a₁+d , gcd ( a₂ - a₁ , a₃ - a₂ , a₄ - a₃ ) )

代码:

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 typedef long long LL;

 4 const int N=2e5+10;

 5 LL a[N],b[N];

 6 LL gcd(LL a,LL b)

 7 {

 8     if(b==0) return a;

 9     else return gcd(b,a%b);

10 }

11 int main()

12 {

13     int n,m;

14     scanf("%d%d",&n,&m);

15     for(int i=1;i<=n;i++)

16         scanf("%lld",&a[i]);

17     for(int i=1;i<=m;i++)

18         scanf("%lld",&b[i]);

19     if(n==1)

20     {

21         for(int i=1;i<=m;i++)

22             printf("%lld ",a[1]+b[i]);

23         return 0;

24     }

25     sort(a+1,a+1+n);

26     LL ans=a[2]-a[1];

27     for(int i=2;i<=n;i++)

28         ans=gcd(ans,a[i]-a[i-1]);

29     printf("%lld\n",ans);

30     for(int i=1;i<=m;i++)

31         printf("%lld ",gcd(ans,a[1]+b[i]));

32     printf("\n");

33     //system("pause");

34     return 0;

35 }

巴特西

Codeforces Round #691 (Div. 2)

最新文章

热门文章