巅峰赛15官方题解

桌子乱的反义词

2024-12-05 13:36:21

发布于：浙江

44阅读

0回复

2点赞

巅峰赛15官方题解

T1

在题目给出的 $n$ 个数字之中，针对于 $h_1$ ，for循环枚举从左往右找到比他更大的第一个 $h_i$ 即，否则输出 $-1$ 。

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

int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for(int i = 0; i < n; i++) cin >> h[i];
  for(int i = 1; i < n; i++) {
    if(h[i] > h[0]) {
      cout << i + 1 << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

T2

题目并未要求计算出最小值，因此可以选择使用二维数组保存每项菜肴的营养价值和其对应的营养种类，然后针对于每一种营养种类的价值累加判断即可。

#include<bits/stdc++.h>
using namespace std;
int x[105][105];
int n, m;
int main(){
	scanf("%d%d", &n, &m);
	int a[100];
	for(int i=0; i<m; i++){
		scanf("%d", &a[i]);
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%d", &x[i][j]);
		}
	}
	for(int j=0; j<m; j++){
		int sum = 0;
		for(int i=0; i<n; i++){
			sum += x[i][j];
		}
		if(sum < a[j]){
			puts("No");
			return 0;
		}
	}
	puts("Yes");
  return 0;
}

T3.

当数组中所有的元素都是大于1的，那么一定合法，我们可以把前 $n - 1$ 个数全变成1，多出来的部分加到最后一个数上面。所以我们只需要考虑1的情况，我们可以令 $cnt1$ 代表1的个数， $cnt$ 代表非1的数和1的差值的和，我们只需要把 $cnt$ 分配给 $cnt1$ 个1即可。

例如

不合法的极端情况
```
4
1 1 1 3
```
这个样例不合法，因为3最多拿出2出来给前面的1，所以至少有一个1和之前一样。
合法的情况
```
4
1 1 1 4
```
这个样例是合法的，因为刚好可以从最后一个元素抽出3出来均匀分配给前面3个元素，使得数组中所有元素都不一样。

#include <bits/stdc++.h>
 #define int long long
using namespace std;
   
const int N = 200010;
int a[N], n, m, k;
 
void solve(){
    cin >> n;
    int cnt1 = 0, cnt = 0;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        if(a[i] == 1) cnt1 ++;
        else cnt += a[i] - 1;
    }
    if(cnt >= cnt1) cout << "^_^\n";
    else cout << ":-(\n";
}
 
signed main(){
    int tt = 1;
    cin >> tt;
    while(tt -- ){
        solve();
    }
    return 0;
}

T4

首先我们需要对 $d*_i$ 进行预处理，求得他在一个星期当中的实际变化数值，通过取 $d_*i$ mod $A+B$ 即可得出。

随后可以对其进行升序排列，去除重复项后得到序列 $E = {E*_1, E_*2,..., E_k}$ 。

如果答案为Yes，那么序列 $E$ 一定满足：存在一个 $i(1 \leq i \leq k)$ ，使得 $(E*_{i+1} - E_*i)$ mod $(A + B) > B$ ，边界值 $E*_{k + 1} = E_*1$ 。

我们可以尝试着枚举 $i$ 的取值，若满足即可输出Yes，否则输出No。

时间复杂度为: $O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
int A, B, n, x , y;
int a[1000005];
int _Mod(int x){
	if(x % (A + B)) return x % (A + B);
	else return A + B;
}
int main(){
	
	cin >> n >> A >> B ;
	int m = 0 ;
	for(int i = 1 ; i <= n ; i ++ ){
		cin >> a[i];
		a[i] = _Mod(a[i]);
	}
	sort(a + 1, a + n + 1);
	if(a[n] - a[1] + 1 <= A){
		cout << "Yes" << endl;
		return 0;
	}
	for(int i = 2 ; i <= n ; i ++ ){
		if(a[i] - a[i - 1] - 1 >= B){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

T5.

本题考虑分块做法。由于本题只有查询，所以我们可以想到离线做，我们只需要考虑两种情况：

1.当步长 $\geq sqrt(n)$ 的时候，那么每次只要走 $sqrt(n)$ 步就能走完，我们可以暴力走，最坏时间复杂度 $O(n\sqrt{n})$ 。
2.当步长 $\leq sqrt(n)$ 的时候，这样步长很小，暴力会超时，但是可以发现这样的步长的种类不是很多，我们可以按步长进行排序，虽然起点可能不一样，但是终点都是在最后一个长度为 $sqrt(n)$ 的块里面，所以我们可以从后往前推即可。这样的时间复杂度最坏也是 $O(n\sqrt{n})$ 。

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 300010;
int n, a[N], q, last = -1;
LL prex[N], ans[N];
vector<array<int,3>>que;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    int Block = sqrt(n);
    cin >> q;
    for(int i = 1; i <= q; i ++ ){
        int x, y; cin >> x >> y;
        que.push_back({x, y, i});
    }
    sort(que.begin(), que.end(),[&](array<int,3> A, array<int,3> B){
        return A[1] < B[1];
    });
    for(int i = 0; i < q; i ++ ){
        int b = que[i][1];
        int st = que[i][0];
        int idx = que[i][2];
        if(b >= Block){
            LL sum = 0;
            for(int j = st; j <= n; j += b){
                sum += a[j];
            }
            ans[idx] = sum;
        }else{
            if(last == b){
                ans[idx] = prex[st];
                continue;
            } 
            for(int j = n; j >= 1; j -- ){
                if(j + b > n) prex[j] = a[j];
                else prex[j] = prex[j + b] + a[j];
            }
            ans[idx] = prex[st];
            last = b;
        }
    }
    for(int i = 1; i <= q; i ++ ){
        cout << ans[i] << '\n';
    }
    return 0;
}

T6.

本题首先应该不难想到要用 $dp$ 来维护答案，我们令 $dp[i]$ 表示以第 $i$ 个数为结尾能得到的最大价值。那么

我们可以不断的枚举 $i$ 前面的下标 $j$ ，令 $S= a_j + a_{j + 1} +…… a[i]$ ，则有三种情况：

$S = 0$ ， $dp[i] = max(dp[i], dp[j])$
$S > 0$ ， $dp[i] = max(dp[i], dp[j - 1] + i - j + 1)$
$S < 0$ ， $dp[i] = max(dp[i], dp[j - 1] - i + j - 1)$

答案就是我们的 $dp[n]$

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

const int N = 500010;
int n;
int dp[N], a[N], sum[N];

signed main(){
	cin >> n;
	for(int i = 1; i <= n; i ++ ){
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
		dp[i] = -9e18;
	}
	for(int i = 1; i <= n; i ++ ){
		for(int j = 1; j <= i; j ++ ){
			int len = i - j + 1;
			if(sum[i] - sum[j - 1] > 0) dp[i] = max(dp[i], dp[j - 1] - j + i  + 1);
			else if(sum[i] - sum[j - 1] < 0) dp[i] = max(dp[i], dp[j - 1] + j - i  - 1);
			else dp[i] = dp[j - 1];
		}
	}
	cout << dp[n];
	return 0;
}

但是很明显，这样会超时，我们可以仔细观察那 $3$ 个式子，把 $i$ 和 $j$ 所在式子分离出来：

$S = 0$ ， $dp[i] = max(dp[i], dp[j])$
$S > 0$ ， $dp[i] = max(dp[i], dp[j - 1] - j + i + 1)$
$S < 0$ ， $dp[i] = max(dp[i], dp[j - 1] + j - i - 1)$

所以首先我们只需要将所有的前缀和当作下标，维护出 $dp[j], dp[j - 1] - j， dp[j - 1] + j$ 的最大值即可，维护这个最大值可以用树状数组或者线段树等数据结构，然后每次求 $dp[i]$ 的时候，只需要在对应的区间上求对应的最大值即可，假设当前前缀和 $s_i$ 离散后的下标为 $idx$ ：

考虑 $S = 0$ 的情况，只需要在 $[idx, idx]$ 中间找最大的 $dp[j]$ , $1 \leq j \leq i$
考虑 $S > 0$ 的情况，只需要在 $[idx + 1, n]$ 中间找 $dp[j] - j$ 的最大值
考虑 $S < 0$ 的情况，只需要在 $[1, idx - 1]$ 中间找 $dp[j] + j$ 的最大值

其次前缀会比较大，所以需要离散化。
时间复杂度 $O(nlogn)$

#include <bits/stdc++.h>
#define int long long
#define ls u << 1
#define rs u << 1 | 1
using namespace std;

const int N = 500010;
int a[N], dp[N], n, sum[N];

/*
维护 dp[j] - j, dp[j] + j, dp[j]的区间最大值
1 
*/
struct Node{
	int maxn;
}seg[4][N * 4];

vector<int>q;
int find(int x){
	return lower_bound(q.begin(), q.end(), x) - q.begin() + 1;
}
void pushup(int id, int u){
	seg[id][u].maxn = max(seg[id][ls].maxn, seg[id][rs].maxn);
}
void build(int id, int u, int l, int r){
	if(l == r){
		seg[id][u].maxn = -9e18;
		return;
	}
	int mid = l + r >> 1;
	build(id, ls, l, mid); build(id, rs, mid + 1, r);
	pushup(id, u);
}
void update(int id, int u, int l, int r, int pos, int val){
	if(l == r && l == pos){
		seg[id][u].maxn = max(seg[id][u].maxn, val);
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid) update(id, ls, l, mid, pos, val);
	else update(id, rs, mid + 1, r, pos, val);
	pushup(id, u);
}
int query(int id, int u, int l, int r, int ql, int qr){
	if(l == ql && r == qr) return seg[id][u].maxn;
	int mid = l + r >> 1;
	if(qr <= mid) return query(id, ls, l, mid, ql, qr);
	else if(ql > mid) return query(id, rs, mid + 1, r, ql, qr);
	else return max(query(id, ls, l, mid, ql, mid), query(id, rs, mid + 1, r, mid + 1, qr));
}
signed main(){
	cin >> n;
	for(int i = 1; i <= n; i ++ ){
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
		dp[i] = -9e18;
	}
	for(int i = 1; i <= n; i ++ ){
		q.push_back(sum[i]);
	}
	sort(q.begin(), q.end());
	q.erase(unique(q.begin(), q.end()), q.end());
	for(int i = 1; i <= 3; i ++ ){
		build(i, 1, 1, n + 1);
		update(i, 1, 1, n + 1, find(0), 0);
	}
	for(int i = 1; i <= n; i ++ ){
		int sum_idx = find(sum[i]);
		int x = query(1, 1, 1, n + 1, sum_idx, sum_idx);//区间和等于0的情况
		int y = -9e18;
		if(sum_idx - 1 >= 1) y = query(2, 1, 1, n + 1, 1, sum_idx - 1);//区间和大于0
		int z = -9e18;
		if(sum_idx + 1 <= n) z = query(3, 1, 1, n + 1, sum_idx + 1, n + 1);//区间和小于0
		dp[i] = max({dp[i], x, y + i, z - i});
		update(1, 1, 1, n + 1, sum_idx, dp[i]);
		update(2, 1, 1, n + 1, sum_idx, dp[i] - i);
		update(3, 1, 1, n + 1, sum_idx, dp[i] + i);
	}
	cout << dp[n];
	return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

巅峰赛15官方题解

T1

T2

T3.

T4

T5.

T6.

热门讨论