牛客周赛 Round 106（思维、RMQ、二分）-EW帮帮网

文章目录

牛客周赛 Round 106（思维、RMQ、二分）

牛客周赛 Round 106（思维、RMQ、二分）

A. 小苯的方格覆盖（思维）

思路

显然， $1 * 2$ 的小方格只能填满偶数列的矩阵。

code

# python

n = int(input())

if n % 2 == 0:
    print('YES')
else:
    print('NO')

// C++

#include<bits/stdc++.h>

using namespace std;

int main(){
    
    int n;
    cin >> n;
    
    if(n&1) cout << "NO" << endl;
    else cout << "YES" << endl;
    
    return 0;
}

B. 小苯的数字折叠（模拟）

思路

按题意模拟即可。

code

# python

ncase = int(input())

for _ in range(ncase):
    n, k = map(int, input().split())
    
    flag = -1
    for i in range(0, k+1):
        rn = int(str(n)[::-1])
        if n == rn:
            flag = i
            break
        elif i != k:
            n = n + rn
    
    print(n, flag)

// C++

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    
    int ncase;
    cin >> ncase;
    
    while(ncase--){
        ll n, k;
        cin >> n >> k;
        int flag = -1;
        for(int i = 0; i <= k; i++){
            ll rn = 0, x = n;
            while(x){
                rn = rn * 10 + x % 10;
                x /= 10;
            }
            if(rn == n){
                flag = i;
                break;
            }
            else if(i != k){
                n = n + rn;
            }
        }
        cout << n << " " << flag << endl;
    }
        
    return 0;
}

C. 小苯的波浪加密器（思维）

思路

乘积的个位数只和两个乘数的个位有关。so，对于 $[l 1, r 1]$ 和 $[l 2, r 2]$ 两个区间，每个区间内最多枚举十个数。

对于每次枚举，只需要验证 $a_3、a_4$ 是否合法即可。

注意， $n$ 可以等于 $3$ 。

注意， $a_i$ 的值可能大于 $MAX\_INT$ （ $in t$ 的最大值）。

code

# python

ncase = int(input())

for _ in range(ncase):
    n, l1, r1, l2, r2 = map(int, input().split())
    
    a = [0, 0] + [int(num) for num in input().split()]
    
    res = (-1, -1)
    for i in range(min(r1-l1+1, 10)):
        for j in range(min(r2-l2+1, 10)):
            ii = (l1 + i) % 10
            jj = (l2 + j) % 10
            if ii * jj % 10 != a[2]:
                continue
            elif n > 3 and jj * a[2] % 10 != a[3]:
                continue
            else:
                res = (l1 + i, l2 + j)
                break
            
        if res != (-1, -1):
            break
            
    print(res[0], res[1])

// C++

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 5e5 + 5;
ll a[maxn];

int main(){
    
    int ncase;
    cin >> ncase;
    
    while(ncase--){
        ll n, l1, r1, l2, r2;
        cin >> n >> l1 >> r1 >> l2 >> r2;
        for(int i = 3; i <= n; i++) cin >> a[i];
        
        a[1] = -1, a[2] = -1;
        
        ll a1, a2;
        for(int i = 0; i < 10; i++){
            if(l1 + i > r1) break;
            a1 = l1 + i;
            for(int j = 0; j < 10; j++){
                if(l2 + j > r2) break;
                a2 = l2 + j;
                
                if(a1 * a2 % 10 != a[3]) continue;
                if(n > 3 && a2 * a[3] % 10 != a[4]) continue;

                a[1] = a1;
                a[2] = a2;
                break;
            }
            if(a[1] != -1) break;
        }
        
        cout << a[1] << " " << a[2] << endl;
    }
    
}

D. 小苯的数字变换（思维）

思路

打表发现【经验】， $\oplus \lfloor\frac{x}{2}\rfloor$ 这个操作是存在循环节的，循环节的长度在 $l o g$ 级别。

故而，只需要在两个循环节中判断是否有相同的数，并统计最小的变换次数即可。

出题人给的证明：传送门

code

涉及位运算，只写了C++代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e5 + 5;
int a[maxn];

int main(){
    
	int ncase;
	cin >> ncase;
	
	while(ncase--){
		int n;
		cin >> n;
		for(int i = 1; i <= n; i++) cin >> a[i];
		int res = 0;
		for(int i = 1; i <= n; i++){
			int j = n + 1 - i;
			if(j <= i) break;
			int x = a[i], nx = 0, y = a[j], ny = 0;
			int flag = 0, mx = 2e9;
			while(1){    // 枚举 第一个数
				y = a[j], ny = 0;
				while(1){ // 枚举 第二个数
					if(x == y){    // 如果相同就记录最小次数
						flag = 1;
						mx = min(mx, ny + nx);
						break;
					} 
					y = y ^ (y / 2);
					ny++;
					if(y == a[j]) break;
				}
				x = x ^ (x / 2);
				nx++;
				if(x == a[i]) break;
			}
			if(flag) res += mx;
			else{
				res = -1;
				break;
			}
		}
		cout << res << endl;
	} 
	
    return 0;
}

E. 小苯的洞数组构造（思维）

思路

根据题意，显然只有 $8 、 4 、 0 、 1$ 是有意义的。 $【 2 、 3 、 4 、 5 、 7 】$ 没有价值， $【 6 、 9 】$ 没有 $4$ 划算。

$81$ 和 $811$ 的价值都是 $2$ ，但是 $811$ 的代价远大于 $81$ ，故而优先考虑低位。

从低位开始考虑，

个位先赋值成 $1$ （ $a_i>0$ 的要求），再考虑变成 $4$ （价值 $+ 1$ ，代价 $3$ ）和 $8$ （价值 $+ 2$ ，代价 $7$ ）。
- 注意是先变成 $4$ ，再考虑 $8$ ，直接变成 $8$ 是亏的。
- 如果在个位都不能令 $n$ 个数都为 $8$ ，其他位都不用考虑。
个位之后，对于第 $x$ 位（ $x > 1$ ，从右往左数），枚举每个元素 $a_i$ ，如 $s u m$ 有剩余，令 $a_i＋4*10^x$ 。所有 $a_i$ 的第 $x$ 位都为 $8$ 之后，令 $x = x + 1$ 。

code

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;
long long a[maxn];

int main(){
    
	int ncase;
	cin >> ncase;
	
	while(ncase--){
		long long n, sum;
		cin >> n >> sum;
		
		if(n > sum){	// sum < n 时，不满足 ai > 0 的条件
			cout << -1 << endl;
			continue;
		} 
		// 考虑个位
		for(int i = 1; i <= n && sum >= 1; i++) a[i] = 1, sum -= 1; 
		for(int i = 1; i <= n && sum >= 3; i++) a[i] += 3, sum -= 3;
		for(int i = 1; i <= n && sum >= 4; i++) a[i] += 4, sum -= 4;
		// 考虑个位之后，注意数据范围
		long long j = 10;
		while(1){
			if(sum < j * 4) break;	// 判断是否有剩余
			for(int i = 1; i <= n && sum >= j * 4; i++){ // 变为4
				a[i] += 4 * j;
				sum -= 4 * j;
			}
			for(int i = 1; i <= n && sum >= j * 4; i++){ // 变为8
				a[i] += 4 * j;
				sum -= 4 * j;
			}
			j = j * 10; // 下一位
		}

		for(int i = 1; i <= n; i++) cout << a[i] << " ";
		cout << endl;
		
	} 
	
    return 0;
}

F. 小苯的数组计数（RMQ、二分）

思路

结论：对于一个“美丽的子数组”，假设其区间为 $[x, y]$ ，且 $a_x < a_y$ 。则，对于任意的 $z > 0$ ，由 $[x, y + z]$ 构成的子数组不可能为“美丽的子数组”。

反证法：假设 $[x, y]$ 和 $[x, y + z]$ 均为 “美丽的子数组”。

因为 $[x, y]$ 是“美丽的子数组”，所以， $a_y > a_x$ 。

因为， $[x, y + z]$ 为“美丽的子数组”，根据规则3， $[x + 1, y + z - 1]$ 之间的元素都要小于 $a_x$ 。即 $a_y < a_x$ 。

前后矛盾，故而， $[x, y + z]$ 不能为“美丽的子数组”。

eg：【3、1、1、4、1、1、5】中【3、1、1、4】是一个“美丽的子数组”，【3、1、1、4、1、1、5】就不可能是一个美丽的子数组，4 > 3，违反规制3。

顺序遍历所有元素作为 $a_x$ ，判断是存在满足的 $a_y$ ，存在满足条件的 $a_y$ ，则令 $res = res + 1$ 。

对于 $a_x＞a_y$ 的情况，逆序遍历， $x 、 y$ 对调。

对于每一个 $a_x$ 查找满足的 $a_y$ 时，循环找的时间复杂度是 $O (n)$ ，综合时间复杂度就是 $O(n^2)$ ，包超时的。

优化这一过程，通过二分区间最大值的方式，找到第一个大于等于 $a_x$ 的元素。
详情参见代码，配合实例更容易理解。

RMQ问题自行百度学习即可。

为什么要找大于等于 $a_x$ 的第一个元素：

如果大于等于 $a_x$ 的第一个元素是等于 $a_x$ 的。对于当前 $a_x$ ，不存在“美丽的子数组”。 $【 3 ， 1 ， 1 ， 3 ， 4 】$
如果大于等于 $a_x$ 的第一个元素是大于 $a_x$ 的，该元素就是符合要求的 $a_y$ 。 $【 3 ， 1 ， 1 ， 2 ， 4 】$

code

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;
int a[maxn], f[maxn][20];

int RMQ(int l, int r){		// O(1) 查询
	if(l > r) return 0;
	int k = log((double)(r - l + 1)) / log(2.0);
	return max(f[l][k], f[r-(1<<k)+1][k]);
}

void init(int n){		// 预处理
	
	for(int i = 1; i <= n; i++) f[i][0] = a[i];
	
	int k = log((double)(n+1)) / log(2.0);
	for(int j = 1; j <= k; j++){
		for(int i = 1; i + (1<<j) - 1 <= n; i++){
			f[i][j] = max(f[i][j-1], f[i+(1<<j-1)][j-1]);
		}
	}
	
}

int main(){
    
	int ncase;
	cin >> ncase;
	
	while(ncase--){
		
		int n;
		cin >> n;
		for(int i = 1; i <= n; i++) cin >> a[i];
		
		init(n);
		
		int res = 0;
		for(int i = 1; i + 2 <= n; i++){
			int l = i+2, r = n, pos = -1;
			while(l <= r){	// 二分找到在【i+2,n】中，第一个大于等于 ai的数
				int mid = l + r >> 1;
				int mx = RMQ(i+2, mid);
				if(mx >= a[i]){
					pos = mid;
					r = mid - 1; 
				}
				else l = mid + 1;
			}
			if(pos != -1)
				res += (a[pos] > a[i] && a[i+1] < a[i]);  // 判断是否可以构成“漂亮的子数组”
		}
			
		
		for(int i = n; i - 2 >= 1; i--){	// 逆序
			int l = 1, r = i-2, pos = -1;
			while(l <= r){  // 二分找到在【1,i-2】中，第一个大于等于 ai的数
				int mid = l + r >> 1;
				int mx = RMQ(mid, i-2);
				if(mx >= a[i]){
					pos = mid;
					l = mid + 1; 
				}
				else r = mid - 1;
			}
			if(pos != -1)
				res += (a[pos] > a[i] && a[i-1] < a[i]); 
		}
	
		cout << res << endl;
		
	} 
	
    return 0;
}

牛客周赛 Round 106（思维、RMQ、二分）

文章目录