Day 19

1.BC76 [NOIP2008]ISBN号码

BC76 [NOIP2008]ISBN号码
模拟

1.1解析

1.2 代码

#include <iostream>
using namespace std;
#include <string>int main()
{string s;cin>>s;int n=s.size(),sum=0,count=1;for(int i=0;i<n-1;i++){if(s[i]>='0'&&s[i]<='9'){sum+=(s[i]-'0')*count;count++;}}sum%=11;if(sum==s[n-1]-'0'||(sum==10&&s[n-1]=='X'))cout<<"Right"<<endl;else{if(sum==10)s[n-1]='X';else s[n-1]=sum+'0';cout<<s<<endl;}return 0;
}

2.kotori和迷宫

kotori和迷宫
bfs

2.1解析

2.2 代码

#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <queue>int n,m;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<vector<int>> vis;void bfs(vector<string>& grid,int i,int j)
{vis[i][j]=0;queue<pair<int,int>> q;q.push({i,j});while(q.size()){int size=q.size();while(size--){auto [a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==-1&&grid[x][y]!='*'){vis[x][y]=vis[a][b]+1;if(grid[x][y]!='e'){q.push({x,y});}}}}}
}
int main()
{cin>>n>>m;vector<string> grid(n);vis=vector<vector<int>>(n,vector<int>(m,-1));for(int i=0;i<n;i++)cin>>grid[i];for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]=='k'){bfs(grid,i,j);}}}int count=0,ret=1e9;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]=='e'&&vis[i][j]!=-1){count++;ret=min(ret,vis[i][j]);}}}if(count)cout<<count<<' '<<ret<<endl;else cout<<-1<<endl;return 0;
}

3.NC138 矩阵最长递增路径

NC138 矩阵最长递增路径
递归、记忆化搜索

3.1 解析

3.2 代码

//递归
class Solution {int n,m;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
public:int dfs(vector<vector<int>>& matrix,int i,int j){int len=1;for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&matrix[x][y]>matrix[i][j]){len=max(len,1+dfs(matrix,x,y));}}return len;}int solve(vector<vector<int> >& matrix) {n=matrix.size(),m=matrix[0].size();int ret=1;for(int i=0;i<n;i++){for(int j=0;j<m;j++){ret=max(ret,dfs(matrix,i,j));}}return ret;}
};//添加备忘录
class Solution {int n,m;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int memo[1010][1010];
public:int dfs(vector<vector<int>>& matrix,int i,int j){//先看备忘录if(memo[i][j]!=-1)return memo[i][j];int len=1;for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&matrix[x][y]>matrix[i][j]){len=max(len,1+dfs(matrix,x,y));}}memo[i][j]=len;//存入备忘录return len;}int solve(vector<vector<int> >& matrix) {n=matrix.size(),m=matrix[0].size();memset(memo,-1,sizeof(memo));int ret=1;for(int i=0;i<n;i++){for(int j=0;j<m;j++){ret=max(ret,dfs(matrix,i,j));}}return ret;}
};