Round#632（Div.2）
A. Little Artem
题意：给你一块n*m的木板，每个单元可被涂成黑白两种颜色。令B为黑色电池的数量，该黑色电池中至少有一个相邻的白色邻居。 令W为至少有一个相邻的黑色邻域的白单元的数量。 如果B = W + 1，则着色为好。请找到任何好的颜色(确保在给定约束下解决方案始终存在)。如果有多个解决方案，请输出其中任何一个。
思路：若木板为2 * 2的，直接输出一个W三个B就可以。
其他情况在大于2的一个方向上连续输出两个W，其他n * m - 2个单元全输出B便可。
代码实现：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#define lowbit(x) (x &(-x))
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define int long long
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 5;
int t, n, m;
signed main()
{
cin >> t;while(t --){
cin >> n >> m;if(n == 2 && m == 2)cout << "WB" << endl << "BB" << endl;else{
if(n == 2){
cout << "WW";for(int i = 3; i <= m; i ++) cout << "B";cout << endl;for(int i = 1; i <= m; i ++) cout << "B";cout << endl;}else if(m == 2){
cout << "WB" << endl;cout << "WB" << endl;for(int i = 3; i <= n; i ++) cout << "BB" << endl;}else{
cout << "WW";for(int i = 3; i <= m; i ++) cout << "B";cout << endl;for(int i = 2; i <= n; i ++){
for(int j = 1; j <= m; j ++)cout << "B";cout << endl;}}}}return 0;
}
B. Kind Anton
题意：给你一个只由0，-1，1组成的长度为n的数组a[]，对于任意1 <= i < j <= n，你可以多次或者零次将ai加在aj上，试问是否可以通过这种操作是a数组等于给定的另一个数组b。
思路：
- 当j=1时，即a[1] != b[1]，就直接输出NO；
- 当j>2时: 若b[j] > a[j]，如果存在1<= i < j的a[i] = 1，就是YES;否则就是NO.若b[j]<a[j]，如果存在1<= i < j的a[i]= -1，就是YES，否则就是NO.
代码实现：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#define lowbit(x) (x &(-x))
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define int long long
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 5;
int t, n;
int a[N], b[N];
signed main()
{
cin >> t;while(t --){
cin >> n;for(int i = 1; i <= n; i ++)cin >> a[i];for(int i = 1; i <= n; i ++)cin >> b[i];if(a[1] != b[1]){
cout << "NO" << endl;continue;}int fu = 0, zheng = 0, vis = 0;if(a[1] == 1) zheng = 1;if(a[1] == -1) fu = 1;for(int i = 2; i <= n; i ++){
if(b[i] > a[i] && !zheng){
vis = 1;break;}if(b[i] < a[i] && !fu){
vis = 1;break;}if(a[i] == 1) zheng ++;if(a[i] == -1) fu ++;}if(vis) cout << "NO" << endl;else cout << "YES" << endl;}return 0;
}
C. Eugene and an array
题意：对于给定的数组a,试求出它含有几个sum非零的子数组(包括本身)。
思路：当找到一个sum为0的子数组时，那么包含它的数组就都不符合条件。所以在处理a数组的某个a[i]时，只看以a[i]为有边界的子数组，即r = i;找到它左边最近的一个sum为0的子数组的左边界l；那么以a[i]为又边界的符合条件的子数组有r -l 个，所以只要记录1到i的sum为0的子数组的最大左边界lmax，ans每次加上i - maxl即可。注意刚开始一个元素都没有的时候得记录下前缀sum为0，不然以第一个数开始得sum为0的数组将无法判断。(注意maxl的去最大值)
代码实现：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#define lowbit(x) (x &(-x))
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define int long long
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 5;
int n, x, sum, ans, maxl;
map<int, int> mp;
signed main()
{
cin >> n;mp[0] = 1;maxl = 1;for(int i = 2; i <= n + 1; i ++){
cin >> x;sum += x;if(mp[sum])maxl = max(maxl, (ll)(mp[sum] + 1));ans += i - maxl;mp[sum] = i;}cout << ans << endl;return 0;
}
D. Challenges in school №41
题意：
明天再来补吧。