《准备实足,冲冲冲 省一》https://www.yuque.com/lenyan-svokd/hi7hp2/hfka297matrtsxy2?singleDoc# 《准备实足,冲冲冲 省一》
#include<bits/stdc++.h> // 包含标准库头文件
using namespace std;
using ll = long long; // 定义 long long 数据类型的别名
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 优化输入输出操作
return 0; // 返回 0 表示成功执行
}
bool check() {} // 声明一个名为 "check" 的函数,返回布尔值
// 二分搜索函数,用于找到条件的第一次出现
int erf1(int l,int r) {
while(l<r) {
int mid = l+r>>1; // 计算中间索引
if(check(mid)) r = mid; // 调整右边界
else l = mid+1; // 调整左边界
}
return l; // 返回索引
}
// 二分搜索函数,用于找到条件的最后一次出现
int erf2(int l ,int r) {
while(l<r) {
int mid = l+r+1>>1; // 计算中间索引
if(check(mid))l = mid; // 调整左边界
else r = mid - 1; // 调整右边界
}
return l; // 返回索引
}
// 在数组的范围内增减元素
s[l]+=c; s[r+1]-=c;
// 在二维数组的矩形范围内增减元素
s[x1][y1]+=c;s[x2+1][y1]-=c;s[x1][y2+1]-=c;s[x2+1][y2+1] +=c;
// 计算二维数组的前缀和
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
// 循环遍历一个范围,同时满足条件
for(int i = 0,j = 0;i<n;i++) {
while(j<i&&check(i,j)) j++; // 增加 j 直到条件满足
}
// 表示四个方向移动的数组
int nxy[4][2] = {0,1,0,-1,1,0,-1,0};
// 深度优先搜索函数
void dfs(int x,int y) {
if(x<1||x>n||y<1||y>m||map[x][y] == 0||vis[x][y] ==1)
return; // 如果条件不满足,则退出
vis[x][y] = 1; // 标记为已访问的单元格
sum+=map1[x][y]; // 添加值到总和
for(int i = 0;i<4;i++) { // 遍历所有四个方向
int nx = x+nxy[i][0]; // 计算新的 x 坐标
int ny = y+nxy[i][1]; // 计算新的 y 坐标
dfs(nx,ny); // 递归调用以探索相邻单元格
if(nx<1||nx>n||ny<1||ny>m||map[nx][ny] == 0||vis[nx][ny] ==1) continue; // 如果条件不满足,则跳过
}
}
int main() {
cin>>n>>m; // 输入网格的维度
for(int i = 1;i <=n;i++) {
for(int j = 1; j <=m ;j++) {
cin>>map1[i][j]; // 输入网格的值
}
}
for(int i = 1;i <=n;i++) {
for(int j = 1; j <=m ;j++) {
if(map1[i][j]!=0) { // 检查单元格是否不为空
sum=0; // 重置总和
dfs(i,j); // 调用 DFS 函数以探索连接的组件
}
ans = ans > sum ? ans:sum; // 更新答案
}
}
cout<<ans<<endl; // 输出答案
return 0; // 返回 0 表示成功执行
}
// 结构体定义,表示树节点
struct tree {
int l,r; // 节点的左右边界
};
tree a[N]; // 树节点数组
// 输入树节点
cin>>n;
for(int i = 1; i<=n;i++) {
cin>>w[i]; // 输入节点权重
}
for(int i = 1;i<=n;i++) {
cin>>a[i].l>>a[i].r; // 输入节点边界
}
int map1[N][N]; // 二维数组,用于存储地图信息
bool vis[N][N]; // 二维数组,用于记录访问状态
int ans,x1,x2,y1,y2; // 变量声明
int nxy[4][2] = {0,1,1,0,0,-1,-1,0}; // 表示四个方向移动的数组
int n,m; // 变量声明
// 结构体定义,表示节点信息
struct node {
int x,y,step; // 节点的坐标和步数
};
queue<node> q; // 队列,用于广度优先搜索
// 广度优先搜索函数
int bfs() {
while(q.size()) // 当队列不为空时
{
node temp = q.front(); // 取出队列的头部节点
q.pop(); // 弹出队列的头部节点
int x = temp.x; // 获取节点的 x 坐标
int y = temp.y; // 获取节点的 y 坐标
int step = temp.step; // 获取节点的步数
if(x==x2&&y==y2) return step; // 如果到达目标节点,则返回步数
for(int i = 0; i < 4; i++) { // 遍历所有四个方向
int nx = x + nxy[i][0]; // 计算新的 x 坐标
int ny = y + nxy[i][1]; // 计算新的 y 坐标
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]|| map1[nx][ny]==" ") // 如果条件不满足,则跳过
{
continue;
}
vis[nx][ny] = 1; // 标记节点为已访问
q.push({nx,ny,step+1}); // 将新节点加入队列,并增加步数
}
}
return -1; // 返回 -1 表示未找到路径
}
// 初始化
node a;
a.x= a.y = a.step=;
vis[x1][y1] = 1;
q.push(a);
cout<<bfs()<<endl; // 输出最短路径长度
// 判断是否为质数
bool zhishu(int x) {
if(x<2) return false; // 小于 2 的数不是质数
for(int i = 2; i<=x/i; i++) {
if(x%i==0) return false; // 如果能被整除,则不是质数
}
return true; // 其他情况为质数
}
// 求小于等于 n 的所有质数
void getzhishu(int n) {
for(int i = 2; i<=n;i++) {
if(st[i]) continue; // 如果已经被标记为非质数,则跳过
zhishu[cnt++] = i; // 将质数存储起来
for(int j = i+i;j<=n;j+=i) {
st[j] = true; // 将 i 的倍数标记为非质数
}
}
}
// 获取一个数的所有约数
vector<int> getyueshu(int x) {
vector<int> ans; // 存储约数的数组
for(int i = 1; i<=x/i; i++) {
if(x%i==0) {
ans.push_back(i); // 如果能整除,则将约数加入数组
}
}
}
// 计算最大公约数
int gcd(int a,int b) {
return b?gcd(b,a%b):a; // 使用辗转相除法求最大公约数
}
// 计算最小公倍数
int lcm(int a,int b) {
return a*b/gcd(a,b); // 最小公倍数等于两数之积除以最大公约数
}
getchar(); // 从标准输入流中获取字符
string str; // 声明字符串变量
getline(cin,str); // 从标准输入流中获取一行字符串
// 快速幂算法
ll ksm(ll a,ll b,ll p) {
ll ans = 1; // 初始化结果为 1
while(b) { // 当指数大于 0 时
if(b&1) ans = ans * a % p; // 如果当前位为 1,则更新结果
a = a * a % p; // 底数平方
b>>=1; // 右移一位,相当于除以 2
}
return ans; // 返回结果
}
//最大递增子序列
// 读入数组 a,并将数组 b 初始化为与 a 相同的值
for(int i = 1; i <= n; i++) {
cin >> a[i]; // 读入数组 a 的第 i 个元素
b[i] = a[i]; // 将数组 b 的第 i 个元素初始化为数组 a 的第 i 个元素
}
// 动态规划计算最大子序列和
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= i; ++j) {
if(a[i] > a[j]) { // 如果当前元素大于前面的元素
b[i] = max(b[i], b[j] + a[i]); // 更新当前位置的最大值
}
}
}
// 找到数组 b 中最大的元素,即为最大子序列和
ll ans = *max_element(b + 1, b + 1 + n);
cout << ans << endl; // 输出结果
//最长上升子序列
for(int i=1;i<=n;i++)
{
f[i]=1
for(int j=1;j<=i;j++)
{
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
}
}
//优化
int len=0;
for(int i=1;i<n;i++)
{
int pos=lower_bound(f, f+len, a[i]) - f; // 查找大于等于 a[i] 的第一个元素的位置
len=max(len,pos+1); // 更新最长上升子序列的长度
f[pos]=a[i]; // 更新序列
}
cout <<len<<endl; // 输出最长上升子序列的长度
// 求最长下降子序列也可以用相同的优化
int len=0;
for(int i=1;i<n;i++)
{
int pos=upper_bound(f, f+len, a[i], greater<int>()) - f; // 查找大于 a[i] 的第一个元素的位置
len=max(len,pos+1); // 更新最长下降子序列的长度
f[pos]=a[i]; // 更新序列
}
cout <<len<<endl; // 输出最长下降子序列的长度
// 最长公共序列模型
int main()
{
int n,m;
cin >>n>>m; // 输入两个序列的长度
for(int i=1;i<=n;i++) cin >>a[i]; // 输入第一个序列
for(int i=1;i<=m;i++) cin >>b[i]; // 输入第二个序列
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]); // 更新最长公共子序列长度
if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); // 如果当前元素相等,则更新长度
}
}
cout <<f[n][m]<<endl; // 输出最长公共子序列长度
}
// f[i][j]表示所有在a[0...i],b[0....j]中出现过,以b[j]结尾的序列的集合
// 最长公共上升序列模型
int ans=0;
for(int i=1;i<=n;i++)
{
int temp=1;
for(int j=1;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j]); // 更新最长公共上升子序列长度
if(a[i]==b[j]) f[i][j]=max(temp,f[i][j]); // 如果当前元素相等,则更新长度
if(a[i]>b[j]) temp=max(temp,f[i-1][j]+1); // 如果当前元素大于,则更新长度
}
}
for(int i=1;i<=n;i++) ans=max(ans,f[n][i]); // 获取最大长度
const int months[] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; // 定义每个月的天数数组
// 判断闰年
int run(int year) {
if(year%4==0 && year%100!=0||year%400==0) return 1; // 满足闰年条件返回 1,否则返回 0
return 0;
}
// 获取指定月份的天数
int getdays(int y,int m) {
if(m==2) return 28+run(y); // 如果是二月,则根据是否是闰年返回对应天数
return months[m]; // 其他情况返回对应月份的天数
}