牟泓睿

UID: 430, 注册于 2026-7-22 20:04:14, 最后登录于 2026-8-16 18:04:05, 目前离线.

解决了 34 道题目，RP: 194.83 (No. 39)

个人简介

打家劫舍：

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int dp[1005];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[1]=a[1];
	for(int i=2;i<=n;i++){
		dp[i]=max(dp[i-2]+a[i],dp[i-1]);
	}
	int maxx=0;
	for(int i=1;i<=n;i++){
		maxx=max(maxx,dp[i]);
	}
	cout<<maxx;
	return 0;
}

不同路径：

#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int dp[105][105];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dp[1][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i==1&&j==1) continue;
			if(a[i][j]==1){
				dp[i][j]=0;
			}else{
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
			}
		}
	}
	cout<<dp[n][m];
	return 0;
}

中位数：

#include<bits/stdc++.h>
using namespace std;
int a[10005];
int n,m;
int l1,r1;
bool check(int x){
	l1=0,r1=0;
	for(int i=1;i<=n;i++){
		if(a[i]<x) l1++;
		else if(a[i]>x) r1++;
	}
	if(l1==r1) return true;
	else return false;
}
int main(){
	cin>>n>>m;
	int maxx=-9;
	int minn=INT_MAX;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		maxx=max(maxx,a[i]);
		minn=min(minn,a[i]);
	} 
	int l=minn,r=maxx;
	int o;
	while(l<=r){
		int mid=(r-l)/2+l;
		if(check(mid)==true){
			o=mid;
			break;
		}else if(check(mid)==false&&l1<r1){
			l=mid+1;
		}else if(check(mid)==false&&l1>r1){
			r=mid-1;
		}
	}
	cout<<o;
	return 0;
}

水杯：

#include<bits/stdc++.h>
using namespace std;
struct node {
	int z1;
	int z2;
	int z3;
	int bu;
};
int a, b, c, a1, b1, c1;
bool f[55][55][55];
queue<node> s;
bool f1 = false;
void bfs(int x, int y, int z, int step) {
	node o = {x, y, z, step};
	f[x][y][z] = true;
	s.push(o);
	while (!s.empty()) {
		node p = s.front();
		s.pop();
		if (p.z1 == a1 && p.z2 == b1 && p.z3 == c1) {
			cout << p.bu << endl;
			f1 = true;
			return ;
		}
		node q;
		if (p.z1 != 0 && p.z2 != b) {
			int x1, y1;
			x1 = max(0, p.z1 - (b - p.z2));
			y1 = min(b, p.z2 + p.z1);
			if (f[x1][y1][p.z3] == false) {
				f[x1][y1][p.z3] = true;
				q = {x1, y1, p.z3, p.bu + 1};
				s.push(q);
			}
		}
		if (p.z1 != 0 && p.z3 != c ) {
			int x1, y1;
			x1 = max(0, p.z1 - (c - p.z3));
			y1 = min(c, p.z3 + p.z1);
			if (f[x1][p.z2][y1] == false) {
				f[x1][p.z2][y1] = true;
				q = {x1, p.z2, y1, p.bu + 1};
				s.push(q);
			}
		}
		if (p.z2 != 0 && p.z1 != a ) {
			int x1, y1;
			x1 = max(0, p.z2 - (a - p.z1));
			y1 = min(a, p.z1 + p.z2);
			if (f[y1][x1][p.z3] == false) {
				f[y1][x1][p.z3] = true;
				q = { y1, x1, p.z3, p.bu + 1};
				s.push(q);
			}
		}
		if (p.z2 != 0 && p.z3 != c ) {
			int x1, y1;
			x1 = max(0, p.z2 - (c - p.z3));
			y1 = min(c, p.z3 + p.z2);
			if (f[p.z1][x1][y1] == false) {
				f[p.z1][x1][y1] = true;
				q = { p.z1, x1, y1, p.bu + 1};
				s.push(q);
			}
		}
		if (p.z3 != 0 && p.z1 != a ) {
			int x1, y1;
			x1 = max(0, p.z3 - (a - p.z1));
			y1 = min(a, p.z1 + p.z3);
			if (f[y1][p.z2][x1] == false) {
				f[y1][p.z2][x1] = true;
				q = { y1, p.z2, x1, p.bu + 1};
				s.push(q);
			}

		}
		if (p.z3 != 0 && p.z2 != b ) {
			int x1, y1;
			x1 = max(0, p.z3 - (b - p.z2));
			y1 = min(b, p.z2 + p.z3);
			if (f[p.z1][y1][x1] == false) {
				f[p.z1][y1][x1] = true;
				q = { p.z1, y1, x1, p.bu + 1};
				s.push(q);
			}
		}
	}
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		f1 = false;
		while (!s.empty()) s.pop();
		memset(f, 0, sizeof(f));
		cin >> a >> b >> c;
		cin >> a1 >> b1 >> c1;
		bfs(a, 0, 0, 0);
		if (f1 == false) {
			cout << -1 << endl;
		}
	}
	return 0;
}

连锁店：

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005];
bool f[1005][1005];
bool ff[1005][1005];
int zhi[1005][1005];
int n, m, k, d;
struct node {
	int l1, r1;
} b[100005];
struct node1 {
	int zuo1;
	int zuo2;
	int bu;
};
queue<node1> s;
int xx[] = {1, -1, 0, 0};
int yy[] = {0, 0, 1, -1};
void bfs(int x, int y, int step) {
	node1 o = {x, y, step};
	s.push(o);
	if(ff[x][y]==true){
		zhi[x][y] = min(zhi[x][y], step);
	}
	while (!s.empty()) {
		node1 p = s.front();
		s.pop();
		if(ff[p.zuo1][p.zuo2]==true){
			zhi[p.zuo1][p.zuo2] = min(zhi[p.zuo1][p.zuo2], p.bu);
		}
		for (int i = 0; i < 4; i++) {
			int xz = xx[i] + p.zuo1;
			int yz = yy[i] + p.zuo2;
			if (xz >= 1 && xz <= n && yz >= 1 && yz <= n && f[xz][yz] == false && a[xz][yz] != -15) {
				f[xz][yz] = true;
				node1 q = {xz, yz, p.bu + 1};
				s.push(q);
			}
		}
	}
}
int main() {
	cin >> n >> m >> k >> d;
	memset(zhi, 99999, sizeof(zhi));
	int idx = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			a[i][j] = 0;
		}
	}
	for (int i = 1; i <= m; i++) {
		int l, r;
		cin >> l >> r;
		b[++idx].l1 = l;
		b[idx].r1 = r;
		a[l][r] = 1;
	}
	for (int i = 1; i <= k; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		a[u][v] = w;
		ff[u][v]=true;
	}
	for (int i = 1; i <= d; i++) {
		int l, r;
		cin >> l >> r;
		a[l][r] = -15;
	}
	for (int i = 1; i <= idx; i++) {
		if (a[b[i].l1][b[i].r1] == 1) {
			f[b[i].l1][b[i].r1] = true;
			zhi[b[i].l1][b[i].r1]=0;
			bfs(b[i].l1, b[i].r1, 0);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(ff[i][j]==true){
				cout<<a[i][j]<<" "<<zhi[i][j]<<endl;
				ans+=(zhi[i][j]*a[i][j]);
			}
		}
	}
	cout<<ans;
	return 0;
}

飞地：



```language
#include<bits/stdc++.h>
using namespace std;
int a[105][105];
bool f[105][105];
int n, m;
int xx[] = {0, 0, 1, -1};
int yy[] = {1, -1, 0, 0};
void dfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int xz = xx[i] + x;
		int yz = yy[i] + y;
		if (xz >= 1 && xz <= n && yz >= 1 && yz <= m && f[xz][yz] == false && a[xz][yz] == 1) {
			f[xz][yz] = true;
			a[xz][yz] = 0;
			dfs(xz, yz);
			f[xz][yz] = false;
		}
	}
}
int main() {
	int ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		if (a[i][1] == 1) {
			f[i][1] = true;
			a[i][1] = 0;
			dfs(i, 1);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (a[i][n] == 1) {
			f[i][n] = true;
			a[i][n] = 0;
			dfs(i, n);
		}
	}
	for (int i = 1; i <= m; i++) {
		if (a[1][i] == 1) {
			f[1][i] = true;
			a[1][i] = 0;
			dfs(1, i);
		}
	}
	for (int i = 1; i <= m; i++) {
		if (a[1][m] == 1) {
			f[1][m] = true;
			a[1][m] = 0;
			dfs(1, m);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 1) {
				ans++;
			}
		}
	}
	cout << ans;
	return 0;
}

火灾：

#include<bits/stdc++.h>
using namespace std;
char a[105][105];
int zhi[105][105];
bool f[105][105];
bool ff[105][105];
int l,r,l1,r1;
struct node{
	int zuo1;
	int zuo2;
	int bu;
};
queue<node> s,s1;
int n,m;
int xx[]={0,0,1,-1};
int yy[]={1,-1,0,0};
void bfs(int x,int y,int step){
	node o={x,y,step};
	s.push(o);
	while(!s.empty()){
		node p=s.front();
		s.pop();
		for(int i=0;i<4;i++){
			int xz=xx[i]+p.zuo1;
			int yz=yy[i]+p.zuo2;
			if(xz>=1&&xz<=n&&yz>=1&&yz<=m&&f[xz][yz]==false&&a[xz][yz]!='#'){
				f[xz][yz]=true;
				zhi[xz][yz]=p.bu+1;
				node q={xz,yz,p.bu+1};
				s.push(q);
			}
		}
	}
}
bool f1=false;
void bfs1(int x,int y,int step){
	node o={x,y,step};
	s.push(o);
	while(!s.empty()){
		node p=s.front();
		s.pop();
		for(int i=0;i<4;i++){
			int xz=xx[i]+p.zuo1;
			int yz=yy[i]+p.zuo2;
			if(xz<1||xz>n||yz<1||yz>m){
				f1=true;
				cout<<p.bu+1;
				return ;
			}
			if(xz>=1&&xz<=n&&yz>=1&&yz<=m&&a[xz][yz]!='#'&&ff[xz][yz]==false&&p.bu+1<zhi[xz][yz]){
				ff[xz][yz]=true;
				node q={xz,yz,p.bu+1};
				s.push(q);
			}
		}
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		f1=false;
		memset(zhi,0,sizeof(zhi));
		memset(f,false,sizeof(f));
		memset(ff,false,sizeof(ff));
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
				if(a[i][j]=='J') l=i,r=j;
				if(a[i][j]=='F') l1=i,r1=j;
			}
		}
		if(l==l1&&r==r1){
			cout<<"IMPOSSIBLE"<<endl;
			continue;
		}
		f[l1][r1]=true;
		zhi[l1][r1]=0;
		bfs(l1,r1,0);
		ff[l][r]=true;
	    bfs1(l,r,0);
	    if(f1==false){
			cout<<"IMPOSSIBLE"<<endl;
		}
	}
	return 0;
}

通过的题目
P1216

P1254

P3337

A6602

A6603

A123456

A4103P

A6601

A3102
A4804

P3291

P3241

P3232

A5903

A5902

P3225

A5505P

A6615
1127

1162

A6604

Y1357

w0006

P3155

Y1355

P3129

A6613
2092

2096

A6701

2169

2170

g6011

2661
最近活动

This person is lazy and didn't join any contests or homework.
最近编写的题解

This person is lazy and didn't write any solutions.

搜索: 15
广搜: 7
栈: 6
深搜: 6
动态规划: 2
二分: 2
分治: 1
枚举: 1
递归: 1
其他: 1
排序: 1
搜索专题: 1
一本通: 1
一本通2018-第五章-搜索与回溯算法: 1

牟泓睿

个人简介

通过的题目

最近活动

最近编写的题解

题目标签

状态

开发

支持