2024/4/9

概况

C++常用vector<vector<int> res(m,vector<int>(n,0));来初始化一个m*n且内部初始值为0的二维数组

P8665 [2018 省 A] 航班时间

本题需要读取比较复杂格式的数据以及，含前导0的数据，此时应当使用scanf，以及不能关闭同步流,全部化成秒防止出现复杂的借位问题,%02d表示读两位若前面有0则也读入,输出则是前面补0

#include <bits/stdc++.h>
using namespace std;

int get(){
	int h1,m1,s1,h2,m2,s2,day=0;
	scanf("%02d:%02d:%02d %02d:%02d:%02d",&h1,&m1,&s1,&h2,&m2,&s2);
	if(getchar()==' '){//没有读到空格就是换行符
		scanf("(+%d)",&day);
	}
	return 24*3600*day+h2*3600+m2*60+s2-(h1*3600+m1*60+s1);
}

int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		int sec=(get()+get())/2;
		printf("%02d:%02d:%02d\n",sec/3600,sec%3600/60,sec%60);
	}
	return 0;
}

P8681 [2019 省 AB] 完全二叉树的权值

经典BFS题，将当前层内结点权值之和相加，并更新最大权值的层数即可

#include <bits/stdc++.h>
using namespace std;
int n,ans=1;
const int N=1e5+7;
int a[N];

void solve(){
	queue<int> q;
	int w=a[1],dep=0;
	q.push(1);
	while(q.size()){
		int t=q.size(),tmp=0;//tmp存当前层的权重
		dep++;//深度加一
		for(int i=0;i<t;i++){
			int d=q.front();//取出子节点
			q.pop();
			tmp+=a[d];
			if(2*d<=n) q.push(2*d);
			if(2*d+1<=n) q.push(2*d+1);
		}
		if(tmp>w) w=tmp,ans=dep;//更新
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	solve();
	cout<<ans;
}

leetcode 746.使用最小花费爬楼梯

本题明确最顶层是由下一层和下二层中花费最小的花费而来，同时站在一号台阶和零号台阶没有花费，所以初始化为0，更据状态转移方程从前往后循环即可

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(1001,0);//表示第i层阶梯的最低花费
        dp[0]=0;
        dp[1]=0;//两个台阶不用花费
        for(int i=2;i<=cost.size();i++){//循环size到最顶层
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.size()];
    }
};

leetcode 62.不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[0][0]=1;
        for(int i=0;i<m;i++)
        for(int j=0;j<n;j++){
            if(i-1>=0) dp[i][j]+=dp[i-1][j];
            if(j-1>=0) dp[i][j]+=dp[i][j-1];
        }
        return dp[m-1][n-1];
    }
};

这种写法不太规范，一般都是先初始化dp[i][0]和dp[0][j]为1也就是刚开始右边和下面一条路径都是一种方案，接着遍历1到m和1到n dp[i][j]=dp[i-1][j]+dp[i][j-1]即可

leetcode 63.不同路径II

本题初始化时要特判条件可能起点就有障碍物，因此起点值的初始化要进行特判

其他只需在递推时判断当前点是否是障碍物即可

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size(),n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        if(!obstacleGrid[0][0])
        dp[0][0]=1;
        else dp[0][0]=0;
        for(int i=1;i<m;i++) if(!obstacleGrid[i][0]) dp[i][0]=dp[i-1][0];
        for(int i=1;i<n;i++) if(!obstacleGrid[0][i]) dp[0][i]=dp[0][i-1];//初始化
        for(int i=1;i<m;i++)
        for(int j=1;j<n;j++){
            if(!obstacleGrid[i][j]) dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
        return dp[m-1][n-1];
    }
};