竞赛常识
- 评测机一秒运行次数约为 2e8次 程序的运行次数最好控制在1e8次以下
- 128MB的存储空间 = 3e7 int，一般题目不卡空间
- 递归深度为n时，递归执行次数约为2^n，但是递归使用的是堆栈，一般仅提供8MB空间，递归深度不易超过1e6层
前缀和
前缀和适用：需要多次查询数组中某个区间的和时，前缀和可以将每次查询的时间复杂度从O(n)降低到O(1)。
prefix[i] = prefix[i-1] + arr[i];prefix为前缀和数组、arr为原数组
若需要计算区间[l,r]的值的和，可以通过：
sum = prefix[r] - prefix[l-1];例题：
补充：
二维前缀和公式：
// 获取前缀和数组
prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + mp[i][j];
// 计算子矩阵和
sum = prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1];差分
差分数组适用于：需要频繁处理区间更新操作
diff[i] = arr[i] - arr[i-1];对于原数组可以通过对差分数组运用前缀和的方式计算得出
其特点是可以高效的更新原数组
diff[l] += z;
diff[r+1] -= z;例题：
补充：
二维差分数组公式：
// 获取二维差分数组
diff[i][j] = mp[i][j] - mp[i-1][j] - mp[i][j-1] + mp[i-1][j-1];
// 从(x1,y1)到(x2,y2)的区域内加k
diff[x1][y1] += k;
diff[x1][y2+1] -= k;
diff[x2+1][y1] -= k;
diff[x2+1][y2+1] += k;
// 还原
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
mp[i][j] = diff[i][j]; // 直接赋值线段树
思想：分治
#include <iostream>
using namespace std;
const int MAXN = 1e5 + 5;
long long m; // 定义全局模数
int arr[MAXN];
struct treeNode {
int left, right;
long long val, add_lazy, mul_lazy;
} tree[4 * MAXN + 5];
// 建树
void build(int node, int start, int end) {
tree[node] = {start, end, 0, 0, 1};
if (start == end) {
tree[node].val = arr[start];
return;
}
int mid = (start + end) >> 1;
build(node << 1, start, mid);
build((node << 1) | 1, mid + 1, end);
tree[node].val = tree[node << 1].val + tree[(node << 1) | 1].val;
}
// 懒标记下传
void spread(int node) {
if (tree[node].mul_lazy != 1) {
tree[node << 1].mul_lazy *= tree[node].mul_lazy;
tree[(node << 1) | 1].mul_lazy *= tree[node].mul_lazy;
tree[node << 1].add_lazy *= tree[node].mul_lazy;
tree[(node << 1) | 1].add_lazy *= tree[node].mul_lazy;
tree[node << 1].val *= tree[node].mul_lazy;
tree[(node << 1) | 1].val *= tree[node].mul_lazy;
tree[node].mul_lazy = 1;
}
if (tree[node].add_lazy != 0) {
int len_left = tree[node << 1].right - tree[node << 1].left + 1;
int len_right = tree[(node << 1) | 1].right - tree[(node << 1) | 1].left + 1;
tree[node << 1].add_lazy += tree[node].add_lazy;
tree[(node << 1) | 1].add_lazy += tree[node].add_lazy;
tree[node << 1].val += tree[node].add_lazy * len_left;
tree[(node << 1) | 1].val += tree[node].add_lazy * len_right;
tree[node].add_lazy = 0;
}
}
// 区间查询
long long query(int node, int start, int end) {
if (start <= tree[node].left && end >= tree[node].right) {
return tree[node].val;
}
spread(node);
int mid = (tree[node].left + tree[node].right) >> 1;
if(end<=mid) return query(node<< 1,start,end);
if(start>=mid+1) return query((node<< 1)|1,start,end);
return query(node<< 1,start,mid)+query((node<< 1)|1,mid+1,end);
}
// 区间修改
void update(int node, int start, int end, int op, long long opNum) {
if (start <= tree[node].left && end >= tree[node].right) {
if (op == 2) { // 区间加
int len = tree[node].right - tree[node].left + 1;
tree[node].val += opNum * len;
tree[node].add_lazy += opNum;
} else if (op == 1) { // 区间乘
tree[node].val *= opNum;
tree[node].add_lazy *= opNum;
tree[node].mul_lazy *= opNum;
}
return;
}
spread(node);
int mid = (tree[node].left + tree[node].right) >> 1;
if (start <= mid) update(node << 1, start, mid, op, opNum);
if (end > mid) update((node << 1) | 1, mid + 1, end, op, opNum);
tree[node].val = tree[node << 1].val + tree[(node << 1) | 1].val;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q ;
for (int i = 1; i <= n; i++) cin >> arr[i];
build(1, 1, n);
while (q--) {
int op, x, y;
cin >> op;
if (op == 1 || op == 2) {
long long z;
cin >> x >> y >> z;
update(1, x, y, op, z);
} else if (op == 3) {
cin >> x >> y;
cout << query(1, x, y) << '\n';
}
}
return 0;
}
离散化
离散化即将一些离散的值，连续放置到一块连续的区域内。
#include <bits/stdc++.h>
using namespace std;
int MAX = 10e5;
int arr[6] = {1, 2, 4, 2, 3, 2}; // 假设已有的数组
vector<int> L; // 离散化后的数组
// 传入值返回该值在离散化数组中的下标
int getIdx(int value) {
return lower_bound(L.begin(), L.end(), value) - L.begin();
}
int main() {
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++) L.push_back(arr[i]);
sort(L.begin(), L.end());
L.erase(unique(L.begin(), L.end()), L.end());
int value;
cout << "Enter a value to find its index in the discretized array: ";
cin >> value;
cout << "The value of {" << value << "} in the discretized array is " << getIdx(value);
return 0;
}
/* Input: 3
Output: 2
Input: 4
Output: 3 */
排序算法
冒泡排序
时间复杂度O(n^2) 空间复杂度O(1)
void bubbleSort(vector<int>& arr){
for(int i=arr.size();i>1;i--){
for(int j=1;j<=i-1;j++){
if(arr[j]>arr[j+1]){
swap(arr[j],arr[j+1]);
}
}
}
}
选择排序
时间复杂度O(n^2) 空间复杂度O(1)
void selectSort(vector<int>& arr,int start,int end){//此处元素索引从1开始存储
for(int i= end;i>start;i--){ //外层循环 元素个数-1 次
int max_idx=start;
for(int j=start+1;j<=i;j++){ //内层循环
if(arr[j]>arr[max_idx])
max_idx=j;
}
swap(arr[i],arr[max_idx]);
}
}插入排序
时间复杂度O(n^2) 空间复杂度O(1)
void insertSort(vector<int>& arr){
int n = arr.size();
for(int i=2;i<=n;i++){
int key = arr[i],j=i-1; // 使用key来记录当前待插入的数，j用来记录待比较的位置
while(j>=1 && arr[j]>key){ // 从后向前比较，如果j指向位置比key大，则将arr[j]向后挪一位
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key; // 找到合适的位置后插入
}
}归并排序
时间复杂度O(nlogn) 空间复杂度O(n)
方案一 易理解
该代码以查找指定序列中的逆序对为背景运用递归
#include <bits/stdc++.h>;
using namespace std;
long long sum = 0;
const int MAXN = 5e+5;
vector<int> arr(MAXN);
vector<int> temp(MAXN);
//合并两个有序的数组
void merge(int left,int mid,int right){
for(int i=left;i<=right;i++)
temp[i] = arr[i];
int i = left,j=mid+1,target = left;
while(i<=mid && j<=right){
if(temp[i]<=temp[j])
arr[target++] = temp[i++];
else{
arr[target++] = temp[j++];
sum+=mid-i+1; // 累加逆序对数
}
}
while(i<=mid)
arr[target++] = temp[i++];
while(j<=right)
arr[target++] = temp[j++];
}
//递归调用
void mergeSort(int left,int right){
if(left>=right) return ;
int mid = (left+right)>>1;
mergeSort(left,mid);
mergeSort(mid+1,right);
merge(left,mid,right);
}
int main(){
int n;
cin>>n;
for(int i=0;i>arr[i];
mergeSort(0,n-1);
cout<< sum;
return 0;
}
方案二
inline void mergeSort(int start,int end){
if(start>=end) return;
int mid = (start+end)>>1;
mergeSort(start,mid);
mergeSort(mid+1,end);
for(int i = start;i<=end;i++)
temp[i] = arr[i];
int i = start,j=mid+1,target=start;
while(i<=mid || j<=end){
if(i>mid) arr[target++] = temp[j++];
else if(j>end) arr[target++] = temp[i++];
else if(temp[i] < temp[j]) arr[target++] = temp[i++];
else arr[target++] = temp[j++];
}
} 桶排序
时间复杂度O(n) 空间复杂度O(n) 非比较排序
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
vector<int> buckets(maxn,0);
int main()
{
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr); //加快输入输出速度
int n;
cin>>n;
int min_bucket = INT_MAX, max_bucket = INT_MIN; //用于确定桶的范围
for(int i=1;i<=n;i++) {
int temp;
cin>>temp;
if(tempmax_bucket) max_bucket = temp;
buckets[temp]++;
}
for(int i=min_bucket;i<=max_bucket;i++)
for(int j=1;j<=buckets[i];j++)
cout<< i<<" ";
return 0;
} 快速排序
时间复杂度O(nlogn) 空间复杂度O(1)
sort(arr.begin(),arr.end());//默认从低到高排序
sort(arr.begin(),arr.end(),[](T a, T b){
return a>b;
}; //通过lambda函数传入传递规则 使得结果从高到低搜索
文本内容
code数论
一些题目
【1.极差】
给定两个整数 N 和 K，以及N张扑克牌，其中第i张牌的数值为Ai。你可以进行任意次操作，每次操作可以选择一张牌并将其数值增加K。在进行了若干次操作(可以为零)后，扑克牌中的最大值减去最小值的差最小为多少?
示例输入
5 2
1 3 5 7 10示例输出
1题解&代码
因为可以进行任意次操作，因此每个输入的数据本质上可以等效在[0,k-1]区间内，因此转化为求该区间中的极值问题，但由于最小值通过加k操作后会变成最大值，此时极值可能变化，因此遍历查找最小值。
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,k,temp;
cin>>n>>k;
vector nums(n);
for(int i=0;i>temp;
nums[i] = temp%k;
}
sort(nums.begin(),nums.end());
int minNum = INT_MAX;
for(int i=1;i < nums.size();i++)
minNum = min(minNum,nums[i-1]+k-nums[i]);
cout<< minNum << endl;
return 0;
} 【2.红包金额】
给定三个红包中金币的初始数量，进行 N 次变换。每次变换中，每个红包的金币数量变为其他两个红包金币数量的乘积。求 N 次变换后，三个红包中金币数量的总乘积对 10E9+7 取模的结果。
示例输入
2
2 3 5 1
1 2 3 2示例输出
900
1296题解&代码
这道题我们通过分析可以知道经过 \( N \) 次变换，红包总金额为：\( (ABC)^{2^N} \)，但 \( 2^N \) 的值可能过大，因此我们需要想办法缩小该值。我们想到利用费马小定理（如果 \( p \) 是一个质数，且 \( a \) 是一个整数，且 \( a \) 不能被 \( p \) 整除，那么：\( a^{p-1} \equiv 1 \pmod{p} \)），因此就可以将原来的计算简化为：
\( (ABC)^{2^N} \pmod{10^9 + 7} \)
\( = (ABC)^k \pmod{10^9 + 7} \)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = 1e9 + 7;
// 快速幂算法
ull quick_pow(ull base, ull exp, ull mod) {
ull result = 1;
while (exp > 0) {
if (exp & 1) {
result = result * base % mod;
}
base = base * base % mod;
exp >>= 1;
}
return result;
}
int main() {
int T;
cin >> T;
while (T--) {
ull A, B, C, N;
cin >> A >> B >> C >> N;
// 计算 k = 2^N % (MOD - 1)
ull k = quick_pow(2, N, MOD - 1);
// 计算 (ABC) % MOD
ull product = A * B % MOD * C % MOD;
// 计算 (ABC)^k % MOD
ull result = quick_pow(product, k, MOD);
cout << result << endl;
}
return 0;
}【3.N皇后问题】（DFS经典问题）
一个如下的 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。请编一个程序找出所有棋子放置的解。并把它们以每行棋子摆放的位置按照行数从低到高的顺序输出，解按字典顺序排列。请输出前 3 个解。最后一行是解的总个数。
示例输入
6示例输出
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
题解代码
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int n;
int ans;
int Vis[N][N];
int pos[N+1];
void dfs(int depth){
if(depth>=n+1){
if(ans<=2){
for(int i=1;i<=n;i++) cout<< pos[i]<< " \n"[i==n];
}
ans++;
return ;
}
for(int i=1;i<=n;i++){
if(Vis[depth][i]) continue;
for(int row=1;row<=n;row++) Vis[row][i]++;
pos[depth] = i;
for(int row =depth,col=i;row>=1&&col>=1;row--,col--) Vis[row][col]++;
for(int row =depth,col=i;row<=n&&col>=1;row++,col--) Vis[row][col]++;
for(int row =depth,col=i;row>=1&&col<=n;row--,col++) Vis[row][col]++;
for(int row =depth,col=i;row<=n&&col<=n;row++,col++) Vis[row][col]++;
dfs(depth+1);
for(int row=1;row<=n;row++) Vis[row][i]--;
for(int row =depth,col=i;row>=1&&col>=1;row--,col--) Vis[row][col]--;
for(int row =depth,col=i;row<=n&&col>=1;row++,col--) Vis[row][col]--;
for(int row =depth,col=i;row>=1&&col<=n;row--,col++) Vis[row][col]--;
for(int row =depth,col=i;row<=n&&col<=n;row++,col++) Vis[row][col]--;
}
}
int main(){
cin>>n;
dfs(1);
cout<< ans;
return 0;
}【4.特殊的三角形】
假设一个三角形三条边为 a、b、c，定义该三角形的值 v = a×b×c。现在有 t 个询问，每个询问给定一个区间 [l,r]，问有多少个三条边都不相等的三角形的值 v 在该区间范围内。
输入数据：第一行包含一个正整数 t，表示有 t 个询问。接下来 t 行，每行有两个空格隔开的正整数 l、r，表示询问区间 [l,r]。
输出数据：输出共 t 行，第 i 行对应第 i 个查询的三角形个数。
示例输入
0
1
18
32示例输出
4
1 10
30 50
60 200
200 400题解代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int t,cnt[N],prefix[N];
void dfs(int depth,int sl,int sum,long long mul){
if(mul>1e6) return; //剪枝
if(depth == 4){
cnt[mul]++;
return ;
}
int up = pow(1e6*1.0/mul,1.0/(3-depth+1))+5; /*注意此处的常数5，该常数用于抵消pow中由于计算的非高精度引起的偏差*/
for(int j = sl+1;j < (depth==3?min(sum,up):up);j++){
dfs(depth+1,j,sum+j,mul*j);
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int l,r;
dfs(1,0,0,1);
cin>>t;
for(int i=1;i<=1e6;i++){
prefix[i] = prefix[i-1]+cnt[i];
}
for(int i=0;i < t;i++){
cin>>l>>r;
cout<< prefix[r]-prefix[l-1]<< '\n';
}
return 0;
}
最强大脑
现在已知有四类科目的数据需要处理，每类科目有若干组数据，小余是一个头脑聪明的人，他可以同时处理同一科的两个数据，现在求处理完这批数据所需要的最短时间
示例输入
1 2 1 3//每门科目的数据组数
5//每组所需要花费的时间 此处仅有一组 因此该组最短处理时间需要5分钟
4 3// 此处有两组 其中第一组需要花费4分钟 第二组需要花费3分钟 因此最短处理时间为4分钟
6//同上
2 4 3
示例输出
20 // 5+4+6+5题解代码
单组处理思路为求当前组内可以同时思考的最大值 也就是分为两个子组时 差值的最小时的分配方案
int sum = accumulate(v.begin(), v.end(), 0); //求出每组的总时间
int target = sum / 2; //求出每组尽可能平均的目标时间
vector dp(target + 1, false); //dp[i]表示是否存在花费时间总和为i的组的分布情况
dp[0] = true; //总和为0 一定存在 因为分为两组时可以将所有的任务分到第一组 那么第二组自然就为0
for (int num:v){
for (int j = target; j >= num; --j) {
if (dp[j - num]) dp[j] = true; //若dp[j-num]可以 那么dp[j]也可以 此时将花费时间为num的数据放在该组即可
}
}
int max_sum = 0;//此值为两组中可以同时处理的时间 也是两组的和相差最小时 和小的那组的值
for (int j = target; j >= 0; --j) {
if (dp[j]) {
max_sum = j;
break;
}
}
cout<< max_sum; 题目
题目描述
示例输入
输入数据示例输出
输出数据题解代码
code一些感悟
2025.02.05
学的相思