2023/3/4天梯备战acwing刷题

news/2024/7/15 17:30:15 标签: 算法, 图论, 动态规划

796子矩阵的和

二维前缀和

#include<iostream>
using namespace std;
const int maxx = 1e3+10;
int ma[maxx][maxx];

int main(){
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ma[i][j];
			ma[i][j]=ma[i-1][j]+ma[i][j-1]-ma[i-1][j-1]+ma[i][j];
		}
	}
	while(q--){
		int x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;
		cout<<ma[x2][y2]-ma[x1-1][y2]-ma[x2][y1-1]+ma[x1-1][y1-1]<<endl;
	}
	return 0;
}

1096地牢大师

bfs模板

#include<iostream>
#include<queue>
using namespace std;

string m[110][110];
int dir[6][3] = {{0,0,1},{0,1,0},{1,0,0},{0,0,-1},{0,-1,0},{-1,0,0}};

int L,R,C;
int sl,sr,sc;

struct Node{
	int l;
	int r;
	int c;
	int step;
};

int bfs(){
	Node cur={sl,sr,sc,0};
	queue<Node> q;
	q.push(cur);
	while(q.size()){
		Node pre = q.front();
		q.pop();
		for(int i=0;i<6;i++){
			int nexl = pre.l+dir[i][0];
			int nexr = pre.r+dir[i][1];
			int nexc = pre.c+dir[i][2];
			int nexStep = pre.step+1;
			if(nexl==L||nexl<0||nexr==R||nexr<0||nexc==C||nexc<0){
				continue;
			}
			if(m[nexl][nexr][nexc]=='#'){
				continue;
			}
			if(m[nexl][nexr][nexc]=='.'){
				Node nex = {nexl,nexr,nexc,nexStep};
				q.push(nex);
				m[nexl][nexr][nexc] = '#';
			}
			if(m[nexl][nexr][nexc]=='E'){
				return nexStep;
			}
		}
	}
	return -1;
}

int main(){
	while(true){
		cin>>L>>R>>C;
		if(L==0){
			break;
		}
		getchar();
		for(int i=0;i<L;i++){
			for(int j=0;j<R;j++){
				getline(cin,m[i][j]);
			}
			string tmp;
			getline(cin,tmp);
		}
		for(int i=0;i<L;i++){
			for(int j=0;j<R;j++){
				for(int k=0;k<C;k++){
					if(m[i][j][k]=='S'){
						sl=i;
						sr=j;
						sc=k;
					}
				}
			}
		}
		int res = bfs();
		if(res == -1){
			cout<<"Trapped!"<<endl;
		}else{
			printf("Escaped in %d minute(s).\n",res);
		}
	}
	return 0;
}

1224交换瓶子

很巧妙的思路，在遍历时不是让a[j]复原，而是让a[a[j]]复原
1 e 4 1e4 1e4的时间复杂度也够用

#include<iostream>
using namespace std;
const int maxx = 1e4+10;

int a[maxx];

int main(){
	int N;
	cin>>N;
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	bool res = false;
	int ans = 0;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			if(a[j]!=j){
				swap(a[j],a[a[j]]);
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

1240完全二叉树的权值

使用数组模拟完全二叉树，注意完全二叉树的性质，即
首先根节点的下标为 1 ，层数从 1 开始 首先根节点的下标为1，层数从1开始 首先根节点的下标为1，层数从1开始
对于第 i 层，结点下标为 [ 2 i − 1 , 2 i − 1 ] 对于第i层，结点下标为[2^{i-1},2^i-1] 对于第i层，结点下标为[2i−1,2i−1]

#include<cmath>
#include<iostream>
using namespace std;
const int maxx = 1e5+10;
typedef long long ll;

int main(){
	int N;
	cin>>N;
	int a[maxx];
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	int maxd = (int)(log(N)/log(2))+1;
	ll maxsum = -1e10-10;
	//2^(n-1)~2^n-1
	int ans = 1;
	for(int i=1;i<=maxd;i++){
		ll sum = 0;
		for(int j=(int)pow(2,i-1);j<=(int)pow(2,i)-1 && j<=N;j++){
			sum+=a[j];
		}
		if(maxsum<sum){
			maxsum=sum;
			ans = i;
		}
	}
	cout<<ans<<endl;
	return 0;
}

895最长上升子序列

模板中的模板

#include<iostream>
using namespace std;

const int maxx = 1e3+100;

int a[maxx];
int dp[maxx];

int main(){
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>a[i];
	}
	int ans = 0;
	for(int i=0;i<N;i++){
		for(int j=0;j<i;j++){
			if(a[i]>a[j]){
				dp[i]=max(dp[i],dp[j]+1);
				ans = max(ans,dp[i]);
			}
		}
	}
	cout<<ans+1<<endl;
	return 0;
}

1015摘花生

dp模板

#include<iostream>
using namespace std;
const int maxx = 110;

int m[maxx][maxx];
int main(){
	int T;
	cin>>T;
	while(T--){
		int R,C;
		cin>>R>>C;
		for(int r=1;r<=R;r++){
			for(int c=1;c<=C;c++){
				cin>>m[r][c];
			}
		}
		for(int r=1;r<=R;r++){
			for(int c=1;c<=C;c++){
				m[r][c] += max(m[r-1][c],m[r][c-1]);
			}
		}
		cout<<m[R][C]<<endl;
	}
	return 0;
}

1211蚂蚁感冒

首先可以把他那个倒转方向的操作，看做相互穿过
假如蚂蚁0往右走，那他右边的往左走的蚂蚁肯定会感冒，接着他左边的向右走的也会感冒
但是如果他右边没有往左走的，那他左边往右走的不会感冒
所以要特判一下
蚂蚁0往左走同理

#include<iostream>
using namespace std;
const int maxx = 60;
int a[maxx];
int main(){
	int N;
	cin>>N;
	cin>>a[0];
	//左右两边朝着第一只蚂蚁走的个数
	int left=0,right=0;
	for(int i=1;i<N;i++){
		cin>>a[i];
		//朝着第一只蚂蚁走的都可能会被干扰
		if(a[i]>0&&(abs(a[i])<abs(a[0]))){
			left++;
		}else if(a[i]<0&&(abs(a[i])>abs(a[0]))){
			right++;
		}
	}
	int ans = left+right+1;
	//左边没有朝着蚂蚁0且蚂蚁0往左走
	if(left==0 && a[0]<0){
		ans=1;
	}
	//右边没有朝着蚂蚁0且蚂蚁0往右走
	if(right==0 && a[0]>0){
		ans=1;
	}
	cout<<ans<<endl;
	return 0;
}

1216 饮料换购

#include<iostream>
using namespace std;

int main(){
	int a,b;
	int ans = 0;
	cin>>a;
	b=0;
	while(true){
		ans += a;
		b += a;
		a = b/3;
		b = b%3;
		if(a==0)break;
	}
	cout<<ans<<endl;
	return 0;
}

4867整除数

#include<iostream>
using namespace std;

typedef long long ll;

int main(){
	int n,k;
	cin>>n>>k;
	int m = n%k;
	if(m==0){
		cout<<n+k<<endl;
	}else{
		cout<<n+k-m<<endl;
	}
	return 0;
}

4867整除数

#include<iostream>
using namespace std;

typedef long long ll;

int main(){
	int n,k;
	cin>>n>>k;
	int m = n%k;
	if(m==0){
		cout<<n+k<<endl;
	}else{
		cout<<n+k-m<<endl;
	}
	return 0;
}

104货仓选址

取中位数，即左边和右边的货舱数量一致

#include<iostream>
#include<algorithm>
using namespace std;
const int maxx = 1e5+10;

int a[maxx];

int main(){
	int N;
	cin>>N;
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	sort(a+1,a+N+1);
	int addr;
	if(N%2){
		addr = a[N/2+1];
	}else{
		addr = (a[N/2]+a[N/2+1])>>1;
	}
	int ans = 0;
	for(int i=1;i<=N;i++){
		ans += abs(a[i]-addr);
	}
	cout<<ans<<endl;
	return 0;
}

1219移动距离

为了方便取余运算，减少心智压力，将所有的数都减一，即
1 2 3 4 5 6变为0 1 2 3 4 5

#include<iostream>
#include<algorithm>
using namespace std;

void get(int m,int w,int& r,int& c){
	int tmpr = m/w;
	int tmpc = m%w;
	if(tmpr%2){
		tmpc = w-tmpc-1;
	}
	r = tmpr;
	c = tmpc;
}

int main(){
	int w,m,n;
	cin>>w>>m>>n;
	m--;
	n--;
	//计算m的行和列
	int mr,mc,nr,nc;
	get(m,w,mr,mc);
	get(n,w,nr,nc);
	int ans = abs(mr-nr)+abs(mc-nc);
	cout<<ans<<endl;
	return 0;
}

1055股票买卖

#include<iostream>
using namespace std;

const int maxx = 1e5+10;

int dp[maxx][2];
int a[maxx];
int main(){
	int N;
	cin>>N;
	//不让dp[1][0]使用后者作为最大值
	dp[0][1]=-100000;
	for(int i=1;i<=N;i++){
		cin>>a[i];
		dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
		dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i]);
	}
	cout<<dp[N][0]<<endl;
	return 0;
}

1245特别数的和

简单枚举

#include<iostream>
using namespace std;

bool check(int i){
	bool res = false;
	while(i){
		int mod = i%10;
		if(mod==2||mod==9||mod==0||mod==1){
			res=true;
			break;
		}
		i/=10;
	}
	return res;	
}

int main(){
	int n;
	cin>>n;
	int sum=0;
	for(int i=1;i<=n;i++){
		if(check(i)){
			sum+=i;
		}
	}
	cout<<sum<<endl;
	return 0;
}

http://www.niftyadmin.cn/n/121622.html

相关文章

Tomcat服务器配置以及问题解决方案

Tomcat服务器配置以及问题解决方案

文章目录01 Tomcat简介02 Tomcat的安装03 Tomcat的使用启动Tomcat服务器 &#xff08;解决一闪而过&#xff09;测试 Tomcat 是否启动Tomcat 服务器的关闭04 Tomcat的配置配置端口控制台配置&#xff08;乱码解决&#xff09;部署工程到Tomcat中01 Tomcat简介 Tomcat是一款开源…
阅读更多...
Unity记录2.2-动作-动画、相机、Debug与总结

Unity记录2.2-动作-动画、相机、Debug与总结

文章首发及后续更新&#xff1a;https://mwhls.top/4453.html&#xff0c;无图/无目录/格式错误/更多相关请至首发页查看。 新的更新内容请到mwhls.top查看。 欢迎提出任何疑问及批评&#xff0c;非常感谢&#xff01; 汇总&#xff1a;Unity 记录 摘要&#xff1a;重写了动画触…
阅读更多...
Object.defineProperty() 详解

Object.defineProperty() 详解

一、对象的定义与赋值 我们经常使用的定义与赋值方法 obj.xxx value 或 obj[xxx] value&#xff0c;并且可以定义任意类型的值&#xff0c;如下所示&#xff1a; let obj {}; obj.name bjl; obj[age] 18; obj.sayHi function() {console.log(Hi)}; console.log(obj) /…
阅读更多...
【剑指Offer】JZ14--剪绳子

【剑指Offer】JZ14--剪绳子

剪绳子详解1.问题描述2.解题思路3.具体实现1.问题描述 2.解题思路 首先想到的思路&#xff1a;因为是求乘积的最大值&#xff0c;所以如果截取剩下的是1&#xff0c;那还是它本身就没有意义。从此出发&#xff0c;考虑绳子长度是2、3、4、5…通过穷举法来找规律。 值–》拆分–…
阅读更多...
AtCoder Beginner Contest 292 (A - E) 记录第一场ABC

AtCoder Beginner Contest 292 (A - E) 记录第一场ABC

AtCoder Beginner Contest 292 A - E前言Q1 A - CAPS LOCKQ2 Yellow and Red CardQ3 Four VariablesQ4 D - Unicyclic ComponentsQ5 E - Transitivity前言 本来晚上在打Acwing周赛&#xff0c;最后一题Trie想不出来咋写&#xff0c;看群里有人说ABC要开始了&#xff0c;想着没…
阅读更多...
C语言字符串

C语言字符串

目录 一、字符串的引入和注意事项 1.1 字符串定义的几种方式&#xff1a; 1.2 定义字符串的方法一和方法二的区别&#xff1a; 1.3 字符串输出的几种方式&#xff1a; 1.3.1 循环下标法遍历输出字符串&#xff1a; 1.3.2 转义字符%s输出字符串&#xff1a; 1.3.3 使用puts函…
阅读更多...
Java代码是如何被CPU狂飙起来的？

Java代码是如何被CPU狂飙起来的？

&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3; &#x1f38d;大家好&#xff0c;我是慕枫 &#x1f38d;前阿里巴巴高级工程师&#xff0c;InfoQ签约作者、阿里云专家博主&#xff0c;一直致力于用大白话讲解技术知识 &#x…
阅读更多...
Unity记录1.3-入门-第一阶段总结

Unity记录1.3-入门-第一阶段总结

文章首发及后续更新&#xff1a;https://mwhls.top/4447.html&#xff0c;无图/无目录/格式错误/更多相关请至首发页查看。 新的更新内容请到mwhls.top查看。 欢迎提出任何疑问及批评&#xff0c;非常感谢&#xff01; 汇总&#xff1a;Unity 记录 摘要&#xff1a;第一阶段的总…
阅读更多...
最新文章

Copyright @ 2022~2023