文章目录
牛客周赛 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 ) (1,1) (1,1) 到 ( n , n ) (n, n) (n,n) 的路径中，是否存在一条路径满足“路径上有 n + m - 1 个 a [ 1 ] [ 1 ] a[1][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 ) (1,n) (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;
}