蓝桥杯C++大学B组一个月冲刺记录2024/3/23
规则：每日三题
今日还是没有完成既定任务（6/9）：D
1.滑动窗口
给定一个大小为 n≤106的数组。
有一个大小为 k的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
单调队列 + 模板题
单调队列能解决的问题：给区间长度为k的区间内求其中的最大值或者最小值
（stl中双端队列deque实现，比手写数组模拟慢许多）
#include<iostream>
#include<queue>
using namespace std;
const int N = 1e6 + 10;
int p[N];
deque<int>q;
int n,k;
int main(){
cin >> n >> k;
for(int i = 1;i <= n;++i) cin >> p[i];
for(int i = 1;i <= n;++i)
{
while(q.size() != 0 && q.front() < i - k + 1) q.pop_front();
while(q.size() != 0 && p[q.back()] > p[i]) q.pop_back();
q.push_back(i);
if(i >= k) cout << p[q.front()] << ' ';
}
cout << endl;
q.clear();
for(int i = 1;i <= n;++i)
{
while(q.size() != 0 &&q.front() < i - k + 1) q.pop_front();
while(q.size() != 0 && p[q.back()] < p[i]) q.pop_back();
q.push_back(i);
if(i >= k) cout << p[q.front()] << ' ';
}
return 0;
}
2.子矩阵
给定一个 n×m（n 行 m 列）的矩阵。
设一个矩阵的价值为其所有数中的最大值和最小值的乘积。
求给定矩阵的所有大小为 a×b（a 行 b 列）的子矩阵的价值的和。
答案可能很大，你只需要输出答案对 998244353
取模后的结果。
二维单调队列
#include<iostream>
using namespace std;
const int N = 1005;
const int mod = 998244353;
int p[N][N];
int row_max[N][N];//第i行j列元素起，长度为b的子序列长度最大值
int row_min[N][N];//第i行j列元素起，长度为b的子序列长度最小值
typedef long long LL;
int n,m,A,B;
LL ans = 0;
void work_max(int a[],int b[],int tot,int k)
{
int h[N];
int r = -1,l = 0;
for(int i = 1; i <= tot; ++i){
while(r >= l && h[l] < i - k + 1) l++;
while(r >= l && a[h[r]] <= a[i]) r--;
r++;
h[r] = i;
if(i - k + 1 >= 1) b[i - k + 1] = a[h[l]];
}
return;
}
void work_min(int a[],int b[],int tot,int k)
{
int h[N];
int r = -1,l = 0;
for(int i = 1; i <= tot; ++i){
while(r >= l && h[l] < i - k + 1) l++;
while(r >= l && a[h[r]] >= a[i]) r--;
r++;
h[r] = i;
if(i - k + 1 >= 1) b[i - k + 1] = a[h[l]];
}
return;
}
int main()
{
cin >> n >> m >> A >> B;
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
cin >> p[i][j];
}
}
for(int i = 1;i <= n;++i)
{
work_max(p[i],row_max[i],m,B);
work_min(p[i],row_min[i],m,B);
}
int a[N],b[N],c[N];
for(int i = 1;i <= m - B + 1;++i)
{
for(int j = 1;j <= n; ++j) a[j] = row_max[j][i];
work_max(a,b,n,A);
for(int j = 1;j <= n; ++j) a[j] = row_min[j][i];
work_min(a,c,n,A);
for(int j = 1;j <= n - A + 1;++j) ans = (ans + (LL)b[j] * c[j])%mod;
}
cout << ans << endl;
return 0;
}
3.最长子序列
输入一个长度为 n 的整数序列，从中找出一段长度不超过 m
的连续子序列，使得子序列中所有数的和最大。
前缀和 + 单调队列
由于求某区间的数总和，考虑到前缀和：res[r] - res[l - 1]表示 l 到 r 区间的数总和且 r - l + 1 <= m
就可以将问题抽象成在给定 r 的情况下 在某个r之前长度为m的区间内找到一个最小值
#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL INF = 0x3f3f3f3f3f;
int p[N];
long long res[N];
deque<int>q;
LL ans = -INF;
int n,k;
int main()
{
cin >> n >> k;
for(int i = 1;i <= n;++i)
{
cin >> p[i];
res[i] = res[i - 1] + p[i];
}
q.push_back(0);
for(int i = 1;i <= n;++i){
while(q.size() != 0 && q.front() < i - k) q.pop_front();
while(q.size() != 0 && res[q.back()] > res[i]) q.pop_back();
ans = max(ans,(LL)res[i] - res[q.front()]);
q.push_back(i);
}
cout << ans << endl;
return 0;
}
4.烽火传递
烽火台是重要的军事防御设施，一般建在交通要道或险要处。
一旦有军情发生，则白天用浓烟，晚上有火光传递军情。
在某两个城市之间有 n 座烽火台，每个烽火台发出信号都有一定的代价。
为了使情报准确传递，在连续 m个烽火台中至少要有一个发出信号。
现在输入 n,m 和每个烽火台的代价，请计算在两城市之间准确传递情报所需花费的总代价最少为多少。
单调队列 + dp
这个题的dp转移思路和最长上升子序列的转移方式有点像。但是暴力转移会tle，所以用单调队列来优化
模型转换和上一个题思路很像
#include<iostream>
using namespace std;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int w[N];
int f[N];//需要仅考虑前i个烽火台且i点亮的方案的最小值
int h[N];
int l = 0,r = - 1;
int n,m;
int main(){
cin >> n >> m;
for(int i = 1;i <= n; ++i) cin >> w[i];
for(int i = 0;i <= n; ++i)
{
while(r >= l&& h[l] < i - m + 1) l++;
while(r >= l&& f[h[r]] >= f[i]) r--;
r++;
h[r] = i;
f[i + 1] = f[h[l]] + w[i + 1];
}
cout << f[n + 1] << endl;
return 0;
}
5.网络分析
小明正在做一个网络实验。
他设置了 n 台电脑，称为节点，用于收发和存储数据。
初始时，所有节点都是独立的，不存在任何连接。
小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。
两个节点如果存在网线连接，称为相邻。
小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。
所有发送和接收的节点都会将信息存储下来。
一条信息只存储一次。
给出小明连接和测试的过程，请计算出每个节点存储信息的大小
并查集 + 路径压缩
这个题的关键在于其精妙的find函数写法。
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int f[N];
int d[N];
int n,m;
int find(int x){
if(x == f[x] || f[f[x]] == f[x]) return f[x];
int r = find(f[x]);
d[x] += d[f[x]];
f[x] = r;
return r;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n; ++i) f[i] = i;
while(m--){
int t,x,y;
cin >> t >> x >> y;
if(t == 1){
if(x == y) continue;
x = find(x),y = find(y);
if(x!=y){
f[x] = y;
d[x] -= d[y];
}
}
else
{
x = find(x);
d[x] += y;
}
}
for(int i = 1;i<=n;++i){
if(i == find(i)) cout << d[i] << ' ';
else cout << d[i] + d[find(i)] << ' ';
}
return 0;
}
6.格子游戏
Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3 ）。
接着，他们两个轮流在相邻的点之间画上红边和蓝边：
直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！
他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序，帮助他们计算他们是否结束了游戏？
并查集 + 判环
依旧是是那个思路：当同一个连通块中的亮点连一条边的时候，产生环
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int n,m;
int query(int x,int y){
return x * n + y;
}
int find(int x){
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
int x,y;
char c;
int main(){
cin >> n >> m;
for(int i = 1;i < 2 * n * n; ++i) f[i] = i;
int ans = -1;
for(int i = 1;i <= m; ++i){
int a,b;
cin >> x >> y >> c;
x--,y--;
a = query(x,y);
if(c == 'D') b = query(x + 1, y);
else b = query(x, y + 1);
int pa = find(a);
int pb = find(b);
if(pa == pb){
ans = i;
break;
}
f[pa] = pb;
}
if(ans == -1) cout << "draw" << endl;
else cout << ans << endl;
return 0;
}