总复习
目标
最后一晚上了 把知识点大概过一遍 盲点或者快忘掉的东西捡一下
高精度
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//用一个t去接每个位的和 当然前提是俩加数的某位上有
//得到的结果%10存入C的该位 剩下的留到下一位当进位
//如果最后俩加数的某位都没东西了 而t还在 就意味着有一个进位 在C中再进一位
//结果仍是逆序存着的
vector<int> add(vector<int> &A,vector<int> &B){
vector<int> C;
int t=0;
for(int i=0;i<A.size() || i<B.size();i++){
if(i<A.size()) t+=A[i];
if(i<B.size()) t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(1);
return C;
}
//减法需要考虑大减小还是小减大 一律让大的减小的 由题意而定加负号
//所以 得先进行比较
bool cmp(vector<int> &A,vector<int> &B){
if(A.size()!=B.size())
return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--)
if(A[i]!=B[i])
return A[i]>B[i];
return true;
}
//同样用t来存储 每位相减的结果 由于确定了A更大 所以只可能B中某位没有
//减完之后可能为负数（也就是不够减)
//对于不够减的情况 我们会选择借位 也就是+10 不过我们把+10的操作滞后 减完再+10 再%10就是该位结果
//而如果真的不够减了 借了一位的话 就需要把t置为1 让下轮多减去1
vector<int> del(vector<int> &A,vector<int> &B){
vector<int> C;
int t=0;
for(int i=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size())
t-=B[i];
C.push_back((t+10)%10);
if(t<0) t=1;
else t=0;
}
while(C.size()>1 && C.back()==0)
C.pop_back();
return C;
}
//这里的乘法不太一样 不是两位两位乘 而是直接用小数作为整体 去与大数的每一位相乘
//用t存储这某位的乘积 同样 模10得到当前位答案 /=10得到下一位的进位
vector<int> mul(vector<int> &A,int c){
vector<int> C;
int t=0;
for(int i=0;i<A.size() || t;i++) {
if(i<A.size())
t+=A[i]*c;
C.push_back(t%10);
t/=10;
}
while(C.size()>1 && C.back()==0)
C.pop_back();
return C;
}
// 除法与加减乘不同 它是从高位开始算 按道理是正序存比较好 但是为了统一 这里也是逆序存
// 那么我们就再逆序取出来做运算 就变成从高位开始做了
// 用r表示余数 在除法中 每轮的被除数都是 上轮的余数*10 + 当前位的数 得到的结果是/b 剩下的余数是%b
// 这个性质对于第一位也是适用的 因为r-0 0*10+第一位 仍等于第一位 不影响结果
vector<int> div(vector<int> &A,int b,int &r){
vector<int> C;
r=0;
for(int i=A.size()-1;i>=0;i--){
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());
while(C.size()>1 && C.back()==0)
C.pop_back();
return C;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string a,b;
int c;
vector<int> A,B;
cin>>a>>b>>c;
for(int i=a.size()-1;i>=0;i--){
A.push_back(a[i]-'0');
}
for(int i=b.size()-1;i>=0;i--){
B.push_back(b[i]-'0');
}
auto ADD=add(A,B);
for(int i=ADD.size()-1;i>=0;i--)
cout<<ADD[i];
cout<<endl;
if(cmp(A,B)){
auto DEL=del(A,B);
for(int i=DEL.size()-1;i>=0;i--)
cout<<DEL[i];
}
else{
auto DEL=del(B,A);
cout<<"-";
for(int i=DEL.size()-1;i>=0;i--)
cout<<DEL[i];
}
cout<<endl;
auto MUL=mul(A,c);
for(int i=MUL.size()-1;i>=0;i--)
cout<<MUL[i];
cout<<endl;
int r=0;
auto DIV=div(A,c,r);
for(int i=DIV.size()-1;i>=0;i--)
cout<<DIV[i];
cout<<endl<<r<<endl;
return 0;
}
__int128
无需读写的情况下 用int128是非常香的
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int __int128
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
return 0;
}
实在要用 看看记得住这个吗 如果不行就高精度吧
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int __int128
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*f;
}
void write(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int a=read();
int b=read();
int sum=a+b;
write(sum);
return 0;
}
基础算法篇
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//基础算法篇
//二分
// ----| ---- 找最大 l=mid r=mid-1 mid=l+r+1>>1
int l=0,r=n;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
// ---- |----- 找最小 r=mid l=mid+1 mid=l+r>>1
int l=0,r=n;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
//双指针 三模型
//1、 i不断走 j符合条件才走 不走回头路 将n*n降到2n
//2、 ij对撞 假定排序后求和 i为小端 j为大端 若结果偏大 j动 若结果偏小 i动
//3、 匹配问题 i一直走 j满足了才走 和1类似
int i=0;
for(int j=0;j<m;j++)
if(i<n && a[i]==b[j])
i++;
if(i==n) cout<<"yes";
else cout<<"no";
//前缀和
//一维
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int l,r;cin>>l>>r;
cout<<s[r]-s[l-1];
//二维
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
//差分
//一维
void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
for(int i=1;i<=n;i++){
cin>>a[i];
insert(i,i,a[i]);
}
int T;cin>>T;
while(T--){
int l,r,c;cin>>l>>r>>c;
insert(l,r,c);
}
for(int i=1;i<=n;i++)
b[i]+=b[i-1];
//二维
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;
}
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]);
}
}
while(T--){
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++){
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
}
}
return 0;
}
位运算
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int lowbit(int x){
return x&-x;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//位运算篇
// ^ 异或 相同为0 不同为1
int x=1,y=1,z=0;
cout<<(x^y)<<endl;
cout<<(x^z)<<endl;
x=5;
// & 取某一位 &1取最后一位
if(x&1) cout<<"奇数"<<endl;
//lowbit 取最后一位1 配套while 可求有多少个1
int cnt=0;
while(x){
x-=lowbit(x);
cnt++;
}
cout<<cnt<<endl;
//bitset 将k进制转为二进制存入容器
bitset<8> bits(7);
cout<<bits<<endl;
//主要是方便转为字符串进行操作 具体操作查文档
cout<<bits.to_string()<<endl;
return 0;
}
单调栈/队列
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//单调栈
//找每个数 左/右 最近的 小/大于它的数
//把当前点 当作是单调栈的最值元素
//以它为基准去剔除栈中不符合条件的数 当踢完之后 栈顶就是答案 再把该数加入栈中
while(tt && x<=stk[tt])
tt--;
//栈顶为答案 进行操作
stk[++tt]=x;
//单调栈+二分
// 找每个数 左右 最远的 小大于它的数
//不以该点为中心 而是以栈为中心
//若该点的加入能保持栈的单调性 就说明前面没有比它大或小的数
//若尝试加入该点 会破坏单调性
//就说明前面一定有若干元素要大于或小于它 那么就可以借助单调栈的单调性进行二分 找到第一个大于\小于它的数
//找第一个 显然是用 ---- |----模板 r-mid l=mid+1
for(int i=1;i<=n;i++){
if(stk.empty() || a[i]<a[stk.back()]){
stk.push_back(i);
ans[i]=i;
}
else{
int l=0,r=stk.size()-1;
while(l<r){
int mid=l+r>>1;
if(a[stk[mid]]<a[i])
r=mid;
else
l=mid+1;
}
ans[i]=stk[r];
}
}
//单调队列
//找窗口最小值 (在队头)
void get_min(int a[],int b[],int tot,int k)
{
int hh=0,tt=-1;
for(int i=0;i<tot;i++)
{
if(hh<=tt && i-q[hh]>=k)
hh++;
//求最小 递增区间 若出现向下 出队
while(hh<=tt && a[i]<=a[q[tt]])
tt--;
q[++tt]=i;
//当前区间的最大值为队头
b[i] = a[q[hh]];
}
}
//找窗口最大
void get_max(int a[],int b[],int tot,int k)
{
int hh=0,tt=-1;
for(int i=0;i<tot;i++)
{
if(hh<=tt && i-q[hh]>=k)
hh++;
//求最大 递减区间 若出现向上 出队
while(hh<=tt && a[i]>=a[q[tt]])
tt--;
q[++tt]=i;
//当前区间的最大值为队头
b[i] = a[q[hh]];
}
}
return 0;
}
串
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//判断字符是什么
//isalpha 是不是英文字母 isdigit是不是数字 isupper 是不是大写 toupper/tolower大小写转换
//数字变字符 +'0' 字符变数字 -'0'
//int变string to_string
//string变int stoi 若过大 就直接用高精度 vector反向存储
string s="123";
int num=stoi(s);
cout<<num;
//反转 reverse
reverse(s.begin(),s.end());
//筛有效字符
string filter(const string& str) {
string res;
for (int i = 0; i < str.size(); ++i) {
auto c = str[i];
if (isalpha(c)) {
res += tolower(c);
indexes.push_back(i); // 记录当前字符在原始字符串中的位置
}
}
return res;
}
//回文串问题
//中心拓展算法 以每个点为潜在回文中心 向两边拓展 实际是暴力
typedef pair<int,int> PII;
PII findLongestPalindrome(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return {left + 1, right - 1};
}
main:
for (int i = 0; i < str.size(); ++i) {
auto [left1, right1] = findLongestPalindrome(str, i, i);
auto [left2, right2] = findLongestPalindrome(str, i, i + 1);
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
//回文串还可以用字符串哈希加二分解决
//字符串哈希是 用131为进制的方式做的
typedef unsigned long long ULL;
const int N=2000010,P=131;
char str[N];
ULL ho[N],hr[N],p[N];
ULL find(ULL h[],int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
main:
int n=strlen(str+1);
n*=2;
for(int i=n;i>0;i-=2){
str[i]=str[i/2];
str[i-1]='#';
}
p[0]=1;
for(int i=1,j=n;i<=n,j>=1;i++,j--){
ho[i]=ho[i-1]*P+str[i];
hr[i]=hr[i-1]*P+str[j];
p[i]=p[i-1]*P;
}
int res=0;
for(int i=1;i<=n;i++){
int l=0,r=min(i-1,n-i);
while(l<r){
int mid=l+r+1>>1;
if(find(ho,i-mid,i-1)==find(hr,n-(i+mid)+1,n-(i+1)+1))
l=mid;
else
r=mid-1;
}
if(isalpha(str[i-r]))
res=max(res,r+1);
else
res=max(res,r);
}
//循环同构
//一个字符串是否可以由另一个字符串循环拼接得到 比较常规的思路是拼接一份 然后在长的里面find短的
//还有一个思路就是 把两个串都用最小表示法表示出来 如果相等 就说明是可以循环拼接得到的
#include<bits/stdc++.h>
using namespace std;
const int N=2000010;
char a[N],b[N];
int n;
int get_min(char s[]){
int i=0,j=1,k;
while(i<=n && j<=n)
{
k=0;
while(k<n && s[i+k]==s[j+k])
k++;
if(k==n)
break;
if(s[i+k]>s[j+k])
i+=k+1;
else
j+=k+1;
if(i==j)
j++;
}
int res=min(i,j);
s[res+n]='\0';
return res;
}
int main()
{
scanf("%s%s",a,b);
n=strlen(a);
memcpy(a+n,a,n);
memcpy(b+n,b,n);
int ap=get_min(a),bp=get_min(b);
if(strcmp(a+ap,b+bp))
puts("No");
else
{
puts("Yes");
puts(a+ap);
}
return 0;
}
//字符串哈希 重点熟悉一下
/*
用P进制换10进制的方式
P取经验值 131
即131进制的数转变成10进制(把字符串当成一个131进制数)
模上2^{64}
等价于一个8字节的东西溢出 直接用unsigned long long存
将本该是问题的溢出巧妙转变成对2^{64}取模
由此可以处理出所有字符串的一个哈希值
为了求某一段显然是前缀和问题
预处理出所有前缀字符串的哈希值的前缀和数组
求某一段s[r]-s[l]
发现错了几位 得把前缀（l）部分 左移到与r 的高位匹配位置上去（后几位补0）
左移一次就是p 左移两位就是p^2
以此类推 要让l与r对齐 实际上是要左移r-l+1位
要快速求到p^{r-l+1}
每一位是乘上一个p的n次方
可以把p预处理出来
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=100010,P=131;
char str[N];
ULL h[N],p[N];
int n,m;
ULL get(ULL h[],int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
cin>>n>>m;
cin>>str+1;
p[0]=1;
for(int i=1;i<=n;i++){
h[i]=h[i-1]*P+str[i];
p[i]=p[i-1]*P;
}
while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(get(h,l1,r1)==get(h,l2,r2))
puts("Yes");
else
puts("No");
}
return 0;
}
return 0;
}
自定义排序
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//单关键字排序
struct Interval {
int start, end;
// 重载 < 操作符以按结束时间升序排序
bool operator<(const Interval& rhs) const {
return end < rhs.end;
}
};
//多关键字排序
struct Person {
string name;
int age;
// 重载 < 操作符以先按年龄升序排序，再按姓名字典序排序
bool operator<(const Person& rhs) const {
if (age != rhs.age)
return age < rhs.age;
return name < rhs.name;
}
};
//优先队列
priority_queue<int> maxHeap;//大根堆
priority_queue<int, vector<int>, greater<int>> minHeap;//小根堆
struct Person {
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
//基于年龄构建最小堆
bool operator<(const Person& rhs) const {
return age > rhs.age;
}
};
priority_queue<Person> people;
struct Person {
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
};
//基于年龄构建最大堆
struct CompareAge {
bool operator()(const Person& a, const Person& b) {
return a.age < b.age; // 较大的年龄优先
}
};
priority_queue<Person, vector<Person>, CompareAge> people;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
vector<Interval> intervals = {{1, 4}, {2, 3}, {8, 10}};
sort(intervals.begin(), intervals.end());
vector<Person> people = {{"John", 30}, {"Jane", 25}, {"John", 25}};
sort(people.begin(), people.end());
return 0;
}
日期问题
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool is_leap(int y){
return y%100 && y%4==0 || y%400==0;
}
int get_days(int y,int m){
return days[m]+(m==2 && is_leap(y));
}
void next_day(int &y,int &m,int &d){
d++;
if(d>get_days(y,m)){
d=1;
m++;
if(m>12){
m=1;
y++;
}
}
}
bool check_date(int y,int m,int d){
if(m<1 || m>12) return false;
if(d<1 || d>get_days(y,m)) return false;
return true;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
while ((curYear < 给定年份) ||
(curYear == 给定年份 && curMonth < 给定月份) ||
(curYear == 给定年份 && curMonth == 给定月份 && curDay < 给定日子)) {
// 执行 next_day 操作
}
return 0;
}
拓展 日期差值 用前缀和思想
// 计算从公元1年1月1日到指定日期的总天数
int daysFromStart(int year, int month, int day) {
int totalDays = 0;
// 添加之前年份的天数
for(int y = 1; y < year; y++) {
totalDays += isLeapYear(y) ? 366 : 365;
}
// 添加当前年份的月份天数
for(int m = 1; m < month; m++) {
totalDays += days[m];
if(m == 2 && isLeapYear(year)) {
totalDays++;
}
}
// 添加当前月份的天数
totalDays += day;
return totalDays;
}
int dateDiff=daysFromStart(endYear,endMonth,endDay) - daysFromStart(startYear,startMonth,startDay) + 1;
数论
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//判断素数
bool is_prime(int n){
if(n < 2) return false;
for(int i = 2;i <= n / i;i ++){
if(n % i == 0){
return false;
}
}
return true;
}
// 筛素数
set<int> primes;
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!isnot_prime[i]){
primes.insert(i);
for(int j=i;j<=n;j+=i)
isnot_prime[j]=true;
}
}
}
//分解质因数
void divide(int x)
{
for(int i=2;i<=n/i;i++){
while(n%i==0){
h[i]++,n/=i;
}
}
if(n>1)
h[n]++;//大于sqrt(n) 的质因子 要么没有 要么只有一个
}
//判断约数
set<int> get_divisors(int n){
set<int> res;
for(int i=1;i<=n/i;i++){
if(n%i==0){
res.insert(i);
res.insert(n/i);
}
}
return res;
}
//约数个数
unordered_map<int,int> weight;
for(int i=2;i<=n/i;i++){
while(n%i==0){
weight[i]++;
n/=i;
}
}
if(n>1)
weight[n]++;
for(auto x:weight){
res=res*(x.second+1);
}
//约数之和
unordered_map<int,int> weight;
for(int i=2;i<=n/i;i++){
while(n%i==0){
weight[i]++;
n/=i;
}
}
if(n>1)
weight[n]++;
LL res=1;
for(auto prime:weight){
int base=prime.first,index=prime.second;
LL temp=1,sum=1;
while(index--){
temp=temp*base%mod;
sum=(sum+temp)%mod;
}
res=res*sum%mod;
}
cout<<res;
//gcd lcm
while(b){
int c=a%b;
a=b;
b=c;
}
cout<<a<<endl;
//或者
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
//另外还有库函数 __gcd
cout<<__gcd(a,b)<<endl;
//三个数的gcd、lcm
gcd(a,b,c)=gcd(gcd(a,b),c);
lcm(a,b)=(a*b)/gcd(a,b);
lcm(a,b,c)=lcm(lcm(a,b),c);
//快速幂
long long qmi(long long a,int k,int p){ //注意a要传入long long a是指数级增长的 容易爆int
long long res=1%p; //防止p=1 res=1%1=0 而不是 1
while(k){
if(k&1)
res=res*a%p;
k>>=1;
a=a*a%p; //不传long long 的话 这里用 a=(long long)a*a%p;
}
return res;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
return 0;
}
其余见根据时间复杂度分析算法 以及最近补充的国赛部分内容
💬 评论