蓝桥杯2.基础算法

蓝桥杯 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

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"; // 4430091 return 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 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, 其本质是每一个数位上的数字乘上这位上的权重, 即: 153 = ( 1 × 1 0 2 ) + ( 5 × 1 0 1 ) + ( 3 × 1 0 0 ) 153 = (1\times10^2) + (5\times10^1) + (3\times10^0) 153=(1×102)+(5×101)+(3×100)而二进制, 只不过是把10换成了2, 即: 153 = ( 10011001 ) 2 = ( 1 × 2 7 ) + ( 1 × 2 4 ) + ( 1 × 2 3 ) + ( 1 × 2 0 ) 153 = (10011001)_2 = (1\times2^7)+(1\times2^4)+(1\times2^3)+(1\times2^0) 153=(10011001)2​=(1×27)+(1×24)+(1×23)+(1×20)在计算机中, 数字均通过二进制补码表示

将任意进制转换为十进制

假设给了一个数组来表示一个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 r e f i x [ i ] = a [ 1 ] + a [ 2 ] + . . . + a [ i − 1 ] + a [ i ] prefix[i] = a[1]+a[2]+...+a[i-1]+a[i] prefix[i]=a[1]+a[2]+...+a[i−1]+a[i]prefix有一个重要的特性, 可以用于快速生成prefix: p r e f i x [ i ] = p r e f i x [ i − 1 ] + a [ i ] prefix[i] = prefix[i - 1] + a[i] prefix[i]=prefix[i−1]+a[i]prefix可以O(1)的求数组a[]的一段区间的和: s u m ( l , r ) = p r e f i x [ r ] − p r e f i x [ l − 1 ] sum(l, r) = prefix[r] - prefix[l - 1] 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 < y cout << "YES" << "\n"; return 0; } } cout << "NO" << "\n"; return 0; } /* 对于231问题: 使用单调栈解决 出栈的元素一定小于栈内某个元素, 一定能找到x < y 如果存在z < x, 那么就有z < x < y 对于3421问题, 引入后缀最小即可解决 */ 差分

差分的原理和特点

对于一个数组a[], 差分数组diff[]的定义是: d i f f [ i ] = a [ i ] − a [ i − 1 ] diff[i] = a[i] - a[i - 1] diff[i]=a[i]−a[i−1]对差分数组做前缀和可以还原为原数组 d i f f [ n ] = a [ n ] − a [ n − 1 ] diff[n] = a[n] - a[n - 1] diff[n]=a[n]−a[n−1] d i f f [ 1 ] + d i f f [ 2 ] + d i f f [ 3 ] + . . . + d i f f [ i ] = a [ 1 ] + ( a [ 2 ] − a [ 1 ] ) + ( a [ 3 ] − a [ 2 ] ) + . . . + ( a [ i ] − a [ i − 1 ] ) = a [ i ] 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] 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的方法 d i f f [ l ] + = x ; diff[l] += x; diff[l]+=x; d i f f [ r + 1 ] − = x ; diff[r + 1] -= 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 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 ) 5*(2^3) 5∗(23) 按位右移>> 高位补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 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; }