牛客周赛 Round 63(构造、组合数、线性基)

A. 小红的好数

按照题意判断即可。

#include<bits/stdc++.h>
using namespace std;int main() {string s;cin >> s;if(s.size() == 2 && s[0] == s[1]) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

B. 小红的好数组

枚举所有区间长度为 k 的子区间即可。

#include<bits/stdc++.h>
using namespace std;const int maxn = 2e5 + 5;
int a[maxn];int main() {int n, k;cin >> n >> k;for(int i = 1; i <= n; i++) cin >> a[i];int res = 0;for(int x = 1; x+k-1 <= n; x++){ // 枚举左端点int cnt = 0;for(int i = 1; i <= k; i++){int l = x + i - 1, r = x + k - i; // 计算对称位置的下标if(l > r) break;if(a[l] != a[r]) cnt++;}		res += (cnt == 1);}cout << res << endl;return 0;
}

C. 小红的矩阵行走(简单思维题)

判断 $(1,1)$ 到 $(n,n)$ 的路径中，是否存在一条路径满足“路径上有 n + m - 1 个$a[1][1]$ ”。

#include<bits/stdc++.h>
using namespace std;const int maxn = 100 + 5;
int a[maxn][maxn];int main() {int ncase;cin >> ncase;while(ncase--){int n, m;cin >> n >> m;int first = -1, x;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> x;if(first == -1) first = x;a[i][j] = max(a[i-1][j], a[i][j-1]) + (x == first);}}if(a[n][m] == n + m - 1) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

D. 小红的行列式构造(构造、数学题)

看代码。

#include<bits/stdc++.h>
using namespace std;int main() {int x;cin >> x;if(x == -1){	// 一行列式等于 -1 的矩阵，下列通法不满足题目条件的一种情况。cout << "1 1 1" << endl;cout << "2 3 2" << endl;cout << "2 2 1" << endl;  }else{	// 全一矩阵加一个对角线矩阵cout << x+1 << " 1 1" << endl;cout << "1 2 1" << endl;cout << "1 1 1" << endl;        }return 0;
}

E. 小红的 red 计数(组合数)

核心思路，总方案数 - 受反转影响消失的red + 受反转影响出现的red。细节看代码。

设，每次查询，可以把 $(1,n)$ 分割为 A、B、C三个区间。

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e5 + 5;
ll r[maxn], e[maxn], d[maxn];
ll re[maxn], de[maxn], er[maxn], ed[maxn];
ll red[maxn], der[maxn];int main() {int n, q;cin >> n >> q;string s;cin >> s;s = " " + s;for(int i = 1; i <= n; i++) {r[i] = r[i-1] + (s[i] == 'r');e[i] = e[i-1] + (s[i] == 'e');d[i] = d[i-1] + (s[i] == 'd');re[i] = re[i-1] + (s[i] == 'e' ? r[i-1] : 0);de[i] = de[i-1] + (s[i] == 'e' ? d[i-1] : 0);er[i] = er[i-1] + (s[i] == 'r' ? e[i-1] : 0);ed[i] = ed[i-1] + (s[i] == 'd' ? e[i-1] : 0);red[i] = red[i-1] + (s[i] == 'd' ? re[i-1] : 0);der[i] = der[i-1] + (s[i] == 'r' ? de[i-1] : 0);}int x, y;while(q--){cin >> x >> y;ll res = red[n];// A区间提供‘r’，B区间提供‘ed’的情况。  // 注意ed[y] - ed[x-1] 包含‘e’在 A区间，‘d’在 B区间的情况。减去这种情况，得到由 B区间提供的‘ed’,其他同理。res = res - r[x-1] * (ed[y] - ed[x-1] - e[x-1] * (d[y] - d[x-1]));res = res + r[x-1] * (de[y] - de[x-1] - d[x-1] * (e[y] - e[x-1]));// 由 B区间提供 re 的情况。res = res - (d[n] - d[y]) * (re[y] - re[x-1] - r[x-1] * (e[y] - e[x-1]));res = res + (d[n] - d[y]) * (er[y] - er[x-1] - e[x-1] * (r[y] - r[x-1]));// 由 B区间提供 red 的情况。res = res - (red[y] - red[x-1] - r[x-1] * (ed[y] - ed[x-1] - e[x-1] * (d[y] - d[x-1])) - re[x-1] * (d[y] - d[x-1]));res = res + (der[y] - der[x-1] - d[x-1] * (er[y] - er[x-1] - e[x-1] * (r[y] - r[x-1])) - de[x-1] * (r[y] - r[x-1]));cout << res << endl;}return 0;
}

F. 小红开灯(线性基)

构造一个 n 维的向量空间，把第 i 个灯出现的位置映射到一个二进制向量的第 i 维。

第 i 个灯和与其同行同列的灯构成一个空间向量 x，一共可以构造出 n 个向量。

同时，对正在开着的灯，构造一个向量tar。如果在向量集合 X 中，可以选出若干个向量 x 表示出 tar，即问题有解。

对于样例一，构造一个 3 维的向量空间，其集合 X 为：

x1: (1, 1, 1) // 第一个灯与第二、第三个灯同行同列
x2: (1, 1, 0) // 第二个灯与第一个灯同列
x3: (1, 0, 1) // 第三个灯与第一个灯同行

构造出的目标向量tar为：

tar: (1, 0, 0) // 只有第一个灯开着的

在 X 中选择 x1、x2 和 x3 可表示出 tar，即 tar = x1 ^ x2 ^ x3，即样例一有解，对1、2、3 三个灯都操作一次就好。

但，显然，对于更复杂的样例，我们不能轻易的判断出都要选择什么灯来操作。

这里，我们引入’基’ 的概念，对于 n 维向量空间，对每一维都创建一个’基‘，即选择若干个向量，通过异或，可以得到最高位在 i 为 1 的向量。

举个例子，在样例一中：

第一维的基y1为 (1, 1, 1)，即 x1
第二维的基y2为 (0, 1, 0), 即 x1 ^ x3
第三维的基y3为 (0, 0, 1), 即 x1 ^ x2

此时，再看目标向量tar，tar 可由 y1 ^ y2 ^ y3 得到，即 (x1) ^ (x1^x3) ^ (X1^x2) = tar，对1、2、3 三个灯都操作(x1、x2、x3 都出现奇数次)。

这里，样例一可能比较特殊，我们把灯的初始状态修改为 001。

此时，tar = (1, 1, 0)，通过 y1 ^ y3 可以得到，即 (x1) ^ (x1 ^ x2) ，即对灯 2 进行一次操作即可。

上述描述，只是为了方便大家了解线性基，深入学习移步其他大佬的教学贴。

#include<bits/stdc++.h>
using namespace std;struct liner_base{vector<bitset<101> > a;	// 表示每个维度的基向量 vector<vector<int> > b;		// 表示每个维度的元素集合 int cnt = 0;liner_base(){a.resize(101);b.resize(101);}int insert(bitset<101> x, int id){vector<int> v = {id};for(int i = 100; i >= 0; i--){	// 高位开始遍历 if(x[i]){	// 第 i 位为1 if(a[i].count() == 0){ // 该维度没有被表示，但是可以被当前集合表示 a[i] = x;b[i] = v;cnt++; 		// 统计可以表示几个维度 return 1; 	// 插入成功 }else{	// 当前维度已经被标示，并且 x 有该维度 x ^= a[i];	// 把 x 中该维度去除 for(auto item : b[i]) v.push_back(item);	// 元素集合合并 } }}return 0; }int size(){return cnt;} vector<int> ask(bitset<101> x){vector<int> res;for(int i = 100; i >= 0; i--){if(x[i]){	// 同上 x ^= a[i];for(auto item : b[i]) res.push_back(item);}}if(x.count() != 0) res.clear();return res;}
};int s[105], x[105], y[105];map<int, vector<int> > m_x, m_y;int main() {int n;cin >> n;char c;for(int i = 1; i <= n; i++){cin >> c;s[i] = c - '0';}for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];for(int i = 1; i <= n; i++) m_x[x[i]].push_back(i);for(int i = 1; i <= n; i++) m_y[y[i]].push_back(i);int count = 0;liner_base lb;for(int i = 1; i <= n; i++){bitset<101> tmp;for(auto item : m_x[x[i]]) tmp[item] = 1;for(auto item : m_y[y[i]]) tmp[item] = 1;lb.insert(tmp, i); // 第i个点相关的灯组合成一个元素，插入线性基 count += s[i];}bitset<101> tar;for(int i = 1; i <= n; i++) if(s[i] == 0) tar[i] = 1;  // 所有没开的灯 if(count == n) cout << 0 << endl;else{vector<int> res = lb.ask(tar);if(res.empty()) cout << -1 << endl;	// 线性基不能表示tar else{vector<int> ans(n+1);for(auto id : res) ans[id]++; 	// 统计第 id 个灯操纵了几次int sum = 0;for(int i = 1; i <= n; i++) sum += ans[i] % 2; // 统计所有奇数次的cout << sum << endl;for(int i = 1; i <= n; i++){if(ans[i] & 1){cout << i << " ";}}}}return 0;
}