XP04-02 DAY04
2025-08-05 20:45:28
发布于：上海
12阅读
0回复
0点赞
今天写的很水，因为时间全拿来背模版了。
今日主要学习了单调队列,快速幂，数论。
中午记得重新过链接描述。（已重过）
一.单调队列
单调队列和单调栈从理论上而言其实差不多。
不过单调队列更灵活，更好玩。
单调队列可以辅助DP，将优化成。
一般优化的是跳跃型，区间型DP。
区间跟传统的区间不一样，更滑动窗口的窗口更像。
单调队列模版：
#include<bits/stdc++.h>
using namespace std;
long long a[1000005];
deque<int>dq;
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
while(!dq.empty()&&a[i]<a[dq.back()])dq.pop_back();
dq.push_back(i);
if(i>=k){
while(!dq.empty()&&dq.front()<=i-k)dq.pop_front();
cout<<a[dq.front()]<<" ";
}
}
while(!dq.empty())dq.pop_back();
cout<<endl;
for(int i=1;i<=n;i++){
while(!dq.empty()&&a[i]>a[dq.back()])dq.pop_back();
dq.push_back(i);
if(i>=k){
while(!dq.empty()&&dq.front()<=i-k)dq.pop_front();
cout<<a[dq.front()]<<" ";
}
}
return 0;
}
二.快速幂&数论
说实话，数论有点恶心，我为了背二元一次方程的模版下午多喝了一袋咖啡，但愿我今晚能有好的睡眠。
二元一次方程：
#include<bits/stdc++.h>
using namespace std;
long long a,b,c;
long long x,y;
int gcd(long long a,long long b){
return (b==0)?a:gcd(b,a%b);
}
void exgcd(long long a,long long b){
if(b==0){
x=1,y=0;
return;
}
exgcd(b,a%b);
long long t=x;
x=y;
y=t-(a/b)*y;
}
void solve(){
cin>>a>>b>>c;
if(c%gcd(a,b)!=0){
cout<<-1<<endl;
return;
}
exgcd(a,b);
x=x*(c/gcd(a,b));
y=y*(c/gcd(a,b));
long long dx=b/gcd(a,b);
long long dy=a/gcd(a,b);
long long k=x/dx;
if(x%dx<=0)k--;
long long x_min=x-dx*k;
long long y_max=y+k*dy;
k=y/dy;
if(y%dy<=0)k--;
long long x_max=x+dx*k;
long long y_min=y-dy*k;
if(y_max<=0||x_max<=0){
cout<<x_min<<" "<<y_min<<endl;
return;
}
cout<<(x_max-x_min)/dx+1<<" "<<x_min<<" "<<y_min<<" "<<x_max<<" "<<y_max<<endl;
}
int main(){
int t;
cin>>t;
while(t--)solve();
return 0;
}
快速幂：
#include<bits/stdc++.h>
using namespace std;
long long a,b,p;
long long c(long long x){
if(x==1)return a;
if(x%2==1){
x--;
return a*c(x/2)%p*c(x/2)%p;
}else return c(x/2)%p*c(x/2)%p;
}
int main(){
cin>>a>>b>>p;
cout<<a<<"^"<<b<<" "<<"mod"<<" "<<p<<"="<<c(b);
return 0;
}
逆元：
#include<bits/stdc++.h>
using namespace std;
long long n,a,p;
long long c(long long x){
if(x==1)return a;
if(x%2==1){
x--;
return a*c(x/2)%p*c(x/2)%p;
}else return c(x/2)%p*c(x/2)%p;
}
int main(){
cin>>n>>p;
for(long long i=1;i<=n;i++){
a=i;
cout<<c(p-2)<<" ";
}
return 0;
}
这里空空如也
有帮助，赞一个