工作服定做厂家_爱采购卖家版下载_无锡网站建设优化公司_天津seo推广服务

蓝桥杯 2.基础算法

基础算法

时空复杂度

时间复杂度

• 算法执行时间随输入规模增长的增长率
• 常见的时间复杂度包括
  • 常熟时间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)nn-1     n-2n-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复制回afor(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){ // 987ret += (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

NO

#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"; // 4430091return 0;
}

NO

#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;
}

NO

#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 acgtccontinue; // 如果当前字符配对正确, 跳过}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, 其本质是每一个数位上的数字乘上这位上的权重, 即: $153=(1\times 10^2)+(5\times 10^1)+(3\times 10^0)$
• 而二进制, 只不过是把10换成了2, 即: $153=(10011001{)}_2=(1\times 2^7)+(1\times 2^4)+(1\times 2^3)+(1\times 2^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; // 153ll 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"; // 63return 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[], 满足: $prefix[i]=a[1]+a[2]+...+a[i-1]+a[i]$
• prefix有一个重要的特性, 可以用于快速生成prefix: $prefix[i]=prefix[i-1]+a[i]$
• prefix可以O(1)的求数组a[]的一段区间的和: $sum(l,r)=prefix[r]-prefix[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 < ycout << "YES" << "\n";return 0;}}cout << "NO" << "\n";return 0;
}/*对于231问题:使用单调栈解决出栈的元素一定小于栈内某个元素, 一定能找到x < y如果存在z < x, 那么就有z < x < y对于3421问题, 引入后缀最小即可解决
*/

差分

差分的原理和特点

• 对于一个数组a[], 差分数组diff[]的定义是: $diff[i]=a[i]-a[i-1]$
• 对差分数组做前缀和可以还原为原数组$diff[n]=a[n]-a[n-1]$
  • $diff[1]+diff[2]+diff[3]+...+diff[i]=a[1]+(a[2]-a[1])+(a[3]-a[2])+...+(a[i]-a[i-1])=a[i]$
• 利用差分数组可以实现快速的区间修改, 下面是将区间[l, r]都加上x的方法
  • $diff[l]+=x;$
  • $diff[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 9ll 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 9ll 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); // aabccdif(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++){ // 预算必须大于等于0ans++;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 4if(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 2for(int i = 1, j = 0, cnt = 0; i <= n; i++){ // 4 2 7 7 6 5 1while(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^14ll 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, 所以输出-1cout << -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\ast (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;
}

#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 6ll 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 2ll 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;
}