B. Odd Sum Segments
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array 𝑎a consisting of 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an. You want to split it into exactly 𝑘k non-empty non-intersecting subsegments such that each subsegment has odd sum (i. e. for each subsegment, the sum of all elements that belong to this subsegment is odd). It is impossible to rearrange (shuffle) the elements of a given array. Each of the 𝑛n elements of the array 𝑎a must belong to exactly one of the 𝑘k subsegments.

Let's see some examples of dividing the array of length 55 into 33 subsegments (not necessarily with odd sums): [1,2,3,4,5][1,2,3,4,5] is the initial array, then all possible ways to divide it into 33 non-empty non-intersecting subsegments are described below:

  • [1],[2],[3,4,5][1],[2],[3,4,5];
  • [1],[2,3],[4,5][1],[2,3],[4,5];
  • [1],[2,3,4],[5][1],[2,3,4],[5];
  • [1,2],[3],[4,5][1,2],[3],[4,5];
  • [1,2],[3,4],[5][1,2],[3,4],[5];
  • [1,2,3],[4],[5][1,2,3],[4],[5].

Of course, it can be impossible to divide the initial array into exactly 𝑘k subsegments in such a way that each of them will have odd sum of elements. In this case print "NO". Otherwise, print "YES" and any possible division of the array. See the output format for the detailed explanation.

You have to answer 𝑞q independent queries.

Input

The first line contains one integer 𝑞q (1≤𝑞≤2⋅1051≤q≤2⋅105) — the number of queries. Then 𝑞q queries follow.

The first line of the query contains two integers 𝑛n and 𝑘k (1≤𝑘≤𝑛≤2⋅1051≤k≤n≤2⋅105) — the number of elements in the array and the number of subsegments, respectively.

The second line of the query contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤1091≤ai≤109), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a.

It is guaranteed that the sum of 𝑛n over all queries does not exceed 2⋅1052⋅105 (∑𝑛≤2⋅105∑n≤2⋅105).

Output

For each query, print the answer to it. If it is impossible to divide the initial array into exactly 𝑘k subsegments in such a way that each of them will have odd sum of elements, print "NO" in the first line. Otherwise, print "YES" in the first line and any possible division of the array in the second line. The division can be represented as 𝑘k integers 𝑟1r1, 𝑟2r2, ..., 𝑟𝑘rk such that 1≤𝑟1<𝑟2<⋯<𝑟𝑘=𝑛1≤r1<r2<⋯<rk=n, where 𝑟𝑗rj is the right border of the 𝑗j-th segment (the index of the last element that belongs to the 𝑗j-th segment), so the array is divided into subsegments [1;𝑟1],[𝑟1+1;𝑟2],[𝑟2+1,𝑟3],…,[𝑟𝑘−1+1,𝑛][1;r1],[r1+1;r2],[r2+1,r3],…,[rk−1+1,n]. Note that 𝑟𝑘rk is always 𝑛n but you should print it anyway.

Example
input
Copy 
3
5 3
7 18 3 14 1
5 4
1 2 3 4 5
6 2
1 2 8 4 10 2
output
Copy 
YES
1 3 5
NO
NO

 

题目大意：

给你一个序列，让你把它分为k份，每一份的和都是奇数

 

思路：

简单的数学问题，奇数+奇数= 偶数     偶数+奇数 = 奇数

我们先不妨就让每份都只有一个奇数。  

如果奇数有的多，我们就要让多的 奇数+奇数 成为偶数

 

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdbool.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <string.h>
 8 #include <stack>
 9 #include <map>
10  
11 #define INF 0x3f3f3f3f
12 #define LL long long
13 using namespace std;
14 const int MAXN = 2e5+10;
15  
16 int a[MAXN];
17  
18 int main()
19 {
20     //freopen("../in.txt","r",stdin);
21     int T;
22     scanf("%d",&T);
23     while (T--)
24     {
25         int n,k;
26         int cnt = 0;
27         scanf("%d%d",&n,&k);
28         for (int i=1;i<=n;i++)
29         {
30             scanf("%d",&a[i]);
31             if (a[i]%2)
32                 cnt++;
33         }
34         if (cnt >= k && (k-cnt)%2 == 0)
35         {
36             printf("YES\n");
37             int now = k-1;
38             for (int i=1;i<=n && now>0;i++)
39             {
40                 if (a[i]%2){
41                     printf("%d ",i);
42                     now--;
43                 }
44             }
45             printf("%d\n",n);
46         } else
47             printf("NO\n");
48     }
49     return 0;
50 }
Ackerman

 

 

C. Robot Breakout
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

𝑛n robots have escaped from your laboratory! You have to find them as soon as possible, because these robots are experimental, and their behavior is not tested yet, so they may be really dangerous!

Fortunately, even though your robots have escaped, you still have some control over them. First of all, you know the location of each robot: the world you live in can be modeled as an infinite coordinate plane, and the 𝑖i-th robot is currently located at the point having coordinates (𝑥𝑖xi, 𝑦𝑖yi). Furthermore, you may send exactly one command to all of the robots. The command should contain two integer numbers 𝑋X and 𝑌Y, and when each robot receives this command, it starts moving towards the point having coordinates (𝑋X, 𝑌Y). The robot stops its movement in two cases:

  • either it reaches (𝑋X, 𝑌Y);
  • or it cannot get any closer to (𝑋X, 𝑌Y).

Normally, all robots should be able to get from any point of the coordinate plane to any other point. Each robot usually can perform four actions to move. Let's denote the current coordinates of the robot as (𝑥𝑐xc, 𝑦𝑐yc). Then the movement system allows it to move to any of the four adjacent points:

  1. the first action allows it to move from (𝑥𝑐xc, 𝑦𝑐yc) to (𝑥𝑐−1xc−1, 𝑦𝑐yc);
  2. the second action allows it to move from (𝑥𝑐xc, 𝑦𝑐yc) to (𝑥𝑐xc, 𝑦𝑐+1yc+1);
  3. the third action allows it to move from (𝑥𝑐xc, 𝑦𝑐yc) to (𝑥𝑐+1xc+1, 𝑦𝑐yc);
  4. the fourth action allows it to move from (𝑥𝑐xc, 𝑦𝑐yc) to (𝑥𝑐xc, 𝑦𝑐−1yc−1).

Unfortunately, it seems that some movement systems of some robots are malfunctioning. For each robot you know which actions it can perform, and which it cannot perform.

You want to send a command so all robots gather at the same point. To do so, you have to choose a pair of integer numbers 𝑋X and 𝑌Y so that each robot can reach the point (𝑋X, 𝑌Y). Is it possible to find such a point?

Input

The first line contains one integer 𝑞q (1≤𝑞≤1051≤q≤105) — the number of queries.

Then 𝑞q queries follow. Each query begins with one line containing one integer 𝑛n (1≤𝑛≤1051≤n≤105) — the number of robots in the query. Then 𝑛n lines follow, the 𝑖i-th of these lines describes the 𝑖i-th robot in the current query: it contains six integer numbers 𝑥𝑖xi, 𝑦𝑖yi, 𝑓𝑖,1fi,1, 𝑓𝑖,2fi,2, 𝑓𝑖,3fi,3 and 𝑓𝑖,4fi,4 (−105≤𝑥𝑖,𝑦𝑖≤105−105≤xi,yi≤105, 0≤𝑓𝑖,𝑗≤10≤fi,j≤1). The first two numbers describe the initial location of the 𝑖i-th robot, and the following four numbers describe which actions the 𝑖i-th robot can use to move (𝑓𝑖,𝑗=1fi,j=1 if the 𝑖i-th robot can use the 𝑗j-th action, and 𝑓𝑖,𝑗=0fi,j=0 if it cannot use the 𝑗j-th action).

It is guaranteed that the total number of robots over all queries does not exceed 105105.

Output

You should answer each query independently, in the order these queries appear in the input.

To answer a query, you should do one of the following:

  • if it is impossible to find a point that is reachable by all 𝑛n robots, print one number 00 on a separate line;
  • if it is possible to find a point that is reachable by all 𝑛n robots, print three space-separated integers on the same line: 11 𝑋X 𝑌Y, where 𝑋Xand 𝑌Y are the coordinates of the point reachable by all 𝑛n robots. Both 𝑋X and 𝑌Y should not exceed 105105 by absolute value; it is guaranteed that if there exists at least one point reachable by all robots, then at least one of such points has both coordinates not exceeding 105105 by absolute value.
Example
input
Copy 
4
2
-1 -2 0 0 0 0
-1 -2 0 0 0 0
3
1 5 1 1 1 1
2 5 0 1 0 1
3 5 1 0 0 0
2
1337 1337 0 1 1 1
1336 1337 1 1 0 1
1
3 5 1 1 1 1
output
Copy 
1 -1 -2
1 2 5
0
1 -100000 -100000

 

 

题意：
给你n个机器人，它们有个初始位置，然后它们可以上下左右（不出故障的话）。问你这几个机器人可以到达的同一个点

 

思路：

本来我想DFS去做，可是一看数据范围，瞬间就打消了这个念头。

其实这道题就是简单一个模拟，题目已经给了边界范围 -1e5 -> 1e5 

如果不能往左走，那么x的范围肯定是在>=x 的区间之内。

可以每次对一个机器人看他哪个方向不能走，不能走的就更新一下边界，然后看左右边界上下边界是否有交集，没有交集NO，有交集随便输出左/右 +上/下

 

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdbool.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <string.h>
 8 #include <queue>
 9 #include <stack>
10 #include <map>
11 
12 #define INF 0x3f3f3f3f
13 #define LL long long
14 using namespace std;
15 const int MAXN = 2e5+10;
16 
17 int T,n;
18 
19 int main()
20 {
21     //freopen("../in.txt","r",stdin);
22     scanf("%d",&T);
23     while (T--)
24     {
25         int minx = -1e5;
26         int maxx = 1e5;
27         int miny = -1e5;
28         int maxy = 1e5;
29         int x,y;
30         scanf("%d", &n);
31         int a, b, c, d;
32         for (int i = 1; i <= n; i++)
33         {
34             scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
35             if (!a)
36                 minx = max(minx,x);
37             if (!c)
38                 maxx = min(x,maxx);
39             if (!b)
40                 maxy = min(maxy,y);
41             if (!d)
42                 miny = max(miny,y);
43         }
44         if (minx > maxx || miny > maxy)
45             printf("0\n");
46         else
47         {
48             printf("1 %d %d\n",minx,miny);
49         }
50     }
51     return 0;
52 }
Ackerman

 

D1. RGB Substring (easy version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between easy and hard versions is the size of the input.

You are given a string 𝑠s consisting of 𝑛n characters, each character is 'R', 'G' or 'B'.

You are also given an integer 𝑘k. Your task is to change the minimum number of characters in the initial string 𝑠s so that after the changes there will be a string of length 𝑘k that is a substring of 𝑠s, and is also a substring of the infinite string "RGBRGBRGB ...".

A string 𝑎a is a substring of string 𝑏b if there exists a positive integer 𝑖i such that 𝑎1=𝑏𝑖a1=bi, 𝑎2=𝑏𝑖+1a2=bi+1, 𝑎3=𝑏𝑖+2a3=bi+2, ..., 𝑎|𝑎|=𝑏𝑖+|𝑎|−1a|a|=bi+|a|−1. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer 𝑞q independent queries.

Input

The first line of the input contains one integer 𝑞q (1≤𝑞≤20001≤q≤2000) — the number of queries. Then 𝑞q queries follow.

The first line of the query contains two integers 𝑛n and 𝑘k (1≤𝑘≤𝑛≤20001≤k≤n≤2000) — the length of the string 𝑠s and the length of the substring.

The second line of the query contains a string 𝑠s consisting of 𝑛n characters 'R', 'G' and 'B'.

It is guaranteed that the sum of 𝑛n over all queries does not exceed 20002000 (∑𝑛≤2000∑n≤2000).

Output

For each query print one integer — the minimum number of characters you need to change in the initial string 𝑠s so that after changing there will be a substring of length 𝑘k in 𝑠s that is also a substring of the infinite string "RGBRGBRGB ...".

Example
input
Copy 
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR
output
Copy 
1
0
3
Note

In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".

 

 

 

思路：

数据范围比较小，我们就干脆模拟所有情况吧。从头匹配到尾，记录最小的更改次数

 

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdbool.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <string.h>
 8 #include <queue>
 9 #include <stack>
10 #include <map>
11  
12 #define INF 0x3f3f3f3f
13 #define LL long long
14 using namespace std;
15 const int MAXN = 2000+10;
16  
17 int T;
18 char ss[MAXN];
19 char s[] = {'R','G','B'};
20  
21 int main()
22 {
23     //freopen("../in.txt","r",stdin);
24     scanf("%d",&T);
25     while (T--)
26     {
27         int n,k;
28         scanf("%d%d",&n,&k);
29         scanf("%s",ss+1);
30         int sum = MAXN;
31         int cnt = 0;
32         for (int i=1;i<=n;i++)
33         {
34             if (ss[i] == 'R')
35             {
36                 cnt = 0;
37                 int start = 1;
38                 for (int j=i+1;j<i+k;j++)
39                 {
40                     if (ss[j] == s[start%3])
41                          ;
42                     else
43                         cnt++;
44                     start++;
45                 }
46                 sum = min(sum,cnt);
47             }
48             else if (ss[i] == 'G')
49             {
50                 cnt = 0;
51                 int start = 2;
52                 for (int j=i+1;j<i+k;j++)
53                 {
54                     if (ss[j] == s[start%3])
55                         ;
56                     else
57                         cnt++;
58                     start++;
59                 }
60                 sum = min(sum,cnt);
61             }
62             else if (ss[i] == 'B')
63             {
64                 cnt = 0;
65                 int start = 0;
66                 for (int j=i+1;j<i+k;j++)
67                 {
68                     if (ss[j] == s[start%3])
69                          ;
70                     else
71                         cnt++;
72                     start++;
73                 }
74                 sum = min(sum,cnt);
75             }
76         }
77         printf("%d\n",sum);
78     }
79 }
Ackerman

 

 

D2. RGB Substring (hard version)

 

 

思路：

数据范围比较大，我们就没法跟D1一样去模拟所有的情况了。

其实对于RGBRGB这个无限长的串来说只存在三种情况：

1、以“R”开头

2、以“G”开头

3、以“B”开头

看样例一：

母串t：BGGGG（3种）
样串s：RBGRBGRBGRBGRBGRBG
贡献a：11011 (不同的话，在这一位的贡献就是1，这个也是3种)

然后因为的们要获得区间长度为K的最小贡献，所以求个a的前缀和
O(1)遍历每一个长度为K的子串，找出最小的那个就是ans

 

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdbool.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <string.h>
 8 #include <queue>
 9 #include <stack>
10 #include <map>
11  
12 #define INF 0x3f3f3f3f
13 #define LL long long
14 using namespace std;
15 const int MAXN = 2e5+10;
16  
17 int T;
18 int num[MAXN];
19 char ss[MAXN];
20 char s[] = {'R','G','B'};
21  
22 int main()
23 {
24     //freopen("../in.txt","r",stdin);
25     scanf("%d",&T);
26     while (T--)
27     {
28         int n,k;
29         scanf("%d%d",&n,&k);
30         scanf("%s",ss+1);
31         int cnt = MAXN;
32         for (int j=0;j<3;j++)
33         {
34             num[0]=0;
35             for (int i=1;i<=n;i++)
36             {
37                 char c = s[(j+i)%3];
38                 if (c == ss[i])
39                     num[i] = 0;
40                 else
41                     num[i] = 1;
42             }
43             for (int i=1;i<=n;i++)
44                 num[i] = num[i] + num[i-1];
45             for (int i=k;i<=n;i++)
46                 cnt = min(cnt,num[i]-num[i-k]);
47         }
48         printf("%d\n",cnt);
49     }
50     return 0;
51 }
Ackerman

 

 

E. Connected Component on a Chessboard
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers 𝑏b and 𝑤w. You have a chessboard of size 109×109109×109 with the top left cell at (1;1)(1;1), the cell (1;1)(1;1) is painted white.

Your task is to find a connected component on this chessboard that contains exactly 𝑏b black cells and exactly 𝑤w white cells. Two cells are called connected if they share a side (i.e. for the cell (𝑥,𝑦)(x,y) there are at most four connected cells: (𝑥−1,𝑦),(𝑥+1,𝑦),(𝑥,𝑦−1),(𝑥,𝑦+1)(x−1,y),(x+1,y),(x,y−1),(x,y+1)). A set of cells is called a connected component if for every pair of cells 𝐶1C1 and 𝐶2C2 from this set, there exists a sequence of cells 𝑐1c1, 𝑐2c2, ..., 𝑐𝑘ck such that 𝑐1=𝐶1c1=C1, 𝑐𝑘=𝐶2ck=C2, all 𝑐𝑖ci from 11 to 𝑘k are belong to this set of cells and for every 𝑖∈[1,𝑘−1]i∈[1,k−1], cells 𝑐𝑖ci and 𝑐𝑖+1ci+1 are connected.

Obviously, it can be impossible to find such component. In this case print "NO". Otherwise, print "YES" and any suitable connected component.

You have to answer 𝑞q independent queries.

Input

The first line of the input contains one integer 𝑞q (1≤𝑞≤1051≤q≤105) — the number of queries. Then 𝑞q queries follow.

The only line of the query contains two integers 𝑏b and 𝑤w (1≤𝑏,𝑤≤1051≤b,w≤105) — the number of black cells required and the number of white cells required.

It is guaranteed that the sum of numbers of cells does not exceed 2⋅1052⋅105 (∑𝑤+∑𝑏≤2⋅105∑w+∑b≤2⋅105).

Output

For each query, print the answer to it.

If it is impossible to find the required component, print "NO" on the first line.

Otherwise, print "YES" on the first line. In the next 𝑏+𝑤b+w lines print coordinates of cells of your component in any order. There should be exactly 𝑏b black cells and 𝑤w white cells in your answer. The printed component should be connected.

If there are several answers, you can print any. All coordinates in the answer should be in the range [1;109][1;109].

Example
input
Copy 
3
1 1
1 4
2 5
output
Copy 
YES
2 2
1 2
YES
2 3
1 3
3 3
2 2
2 4
YES
2 3
2 4
2 5
1 3
1 5
3 3
3 5

 

思路：

这题完全就是一个构造题目，如果想得到就可以做，想不到就根本做不了这题。

这次没做出来的话就积累经验吧，下次争取做出来

 

首先我们要知道最极端的情况：

  -  -  -  -

-+-+-+-+-

 -  -  -  -

 

- 代表白色

+ 代表黑色

w = b*3+1 (极端情况)

 

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdbool.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <string.h>
 8 #include <queue>
 9 #include <stack>
10 #include <map>
11  
12 #define INF 0x3f3f3f3f
13 #define LL long long
14 using namespace std;
15 const int MAXN = 2e5+10;
16  
17 int T;
18  
19  
20  
21  
22 int main()
23 {
24     //freopen("../in.txt","r",stdin);
25     scanf("%d",&T);
26     while (T--)
27     {
28         int b,w;
29         scanf("%d%d",&b,&w);
30         int x = 2;
31         int y = 3;
32         if (w<b) // 交换，并且起始位置应为黑色的
33         {
34             y++;
35             swap(w,b);
36         }
37         if (w>3*b+1) { // 超出极端情况
38             printf("NO\n");
39             continue;
40         }
41         printf("YES\n");
42         for (int i=0;i<b;i++)  // 打印中间那行
43             printf("%d %d\n%d %d\n",x,y+2*i,x,y+2*i+1);
44         w -= b;
45         if (w>0)
46             printf("%d %d\n",x,y-1);  // 打印中间的最左边
47         --w;
48         for (int i=0;i<b && w>0;i++)
49         {
50             if (w>0){
51                 printf("%d %d\n",x-1,y+2*i); // 打印上面一行
52                 w--;
53             }
54             if (w>0){
55                 printf("%d %d\n",x+1,y+2*i); // 打印下面一行
56                 w--;
57             }
58         }
59     }
60     return 0;
61 }
62
Ackerman