第三次周赛

A：初见组合数学

球在分叉点有两种情况，向左和向右；

由此可算出最底一层每个格子的情况，所有格子加起来为总情况；

每个格子的情况数除总情况即为答案；

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

void solve(){
    int n;
    cin >> n;
    vector<vector<int>> c(n + 1,vector<int>(n + 1));
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= i; j++){
            if (!j) c[i][j] = 1;
            else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; i++){
        ans += c[n][i];
    }
    for (int i = 0; i <= n; i++){
        double t =  c[n][i] / 1.0 / ans;
        cout << fixed << setprecision(3) << t << " ";
    }
    cout << endl;
    
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

B：最大子段和

从头向后遍历，将该处的值加入答案；

如果答案小于0，则这一段的贡献为负，直接抛弃即可，将答案重置为0；

遍历完的答案为最终结果；

想不通找学长（）；

#include<iostream>
using namespace std;
#define int long long
const int N = 2010; 
int n;
int a[N];

signed main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int ans = 0, res = 0;
    for (int i = 1; i <= n; i++){
        ans += a[i];
        res = max(res,ans);
        if (ans < 0) ans = 0;
    }
    cout << res << endl;
}

C：回文数组

顾名思义，头尾对应相等的数组是回文数组；

第一个对应最后一个，第二个对应倒数第二个........;

如果发现有不对应的，就不是；

全部检查完了没有问题就是回文数组；

#include<iostream>
using namespace std;
#define int long long
const int N = 1005;
int a[N];
int n;

signed main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int f = 1;
    for (int l = 1, r = n; l <= r; l++, r--){
        if (a[l] != a[r]){
            f = 0;
            break;
        }
    }
    if (f) cout << "YES" << endl;
    else cout << "NO" << endl;
}

D：变化的数

这两个操作都是让n变小的操作，如果操作到n小于m时，就可以不用再操作了；

可以发现/2和开根号都会让n迅速减小，所以完全可以将所有操作都模拟一遍；

比如先除2，再全开根号或先开根号再全除2等等操作；

此处需要用到dfs（深度优先搜索），没有了解的可以去查，自己学习一下；

将所有情况遍历完如果能等于m就输出yes，反之no；

#include<bits/stdc++.h>
using namespace std;
int n, m;

bool dfs(int x){
    if (x < m) return false;
    if (x == m) return true;
    int res = 0;
    res |= dfs(x / 2);
    res |= dfs(sqrt(x));
    return res;
}

signed main(){
    cin >> n >> m;
    int f = dfs(n);
    if (f) cout << "YES" << endl;
    else cout << "NO" << endl;
}

E：数矩形

可以先思考1*n的方格块以及1*m的方格块分别可以组成多少个矩形；

两者相乘就是答案；

想不明白可在群里问；

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

void solve() {
    int n, m;
    cin >> n >> m;
    cout << n * (n + 1) / 2 * m * (m + 1) / 2 << endl;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

F:刘学姐的差分数组

正常写的人一定会超时；可以自己算一下时间复杂度；

本题可以说是差分板子题，一定要补（）；

举个例子，有个数组全是零，现在我将l和r+1处分别变成1和-1；

求其前缀和（应该没有人不会了吧，不会快去补！），是不是可以发现只有l到r的前缀和是1；

其他部分前缀和都是0，这样是不是就把l到r标记了，而且时间复杂度为O（1）；

本题中前缀和cnt小于等于0时就代表没有被标记覆盖；

不明白的可以去查一下，很重要；

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

void solve() {
    int n,ans=0;
    cin >> n;
    vector<int> a(n + 2);
    int m; cin >> m;
    for (int i = 1; i <= m; i++){
        int l, r;
        cin >> l >> r;
        a[l] += 1, a[r + 1] -= 1;
    }    
    int cnt = 0;//前缀和
    for (int i = 0; i <= n; i++){
        cnt += a[i];
        if(cnt<=0) ans++;
    }
    cout << ans << endl;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

G:逆序对

二进制数组由01构成

可以想到1在0前面就是一个逆序对；

所以思路是先求出现有的逆序对个数；

然后对于每个位置都反转一下看谁的贡献最高；

最高贡献加现有个数就是答案；

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

void solve() {
    cin >> n;
    vector<int> a(n + 2), s1(n + 2), s2(n + 2);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int sum = 0, cnt = 0;
    for (int i = n; i >= 1; i--){
        if (a[i] == 0) cnt++;
        else sum += cnt;
    }
    int ans = sum;
    for (int i = 1; i <= n; i++){
        s1[i] = s1[i - 1] + (a[i] == 1);
    }
    for (int i = n; i >= 1; i--){
        s2[i] = s2[i + 1] + (a[i] == 0);
    }
    for (int i = 1; i <= n; i++){
        if (a[i] == 1) ans = max(ans, sum + s1[i - 1] - s2[i + 1]);
        if (a[i] == 0) ans = max(ans, sum + s2[i + 1] - s1[i - 1]);
    }
    cout << ans << endl;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

H：离散化

数据有点水，本来没人可以出的；

离散化是很重要的算法基础；

比如在1到1e18的范围，却只有很少的数，如果遍历一定会超时，这时候就要用离散化；

用处是将数集中起来，原本一个数和另一个数可能中间相隔很长，离散化可以让它们变得挨在一起；

这样就不会超时；

上网搜离散化板子，自行学习；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
typedef pair<int, int> PII;  
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;

int find(int x){
    int l = 0, r = alls.size() - 1;
    while (l < r){
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

signed main(){
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        int x, c;
        cin >> x >> c;
        add.push_back({ x, c });
        alls.push_back(x);
    }
    for (int i = 0; i < m; i++){
        int l, r;
        cin >> l >> r;
        query.push_back({ l, r });
        alls.push_back(l);
        alls.push_back(r);
    }
    //去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()),alls.end());

    for (auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }

    for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
    for (auto item : query){
        int l = find(item.first) , r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
}