Codeforces Round #575 (Div. 3) B. Odd Sum Segments 、C Robot Breakout

B题题意：

给你n个数，让你把这n个数分成k个段(不能随意调动元素位置)。你需要保证这k个段里面所有元素加起来的和是一个奇数。问可不可以这样划分成功。如果可以打印YES，之后打印出来是从哪里开始断开的。

否则打印出NO

题解：

加上奇数可以使和的性质改变，原来使偶数则变为奇数，奇数则变为偶数。加上一个偶数就不会有这样的变化。所以第一步就找出来有多少个奇数。因为要保证k个段的和都为奇数，所以每个段得先有一个奇数

剩下来的奇数数量如果是偶数那就不影响，这样就可以成功划分。如果是奇数那就划分不成功

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<map>

 6 #include<math.h>

 7 using namespace std;

 8 typedef long long ll;

 9 const int maxn=2e5+5;

10 const int mod=26;

11 const int block=300;

12 int v[maxn];

13 int main()

14 {

15     int t;

16     scanf("%d\n",&t);

17     while(t--)

18     {

19         int n,m,sum=0,a;

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

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

22         {

23             scanf("%d",&v[i]);

24             if(v[i]%2)

25                 sum++;

26         }

27         sum-=m;

28         if(sum<0)

29             printf("NO\n");

30         else if(sum==0 || sum%2==0)

31         {

32             //sum/=2;

33             printf("YES\n");

34             int i;

35             if(sum==0) i=0;

36             else i=1;

37             if(sum!=0)

38             for(i;i<=n;++i)

39             {

40                 if(v[i]%2)

41                 {

42                     sum--;

43                     if(sum==0)

44                         break;

45                 }

46             }

47             for(i+=1;i<=n;++i)

48             {

49                 if(m==1)

50                 {

51                     printf("%d\n",n);

52                     break;

53                 }

54                 if(v[i]%2)

55                 {

56                     printf("%d ",i),m-=1;

57                 }

58             }

59         }

60         else printf("NO\n");

61     }

62     return 0;

63 }

C题题意：

给你n个机器人，这n个机器人有四个移动方向，但是有可能它的中枢坏了导致不能向某个方向移动。现在你需要找到一个坐标，机器人得到这个坐标会来到这里，但是也有某些方向损坏的机器人来不了

所以你需要找出来有没有能让所有机器人都到达这里的一个坐标。能找出来的话就先打印一个“1”再打印出这个坐标，否则打印出0

题解：

找出来所有机器人可移动区间，再让它们取并集就可以了

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<map>

 6 #include<math.h>

 7 using namespace std;

 8 typedef long long ll;

 9 const int maxn=1e5;

10 const int mod=26;

11 const int block=300;

12 struct shudui

13 {

14     int xmin,xmax,ymin,ymax,x,y;

15 } m[maxn+5];

16 int main()

17 {

18     int t;

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

20     while(t--)

21     {

22         int xmin=-maxn,xmax=maxn,ymin=-maxn,ymax=maxn,flag=0;

23         int n,x1,x2,x3,x4,x,y;

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

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

26         {

27             scanf("%d%d%d%d%d%d",&x,&y,&x1,&x2,&x3,&x4);

28             m[i].x=x;

29             m[i].y=y;

30             if(!flag)

31             {

32                 if(x1)

33                     m[i].xmin=-maxn;

34                 else m[i].xmin=x;

35                 if(x2)

36                     m[i].ymax=maxn;

37                 else m[i].ymax=y;

38                 if(x3)

39                     m[i].xmax=maxn;

40                 else m[i].xmax=x;

41                 if(x4)

42                     m[i].ymin=-maxn;

43                 else m[i].ymin=y;

44                 if(xmin>m[i].xmax || xmax<m[i].xmin || ymin>m[i].ymax || ymax<m[i].ymin)

45                 {

46                     flag=1;

47                 }

48                 else

49                 {

50                     xmin=max(xmin,m[i].xmin);

51                     xmax=min(xmax,m[i].xmax);

52                     ymin=max(ymin,m[i].ymin);

53                     ymax=min(ymax,m[i].ymax);

54                 }

55             }

56         }

57         if(!flag)

58         {

59             printf("1 %d %d\n",xmin,ymin);

60         }

61         else printf("0\n");

62     }

63     return 0;

64 }

巴特西

Codeforces Round #575 (Div. 3) B. Odd Sum Segments 、C Robot Breakout

最新文章

热门文章