吴凡的题库——快快编程1801+

博主： WinRTAS
发布时间：2022 年 08 月 10 日
212 次浏览
暂无评论
768字数
分类：默认分类

## 1817. 马步
```
题目描述
中国象棋中的“马”走“日”字，我们要研究马在棋盘格里的行走规律。已知棋盘格共有10行9列个格点，马的起始位置为第r1行第c1列，目标位置是第r2行第c2列。请求出 从起点到目标格点的最少步数，若无法走到就输出-1。注意马不可以走出棋盘格范围。

```
```
输入输出格式
输入格式
输入文件horse.in 输入第一行为正整数r1, c1, r2, c2，其中r1, r2均在1到10的范围内，其中c1, c2均在1到9的范围内。
输出格式
输出文件horse.out 输出一个整数。
```
```
输入输出样例
输入样例#1:
1 1 1 2
输出样例#1:
3
说明：共3步：(1,1)->(3,2)->(2,4)->(1,2)
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
const int N=509;
struct Node{int x,y;};
int dx[8]={1,1,-1,-1,2,2,-2,-2};
int dy[8]={2,-2,2,-2,1,-1,1,-1};
bool vst[N][N];
int r1,c1,r2,c2,d[N][N]; 
int n=10,m=9;
void bfs(){
	queue<Node> q;
	vst[r1][c1]=1;
	d[r1][c1]=0;
	q.push((Node){r1,c1});
	while(!q.empty()){
		Node now=q.front();q.pop();
		for(int k=0;k<8;k++){
			int nx=now.x+dx[k],ny=now.y+dy[k];
			if(nx<1||nx>n||ny<1||ny>m)continue;
			if(vst[nx][ny])continue;
			vst[nx][ny]=1;
			d[nx][ny]=d[now.x][now.y]+1;
			q.push((Node){nx,ny});
		}
	}
	if(!vst[r2][c2])cout<<-1<<endl;
	else cout<<d[r2][c2]<<endl;
}
int main(){
	freopen("horse.in","r",stdin);
	freopen("horse.out","w",stdout);
	cin>>r1>>c1>>r2>>c2;
	bfs();
	return 0;
}
```

## 1857. 长方形面积
```
题目描述
请计算下面长方形的面积，结果保留2位小数。

长方形的面积计算公式：面积=长*宽

第一行输出第一个长方形的面积：长3，宽2，注意结果要保留2位小数

第二行输出第二个长方形的面积：长4，宽2.6，注意结果要保留2位小数

第三行输出第三个长方形的面积：长5.4，宽5.6，注意结果要保留2位小数

输入输出格式
输入格式
无
输出格式
见题目描述
```
```
输入输出样例
输入样例#1:
无
输出样例#1:
无
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	cout<<fixed<<setprecision(2)<<3.0 * 2.0<<endl;
	cout<<fixed<<setprecision(2)<<4.0 * 2.6<<endl;
	cout<<fixed<<setprecision(2)<<5.4 * 5.6<<endl;
	return 0;
}
```

## 1907. 最高的山
```
题目描述
有n座山，编号从1到n，第i座山的高度为hi，请问其中最高的山是哪一座？
```
```
输入输出格式
输入格式
第一行一个正整数n，表示山的数量，n<=1000。
第二行n个正整数，中间由空格隔开。山的高度不超过10000。
输出格式
一个正整数，最高的山最早出现的编号。
```
```
输入输出样例
输入样例#1:
5
1 2 3 4 6
输出样例#1:
5
输入样例#2:
5
6 4 3 2 1
输出样例#2:
1
输入样例#3:
无
输出样例#3:
无
```
```
#include<iostream>
using namespace std;
int main(){
	int n,high[10005],num;
	cin>>n;
	for(int i = 0;i < n;i++){
		cin>>high[i];
	}
	num = 0;
	for(int i = 0;i < n;i++){
		if(high[i] > high[num])
			num = i;
	}
	cout<<num + 1;
	return 0;
}
```

## 2084. 口算王
```
题目描述
口算大王就是你，几个数字间的四则运算对你来说就是小菜一碟。已知一条计算式子，请你回答出计算结果。例如：

3-5=-2

1+2*3=7

8-2*2-1=3

输入输出格式
输入格式
输入文件calculator.in 输入一行式子，包含若干非负整数，以及加号+减号-乘号*，不包含括号。至少有一个符号，所有数字均不超过100。
【数据规模】
10%数据， 全部数字都是1位数
10%数据， 恰有1个运算符号
10%数据， 恰有2个运算符号
100%数据， 最多有8个运算符号。
输出格式
输出文件calculator.out 输出一个整数，代表计算结果。
```
```
输入输出样例
输入样例#1:
3-5
输出样例#1:
-2
输入样例#2:
10-2*2-1
输出样例#2:
5
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
using namespace std;
stack<int> num;
stack<char> op;
void solve(){
	while(!op.empty()){
		char z=op.top();
		op.pop();
		int y=num.top();
		num.pop();
		int x=num.top();
		num.pop();
		if(z=='+')x+=y;
		else x-=y;
		num.push(x);
	}
}
int main(){
	freopen("calculator.in","r",stdin);
	freopen("calculator.out","w",stdout);
	int a,b;
	char c;
	cin>>a;
	num.push(a);
	while(cin>>c>>b){
		if(c=='*'){
			a=num.top();
			num.pop();
			a*=b;
			num.push(a);
		}
		else{
			solve();
			op.push(c);
			num.push(b);
		}
	}
	solve();
	cout<<num.top()<<endl;
	return 0;
}
```

## 2408. train-螺旋矩阵
```
题目描述
一个 n 行 n 列的螺旋矩阵可由如下方法生成：
从矩阵的左上角（第 1 行第 1 列）出发，初始时向右移动；如果前方是未曾经过的格子， 则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过 顺序，在格子中 依次填入 1, 2, 3, ... , n2，便构成了一个螺旋矩阵。

下图是一个 n = 4 时的螺旋矩阵。

11.png

现给出矩阵大小 n 以及 i 和 j，请你求出该矩阵中第 i 行第 j 列的数是多少。

输入输出格式
输入格式
输入共一行，包含三个整数 n，i，j，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。
对于 50%的数据，1 ≤ n ≤ 100;
对于 100%的数据，1 ≤ n ≤ 30,000，1 ≤ i ≤ n，1 ≤ j ≤ n。
输出格式
输出共一行，包含一个整数，表示相应矩阵中第 i 行第 j 列的数。
```
```
输入输出样例
输入样例#1:
4 2 3
输出样例#1:
14
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
说明
题目有O(1)的解法，用O(n)写出来的同学可以思考一下怎么优化
```
```
#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
    ios::sync_with_stdio(false);
    long long n,i,j,mi,ans=0;
    cin>>n>>i>>j;
    mi=min(i,min(j,min(n-i+1,n-j+1)));
    if(i<=j)ans=mi*(4*(n-1)-4*mi)+10*mi-4*n-3+i+j;
    else ans=mi*(4*n-4*mi)+2*mi+1-i-j;
    cout<<ans<<endl;
    return 0;
}
```
## 2438. train-排座椅
```
题目描述
上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来后，只
有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行的第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向通道，，
条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通  道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。

输入输出格式
输入格式
输入的第一行，有5个用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=1000,0<=K<M，0<=L<N，D<=2000）。
接下来D行，每行有4个用空格隔开的整数。第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置（Xi，Yi）与（Pi，Qi）的两个同学会交头接耳（输入保证他们前后相邻或者右相邻）。
输出格式
输出文件共两行。
第一行包含K个整数，a1 a2 ……ak，表示a1行和a1+1行之间、a2行和a2+1行之间、…、第ak行和第ak+1行之间要开辟通道，其中ai<ai+1，每两个整数之间用空格隔开（行 尾没有空格）。
第二行包含L个整数，b1 b2……bl，表示第b1列和b1+1列之间、第b2列和第b2+1列之间、…、第bl列和bl+1列之间要开辟通道，其中bi<bi+1，每两个整数之间用空格隔开（尾没有空格）。

如果有多种方案使得划分结果相同，取划分行号和列号最小的方案。
例如划分1、3、5列和划分1、5、6列都能让6对同学不交流，则选择最小的方案(1、3、5)。
```
```
输入输出样例
输入样例#1:
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
输出样例#1:
2
2 4
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
#define N 1003
using namespace std; 
int m,n,k,l,d,x[N],y[N],c[N],o[N],res[N],len=1;
int main(){
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d); 
    for(int i=1;i<=d;i++){ 
        int xi,yi,pi,qi; 
        scanf("%d%d%d%d",&xi,&yi,&pi,&qi); 
        if(xi==pi)x[min(yi,qi)]++;
        else y[min(xi,pi)]++;
    } 
    for(int i=1;i<=k;i++){
        int maxn=-1,p;
        for(int j=1;j<m;j++)
            if(y[j]>maxn){maxn=y[j];p=j;} 
        y[p]=0;c[p]++;
    } 
    for(int i=1;i<=l;i++){ 
        int maxn=-1,p;
        for(int j=1;j<n;j++)
            if(x[j]>maxn){maxn=x[j];p=j;} 
        x[p]=0;o[p]++; 
    } 
    for(int i=0;i<N;i++)if(c[i]&&i!=0)res[++len]=i;
    for(int i=1;i<len;i++)if(res[i]!=0)printf("%d ",res[i]);
    printf("%d
",res[len]);
	for(int i=1;i<=len;i++)res[i]=0;len=1; 
    for(int i=0;i<N;i++)if(o[i]&&i!=0)res[++len]=i;
    for(int i=1;i<len;i++)if(res[i]!=0)printf("%d ",res[i]);
    printf("%d
",res[len]);
    return 0; 
}
```

## 2667. 高手集训
```
题目描述
太戈编程团队聚集了本市众多的编程高手。你作为总教练，要为高手们安排集训计划。课程表里有连续的n天可以供你选择，每天都有专题课程。其中第i天的专题趣味程为h[i]。假设你选择了其中连续的若干天，从第l天到第r天。那么，

训练效果 = h[l]*1 + h[l+1]*2 + ... + h[r]*(r-l+1)

随着训练的深入进行，每天的趣味程度会得到更多倍数的效果。

目前有m种训练方案，每种方案由起始时间和结束时间来描述。请对每种方案输出训练效果。

输入输出格式
输入格式
输入文件training.in
输入第一行为正整数n和m, 均不超过100000。第二行为n个正整数代表每天专题的趣味程度，均不超过100000。随后共m行，每行为两个正整数l,r, 保证1<=l<=r<=n。   
输出格式
输出文件training.out
输出一行共m个整数,由空格隔开。
```
```
输入输出样例
输入样例#1:
3 2
5 6 7
1 3
2 3
输出样例#1:
38 20
【说明】5*1+6*2+7*3=38；6*1+7*2=20。
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
```
```
#include<bits/stdc++.h>
#define N 100003
#define int long long
using namespace std;
int h[N],s[N],g[N],n,m,l,r;
void input(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>h[i];
}
void solveBF(){
	for(int i=1;i<=m;i++){
		cin>>l>>r;
		int ans=0;
		for(int j=l;j<=r;j++)ans+=h[j]*(j-l+1);
		cout<<ans<<" ";
	}
}
void solve(){
	for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];
	for(int i=1;i<=n;i++)g[i]=g[i-1]+h[i]*i;
	for(int i=1;i<=m;i++){
		cin>>l>>r;
		cout<<g[r]-g[l-1]-(s[r]-s[l-1])*(l-1)<<" ";
	}
}
signed main(){
	freopen("training.in","r",stdin);
	freopen("training.out","w",stdout);
	input();
	if(n<=1000&&m<=1000)solveBF();
	else solve();
	return 0;
}
```

最后修改：2022 年 08 月 10 日