这周是我第一次接触C++
首先是要知道编译器和编辑器
- 编辑器：是应用软件，作用是将源代码翻译成另一种语言（目标代码/计算机代码）
- 编译器：作用是编写程序的源代码
C++输出"Hello,World!"
#include<iostream> //头文件
using namespace std;
int main(){
cout<<"Hello,World!"<<endl; //输出，是一个对象不是函数
return 0;
}C++的输入和输出
C++的输入：
scanf()：从键盘（标准输入）
#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
int a;
//读取单个字符
scanf("%d", &a); //从键盘读取一个数字
printf("%d\n", a); //打印出a的值
int b, c;
//读取多个字符
scanf("%d %d", &b, &c);
printf("%d %d\n", b, c);
//"\n"换行
return 0;
}
cin：从键盘（标准输入）读取数据
-
#include<iostream> using namespace std; int main() { int a; //读取单个字符 cin >> a; cout << a << endl; int b, c; //读取多个字符 cin >> b >> c; cout << b << " " << c << endl; //"endl"换行 return 0; }
C++的输出：
printf()：在控制台打印数据
#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
int a;
a = 6;
printf("%d\n", a);
return 0;
}
cin：在控制台打印数据
#include <iostream>
using namespace std;
int main()
{
int a;
a = 6;
cout << a << endl;
return 0;
}
C++时间复杂度
? ? ? ? ?一条语句的频度是指该语句在算法中被重复执行的频率。而算法中所有语句的频度之和记做T(n)，它是该算法问题规模 n 的函数，而时间复杂度主要就是分析 T(n) 的数量级。算法中基本运算（就是指最深层的循环内的语句）与T(n) 同数量级，所以通常采用算法中基本运算的频度 f(n) 来分析算法的时间复杂度。我们将 f(n) 中随 n 增长最快的项的系数置为1作为时间复杂度的度量。f(n) = a*n^3+b*n^2+c; 时间复杂度为O(n^3)
算法的时间复杂度记作：T(n) = O(f(n));
运算规则：
加法：T(n) = T1(n) +T2(n) = O(f(n))+O(g(n)) = O(max(f(n),g(n)))
乘法：T(n) = T1(n)*T2(n) =?O(f(n))*O(g(n)) = O(f(n)*g(n))
常见的时间复杂度：O(1) < O(logn) < ?O(n)?< ?O(nlogn)?< ?O(n^2)?< ?O(n^3)?< ?O(2^n)?< ?O(n!) <O(n^n)
二分法
? ? ? ? ? 二分法是一个排好序列（数组，链表）中，不断收缩区间来进行目标值查找的一种算法
二分法的通用框架
int binarySearch(vector<int>& nums, int target){
int left=0, right=nums.size();
while(left < right)
{
int mid=(left+right)/2;
if(nums[mid] == target){
// 条件一：中间的值与目标值相同
}
else if(nums[mid] > target){
// 条件二：中间的值大于目标值
}
else if(nums[mid] < target){
// 条件三：中间的值小于目标值
}
}
return -1;
}二分法查找一个值
int binarySearch(vector<int>& nums, int target){
int left=0, right=nums.size();
while(left < right)
{
int mid=(left+right)/2;
if(nums[mid] == target){
return mid; // 查询到目标值，直接返回目标值的位置
}
else if(nums[mid] > target){
right = mid; // 中间的值大于目标值，向左收缩区间
}
else if(nums[mid] < target){
left = mid+1;// 中间的值小于目标值，向右收缩区间
}
}
return -1; // 当没有找到，直接返回-1
}二分法查找值的左右边界
// 查找目标值的左边界
int binarySearch(vector<int>& nums, int target){
int left=0, right=nums.size();
while(left < right)
{
int mid=(left+right)/2;
if(nums[mid] == target){
right = mid; // 查询到目标值不进行返回，而是收缩区间继续查找
}
else if(nums[mid] > target){
right = mid; // 中间的值大于目标值，向左收缩区间
}
else if(nums[mid] < target){
left = mid+1;// 中间的值小于目标值，向右收缩区间
}
}
return left;
}// 查找目标值的左边界
int binarySearch(vector<int>& nums, int target){
int left=0, right=nums.size();
while(left < right)
{
int mid=(left+right)/2;
if(nums[mid] == target){
left = mid+1; // 查询到目标值不进行返回，而是收缩区间继续查找
}
else if(nums[mid] > target){
right = mid; // 中间的值大于目标值，向左收缩区间
}
else if(nums[mid] < target){
left = mid+1;// 中间的值小于目标值，向右收缩区间
}
}
return left-1;
}前缀和与差分
差分步骤：
1.求出差分数组
2.对差分数组进行加减
3.对操作后的差分数组求前缀和
一维前缀和
注意
1.前缀和下标从1开始，因为边界S0要定义成0
2.作用：快速求出某个数组区间内的和
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int s[N],a[N];//全局变量默认为0
int main()
{
int m,n;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
while(m--)
{
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
?二维前缀和
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N][N],s[N][N];
int main()
{
int 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++) s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];//计算前缀和
while(q--)
{
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout<<s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]<<endl;//计算部分和
}
return 0;
}
一维差分
给一个区间加一个值或者减一个值
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 +10;
int a[N],b[N];
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
insert(i,i,a[i]);//重点理解==》差分（上面提到的加值操作）
}
while(m--)
{
int l,r,c;
cin>>l>>r>>c;
insert(l,r,c);
}
for(int i=1;i<=n;i++)
{
b[i]+=b[i-1];
cout<<b[i]<<' ';
}
return 0;
}
二维差分
某一个子矩阵内的值加一个值或者减去一个值
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N][N];
//int b[N][N];
void insert(int x1,int y1,int x2,int y2,int c)
{
// b[x1][y1] += c;
// b[x2+1][y1] -= c;
// b[x1][y2+1] -= c;
// b[x2+1][y2+1] += c;
a[x1][y1] += c;
a[x2+1][y1] -= c;
a[x1][y2+1] -= c;
a[x2+1][y2+1] += c;
}
int main()
{
int 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];
//insert(i,j,i,j,a[i][j]);//方法二求差分数组（要开两个数组）
}
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--) a[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];//方法一求差分数组（只需要开一个数组）
while(q--)
{
int x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
insert(x1,y1,x2,y2,c);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j] = a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
cout<<a[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
