[牛客周赛 Round 51比赛链接](https://ac.nowcoder.com/acm/contest/86034)

A.小红的同余

题意

给一个**奇数**m，请你找出一个数` () 使得

思路

即 取余m等于1. 那么由于m是奇数， 很容易想到一个方案 ， 即

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int m;
	cin>>m;
	cout<<(m+1)/2;	
}
signed main(){
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

B.小红的三倍数

题意

给n个数，问是否存在一种方案，使得 **这n个数拼接之后是3的倍数**。

思路

这里要用到一个数学知识，即**x是3的倍数**等价于 **x的每一位相加的结果是3的倍数**。

如123 ，按位相加后 于是123是3的倍数。

所以我们不需要关心拼接的方案，只需要将每个数按位加和。 判断最终的总和是不是3的倍数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n;
	cin>>n;
	int ans =0;
	rep(i,1,n){
		string str;
		cin>>str;
		for(auto p : str){
			ans += (p - '0');
		}
	}
	if(ans%3 == 0) cout<<"YES\n";
	else cout<<"NO\n";
}
signed main(){
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

C.小红充电

题意

题目中的题意就很好懂，我这边直接粘贴下来

思路

如果当前的电量x小于超级充电的门槛电量t。 那么我们直接开启超级快充直到充满即可

如果当前的电量x大于超级充电的门槛电量t。 那么我们有两个选择

  1. 使用普通充电，耗时
  2. 先玩游戏使得电量等于门槛电量t，然后开始超级快充 ，耗时

最终答案为

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int x,y,t,a,b,c;
	cin>>x>>y>>t>>a>>b>>c;
	if(x <= t) {printf("%.8lf",(100 - x+0.0)/c);}
	else{
		double ans1 = 0;
		double ans2 = 0;
		ans1 = (100.0-x)/b;
		ans2 = (x-t+0.0)/y + (100.0-t)/c;
		printf("%.8lf",min(ans1,ans2));
	}
	return ;
}
signed main(){
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

D. 小红的 gcd

题意

求 , 其中

思路

本题考察辗转相除法。 即 因此我们计算出 之后， 再使用基本的就可以得出结果于是我们问题就变为了如何求 。

我们设a一共有n位，每一位为 。那么有

于是 .这样就可以保证运算过程中的数据始终在的范围内

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	string a;
	int b;
	cin>>a>>b;
	int aa = 0;
	for(auto p : a){
		aa = aa*10 + p - '0';
		aa %= b;
	}
	cout<<__gcd(aa,b)<<endl;
}
signed main(){
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

E.小红走矩阵

题意

有一个 的矩阵,小红从 undefined1,1)(n,n)$ ,定义一条路径的权值为**经过的所有点的最大值** . 请你找到**权值最小**的路径

思路

求某个东西的 **最小的最大值** .考虑二分答案 .

我们假设要找一条权值不大于的路径 , 那么显然 , 所有大于的点我们都不能走 , 所以在本次check中 , 将所有大于k的点都视为障碍物,使用bfs检查是否能从起点走到重点 , 若能则代表 , 否则

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int n;
bool vis[505][505];
int nextx[4] = {0,0,1,-1};
int nexty[4] = {1,-1,0,0};
int mp[505][505];
bool check(int mid){
	if(mp[1][1] > mid) return false;
	memset(vis,0,sizeof(vis));
	queue<PII> q;
	q.push({1,1});
	vis[1][1] = true;
	while(q.size()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if(x == n && y == n) return true;
		for(int i = 0;i<4;i++){
			int nx = x + nextx[i];
			int ny = y + nexty[i];
			if(nx < 1 || nx > n || ny < 1 || ny > n || vis[nx][ny]) continue;
			if(mp[nx][ny] > mid) continue;
			vis[nx][ny] = true;
			q.push({nx,ny});
		}
	}
	return false;
}
void solve(){
	cin >> n;
	for(int i =1;i<=n;i++){
		for(int j = 1;j<=n;j++) cin>>mp[i][j];
	}
	int l = 1,r = 1e9+5;
	while(l<r){
		int mid = (l+r) >> 1;
		if(check(mid)){
			r = mid;
		}else
		l = mid+1;
	}
	cout<<l;

}
signed main(){
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

F.小红的数组

题意

给n个数 , 以及q组询问 , 每次询问两个参数 , 问区间连续子段和的绝对值最大是多少 . 即有 , 求最大的 是多少

思路

先对a数组进行求前缀和,

于是求 就等价于求 , 而题目规定 , 那么我们只需要找到 ， 以及 , 二者进行相减即可得出答案。

对于求区间最大/最小值问题， 我们使用ST表即可。

注意使用cin和cout可能会超时，需要关闭IO同流。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int lg[500005];
int n;	
int a[500005];
int f1[500005][30];
int f2[500005][30];
void init(){
	lg[1] = 0;
	rep(i,2,500003) lg[i] = lg[i>>1]+1;
	rep(i,1,n) {
		f1[i][0] = a[i];
		f2[i][0] = a[i];
	}
	for(int j = 1;j<=lg[n+1];j++){
		for(int i = 0;i <= n-(1<<j)+1;i++){
			f1[i][j] = max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
			f2[i][j] = min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
		}
	}
}
void solve(){
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>a[i];
		a[i] += a[i-1];
	}
	init();
	int q;
	cin>>q;
	while(q--){
		int l, r;
		cin>>l>>r;
		l--;
		int log = lg[r-l+1];
		int ans = \
		max(f1[l][log],f1[r-(1<<log)+1][log])- \
		min(f2[l][log],f2[r-(1<<log)+1][log]);
		cout<<ans<<'\n';
	}
}
signed main(){
	IO;
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}