新一届暑期积分赛题目记录

原题位置忘了，自己造的数据，两题通过率均不超过0.15，但是是过人最多的两道，整体比赛出的有点失败。。

D.最近的商店（比赛中叫 不会吧不会有人觉得这不是签到吧）

Time limit：1 seconds

Memory limit：64 megabytes

​ 协会成员马上要入住算协小镇了！他们不想去一个离自己很远的商店，因此每个人都想知道离自己房子最近的商店有多远。

​ 他们向你求助，希望你能帮他们做一个标有商店距离的平面图。

​ 算协小镇上的房子严格按照$n\ast m$的点阵建造，其中分布有居民楼和商店，距离按照每个单元格进行计算(横与纵坐标差之和)。

输入

​ 第一行输入$n$和$m$，随后$n$行，每行$m$列，$1$代表商店，$0$代表居民楼。

输出

​ 输出一个$n\ast m$的矩阵，代表距离商店的平面图。(商店本身输出$0$)

保证

对于所有输入$x$(代指所有可能出现的输入)，都有$1\le x\le 999$

测试样例1

input

4 5
00001
00110
01100
00010

output

3 2 1 1 0
2 1 0 0 1
1 0 0 1 2
2 1 1 0 1

多源BFS模板题，若单个查找每个起点，其时间复杂度最大为$O((n\ast m{)}^2)$​，因此需要一次将所有起点加入队列进行BFS查找。

代码

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<string>
#include<queue>

using namespace std;

const int goin[4][2] = { 1,0,0,1,-1,0,0,-1 };
int n, m;
int num[1005][1005], vis[1005][1005], g[1005][1005];
queue<pair<int, int>>q;

bool pd(int x, int y) {
	return (x > -1 && y > -1 && x < n&& y < m);
}

pair<int, int> move(int x, int y, int i) {
	return {(x + goin[i][0]), (y + goin[i][1])};
}

void bfs() {
	while (!q.empty()) {
		auto [x, y] = q.front();
		q.pop();
		for (int i = 0; i < 4; i++){
			auto [x1, y1] = move(x, y, i);
			if (pd(x1, y1)){
			    if(!vis[x1][y1] && num[x1][y1] == 0) {
			    	vis[x1][y1] = 1;
				    q.emplace(x1, y1);
			    	g[x1][y1] = g[x][y] + 1;
			    }
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &num[i][j]);
			if (num[i][j] == 1) q.emplace(i, j);
		}
	}
	bfs();
	for (int i = 0; i < n; i++) {
		cout << g[i][0];
		for (int j = 1; j < m; j++) {
			cout << ' ' << g[i][j];
		}
		cout << endl;
	}
	return 0;
}

G.红烧羊排（比赛中 叫别说了别说了我真不是签到）

Time limit：1 seconds

Memory limit：32 megabytes

​ 红烧羊排想要过河。河非常的宽，每隔一米有一个落脚点。羊排每次可以有如下行动：

​ 【1】 每次可以走*$1$*米。

​ 【2】 每次可以走上一步的两倍距离。

​ 河的那边有陷阱，所以小羊排的最后一步必须恰好落在岸边，现在给你河宽*$n$*，请你求出羊排最少多少步可以过河。

输入

​ 第一行输入$t$，代表$t$个测试样例。

​ 之后t行，每行输入一个$n$，代表河宽。

输出

​ 对于每一行$n$，输出一个结果。

保证

$1\le t\le 1e6$

$1\le n\le 1e18$

测试样例1

input

10
1
2
3
4
5
6
7
8
9
10

output

1
2
2
3
4
4
3
4
5
5

测试样例2

input

6
1022
1023
1024
2046
2047
2048

output

18
10
11
20
11
12

​ 本题使用贪心的思想，每次走尽可能大的步数，若这一步的两倍要多于剩余距离，再从1开始走。

​ 数据量比较大，极限情况下若每走一步一计算，复杂度约为$1e9$乘一个常数，因此需要提前打表。

​ 因每一次是上一步的两倍，因此跳跃一次可当作$2^n-1$ ，此时$n$为这一次跳跃的步数。因$(2^n-1)\ast 2<2^n\ast 2-1$,每次跳跃的距离需要判断两次。

代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
typedef long long ll;

using namespace std;

int t, i, ans;
ll n, sic[70];

int main() {
	sic[0]=1;	
	for(i = 1; sic[i - 1] <= 1e18 / 2; i++){
		sic[i] = sic[i-1] * 2;
	}
	cin >> t;
	while(t--){
		scanf("%lld", &n);
		int j = i - 1; ans = 0;
		for( ; n && j > 0; j--){
			if(n >= sic[j] - 1){
				n -= (sic[j] - 1);
				ans += j;
				j++;
			}
		}
		printf("%dn", ans);
	}
	return 0;
}

最后

以上就是俭朴往事为你收集整理的新一届暑期积分赛题目记录的全部内容，希望文章能够帮你解决新一届暑期积分赛题目记录所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。