当前位置：首页 > article >正文

蓝桥杯 2.基础算法

article 2025/2/22 22:38:28

蓝桥杯 2.基础算法

文章目录

蓝桥杯 2.基础算法
- 基础算法
- - 时空复杂度
  - 枚举
  - 模拟
  - 编程11-16
  - 递归
  - 编程17
  - 进制转换
  - 编程18-19
  - 前缀和
  - 编程20-22
  - 差分
  - 编程23-27
  - 离散化
  - 贪心
  - 编程28-37
  - 二分
  - 双指针
  - 编程38-45
  - 构造
  - 编程46-49
  - 位运算
  - 编程50-55
- 排序
- - 冒泡排序
  - 选择排序
  - 插入排序
  - 快速排序
  - 归并排序
  - 编程56-65

基础算法

时空复杂度

时间复杂度

算法执行时间随输入规模增长的增长率
常见的时间复杂度包括
- 常熟时间O(1)
- 线性时间O(n)
- 对数时间O(𝑙𝑜𝑔𝑛)
- 平方时间O(𝑛2)
在计算的时候应该关注复杂度的数量级, 并不要求严格的表达式
- 比如: 一个for()循环从1到n, 时间复杂度为O(n), 两个for()应该是O(2n), 但是关注的是数量级, 所以两个for()就是O(n)
一般关注的是最坏时间复杂度, 用O(f(n))表示, 大多时候只需要估算即可
一般来说, 评测机1秒大约可以跑2e8次运算, 我们要尽可能让我们的程序运算规模的数量级控制在1e8以内

空间复杂度

跟时间复杂度类似
题目一般不会卡空间, 一般是卡时间

分析技巧

基本操作: 算术运算(加法, 乘法, 位运算), 比较操作, 赋值操作
循环结构: for()循环1到n, O(n)
递归算法: 相对复杂
最坏情况: 需要考虑最坏情况下的执行时间
善用结论: 某些算法的复杂度已经被广泛使用

代码示例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAXN = 2e5 + 5;
ll a[MAXN];

ll calculateSum(vector<ll>& nums){
    ll sum = 0;
    for(auto num : nums){
        sum += num;
    } // 时间复杂度: O(n)
    return sum;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll n; cin >> n;
    vector<ll> nums(n);
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    } // 时间复杂度: O(n)
    
    ll sum = calculateSum(nums);
    cout << sum << "\n";
    return 0;
}
/*
    时间复杂度: O(n)
    O(2n) = O(n)
    
    注意:
        抓大头, 找到里面量级最大的
        O(n^2 + nlogn + n) = O(n^2)
*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAXN = 2e5 + 5;
ll a[MAXN];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll n; cin >> n;

    for(int i = 0; i < n; i++){
        for(int j = i; j <= n; j += i){
            
        } // 执行次数与i有关
    } // 时间复杂度: O(n)
    
    cout << sum << "\n";
    return 0;
}
/*
    时间复杂度: O(nlogn)
        n/i(i从1到n求和) 约等于 n*调和级数(1+1/2+1/3+...+1/n) 约等于 nlogn
*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAXN = 2e5 + 5;
ll a[MAXN];

ll fibonacci(ll n){ // 斐波那契数列
    if(n <= 1){
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll n; cin >> n;
    
    ll result = fibonacci(n);
    
    cout << n << ": " << result << "\n";
    return 0;
}
/*
    时间复杂度: O(2^n)
            n
      n-1     n-2
    n-2 n-3  n-3 n-4
    ..........
   1..........
        
    每个递归调用会产生两个额外的递归调用, 因此递归深度为2^n, 其中n为斐波那契数列的位置
*/

枚举

枚举介绍

将问题的接空间中的每个可能的解都枚举出来
适用于问题规模较小, 解空间可穷举的情况

解空间的类型

一个范围内的所有数字(或者二元数组, 字符串等), 或者满足某个条件的所有数字
也可以是解空间树, 分为子集数和排列数(回溯法)

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAXN = 2e5 + 5;
ll a[MAXN];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll n; cin >> n;
    ll sum = 0;
    for(int i = 1; i <= n; i++){
        ll num = i;
        while(num){
            ll digit = num % 10;
            num /= 10;
            if(digit == 2 || digit == 0 || digit == 1 || digit == 9){
                sum += i; 
                break;
            }
        }
    }
    cout << sum << "\n";
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAXN = 2e5 + 5;
ll a[MAXN];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll n; cin >> n;
    ll a, b, c; cin >> a >> b >> c;
    ll count = 0;
    for(int i = 1; i <= n; i++){
        if(i % a != 0 && i % b != 0 && i % c != 0){
            count ++;
        }
    }
    cout << count << "\n";
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAXN = 2e5 + 5;
ll a[MAXN];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll n, m; cin >> n >> m;
    map<ll, ll> mp;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ll num; cin >> num;
            mp[num]++;
        }
    }
    for(auto it : mp){
        if(it.second > n * m / 2){
            cout << it.first << "\n";
        }
    }
    return 0;
}

模拟

模拟介绍

通过模拟实际情况来解决问题
考察细心程度, 一般暴力求解即可, 不会卡时间复杂度
为了使得模拟题写的逻辑清晰一些, 经常写一些小函数来帮助解题, 例如int和string的相互转换, 回文串的判断, 日期的转换等等

例题讲解

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

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;

    cin >> n >> m;
    int a[n][m];    
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
             if(a[i][j] == 0){
                int count = 0;
                for(int ii = i - 1; ii <= i + 1; ii++){
                    for(int jj = j - 1; jj <= j + 1; jj++){
                        if(ii >= 0 && jj >= 0 && ii < n && jj < m && a[ii][jj] == 1){
                            count++;
                        }
                    }
                }
                cout << count << " ";
             } else {
                 cout << 9 << " ";
             }
        }
        cout << "\n";
    }
    
    
    return 0;
}

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

const int N = 120;
bool a[N][N], b[N][N];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n, m; cin >> n >> m;
    int t; cin >> t;
    
    
    for(int i = 0; i < t; i++){
        int r, c; cin >> r >> c;
        a[r - 1][c - 1] = 1;
    }
    
    int k; cin >> k;
    while(k--){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(a[i][j]){
                    b[i][j] = b[i - 1][j] = b[i + 1][j] = b[i][j - 1] = b[i][j + 1] = 1;
                }
            }
        }
        
        // 将b复制回a
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                a[i][j] = b[i][j];
            }
        }
    }
    
    int count = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j]){
                count++;
            }
        }
    }
    
    cout << count << "\n";
    return 0;
}

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


// 从string转换成int的函数
int s2i(string s){
    int ret = 0;
    for(const auto &i : s){
        ret = ret * 10 + i - '0'; // i - '0', 这里的i是一个字符, 字符-'0'得到的就是该字符的整数
    }
    return ret;
}

// 从int转换成指定位数的string的函数
string i2s(int x, int w){
    string ret;
    while(x){ // 987
        ret += (x % 10) + '0'; // (x%10) + '0', 这里的(x%10)是一个int, int+'0'得到的就是该int的字符
        x /= 10;
    }
    while(ret.length() < w){
        ret += '0';
    }
    reverse(ret.begin(), ret.end());
    return ret;
}


// 判断闰年的函数
bool runYear(int year){
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

// 判断日期是否合法的函数
bool isYear(int year, int month, int day){
    int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if(runYear(year)){
        days[1] = 29;
    }
    return day <= days[month - 1];
    
}

// 判断字符串是否是回文的函数
bool isPa(string s){
    for(int i = 0; i < s.length() / 2; i++){
        if(s[i] != s[s.length() - i - 1]){
            return false;
        }
    }
    return true;
}


// 判断字符串是否是ABABBABA型回文的函数
bool isPa2(string s){
    if(!isPa(s)){
        return false;
    }
    return s[0] == s[2] && s[1] == s[3];
}


int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    string s; cin >> s;
    int year = s2i(s.substr(0, 4)), month = s2i(s.substr(4, 2)), day = s2i(s.substr(6, 2));
    
    bool ans1 = false, ans2 = false;
    for(int i = year; i <= 9999; i++){
        for(int j = 1; j <= 12; j++){
            if(i == year && j < month){
                continue;
            }
            for(int k = 1; k <= 31; k++){
                if(i == year && j == month && k <= day){
                    continue;
                }
                
                if(!isYear(i, j, k)){
                    continue;
                }
                string date = i2s(i, 4) + i2s(j, 2) + i2s(k, 2);
                if(!ans1 && isPa(date)){
                    cout << date << "\n";
                    ans1 = true;
                }
                if(!ans2 && isPa2(date)){
                    cout << date << "\n";
                    ans2 = true;
                }
            }
        }
    }
    
    return 0;
}

编程11-16

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t; cin >> t;
    int n, k;
    int a[N];
    for(int i = 0; i < t; i++){
        cin >> n >> k;
        for(int j = 0; j < n; j++){
            cin >> a[j];
        }
        
        // 3
        // 5 2
        // 1 1 2 2 1
        // 6 2
        // 1 2 2 3 3 3
        // 5 2
        // 1 1 2 1 2 注意这组数据
        int ans = N;
        for(int j = 1; j <= 60; j++){ // 遍历所有目标颜色
            int cnt = 0; // 当前颜色需要的天数
            for(int m = 0; m < n;){ // 遍历所有房子
                if(a[m] != j){ // 如果当前的房子颜色不等于目标颜色
                    cnt++; // 需要涂漆
                    m += k; // 跳过长度为k的区间
                    continue;
                }
                m++; // 颜色相同, 继续下一个房子
            }
            ans = min(ans, cnt); // 更新最优天数
        }
        cout << ans << "\n";
    }


    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e8;

// 判断i是几位数
ll wei(ll i){
    ll count = 0;
    while(i){
        i /= 10;
        count++;
    }
    return count;
}

// 判断是否是偶数
bool isO(ll weiShu){
    return weiShu % 2 == 0;
}

// 判断i是否是幸运数字
bool isLucky(ll i, ll weiShu){
    ll ban = 1;
    weiShu /= 2;
    while(weiShu--){
        ban *= 10;
    }
    ll sum1 = 0, sum2 = 0;
    ll j = i % ban;
    ll k = i / ban;
    while(j){
        ll digit = j % 10;
        j /= 10;
        sum1 += digit;
    }
    while(k){
        ll digit = k % 10;
        k /= 10;
        sum2 += digit;
    }
    return sum1 == sum2;
}


int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll count = 0;
    ll weiShu;
    for(ll i = 10; i < N; i++){
        if(i % 10 == 0){
            weiShu = wei(i);
            if(isO(weiShu)){
                if(isLucky(i, weiShu)){
                    count++;
                }
            }
        } else {
            if(isO(weiShu)){
                if(isLucky(i, weiShu)){
                    count++;
                }
            }
        }
    }
    cout << count << "\n";
    return 0;
}




// 解析
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll f[10][40], g[10][40]; // f[数位][数位和]不含前导零, g[数位][数位和]可以含前导零


void calc(ll x){
    ll sum = 0;
    ll cnt = 0;
    while(x){
        sum += x % 10;
        x /= 10;
        cnt++;
    }
    f[cnt][sum]++;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    for(int i = 1; i <= 10000; i++){
        calc(i);
    }
    // DP动态规划思想, 这里还没学到
    for(int i = 1; i <= 4; i++){
        for(int j = 1; j <= 36; j++){
            g[i][j] = g[i - 1][j] + f[i][j];
        }
    }
    ll ans = 0;
    for(int i = 1; i <= 4; i++){
        for(int j = 1; j <= 36; j++){
            ans += f[i][j] * g[i][j];
        }
    }
    cout << ans << "\n"; // 4430091
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100;
int a[N] = {13, 1, 2, 3, 5, 4, 4, 2, 2, 2};

// 判断是否为闰年
bool isLeapYear(int year){
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

// 取出来每一位数并求和
int perNum(int num){
    int sum = 0;
    while(num){
        int digit = num % 10;
        num /= 10;
        sum += a[digit];
    }
    return sum;
}

// 求笔画
int biHua(int year, int month, int day){
    int sum = 0;
    if(month < 10){
        sum += 13;
    }
    if(day < 10){
        sum += 13;
    }
    sum += perNum(year);
    sum += perNum(month);
    sum += perNum(day);
    return sum;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int days[N] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int count = 0;
    // 年
    for(int i = 2000; i <= 2024; i++){
        if(isLeapYear(i)){
            days[1] = 29;
        } else {
            days[1] = 28;
        }
        if(i == 2024){
            // 月
            for(int j = 1; j <= 4; j++){
                // 日
                if(j == 4){
                    for(int k = 1; k <= 13; k++){
                        if(biHua(i, j, k) > 50){
                            count++;
                        }
                    }
                } else {
                    for(int k = 1; k <= days[j - 1]; k++){
                        if(biHua(i, j, k) > 50){
                            count++;
                        }
                    }
                }
            }  
        } else {
            // 月
            for(int j = 1; j <= 12; j++){
                // 日
                for(int k = 1; k <= days[j - 1]; k++){
                    if(biHua(i, j, k) > 50){
                        count++;
                    }
                }
            }   
        }
    }
    cout << count << "\n";
    return 0;
}




// 解析
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100;
int a[N] = {13, 1, 2, 3, 5, 4, 4, 2, 2, 2};

// 判断是否为闰年
bool isLeapYear(int year){
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int days[N] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int ans = 0;
    // 年
    for(int i = 20000101; i <= 20240412; i++){
        int year = i / 10000;
        int month = i / 100 % 100;
        int day = i % 100;
        if(month < 1 || month > 12){
            continue;
        }
        int p = isLeapYear(year) && month == 2;
        if(day < 1 || day > days[month] + p){
            continue;
        }
        int cnt = 0, i_ = i;
        while(i_){
            cnt += a[i_ % 10];
            i_ /= 10;
        }
        ans += cnt > 50;
    }
    cout << ans << "\n";
    return 0;
}

// 自己写的
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    string s; getline(cin, s);
    map<char, int> mp;
    vector<char> vec;
    for(int i = 0; i < s.length(); i++){
        mp[s[i]]++;
    }
    int maxCount = 0;
    for(auto it : mp){
        maxCount = max(maxCount, it.second);
    }
    for(auto it : mp){
        if(maxCount == it.second){
            vec.push_back(it.first);
        }
    }
    char minChar = 'z' + 1;
    for(auto it : vec){
        minChar = min(minChar, it);
    }
    cout << minChar << "\n";
    cout << maxCount << "\n";
    
    return 0;
}




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

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll cnt[128]; // 桶, 和ASCII码有关
    string s; getline(cin, s);
    
    for(int i = 0; i < s.length(); i++){
        cnt[s[i]] ++; // 每个字母对应出现的次数
    }
    
    ll index = max_element(cnt + 'a', cnt + 'z' + 1) - cnt; // max_element返回的是迭代器, 还需要减掉数组名得到下标
    
    cout << (char)(index) << "\n" << cnt[index] << "\n"; // 下标转换成char类型得到该字符, 通过下标找到字符对应出现的次数
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t; cin >> t;
    for(int i = 0; i < t; i++){
        int n; cin >> n;
        int a[N];
        int count = 0;
        int sum = 0; 
        for(int j = 0; j < n; j++){
            cin >> a[j];
            if(a[j] == 0){ // 有0则改为1, 同时count++, 次数为0的个数
                a[j] = 1;
                count++;
            }
            sum += a[j]; // 求和
        }
        if(!sum){ // 和为0则count++, 最多一次
            count++;
        }
        cout << count << "\n";
    }
    
    return 0;
}

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

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n; cin >> n;
    string a, b; cin >> a >> b;
    map<char, char> f = {
        {'A', 'T'},
        {'C', 'G'},
        {'G', 'C'},
        {'T', 'A'}
    };
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(f[a[i]] == b[i]){ // acgtg acgtc
            continue; // 如果当前字符配对正确, 跳过
        }
        bool swapped = false;
        // 尝试通过交换来修正错误
        for(int j = i + 1; j < n; j++){
            if(f[a[i]] == b[j] && f[a[j]] == b[i]){ // 交换的条件: 上下相等, 交错匹配
                swap(b[i], b[j]); // 交换
                ans++; // 增加交换次数
                swapped = true;
                break; // 如果交换成功, 跳出
            }
        }
        
        // 如果没有交换成功, 说明只能通过替换来修正
        if(!swapped){
            ans++; // 增加替换次数
        }
    }
    cout << ans << "\n";
    return 0;
}

递归

递归介绍

函数调用自己
两个关键要素
- 终止条件
- 递归表达式

递归和循环的比较

递归
- 可以处理复杂的数据结构和算法, 如树和图的遍历
- 存在栈溢出风险(栈空间一般只有8mb, 所以递归层数不宜过深, 一般不超过1e6层)
循环
- 效率高
- 适合处理大部分的动态规划问题

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
const ll p = 1e9 + 7;

// 带备忘录的递归, 将每次计算过的f(n)的值记录下来, 这样就可以提高递归的效率
ll dp[N];

ll f(ll n){
    if(dp[n]){
        return dp[n];
    }
    if(n == 1 || n == 2){
        return 1;
    }
    return dp[n] = (f(n - 1) + f(n - 2)) % p;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll n; cin >> n;
    for(int i = 1; i <= n; i++){
        cout << f(i) << "\n";
    }
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];


ll f(ll n){ // n表示当前的深度
    int ret = 1;
    for(int i = 1; i <= a[n  - 1] / 2; i++){
        a[n] = i;
        ret += f(n + 1);
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n; cin >> n;
    a[1] = n;
    cout << f(2) << "\n"; 
    
    return 0;
}

编程17

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

ll s(ll x){
    if(x == 0){
        return 1;
    } else if (x % 2 == 0){
        return s(x / 2);
    } else {
        return s(x - 1) + 1;
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll x; cin >> x;
    cout << s(x) << "\n";
    
    return 0;
}

进制转换

进制的本质

对于一个十进制数字, 比如说153, 其本质是每一个数位上的数字乘上这位上的权重, 即: $(1\times10^2) + (5\times10^1) + (3\times10^0)$
而二进制, 只不过是把10换成了2, 即: $(10011001)_2 = (1\times2^7)+(1\times2^4)+(1\times2^3)+(1\times2^0)$
在计算机中, 数字均通过二进制补码表示

将任意进制转换为十进制

假设给了一个数组来表示一个k进制(假设k>10)的整数

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N]= {1, 3, 10, 5, 7};

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll k; cin >> k;
    
    ll x = 0;
    for(ll i = 0; i < 5; i++){
        x = x * k + a[i];
    }
    cout << x << "\n";
    return 0;
}

将十进制转换为任意进制

假设现在有一个十进制数x, 将x转换成k进制, x先对k去模存放到一个数组中, 然后x再除等k, 即: a[i] = x % k, x /= k
将数组中的数反转, 得到的就是k进制的数

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll x; cin >> x; // 153
    ll k; cin >> k; // 2
    // vector实现
    // vector<ll> vec;
    // for(ll i = 0; x > 0; i++){
    //     vec.push_back(x % k);
    //     x /= k;
    // }
    // reverse(vec.begin(), vec.end());
    // for(auto it : vec){
    //     cout << it;
    // }
    
    // 数组实现
    ll cnt = 0;
    for(ll i = 0; x > 0; i++){
        a[cnt++] = x % k;
        x /= k;
    }
    reverse(a, a + cnt); // 注意: 存完之后需要反转一下
    for(ll i = 0; i < cnt; i++){
        cout << a[i];
    }
    return 0;
}

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    string s = "2021ABCD";
    
    for(int i = 0; i < s.length(); i++){
        if(s[i] >= '0' && s[i] <= '9'){
            a[i] = s[i] - '0'; // string(1-9) 转换成 int
        } else {
            a[i] = s[i] - 'A' + 10; // string(A-F) 转换成 int(10-15)
        }
    }
    ll x = 0;
    for(int i = 0; i < s.length(); i++){
        x = x * 16 + a[i];
    }
    cout << x << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  string s = "2022";
  for(int i = 0; i < s.length(); i++){
    a[i] = s[i] - '0';
  }
  ll x = 0;
  for(int i = 0; i < s.length(); i++){
    x = x * 9 + a[i];
  }
  cout << x << "\n";
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];
char ch[N] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  for(ll i = 0; i < t; i++){
    // 将n进制转换成十进制
    ll n, m; cin >> n >> m;
    string s; cin >> s;
    for(ll j = 0; j < s.length(); j++){
      if(s[j] >= '0' && s[j] <= '9'){
        a[j] = s[j] - '0';
      } else {
        a[j] = s[j] - 'A' + 10;
      }
    }
    ll x = 0;
    for(ll j = 0; j < s.length(); j++){
      x = x * n + a[j];
    }
    // 将十进制x转换成m进制
    string ans;
    while(x){
        ans += ch[x % m];
        x /= m;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
  }
  
  
  return 0;
}

编程18-19

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

ll ten2n(ll x, ll n){
  ll cnt = 0;
  while(x){
    a[cnt++] = x % n;
    x /= n;
  }
  reverse(a, a + cnt);
  return cnt;
}

ll sum(ll cnt){
  ll sum = 0;
  for(int i = 0; i < cnt; i++){
    sum += a[i];
  }
  return sum;
}

bool isOk(ll x){
  ll n = 2, m = 4;
  // 十进制转换成n进制
  ll cnt1 = ten2n(x, n);
  // 求和
  ll ret1 = sum(cnt1);
  
  // 十进制转换成n进制
  ll cnt2 = ten2n(x, m);
  // 求和
  ll ret2 = sum(cnt2);
  
  return ret1 == ret2;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll cnt = 0;
  for(ll i = 1; i <= 2024; i++){
    if(isOk(i)){
      cnt++;
    }
  }
  cout << cnt << "\n"; // 63
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, k; cin >> n >> k;
  ll sum = 0;
  for(ll i = 0; i < n; i++){
    cin >> a[i];
    sum += a[i];
  }
  if(sum % 2 != 0){
    cout << "Alice" << "\n";
  } else {
    cout << "Bob" << "\n";
  }
  
  return 0;
}

/*
	博弈论题:
		结论: 必败态的上一个状态(操作之前的状态)一定是必胜态
		本题: 奇数必胜, 偶数必败
*/

前缀和

前缀和原理和特点

prefix表示前缀和, 前缀和由一个用户输入的数组生成
对于一个数组a[] (下标从1开始), 我们定义一个前缀和数组prefix[], 满足: $p re f i x [i] = a [1] + a [2] + ... + a [i - 1] + a [i]$
prefix有一个重要的特性, 可以用于快速生成prefix: $p re f i x [i] = p re f i x [i - 1] + a [i]$
prefix可以O(1)的求数组a[]的一段区间的和: $s u m (l, r) = p re f i x [r] - p re f i x [l - 1]$
注意: prefix是一种预处理算法, 只适用于a数组为静态数组的情况下, 即a数组中的元素在区间和查询过程中不会进行修改

实现前缀和

利用它的特性

// 这里的数组下标均从1开始, a[0]=0
for(int i = 1; i <= n; i++){
    prefix[i] = prefix[i - 1] + a[i];
}

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll P = 1e9 + 7;
ll a[6][N], prefix[6][N];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[1][i];
    }
    for(int i = 2; i <= 5; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = a[i - 1][j] * a[1][j] % P;
        }
    }
    for(int i = 1; i <= 5; i++){
        for(int j = 1; j <= n; j++){
            prefix[i][j] = (prefix[i][j - 1] + a[i][j]) % P; // prefix特性
        }
    }
    ll l, r, k;
    for(int i = 1; i <= m; i++){
        cin >> l >> r >> k;
        cout << (prefix[k][r] - prefix[k][l - 1] + P) % P << "\n"; // sum(l, r) = prefix[r] - prefix[l-1], +P是因为前面的结果有可能是负数, 负数不能取模
    }
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll prefix[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  string s; cin >> s;
  for(ll i = 0; i < s.length(); i++){
    prefix[i] = prefix[i - 1] + (s[i] == 'L' ? 1 : -1);
  }
  ll mx = 0;
  for(ll i = 0; i < s.length(); i++){
    for(ll j = 0; j < s.length(); j++){
        if(prefix[j] - prefix[i - 1] == 0){
            mx = max(j - i + 1, mx);
        }
    }
  }
  cout << mx << "\n";
  
  return 0;
}

编程20-22

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll INF = 1e18 + 9;
ll pre_a[N], suf_a[N], pre_cost[N], suf_cost[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  vector<pair<ll, ll>> a(n + 2);
  for(ll i = 1; i <= n; i++){
    cin >> a[i].second >> a[i].first;
  }
  sort(a.begin() + 1, a.begin() + n + 1); // 将石头按照位置进行排序, 方便计算
  for(int i = 1; i <= n; i++){
      pre_a[i] = pre_a[i - 1] + a[i].second; // 表示前i堆石头的总重量
      pre_cost[i] = pre_cost[i - 1] + pre_a[i - 1] * (a[i].first - a[i - 1].first); // 表示将前i堆石头移动到第i堆位置的总费用
  }
  for(int i = n; i >= 1; i--){
      suf_a[i] = suf_a[i + 1] + a[i].second; // 表示后i堆石头的总重量
      suf_cost[i] = suf_cost[i + 1] + suf_a[i + 1] * (a[i + 1].first - a[i].first); // 表示将后i堆石头移动到第i堆位置的总费用
  }
  ll ans = INF; // 因为要求最小值, 所以这个值需要非常大
  for(ll i = 1; i <= n; i++){
    ans = min(ans, pre_cost[i] + suf_cost[i]); // 总费用取最小值
  }
  cout << ans << "\n";
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N], prefix[N];

void AC(){
  ll n, k; cin >> n >> k;
  for(ll i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  for(ll i = 1; i <= n; i++){
    prefix[i] = prefix[i - 1] + a[i]; // 1 2 5 6 10     1   1+2     1+2+5   1+2+5+6     1+2+5+6+10
  }
  ll l = 1, r = n - k, ans = 0;
  while(r <= n){
    ans = max(ans, prefix[r] - prefix[l - 1]);
    r++;
    l += 2; // l和r双指针
  }
  cout << ans << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  while(t--){
    AC();
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 5e5 + 5;
const ll INF = 1e18 + 5;
ll a[N], suf_mn[N];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    ll n; cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    suf_mn[n + 1] = INF;
    for(int i = n; i >= 1; i--){
        suf_mn[i] = min(suf_mn[i + 1], a[i]); // 后缀最小
    }
    stack<ll> stk;
    ll x = -INF, y, z;
    for(int i = 1; i <= n; i++){
        while(!stk.empty() && stk.top() < a[i]){
            x = max(x, stk.top());
            stk.pop();
        }
        stk.push(a[i]);
        z = a[i];
        if(z < x && suf_mn[i + 1] < z){ // t < z < x < y
            cout << "YES" << "\n";
            return 0;
        }
    }
    cout << "NO" << "\n";
    return 0;
}

/*
	对于231问题:
		使用单调栈解决
		出栈的元素一定小于栈内某个元素, 一定能找到x < y
		如果存在z < x, 那么就有z < x < y
	对于3421问题, 引入后缀最小即可解决
*/

差分

差分的原理和特点

对于一个数组a[], 差分数组diff[]的定义是: $d i ff [i] = a [i] - a [i - 1]$
对差分数组做前缀和可以还原为原数组 $d i ff [n] = a [n] - a [n - 1]$
- $d i ff [1] + d i ff [2] + d i ff [3] + ... + d i ff [i] = a [1] + (a [2] - a [1]) + (a [3] - a [2]) + ... + (a [i] - a [i - 1]) = a [i]$
利用差分数组可以实现快速的区间修改, 下面是将区间[l, r]都加上x的方法
- $d i ff [l] + = x;$
- $d i ff [r + 1] - = x;$
- 在修改完成后, 需要做前缀和恢复为原数组

例题讲解

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], diff[N];

void solve(int n, int m){
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    diff[i] = a[i] - a[i - 1];
  }
  for(int i = 1; i <= m; i++){
    int x, y, z; cin >> x >> y >> z;
    diff[x] += z;
    diff[y + 1] -= z;
  }
  // 前缀和 还原
  for(int i = 1; i <= n; i++){
    a[i] = a[i - 1] + diff[i]; // 这里把a[i]当成前缀和数组, 把diff[i]当成原数组
  }
  for(int i = 1; i <= n; i++){
    cout << a[i] << " \n"[i == n]; // i == n时换行, 不等于时输出空格
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  
  int n, m; 
  while(cin >> n >> m){
    solve(n, m);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N], diff[N];

void solve(ll n, ll q){
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    diff[i] = a[i] - a[i - 1];
  }
  for(int i = 1; i <= q; i++){
    ll x, y, z; cin >> x >> y >> z;
    diff[x] += z;
    diff[y + 1] -= z;
  }
  // 前缀和 还原
  for(int i = 1; i <= n; i++){
    a[i] = a[i - 1] + diff[i]; // 这里把a[i]当成前缀和数组, 把diff[i]当成原数组
  }
  for(int i = 1; i <= n; i++){
    cout << (a[i] < 0 ? 0 : a[i]) << " \n"[i == n]; // i == n时换行, 不等于时输出空格. a[i]为负数时输出0
    // cout << max(0ll, a[i]) << " \n"[i == n]; // i == n时换行, 不等于时输出空格, 0ll表示ll类型的0, 取0ll和a[i]的最大值
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  
  ll n, q; 
  while(cin >> n >> q){
    solve(n, q);
  }
  return 0;
}

编程23-27

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N], diff[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, q; cin >> n >> q;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    diff[i] = a[i] - a[i - 1];
  }
  for(int i = 1; i <= q; i++){
    ll l, r, c; cin >> l >> r >> c;
    diff[l] += c;
    diff[r + 1] -= c; 
  }
  // 前缀和还原
  for(int i = 1; i <= n; i++){
    a[i] = a[i - 1] + diff[i];
  }
  for(int i = 1; i <= n; i++){
    cout << a[i] << " \n"[i == n];
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3 + 5;
ll a[N][N], diff[N][N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, m, q; cin >> n >> m >> q;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cin >> a[i][j];
    }
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      diff[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
    }
  }
  for(int i = 1; i <= q; i++){
    ll x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c;
    diff[x1][y1] += c;
    diff[x1][y2 + 1] -= c; 
    diff[x2 + 1][y1] -= c;
    diff[x2 + 1][y2 + 1] += c; 
  }
  // 前缀和还原
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + diff[i][j];
    }
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cout << a[i][j] << " ";
    }
    cout << "\n";
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N], diff[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, w; cin >> n >> w;
  for(int i = 1; i <= n; i++){
    ll s, t, p; cin >> s >> t >> p;
    diff[s] += p;
    diff[t] -= p; // 左闭右开, 不需要+1
  }
  // 前缀和还原
  a[0] = diff[0]; // 坑: 数组从0开始, 所以需要把0位置手动赋值
  for(int i = 1; i <= N - 5; i++){
    a[i] = a[i - 1] + diff[i];
  }
  cout << (*max_element(a, a + N - 4) <= w ? "Yes" : "No") << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 3e5 + 5;
ll a[N], diff[N], l[N], r[N], f1[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, m; cin >> n >> m;
  // 1. 差分
  for(int i = 1; i <= m; i++){
    cin >> l[i] >> r[i];
    diff[l[i]] += 1;
    diff[r[i] + 1] -= 1;
  }
  // 2. 看区间内0和1的个数(使用前缀和)
  ll c0 = 0;
  for(int i = 1; i <= n; i++){
    a[i] = a[i - 1] + diff[i];
    if(a[i] == 0){
      c0++;
    }
  }
  for(int i = 1; i <= n; i++){
    if(a[i] == 1){
      f1[i] = f1[i - 1] + 1;
    } else {
      f1[i] = f1[i - 1];
    }
  }
  
  for(int i = 1; i <= m; i++){
    cout << f1[r[i]] - f1[l[i] - 1] + c0 << "\n";  
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e3 + 5;
ll a[N][N], diff[N][N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, m; cin >> n >> m;
  for(int i = 1; i <= m; i++){
    ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    diff[x1][y1]++;
    diff[x1][y2 + 1]--;
    diff[x2 + 1][y1]--;
    diff[x2 + 1][y2 + 1]++;
  }
  for(int i = 1; i <= m; i++){
    for(int j = 1; j <= n; j++){
      a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + diff[i][j];
      if(a[i][j] % 2 != 0){
        cout << 1;
      } else {
        cout << 0;
      }
    }
    cout << "\n";
  }
  
  return 0;
}

离散化

离散化简介

把无限空间中有限的个体映射到有限的空间中去
离散化是一种将数组的值域压缩, 从而更加关注元素的大小关系的算法
离散化数组要求内部是有序的(一般是去重的), 可以直接通过离散化下标得到值

离散化的实现方法

离散化的实现方法有很多, 但是原理都相同, 这里使用vector来进行离散化

代码示例

离散化不会单独考察, 一般会结合其他算法或数据结构一起考察, 例如树状数组, 线段树, 二维平面的计算几何等.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N];
vector<int> L;

// 返回x再L中的下标
int getIndex(int x){
    return lower_bound(L.begin(), L.end(), x) - L.begin();
}


int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    // 存入到L中
    for(int i = 1; i <= n; i++){
        L.push_back(a[i]);
    }
    
    // 排序
    sort(L.begin(), L.end());
    // 去重
    L.erase(unique(L.begin(), L.end()), L.end());
    // 打印
    cout << "离散化后的数组: ";
    for(const auto &it : L){
        cout << it << " ";
    }
    cout << "\n";
    
    int x; cin >> x;
    cout << getIndex(x) << "\n";
    return 0;
}

贪心

贪心算法介绍

基本原理: 每一步都选择局部最优解, 而尽量不考虑对后续的影响
局限性: 不能保证获得全局最优解
特性: 贪心选择性质, 最优子结构性质
贪心的类型多且杂, 需要不断练习和积累

贪心算法实现步骤

确定问题的最优子结构
构建贪心选择的策略, 可能通过分类讨论, 最小代价, 最大价值等方式来思考贪心策略

常见贪心模型和例题

简单排序模型

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll INF = 1e18 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  ll ans = a[2] - a[1];
  for(int i = 1; i < n; i++){
    ans = min(ans, a[i + 1] - a[i]);
  }
  cout << ans << "\n";

  return 0;
}

最小代价模型

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  priority_queue<ll, vector<ll>, greater<ll>> pq;
  for(int i = 1; i <= n; i++){
    ll x; cin >> x;
    pq.push(x);
  }// 1 3 5 9
  ll ans = 0;
  while(pq.size() >= 2){
    ll x = pq.top(); pq.pop();
    ll y = pq.top(); pq.pop();
    ans += x + y;
    pq.push(x + y);
  }
  cout << ans << "\n";
  
  return 0;
}

最少数目模型

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll w; cin >> w;
  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n); // 2 2 3 5 6 7 8 9 9
  ll ans = 0;
  ll l = 1, r = n;
  while(l <= r){
    ans++;
    if(l == r){
      break;
    }
    if(a[l] + a[r] <= w){
      l++;
    }
    r--;
  }
  cout << ans << "\n";

  
  return 0;
}

找规律的贪心

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e6 + 5;
char s[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, x; cin >> n >> x;
  cin >> s + 1;
  sort(s + 1, s + 1 + n); // aabccd

  if(s[1] == s[n]){ // 字符串全相等(假设全是a), 则尽量使得每个人分到的字符串的最大长度尽可能小(aa, aa, aaa)
    for(int i = 1; i <= n / x + (n % x ? 1 : 0); i++){
      cout << s[i];
    }
  } else if(s[1] == s[x]){ // 
    for(int i = x; i <= n; i++){
      cout << s[i]; // (aaabbbccc), 假如s[x]为最后一个a, 则(a, a, abbbccc), 此时s[x~n]为最大
    }
  } else if(s[1] != s[x]){ // s[1]!=s[x], s[x]后面一坨字符可以直接丢到s[1]后面, 分给第一个同学, 此时s[x]就是最大的
    cout << s[x]; // (aaabbbcccddd), 假如s[x]为第一个c, 则(accddd, a, a, b, b, b, c), 此时s[x]即c为最大
  }
  
  return 0;
}

编程28-37

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N], b[N], c[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, k; cin >> n >> k;
  k = min(k, n);
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    cin >> b[i];
    c[i] = max(b[i] - a[i], 0ll); // 如果上方的小于下方的, 则将差值给c
  }
  sort(c + 1, c + 1 + n, greater<ll>()); // 降序
  
  cout << accumulate(a + 1, a + 1 + n, 0ll) + accumulate(c + 1, c + 1 + k, 0ll) << "\n"; // 上方的和 + 翻转之后差值的和

  
  return 0;
}

29最小战斗力差距, 上面已经写过了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll INF = 1e18 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  ll mn = INF, mx = -INF, ans = 0;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    a[i] = abs(a[i]); // 取绝对值
    if(i % 2 != 0){
      mn = min(mn, a[i]); // 奇数项求最小值
      ans += a[i]; // 奇数项+
    } else {
      mx = max(mx, a[i]); // 偶数项求最大值
      ans -= a[i]; // 偶数项-
    }
  }
  if(mx > mn){
    cout << ans + 2 * mx - 2 * mn << "\n"; // 交换a1和a2, 原本:a1-a2, 变成0:-a1+a2, 交换:a2-a1
  } else {
    cout << ans << "\n"; // mx>mn才交换, 否则不交换
  }
  
  

  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, k; cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n);
  ll i, ans = 0;
  for(i = 1; k >= 0 && i <= n; i++){ // 预算必须大于等于0
    ans++;
    if(k - a[i] < 0){ // 预算-价格<0则提前跳出
      break;
    }
    k -= a[i]; // 预算-商品价格
  }
  if(k - (a[i] + 2 - 1) / 2 < 0){ // 预算-打折(向上取整)还是小于0则数量--
    ans--;
  }

  cout << ans << "\n";  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

ll same_count(){ // 计算有多少个相同的数
  map<ll, ll> mp;
  ll ret = 0;
  for(int i = 1; i <= 4; i++){
    mp[a[i]]++;
    ret = max(ret, mp[a[i]]);
  }
  return ret;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> a[1] >> a[2] >> a[3] >> a[4];
  sort(a + 1, a + 1 + 4); // 1 3 3 4
  
  if(same_count() >= 3){ // 相同的数为3或者4的情况
    if(a[1] < a[2]) { // 后三个相同
      cout << a[1] + a[2] * 2 << "\n";
    } else{ // 前三个相同
      cout << a[4] + a[1] * 2 << "\n";
    }
    return 0;
  }

  // 两个相同或者四个不同的情况
  a[4] += 2 * a[1];
  a[2] -= a[1];
  a[3] -= a[1];
  a[4] += a[2] / 3 * 3;
  
  if(a[2] % 3 == 2){
    a[4]++;
  }
  cout << a[4] << "\n";
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n, greater<ll>()); // 降序
  vector<ll> tmp; // 存放偶数个的时候的和
  ll sum = 0;
  for(int i = 1; i <= n; i++){
    sum += a[i];
    if(i % 2 == 0){ // 必须是偶数个
      tmp.push_back(sum); // 存到里面
    }
  }
  cout << *max_element(tmp.begin(), tmp.end()) << "\n"; // 找到这个当中的最大值

  
  return 0;
}

// 首先是所有村庄的最大任务都需要被解决, 我们尽可能让一个大于等于最大任务且花费代价最小(lower_bound())的勇士去一次性解决.
// 不断重复上述过程, 知道结束(求和)或者没用勇士能够解决(-1)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
multiset<ll> st;
priority_queue<ll> pq[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll m, n; cin >> m >> n;
  for(int i = 1; i <= m; i++){
    ll x; cin >> x;
    st.insert(x); // 默认升序
  }
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    ll k; cin >> k;
    for(int j = 1; j <= k; j++){
      ll x; cin >> x;
      pq[i].push(x); // 默认为大根堆(降序)
    }
  }
  while(1){
    ll mx = -1;
    for(int i = 1; i <= n; i++){
      if(pq[i].empty()){
        continue;
      }
      mx = max(pq[i].top(), mx);
    }
    if(mx == -1){ // pq中没有元素
      break;
    }
    if(st.empty()){
      cout << -1 << "\n";
      return 0;
    }
    auto index = st.lower_bound(mx); // lower_bound如果没有找到则返回end()
    if(index == st.end()){ // 表示找了一圈没有找到
      cout << -1 << "\n";
      return 0;
    }
    ans += *index; // 加上迭代器对应的值
    st.erase(index); // 操作完成之后删除该值
    for(int i = 1; i <= n; i++){
      if(pq[i].empty()){
        continue;
      }
      pq[i].pop(); // 所有的最大任务都弹出
    }
  }
  cout << ans << "\n";
  return 0;
}

// 扰动法证明贪心, 结论:
// 总时相同, 交换对ans不产生影响
// 总时不同, 总时小的放在前面更优

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;

bool cmp(pair<ll, ll> xx, pair<ll, ll> yy){
  return xx.first + xx.second < yy.first + yy.second; // 结构体排序
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  vector<pair<ll, ll>> a;
  for(int i = 1; i <= n; i++){
    ll x, y, z;
    cin >> x >> y >> z;
    a.push_back({x + y, z});
  }
  sort(a.begin(), a.end(), cmp);
  ll ans = 0, sum = 0;
  for(int i = 0; i < n; i++){
    ans += a[i].first + sum;
    sum += a[i].first + a[i].second;
  }
  cout << ans << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll INF = 1e18 + 5;

bool cmp(pair<ll, ll> xx, pair<ll, ll> yy){
  return xx.second < yy.second;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, s; cin >> n >> s;
  vector<pair<ll, ll>> a(n + 1, {0, 0});
  ll mx_cnt = 0, sum_cost = 0, index = 1;
  for(int i = 1; i <= n; i++){
    cin >> a[i].first >> a[i].second;
    mx_cnt = max(mx_cnt, a[i].second);
    sum_cost += a[i].first;
  }
  sort(a.begin() + 1, a.begin() + 1 + n, cmp);

  ll ans = 0;
  for(int i = 1; i <= mx_cnt; i++){
    while(index <= n && a[index].second < i){
      sum_cost -= a[index].first;
      index++;
    }
    ans += min(s, sum_cost);
  }
  cout << ans << "\n";
  return 0;
}

// 从后往前考虑, 从x天开始, 考虑没有过期并且价格便宜并且没有买到上限, 那么我们就买, 没有我们就买不了(-1)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll INF = 1e18 + 5;
struct node{
  ll a, b, c; // 单价, 保质期, 购买次数
} qwq[N];
bool operator < (node xx, node yy){
  return xx.b > yy.b;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll x, n; cin >> x >> n;
  for(int i = 1; i <= n; i++){
    cin >> qwq[i].a >> qwq[i].b >> qwq[i].c;
  }

  sort(qwq + 1, qwq + 1 + n); // 对保质期排序

  priority_queue<ll, vector<ll>, greater<ll>> pq; // 小根堆, 当前没有过期的巧克力的最小价格的堆

  ll index = 1, ans = 0;

  map<ll, ll> cnt, dq; // cnt表示价钱最多可以买的数量, dq表示当前已经买了的数量

  for(int Time = x; Time >= 1; Time--){
  
    while(index <= n && qwq[index].b >= Time){
      pq.push(qwq[index].a);
      cnt[qwq[index].a] += qwq[index].c;
      index++;
    } // 先把在保质期内的巧克力丢到堆里去
  
    while(pq.size() && cnt[pq.top()] == dq[pq.top()]) pq.pop(); // 如果巧克力买到了上限
  
    if(pq.empty()){
      cout << -1 << "\n";
      return 0;
    } // 没有巧克力买
  
    dq[pq.top()]++;
    ans += pq.top();
  }
  
  cout << ans << "\n";
  return 0;
}

二分

上面已经讲过了

双指针

双指针简介

通常用在数组或字符串中进行快速查找, 匹配, 排序或移动等
双指针并非真的用指针实现, 一般用两个变量来表示下标

对撞指针

指的是两个指针left, right(简写为l, r)分别指向序列第一个元素和最后一个元素
l指针不断递增, r不断递减, 直到两个指针碰撞或错开(即l >= r)为止
常见的: 二分查找, 数字之和, 反转字符串, 回文数, 颠倒二进制等

// #include <bits/stdc++.h>
// using namespace std;
// using ll = long long;
// const ll N = 2e6 + 5;
// string s; 

// int main(){
//   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

//   cin >> s;
//   for(int i = 0; i < s.length() / 2; i++){
//     if(s[i] != s[s.length() - 1 - i]){
//       cout << 'N' << "\n";
//       return 0;
//     }
//   }
//   cout << 'Y' << "\n";
//   return 0;
// }



// 双指针
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e6 + 5;
string s; 

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> s;
  ll l = 0, r = s.length() - 1;
  while(l < r){
    if(s[l] != s[r]){
      cout << 'N' << "\n";
      return 0;
    }
    l++; r--;
  }
  cout << 'Y' << "\n";
  return 0;
}

快慢指针

指的是两个指针从同一侧开始遍历序列, 且移动的步长一个快一个慢
为了方便理解, 称快指针为r, 慢指针为l, 这样就构成了区间[l, r]
两个指针以不同的速度不同的策略移动, 直到两个指针相交或者满足其他特殊条件为止

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
  ll n, s; cin >> n >> s;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  int ans = n + 1;
  for(int i = 1, j = 0, sum = 0; i <= n; i++){
    // 考虑移动j, 即j++
    while(i > j || (j + 1 <= n && sum < s)){
      sum += a[++j];
    }
    if(sum >= s){
      ans = min(ans, j - i + 1); // 区间的长度
    }
    sum -= a[i];
  }
  cout << (ans > n ? 0 : ans) << "\n";
   
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5+5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, m, k; cin >> n >> m >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  } 
  ll ans = 0; // 7 4 2
  for(int i = 1, j = 0, cnt = 0; i <= n; i++){ // 4 2 7 7 6 5 1
    while(i > j || (j + 1 <= n && cnt < k)){
      cnt += (a[++j] >= m);
    }
    if(cnt >= k){
      ans += n - j + 1;
    }
    cnt -= (a[i] >= m);
  }

  cout << ans << "\n";
  
  return 0;
}

编程38-45

// 给定L和R, 让求[L, R]区间内的一些东西
// 先求0到R之间, 再求0到L - 1之间再相减即可
// 排序不影响答案
// 后面用双指针求就好了, 也可二分, 时间复杂度更高

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];
ll n, k, L, R;

ll calc(ll x){
  ll cnt = 0, l = 1, r = n;
  while(l < r){
    if(a[l] + a[r] <= x){
      cnt += r - l;
      l++;
    } else {
      r--;
    }
  }
  return cnt;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> L >> R;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n);
  cout << calc(R) - calc(L - 1) << "\n";
  
  return 0;
}

// 异或的性质: a^b <= a+b, a^a=0, a^0=a, 满足交换律
// 双指针每次看上一个是否继续满足a^b == a+b条件, 满足就能选, 否则不能选

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  ll ans = 0;
  for(int i = 1, j = 1, s = 0; i <= n; i++){
    while(j <= n && ((s ^ a[j]) == (s + a[j]))){ // 满足条件
      s ^= a[j++]; // 取值, 右指针++
    }
    ans += j - i; // 下标的对数
    s ^= a[i]; // 拿走
  }
  cout << ans << "\n";
  return 0;
}

// 细节: 可能爆long long

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll INF = 1e18 + 5;
ll a[N];
ll n, k; 

bool check(ll x){ // 这里的x表示的是最多可以有多少束花, x的最大值为2* 10^5 * 10^9 = 2 * 10^14
  ll cnt = 0;
  for(int i = 1; i <= n; i++){
    cnt += min(a[i], x); // 求和, 得出不等式cnt >= x*k;
  }
  return cnt / k >= x; // 这里x太大, 所以使用除法
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  ll l = 0, r = INF;
  while(l + 1 < r){
	ll mid = (l + r) / 2;
    if(check(mid)){ // 使用二分答案
      l = mid;
    } else {
      r = mid;
    }
  }
  cout << l << "\n";
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N], b[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, m, k; cin >> n >> m >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    a[i] += a[i - 1]; // 前缀和
  }
  for(int i = 1; i <= m; i++){
    cin >> b[i];
    b[i] += b[i - 1]; // 前缀和
  }
  ll ans = 0;
  for(ll i = 0; i <= n; i++){
    if(a[i] > k){ // k - a[i]为负数, 就没必要了
      break;
    }
    ll res = k - a[i];
    ll x = upper_bound(b, b + m + 1, res) - b - 1; // upper_bound() - b - 1得到下标
    ans = max(ans, i + x); // 左边打了i, 右边打了x
  }
  cout << ans << "\n";
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N], b[N];
ll n, k, t; 

bool check(ll mid){
  for(int i = 1; i <= mid; i++){
    b[i] = a[i];
  }
  sort(b + 1, b + 1 + mid);
  ll v2 = 0, v = 0;
  for(int i = 1; i < k; i++){
    v2 += 1ll * b[i] * b[i]; // vi^2的前缀和
    v += b[i]; // vi的前缀和
  }
  for(int i = k; i <= mid; i++){
    v2 += 1ll * b[i] * b[i] - 1ll * b[i - k] * b[i - k]; // 滑窗, 加上后一项, 减去前一项, 直到结束
    v += b[i] - b[i - k]; // 滑窗
    double avg = 1.0 * v / k; // 平均数
    if((v2 - 2 * avg * v + k * avg * avg) / k < t){ // 完全平方展开再除以k, 即方差
      return true;
    }
  }
  return false;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> k >> t;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  ll l = k, r = n + 1;
  while(l + 1 < r){
    ll mid = (l + r) / 2;
    if(check(mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }
  if(r == n + 1){
    cout << -1 << "\n";
  } else {
    cout << r << "\n";
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll INF = 1e9 + 5;
ll a[N];
ll n, k;

bool check(ll x){
  ll cnt = 0;
  for(int i = 1; i <= n; i++){
    cnt += a[i] / x; // 向下取整
  }
  return cnt >= k; // k个完全相同的
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  ll l = 0, r = INF;
  while(l + 1 < r){ // 二分答案模板
    ll mid = (l + r) / 2;
    if(check(mid)){
      l = mid;
    } else {
      r = mid;
    }
  }
  if(l == 0){ // l是答案, 为0说明check函数一直是false, 所以输出-1
    cout << -1 << "\n";
  } else {
    cout << l << "\n"; // 否则为l
  }
  
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 3e5 + 5;
ll a[N], cnt[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, q, k; cin >> n >> q;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n); // 排序不影响结果
  for(int i = 1; i <= n; i++){
    cnt[i] = (n - i) * (n - i - 1) / 2; // cnt(n-i, 2)
    cnt[i] += cnt[i - 1]; // 前缀和
  } 
  while(q--){
    cin >> k;
    cout << a[lower_bound(cnt + 1, cnt + 1 + n, k) - cnt] << "\n"; // lower_bound()-cnt返回第一个大于等于k的下标
  }

  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll s[N];

struct node{
  ll x, y;
} a[N];

bool operator < (node xx, node yy){ // 贪心里面的扰动法
  return xx.x + xx.y < yy.x + yy.y;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, k; cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i].x;
  }
  for(int i = 1; i <= n; i++){
    cin >> a[i].y;
  }
  sort(a + 1, a + 1 + n);
  for(int i = 1; i <= n; i++){
    s[i] = s[i - 1] + a[i].x + a[i].y; // 前缀和
  }
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    ll sy = k - a[i].x;
    ll l = 0, r = n + 1;
    while(l + 1 < r){ // 二分
      ll mid = (l + r) / 2;
      bool p = 0;
      if(mid < i) p = s[mid] <= sy;
      else p = (s[mid] - a[i].x - a[i].y <= sy);
        
      if(p) l = mid;
      else r = mid;
    }
    if(l < i) ans = max(ans, l + 1);
    else ans = max(ans, l);
  }  
  
  cout << ans << "\n";
  return 0;
}

构造

跟贪心一样, 需要靠题目的积累

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N];

void AC(){
  ll n; cin >> n;
  ll sum = 0;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  ll cnt = 0;
  for(int i = 1; i <= n; i++){
    if(a[i] == 0){
      a[i]++;
      cnt++;
    }
    sum += a[i];
  }
  cout << (sum == 0 ? ++cnt : cnt) << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  while(t--){
    AC();
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

ll f(ll n){
  return n - n / 4 - (ll)(n % 4 >= 2);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll l, r; cin >> l >> r;
  
  cout << f(r) - f(l - 1) << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];ll n; 

bool check(ll mid){
  // 栈根据pos升序
  vector<pair<ll, ll>> v; // v = [{pos, val}]
  // 第一个字符串是全0, 不需存储
  for(int i = 2; i <= n; i++){
    while(v.size() && v.back().first > a[i]){
      v.pop_back();
    }
    if(v.size() && v.back().first == a[i]){
      v[v.size() - 1].second++;
    } else {
      v.push_back({a[i], 1});
    }
    while(v.size() && v.back().second >= mid){
      int pos = v.back().first;
      // 将pos - 1进位
      v.pop_back();
      if(v.size() && v.back().first == pos - 1){
        v[v.size() - 1].second++;
      } else {
        v.push_back({pos - 1, 1});
      } 
    }
    if(v.size() && v.front().first == 0){
      return false;        
    }
    return true;
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  bool rising = true;
  for(int i = 2; i <= n; i++){
    if(a[i - 1] >= a[i]){
      rising = false;
    }
  }
  if(rising){
    cout << 1 << "\n";
    return 0;
  }
  ll l = 1, r = 2e5 + 5;
  while(l + 1 < r){
    ll mid = (l + r) / 2;
    if(check(mid)){
      r = mid;
    } else {
      l = mid;
    }
  }
  cout << r << "\n";

  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N]; ll n, k; 
vector<int> c[N]; // c[x]表示对k同余, 余数为x的所有元素

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    c[a[i] % k].push_back(a[i]);
  }
  for(int i = 0; i < k; i++){
    sort(c[i].begin(), c[i].end(), [](int u, int v){
      return u > v;
    });
  }
  int ans = 0;
  for(int i = 0; i < k; i++){
    if(!c[i].size()){
      continue;
    }
    for(int j = i; j < k; j++){
      int t = (2 * k - i - j) % k;
      if(t < j || !c[j].size() || !c[t].size()){
        continue;
      }
      if(i == j && j == t){
        if(c[i].size() < 3){
          continue;
          ans = max(ans, c[i][0] + c[i][1] + c[i][2]);
        }
      } else if(i == j){
          if(c[i].size() < 2){
            continue;
          }
          ans = max(ans, c[i][0] + c[i][1] + c[t][0]);     
      } else if(j == t){
          if(c[t].size() < 2){
            continue;
          }
          ans = max(ans, c[i][0] + c[t][0] + c[t][1]);
      } else {
        ans = max(ans, c[i][0] + c[j][0] + c[t][0]);
      }
    }
  }
  
  cout << ans << "\n";

  
  return 0;
}

编程46-49

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

void AC(){
  ll x; cin >> x;
  if(x == 1){
    cout << -1 << "\n";
  } else {
    ll maxx = 1e6, a, b, c;
    if(x <= maxx + 1){
      a = x - 1, b = 1, c = 1;
    } else {
      a = maxx, c = x % maxx == 0 ? maxx : x % maxx, b = (x - c) / a;
    }
    cout << a << " " << b << " " << c << "\n";
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  while(t--){
    AC();
  }
  
  return 0;
}

// 结论: 一个大于等于4的数一定能由若干个2或3加起来表示
// gcd(a, b)等于1说明最大绝对差的最小值为1
// gcd(a, b)大于等于2说明最大绝对差的最小值为0

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

void AC(){
  ll a, b; cin >> a >> b;
  if(a == 1 || b == 1){ // 等于1说明不能构成质数序列
    cout << -1 << "\n";
  } else if(__gcd(a, b) != 1){
    cout << 0 << "\n";
  } else {
    cout << 1 << "\n";
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  while(t--){
    AC();
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

void AC(){
  ll a, b, n; cin >> a >> b >> n;
  if((n - 1) % b == 0){
    cout << "Yes" << "\n";
    return;
  }
  if(a == 1){
    cout << "No" << "\n";
    return;
  }
  ll res = 1;
  while(res < n){
    res += a;
    if(res > n) break;
    if(res == n) {
      cout << "Yes" << "\n";
      return;
    }
    if((n - res) % b == 0){
      cout << "Yes" << "\n";
      return;
    }
  }
  cout << "No" << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  while(t--){
    AC();
  }
  
  return 0;
}

位运算

简介

对二进制的位进行操作
只能用于整数, 且一般为非负整数
整数是通过补码表示的, 正整数的三码相同, 即补码=反码=原码

常见的

按位与&
- 全1为1, 否则为0
- 两个数字做与运算, 结果不会变大
按位或|
- 全0为0, 否则为1
- 两个数字做或运算, 结果不会变小
按位异或^
- 不同为1, 相同为0
- 两个数字做异或运算, 结果可能变大也可能变小, 也可能不变
- 性质
  - 交换律, 结合律
  - 自反性: x ^ x = 0
  - 零元素: x ^ 0 = x
  - 逆运算: x ^ y = z, 则z ^ y = x (两边同时异或y, 抵消掉)
按位取反~
- 1变0, 0变1
- 通常用于无符号整数(unsigned int / ll), 为了避免符号位取反造成干扰
按位左移<<
- 二进制向左移动指定的位数, 低位补0
- 左移操作相当于对原数进行乘以2的幂次方, 例如5左移3, 相当于 $5*(2^3)$
按位右移>>
- 高位补0
- 相当于对原数除以2的幂次方

技巧

判断数字奇偶性
- x & 1: 结果为1说明是奇数, 为0是偶数
获取二进制数中的某一位
- x >> i & 1: 表示x的二进制表示中的第i位
修改二进制中的某一位为1
- x | (1 << i)
- 修改为0, 则类似的做与运算, 即x & ~(1 << i)
判断一个数是否为2的幂次方
- x & (x - 1)
获取二进制位中最低位的1
- lowbit(x) = x & -x
- 如果x = (010010), 则lowbit(x) = (000010)
- 常用于数据结构树状数组中

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  unsigned int x; cin >> x;
  ll cnt = 0;
  while(x){
    if(x & 1 == 1) {
      cnt++;
    }
    x >>= 1;
  }
  cout << cnt << "\n";
  
  return 0;
}

// 差一点超时
// #include <bits/stdc++.h>
// using namespace std;
// using ll = long long;
// const ll N = 1e5 + 5;
// ll a[N];

// int main(){
//   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

//   ll n, q; cin >> n >> q;
//   for(int i = 1; i <= n; i++){
//     cin >> a[i];
//   }
//   for(int i = 1; i <= q; i++){
//     ll l, r; cin >> l >> r;
//     ll ans = a[l];
//     for(int j = l; j <= r; j++){
//       ans |= a[j];
//     }
//     cout << ans << "\n";
//   }
  
  
//   return 0;
// }



// 使用前缀和
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N], prefix[35][N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, q; cin >> n >> q;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int w = 0; w <= 30; w++){ // 每一位
    for(int i = 1; i <= n; i++){
      prefix[w][i] = prefix[w][i - 1] + (a[i] >> w & 1); // 前缀和, ()当中表示取出来每一位
    }
  }
  while(q--){
    ll l, r; cin >> l >> r;
    ll ans = 0;
    for(int w = 0; w <= 30; w++){ // 每一位
      ans += (1 << w) * (prefix[w][r] - prefix[w][l - 1] ? 1 : 0);
    } 
    cout << ans << "\n";
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N], prexor[N], cnt[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    prexor[i] = prexor[i - 1] ^ a[i];
  }
  cnt[0] = 1;
  ll ans = n * (n + 1) / 2;
  for(int i = 1; i <= n; i++){
    for(int j = 0; j <= 200; j++){
      ll sq = j * j;
      ans -= cnt[prexor[i] ^ sq];
    }
    cnt[prexor[i]]++;
  }
  cout << ans << "\n";
  
  
  return 0;
}

编程50-55

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N =1e6+4;
const ll MOD = 1e9 + 7;
ll a[N], prefix[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    prefix[i] = prefix[i - 1] ^ a[i];
  }
  ll ans = 1;
  for(int i = 1; i <= n; i++){
    for(int j = i; j <= n; j++){
      ll t = prefix[i - 1] ^ prefix[j];
      if(!t){
        cout << 0 << "\n";
        return 0;
      }
      ans = ans * (t) % MOD;
    }
  }
  cout << ans << "\n";
  
  
  return 0;
}

51题异或森林上面有

// 实际上, 不需要考虑左右两边的0, 即将左右两边的0都删掉, 然后再在a的字符串中找b这个子串

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N =1e6+4;
const ll MOD = 1e9 + 7;
ll a[N], prefix[N];


string calc(ll x){ // 将整数x变成二进制下的字符串
  string ret;
  while(x){
    ret.push_back('0' + (x & 1)); // 翻着存放
    x >>= 1;
  }
  while(ret.size() && ret.back() == '0'){ // back()为最后面的元素
    ret.pop_back(); // 这句话表示将右边的0全部去除
  }
  reverse(ret.begin(), ret.end()); // 翻转字符串
  while(ret.size() && ret.back() == '0'){
    ret.pop_back(); // 这句话表示将左边的0全部去除
  }
  return ret;
}


void AC(){
  ll a, b; cin >> a >> b;
  string aa = calc(a);
  string bb = calc(b);
  if(aa.find(bb) != -1){ // 在aa里面找bb, 如果bb是aa的子串说明可以, 否则不可以
    cout << "Yes" << "\n";
  } else {
    cout << "No" << "\n";
  }  
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll t; cin >> t;
  while(t --){
    AC();
  }
  
  return 0;
}

// 核心考点: 枚举子集

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll MOD = 1e9 + 7;
ll a[N], prefix[N];


int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, l, r, x; cin >> n >> l >> r >> x;
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  sort(a, a + n);
  ll ans = 0;
  for(int S = 1; S < (1 << n); S++){ // S表示状态
    vector<ll> dq;
    for(int i = 0; i < n; i++){
      if((S >> i) & 1){
        dq.push_back(a[i]);
      }
    }
    
    ll sum = accumulate(dq.begin(), dq.end(), 0ll);
    ll mx = *max_element(dq.begin(), dq.end());
    ll mn = *min_element(dq.begin(), dq.end());
    ll len = unique(dq.begin(), dq.end()) - dq.begin();
    if(mx - mn >= x && sum >= l && sum <= r && len >= 3){
      ans++;
    }
  }
  cout << ans << "\n";
  return 0;
}

{19558553-05E9-4068-9806-64C3170CB6B2}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
const ll MOD = 1e9 + 7;
ll a[N], prefix[N];

bool isOK(int x){
  ll cnt = 0;
  while(x){
    if(x & 1 == 1){
      cnt++;
    }
    x >>= 1;
  }
  return cnt == 3;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n = 23;
  ll cnt = 0;
  int i = 1;
  while(cnt < n){
    if(isOK(i)){
      cnt++;
    }
    i++;
  }
  cout << --i << "\n";
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N], f[25][2];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    a[i] ^= a[i - 1];
  }
  for(int i = n; i >= 0; i--){
    for(int j = 0; j <= 20; j++){
      if((a[i] >> j) & 1) f[j][1]++;
      else f[j][0]++;
    }
  }
  ll cur = 1, ans = 0;
  for(int x = 0; x <= 20; x++){
    for(int i = 0; i < n; i++){
      if((a[i] >> x) & 1) ans += cur * f[x][0], f[x][1]--; 
      else ans += cur * f[x][1], f[x][0]--;
    }
    cur <<= 1;
  }

  cout << ans << "\n";
  return 0;
}

排序

冒泡排序

冒泡排序的思想

每次将最大的一下一下运到最右边, 然后将最右边这个确定下来, 再确定第二大的, 第三大的…
时间复杂度: O(n^2)

例题讲解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  
  for(int i = 1; i < n; i++){
    for(int j = i; j < n; j++){
      if(a[i] > a[j + 1]){
        swap(a[i], a[j + 1]);
      }
    }
  }
  for(int i = 1; i <= n; i++){
    cout << a[i] << " \n"[i == n];
  }
  
  return 0;
}

选择排序

选择排序的思想

每次找出最大的然后直接放到右边对应位置, 然后将最右边这个确定下来(而不是一个一个的交换过去), 再来确定第二大的, 第三大的…
时间复杂度: O(n^2)

例题讲解

宝藏序列1

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  // 选择排序
  for(int i = 1; i <= n; i++){
    ll index = i;
    for(int j = i + 1; j <= n; j++){
      if(a[index] > a[j]){
        index = j;
      }
    }
    swap(a[index], a[i]);
    
  }
  for(int i = 1; i <= n; i++){
    cout << a[i] << " \n"[i == n];
  }
  
  return 0;
}

插入排序

插入排序的思想

将待排序的元素逐个插入到已排序序列的合适位置中, 使得已排序序列逐渐扩大
类似于打扑克牌时的排序方式
时间复杂度: O(n^2)

例题讲解

宝藏序列1

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  
  for(int i = 2; i <= n; i++){
    int val = a[i], j;
    for(j = i; val < a[j - 1]; j--){
      a[j] = a[j - 1];
    }
    a[j] = val;
  }
  for(int i = 1; i <= n; i++){
    cout << a[i] << " \n"[i == n];
  }
  
  return 0;
}

快速排序

快速排序的思想

将一个数组分为两个子数组, 其中一个子数组的所有元素都小于另一个子数组的元素, 然后递归的对这两个子数组进行排序
时间复杂度: O(nlogn)

例题讲解

宝藏排序2
- 注意：这道题于宝藏排序Ⅰ的区别仅是数据范围

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
int a[N];

int Partition(int a[], int l, int r){
  int pivot = a[r];
  int i = l, j = r;
  while(i < j){
    while(i < j && a[i] <= pivot){
      i++;
    }
    while(i < j && a[j] >= pivot){
      j--;
    }
    if(i < j){
      swap(a[i], a[j]);
    } else {
      swap(a[i], a[r]);
    }
  }
  return i;
}

void QuickSort(int a[], int l, int r){
  if(l < r){
    int mid = Partition(a, l, r);
    QuickSort(a, l, mid - 1);
    QuickSort(a, mid + 1, r);
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  QuickSort(a, 1, n);
  for(int i = 1; i <= n; i++){
    cout << a[i] << " \n"[i == n];
  }
  
  return 0;
}

归并排序

归并排序的思想

将一个数组分成两个子数组, 将子数组向下递归的排序后(当数组中仅剩一个元素时不需再排序了, 直接返回), 得到两个有序数组, 然后进行O(n)的合并, 最终合并成有序的原数组
时间复杂度: O(nlogn)

例题讲解

宝藏排序2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
int a[N], b[N];

void MergeSort(int a[], int l, int r){
  if(l == r){
    return;
  }
  int mid = (l + r) / 2;
  MergeSort(a, l, mid);
  MergeSort(a, mid + 1, r);
  int pl = l, pr = mid + 1, pb = l;
  while(pl <= mid || pr <= r){
    if(pl > mid){
      b[pb++] = a[pr++];
    } else if (pr > r){
      b[pb++] = a[pl++];
    } else {
      if(a[pl] < a[pr]){
        b[pb++] = a[pl++];
      } else {
        b[pb++] = a[pr++];
      }
    }
  }
  for(int i = l; i <= r; i++){
    a[i] = b[i];
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  MergeSort(a, 1, n);
  for(int i = 1; i <= n; i++){
    cout << a[i] << " \n"[i == n];
  }
  
  return 0;
}

编程56-65

56, 57宝藏排序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n);
  ll l = 1, r = n;
  while(a[1] == a[l]){
    l++;
  }
  while(a[n] == a[r]){
    r--;
  }
  cout << accumulate(a + l, a + 1 + r, 0ll) << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
const ll INF = 1e18 + 5;
ll a[N], b[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= 2 * n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + 2 * n); // 1 2 2 2 3 3 4 6
  ll l = 1, r = n, mn = INF;
  for(int i = 1; i <= n + 1; i++){
    mn = min(mn, a[r] - a[l]);
    l++, r++;
  }
  cout << mn << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
const ll INF = 1e18 + 5;

struct node{
  ll x, y;
}a[N];

bool operator < (node xx, node yy){ // x降序, y升序
  if(xx.x == yy.y) return xx.y < yy.y;
  return xx.x > yy.x;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i].x >> a[i].y;
  }
  sort(a + 1, a + 1 + n);
  ll ans = 0, mx = 0;
  for(int i = 1; i <= n; i++){
    if(a[i].y >= mx){
      mx = a[i].y;
      ans++;
    }
  }
  cout << ans << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
const ll INF = 1e18 + 5;
ll a[N];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n, greater<ll>()); // 5 3 2
  ll ans = 0, mx = 0, l = 1, r = 2;
  for(int i = 1; i <= n - 1; i++){ // 滑窗
    mx = max(mx, a[l] * a[r] + a[l] - a[r]);
    l++, r++;
  }
  cout << mx << "\n";
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
const ll INF = 1e18 + 5;

struct node{
  string s;
  ll inv_cnt = 0;
  void calc(){
    for(int i = 0; i < s.size(); i++){
      for(int j = i + 1; j < s.size(); j++){
        if(s[i] > s[j]){
          inv_cnt++;
        }
      }
    }
  }
}a[N];

bool operator < (node xx, node yy){
  if(xx.inv_cnt == yy.inv_cnt){
    string s1 = xx.s, s2 = yy.s;
    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());
    while(s1.size() && s1.back() == '0') s1.pop_back();
    while(s2.size() && s2.back() == '0') s2.pop_back();
    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());
    if(s1.size() == s2.size()) return s1 < s2;
    return s1.size() < s2.size();
  }
  return xx.inv_cnt < yy.inv_cnt;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i].s;
    a[i].calc();
  }
  sort(a + 1, a + 1 + n);
  for(int i = 1; i <= n; i++){
    cout << a[i].s << "\n";
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
const ll INF = 1e18 + 5;
ll flag[N];
struct node{
  ll x, y;
} a[N];

bool operator < (node xx, node yy){
  return xx.y < yy.y;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n, k; cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i].x;
  }
  for(int i = 1; i <= n; i++){
    cin >> a[i].y;
  }
  sort(a + 1, a + 1 + n);
  ll ans = 0, cnt = 0;
  for(int i = 1; i <= n; i++){
    if(!flag[a[i].x]){
      ans += a[i].y;
      flag[a[i].x] = 1;
      cnt++;
    }
    if(cnt == k){
      break;
    }
  }
  if(cnt == k){
    cout << ans << "\n";
  } else {
    cout << -1 << "\n";
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;

vector<ll> a, b;

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  for(int i = 1; i <= n; i++){
    ll x; cin >> x;
    if(x % 2) a.push_back(x);
    else b.push_back(x);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  for(const auto& it : a){
    cout << it << " ";
  }  
  for(const auto& it : b){
    cout << it << " \n"[1 == n];
  }
  
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;

ll cmp(string s1, string s2){
  return s1 + s2 < s2 + s1; // 扰动法, 特殊样例: 10, 100, 10比100更优, 所以为10100, 但是翻着拼成10010比10100更优, 所以要使用前后拼接的方式进行比较
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  ll n; cin >> n;
  vector<string> s(n); // 注意: 是圆括号
  for(int i = 0; i < n; i++){ // 注意: 应该从0开始
    cin >> s[i];
  }
  sort(s.begin(), s.end(), cmp);
  
  for(int i = 0; i < n; i++){
    cout << s[i];
  }
  cout << "\n";
  return 0;
}
[l]);
    l++, r++;
  }
  cout << mn << "\n";
  
  return 0;
}