大四的萌新辣！

Codeforces-Round-632-Div-2

Posted on Edited on In Valine:

菜鸡的$div2$补题现场……

A:Little Artem

1.题目描述：

给你一个$n * m$的矩形，现在让你涂色。$’B’$表示黑色，$’W’$表示白色。

Lets $B$ be the number of black cells that have at least one white neighbor adjacent by the side. Let $W$ be the number of white cells that have at least one black neighbor adjacent by the side.

先（重新）定义：

  • $’B’$表示具有至少一个相邻的白色邻居的单元格数量。
  • $‘W’$表示具有至少一个相邻的黑色邻居的单元格数量。

当$B = W + 1$时，我们称该矩形是好的。

让你输出任何一个好的矩形。

input:

1
2
3
2
3 2
3 3

output:

1
2
3
4
5
6
BW
WB
BB
BWB
BWW
BWB

2.思路

【！！！读题仔细！！！】

所以我们可以构造出一个样例，即构造出$2 (B)= 1(W) + 1$这种，就满足题目要求。

我们就可以让随便一个位置为$W$,然后构造两个$B$围着即可。

即矩形四个角的位置设置为$W$,其他均为$B$即可。

【qwq 我没有想到www~】

3.代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Copyright(c)
* Author : tiketiskte
*/
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define INF 0x3f3f3f3f

using namespace std;
int t, n, m;
int main()
{
   IOS
   cin >> t;
   while(t--) {
       cin >> n >> m;
       for(int i = 1; i <= n; i++) {
           for(int j = 1; j <= m; j++) {
               if(i == 1 && j == m) {//判断条件随便写 构造即可
                   cout <<'W';
               } else {
                   cout <<'B';
               }
           }
           cout << endl;
       }
   }
   //system("pause");
   return 0;
}

B:Kind Anton

1.题目描述

一个$a$数组，里边的元素只有${-1, 0, 1}$，你可以执行操作：

  • 选择一对$(i, j)$满足$1 \le i < j \le n$,可以多次选择同一对。
  • 将$a_i$ 加到$a_j$上， 即:$a_j = a_i + a_j$

问：给你一个$a$, $b$，能否对$a$进行上述操作，使得成为$b$数组？输出”YES/NO”

数据量：

  • T组数据：$1\le t \le 10000$
  • N—数组长度：$1\le n \le 10^5$

input:.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
5
3
1 -1 0
1 1 -2
3
0 1 1
0 2 2
2
1 0
1 41
2
-1 0
-1 -41
5
0 1 -1 1 -1
1 1 -1 1 -1

output:

1
2
3
4
5
YES
NO
YES
YES
NO

2.思路：

思维题

我们考虑，既然$i < j$恒成立，则：当$a_j <= a_j$时，我们就可以通过无限次累加$1$使得成立。

即：当$a_j >= a_j$时，我们也可以通过无限次累加$-1$使得成立。

所以我们要做的判断就是当$a_j <= b_j$时，是否存在$1$使得可以成立。 $>=$情况同理。

具体细节见代码。

逻辑判断条件要搞清….不然会很乱….

3.代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
* Copyright(c)
* Author : tiketiskte
*/
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define INF 0x3f3f3f3f

using namespace std;
int t, n, x;
//vector<int>a,b;
const int maxn = 1e5 + 5;
int a[maxn], b[maxn];
bool solve() {
    bool flag = false, x1 = false, x2 = false;
    for(int i = 1; i <= n; i++) {
        if(a[i] < b[i] && !x1) {
            flag = true;
            break;
        } else if(a[i] > b[i] && !x2) {
            flag = true;
            break;
        }
        if(a[i] == 1) {
            x1 = true;
        } else if(a[i] == -1) {
            x2 = true;
        }
    }
    return flag;
}
int main()
{
   IOS
   cin >> t;
   while(t--) {
       //int x;
       memset(a, 0, sizeof(a));
       memset(b, 0, sizeof(b));
       cin >> n;
       for(int i = 1; i <= n; i++) {
          /*  cin >> x;
           a.push_back(x); */
           cin >> a[i]; 
       }
       for(int i = 1; i <= n; i++) {
          /*  cin >> x;
           b.push_back(x); */
           cin >> b[i]; 
       }
       /* for(int x : a) {
           cout << x << " ";
       }
       for(int x : b) {
           cout << x << " ";
       } */
       if(solve()) {
           puts("NO");
       } else {
           puts("YES");
       }
   }
   system("pause");
   return 0;
}

C:Eugene and an array

1.题目描述

给你一个序列$a$，让你找出$a$的所有$sum != 0$的子序列个数。

input：

1
2
3
4
5
6
first:
3
1 2 -3
second:
3
41 -41 41

output：

1
2
3
4
first:
5
second:
3

2.思路：

子序列$sum$问题考虑前缀和。

题目中说明：一个序列的子序列如果$sum == 0$那么也不是一个$good$序列。于是我们可以用一个$map$来维护当前的前缀和，即：维护$sum$和对应的下标$i$。

！！！注意！！求前缀和的时候，原来的每一项数据范围是$int$，可能会爆$int$,所以我们采用$long long map$来维护。

【就是$map$保存前缀和嘛~出现前缀和相同，就是证明里边有$sum == 0$的子串，我们就去找最大左端点，然后用当前减去即可。】

思路就是 :

  • 我们首先对每一个i 找包含$a[i]$的子串的个数
  • 显然为$n$个，证明：对于第$i$个，左边有$i - 1$个，右边有$n - i$个，包含自身，即：$i - 1 + 1 + n - i$ 为$n$
  • 我们可以枚举每一个$a[i]$，求出其往左延伸有多少符合的子串，然后我们在加一下即可。
  • 对每一个$a[i]$，我们最后$ans += i - (max_l + 1)$[注意要+1，$max_l$ 表示前缀和相等的下标，实际区间要多减去1]

3.代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Copyright(c)
* Author : tiketiskte
*/
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define ll long long
#define INF 0x3f3f3f3f
#define endl "\n"
using namespace std;
const int maxn = 2e5 + 5;
ll a[maxn];
ll ans;
map<ll, ll>mp;//每一个前缀和出现的下标
int main()
{
   IOS
   int n;
   cin >> n;
   for(int i = 1; i <= n; i++) {
       cin >> a[i];
   }
   ll sum = 0;
   mp[0] = 0;
   ll temp = -1;//当前位置 区间 注意初始化
   for(int i = 1; i <= n; i++) {
       sum += a[i];
       if(mp.count(sum)) {
           temp = max(temp, mp[sum]);
       }
       mp[sum] = i;//更新
       ans += i - (temp + 1);
   }
   cout << ans << endl;
   system("pause");
   return 0;
}