蓝桥杯基础知识2

1.哈希表

map哈希表默认按照升序来排序key，就是map<string,int>中string那一部分，系统排顺序就是依照他的升序

但是基于map实现的unorderede_map就是无序的

2.前缀和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll n, a[maxn], b[maxn];
int main()
{
    cin >> n;
    //预处理b数组
    for(int i = 1; i <= n; i++)
        cin >> a[i], b[i] = b[i - 1] + a[i];
    ll S = 0;
    //O(n)求解S
    for(int i = 1; i <= n; i++)
        S += a[i] * (b[n] - b[i]);
    cout<<S<<endl;
    return 0;
}

3.二分

满足某个条件使得一边均满足，另一边均不满足的，就是二分

4.整数与整除

符号^代表的是同时成立的意思

4.组合数公式

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

int C(int n, int m)
{
    if (m == 0) return 1;//此时组合数为0
    if (m == 1) return n;//此时组合数为n
    if (n == m) return 1;//此时组合数为1
    else return C(n - 1, m - 1) + C(n - 1, m);
}
int main()
{
    int t, n, m;
    cin >> t;
    while (t--)
    {
        int ans;
        cin >> n >> m;
        ans = C(n, m);
        cout << ans << endl;
    }
    return 0;
}

优先级

前缀和 差分

排序 贪心

标准库

填空

递归

dfs bfs