Codeforces Round #575 (Div. 3) B. Odd Sum Segments 、C Robot Breakout
阅读原文时间:2023年07月11日阅读:1

传送门

B题题意:

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

否则打印出NO

题解:

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

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

代码:

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
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
2 #include
3 #include
4 #include
5 #include
6 #include
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 || xmaxm[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 }