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

╰半夏微凉° 2023-10-11 09:40 35阅读 0赞

[传送门][Link 1]

B题题意：

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

否则打印出NO

题解：

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

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

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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

题解：

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

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11538434.html

[Link 1]: https://codeforc.es/contest/1196
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif