Codeforces Round #632 (Div. 2)
吐槽：最近cf题都不算简单的情况下过掉的人还是很多，同是3题下Rating可以差2,3K左右.希望国外疫情早日结束，大家上班上学出去玩，都别在cf上吊打我了！
A. Little Artem
Young boy Artem tries to paint a picture, and he asks his mother Medina to help him. Medina is very busy, that's why she asked for your help.
Artem wants to paint an n×m board. Each cell of the board should be colored in white or black.
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. A coloring is called good if B=W+1.
The first coloring shown below has B=5 and W=4 (all cells have at least one neighbor with the opposite color). However, the second coloring is not good as it has B=4, W=4 (only the bottom right cell doesn't have a neighbor with the opposite color).
Please, help Medina to find any good coloring. It's guaranteed that under given constraints the solution always exists. If there are several solutions, output any of them.
Input
Each test contains multiple test cases.
The first line contains the number of test cases t (1≤t≤20). Each of the next t lines contains two integers n,m (2≤n,m≤100) — the number of rows and the number of columns in the grid.
Output
For each test case print n lines, each of length m, where i-th line is the i-th row of your colored matrix (cell labeled with 'B' means that the cell is black, and 'W' means white). Do not use quotes.
It's guaranteed that under given constraints the solution always exists.
Example
inputCopy
2
3 2
3 3
outputCopy
BW
WB
BB
BWB
BWW
BWB
当构造出一个2*2的WB/BB 其余位置都是B，此时一直有：B=2，W=1
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N=150;
char g[N][N];
int main(){
int T;
cin>>T;
g[1][1]='W';g[1][2]='B';
g[2][1]='B';g[2][2]='B';
while(T--){
int n,m;
cin>>n>>m;
for(int i=3;i<=m;++i){
g[1][i]='B';
}
for(int i=3;i<=m;++i){
g[2][i]='B';
}
for(int i=3;i<=n;++i){
for(int j=1;j<=m;++j)
g[i][j]='B';
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)
cout<<g[i][j];
cout<<endl;
}
}
return 0;
}
Once again, Boris needs the help of Anton in creating a task. This time Anton needs to solve the following problem:
There are two arrays of integers a and b of length n. It turned out that array a contains only elements from the set {−1,0,1}.
Anton can perform the following sequence of operations any number of times:
Choose any pair of indexes (i,j) such that 1≤i<j≤n. It is possible to choose the same pair (i,j) more than once.
Add ai to aj. In other words, j-th element of the array becomes equal to ai+aj.
For example, if you are given array [1,−1,0], you can transform it only to [1,−1,−1], [1,0,0] and [1,−1,1] by one operation.
Anton wants to predict if it is possible to apply some number (zero or more) of these operations to the array a so that it becomes equal to array b. Can you help him?
Input
Each test contains multiple test cases.
The first line contains the number of test cases t (1≤t≤10000). The description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤105) — the length of arrays.
The second line of each test case contains n integers a1,a2,…,an (−1≤ai≤1) — elements of array a. There can be duplicates among elements.
The third line of each test case contains n integers b1,b2,…,bn (−109≤bi≤109) — elements of array b. There can be duplicates among elements.
It is guaranteed that the sum of n over all test cases doesn't exceed 105.
Output
For each test case, output one line containing "YES" if it's possible to make arrays a and b equal by performing the described operations, or "NO" if it's impossible.
You can print each letter in any case (upper or lower).
Example
inputCopy
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
outputCopy
YES
NO
YES
YES
NO
Note
In the first test-case we can choose (i,j)=(2,3) twice and after that choose (i,j)=(1,2) twice too. These operations will transform [1,−1,0]→[1,−1,−2]→[1,1,−2]
In the second test case we can't make equal numbers on the second position.
In the third test case we can choose (i,j)=(1,2) 41 times. The same about the fourth test case.
In the last lest case, it is impossible to make array a equal to the array b.
由于a数组只能是1，-1，0，所以我们从后向前考虑，如果当前(a_i)小于(b_i)，如果i前面有1则可以通过加1与(b_i)相等，小于时同理
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
int a[100010],b[100010];
bool add[100010],dele[100010];
int main(){
int T;
cin>>T;
while(T--){
int n;
memset(add,0,sizeof add);
memset(dele,0,sizeof dele);
cin>>n;
for(int i=1;i<=n;++i) {
cin>>a[i];
}
for(int i=1;i<=n;++i){
if(add[i-1]==1||a[i-1]==1) add[i]=1;
if(dele[i-1]==1||a[i-1]==-1) dele[i]=1;
}
for(int i=1;i<=n;++i) cin>>b[i];
int f=1;
for(int i=1;i<=n;++i){
if(a[i]!=b[i]){
int t=b[i]-a[i];
if(t>0&&add[i]==0) {
f=0;
break;
}
else if(t<0&&dele[i]==0){
f=0;
break;
}
}
}
if(f) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
Eugene likes working with arrays. And today he needs your help in solving one challenging task.
An array c is a subarray of an array b if c can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
Let's call a nonempty array good if for every nonempty subarray of this array, sum of the elements of this subarray is nonzero. For example, array [−1,2,−3] is good, as all arrays [−1], [−1,2], [−1,2,−3], [2], [2,−3], [−3] have nonzero sums of elements. However, array [−1,2,−1,−3] isn't good, as his subarray [−1,2,−1] has sum of elements equal to 0.
Help Eugene to calculate the number of nonempty good subarrays of a given array a.
Input
The first line of the input contains a single integer n (1≤n≤2×105) — the length of array a.
The second line of the input contains n integers a1,a2,…,an (−109≤ai≤109) — the elements of a.
Output
Output a single integer — the number of good subarrays of a.
Examples
inputCopy
3
1 2 -3
outputCopy
5
inputCopy
3
41 -41 41
outputCopy
3
Note
In the first sample, the following subarrays are good: [1], [1,2], [2], [2,−3], [−3]. However, the subarray [1,2,−3] isn't good, as its subarray [1,2,−3] has sum of elements equal to 0.
In the second sample, three subarrays of size 1 are the only good subarrays. At the same time, the subarray [41,−41,41] isn't good, as its subarray [41,−41] has sum of elements equal to 0.
这道题的题意其实时有点绕的，我们需要统计字符串a，它有多少子串不包含区间和为0的子串，即子串的子串
子串的子串也是嘛，我们可以统计a中区间和为0的区间，计算不包含这些区间的字串个数，不过一个个统计区间有点麻烦，可以转化为一个DP问题
f[i]表示以i结尾的不包含区间和为0的子串个数，从左向右遍历i，并且判断j~i中不包含区间和为0的子区间，这里用到前缀和和map：假设当j~i-1不存在前缀和为0的区间，j是j~i-1不包含区间和为0的最小端点。当sum[i]等于sum[k]时，说明k+1~i这一部分和为0，j如果在k前面则需要需要跳到k+2，那么j~i-1中的每个点都可以作为一个合法的右端点，为了不包含区间和为0的部分，sum[i]需要更新到map[sum[i]]中作为最大的点，需要特判一下前缀和为0和当前a为0的情况（感觉我这个写法需要注意的细节有点多
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N=200010;
LL sum[N],a[N],f[N];
map<LL,int> mmp;
int main(){
int n;
scanf("%d",&n);
LL ans=0;
mmp[0]=0;
int idx=0;
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
int j=1;
for(int i=1;i<=n;++i){
LL vv=sum[i];
j=min(i,max(mmp[vv]==0&&vv!=0?0:mmp[vv]+2,j));
ans+=i-j;
if(a[i]) ans++;
if(!a[i]) j=i+1;
mmp[vv]=i;
}
cout<<ans<<endl;
return 0;
}