寒假思维训练计划day11

发布时间:2024年01月19日

?每日一题,这两天有事,断更了一天,今天补上,感觉状态也不太好,来道1500的题压压惊。


?宣传一下我总结的几个构造题模型,一点个人的浅薄见解:

??1、前后缀贪心,比如说观察前后缀的sum,去看以后怎么考虑最好。Problem - 1903C - Codeforces

2、双指针贪心法,考虑两端相消或者相互作用,还有就是考虑左右边界。? ?Problem - 1891C - Codeforces

Problem - 1907D - Codeforces

3、转换观察法,有些关系可以抽象成图,观察图的某些性质去总结规律。也可以抽象成一个集合,两个集合相等可以说明有解可构造。Problem - 1891C - Codeforces

4、打表找规律,一般没什么规律可循即可打表找规律,一般和数论有关的很喜欢考,acm也喜欢考,属于人类智慧题。Problem - 1916D - Codeforces

5、公式推导演算,常见的分为公式的等价变形、公式的化简(这个常考,一般需要先证明某些性质,可以直接抵消,一般如果原公式处理起来很复杂时就可以考虑)。Problem - 1889B - Codeforces

6、考虑奇偶数去简化问题或者分类问题,从其中的一些运算性质入手,因为奇数偶数的加减以及%运算(这个结论很重要)的结果的奇偶性是固定的,Problem - 1898C - Codeforces

7、根据性质构造模型,看看能不能分成几个块,几个不同的集合,再选择算法去解决。Problem - 1873G - Codeforces

8、考虑从小到大处理,或者是从大到小处理,有时候先处理小的对大的不会有影响,或者反过来,这样的处理顺序是最完美的。Problem - 1904D2 - Codeforces

9、边界贪心法,一般要在问题的最边界处考虑,有时候这样做结果是最优的,或者考虑边界上的影响,假如让影响最小,就使得影响<= 固定值 。???????Problem - E - Codeforces?and?Problem - 1903C - Codeforces



寒假每日一题(思维 + 贪心):Problem - C - Codeforces

题意: 给定一个长度为n的序列,元素给定,给出q个询问,每次需要求l到r的和,问可以重排数组使得所有询问的和最大的和是多少。

题解(证明):

已知有q个询问,a[1], a[2], a[3], ..., a[n]?给定。

设? ??Sum(l, r)? 为数组重排后l到r的结果,L[i], R[i]?: 是第i次询问的左边界和右边界,

1、\sum_{i = 1}^{q} Sum(L[i], R[i]) = \sum_{i = 1}^{q} a[1] + \sum_{i = 1}^{q} a[2] + ... + \sum_{i = 1}^{q} a[n]

2、设??Apear[i]? 为数组第i个位置出现的次数,value[i]?为重排后数组第i个位置的值

3、继续推导:

\sum_{i = 1}^{q} a[1] + \sum_{i = 1}^{q} a[2] + ... + \sum_{i = 1}^{q} a[n] = \sum_{i = 1}^{n} Appear[i] * value[i]

4、根据题中条件很显然可以得到Appear[i],那么让越大的Appear对应越大的a[i]就是最优解。

code:

#include <bits/stdc++.h> 
#define int long long 
#define ff first 
#define ss second 
using namespace std; 
using PII = pair<int, int>; 
using psi = pair<string,int>;
const int N = 1e6 + 10, inf = 0x3f3f3f3f; 
int n, m; 
int a[N], s[N];
void solve() { 
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i]; 
    sort(a + 1, a + 1 + n);
    while(m -- ) {
        int l, r; 
        cin >> l >> r; 
        s[l] ++, s[r + 1] --; 
    }
    
    for(int i = 1; i <= n; i ++ ) s[i] += s[i - 1];
    sort(s + 1, s + 1 + n);
    int l = n, ans = 0; 
    for(int i = n; i >= 1; i -- ) {
        if(!s[i]) break;
        ans += s[i] * a[l]; 
        l --; 
    }
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    
    int T = 1; 
    // cin >> T;
    while(T --) solve();
    
    return 0;
}

文章来源:https://blog.csdn.net/m0_74847145/article/details/135704936
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。