2019牛客暑期多校(一)题解
A.Equivalent Prefixes
单调栈求每个i所能影响的最左端（思考下为什么不用考虑右端）。
#include<iostream>
#include<cstdio>
#include<stack>
#define ll long long
using namespace std;
const int maxn=100001;
int n;
int a[maxn],b[maxn];
int A[maxn],B[maxn];
void solve(int *t,int *T)
{
stack<int> s;
while(s.size()) s.pop();
for(int i=1;i<=n;i++)
{
while(s.size()&&t[s.top()]>t[i]) s.pop();
if(s.empty()) T[i]=1;
else T[i]=s.top()+1;
s.push(i);
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
solve(a,A);solve(b,B);
int i;
for(i=1;i<=n;i++)
if(A[i]!=B[i]) break;
cout<<i-1<<endl;
}
return 0;
} E.ABBA
开始就觉得是卡特兰数，只能说没学通，不然还是很容易看出来的。
卡特兰数处理类似一次进栈出栈问题，本题可以看为两次进出栈。
#include<bits/stdc++.h>
#define ll long long
#define M (ll)(1e9+7)
using namespace std;
ll CM[4001]={1};
ll Pow(ll a,ll b){ //快速幂
a%=M;
ll ans = 1;
for(;b;b>>=1)
{
if(b&1) ans = (ans*a)%M;
a = (a*a)%M;
}
return ans;
}
ll Quk(ll a,ll b){ //快速乘
a%=M;
ll ans = 0;
for(;b;b>>=1)
{
if(b&1) ans = (ans+a)%M;
a = (a+a)%M;
}
return ans;
}
ll C(ll m,ll n){ //n>=m
return Quk(Quk(CM[n],Pow(CM[n-m],M-2)),Pow(CM[m],M-2))%M;
}
ll A(ll m,ll n){ //n>=m
return Quk(CM[n],Pow(CM[n-m],M-2))%M;
}
int main()
{
ll a,b;
for(int i=1;i<4001;i++) CM[i]=Quk(CM[i-1],i);
while(cin>>a>>b)
{
ll ans=C(a+b,2*(a+b));
if(a) ans-=C(a-1,2*(a+b));
if(b) ans-=C(b-1,2*(a+b));
cout<<(ans+2*M)%M<<endl;
}
return 0;
} J.Fraction Comparision
还傻乎乎地用什么大数，明明题目都暗示地要死😓
把分数化为假分数，这样一来所有数字都能用long long表示。
#include<iostream>
#define ll long long
using namespace std;
ll a,b,c,d;
int main()
{
while(cin>>a>>b>>c>>d)
{
ll x=a/b,y=a%b;
ll p=c/d,q=c%d;
if(x>p) cout<<">"<<endl;
else if(x<p) cout<<"<"<<endl;
else
{
if(y*d>q*b) cout<<">"<<endl;
else if(y*d==q*b) cout<<"="<<endl;
else cout<<"<"<<endl;
}
}
return 0;
} 
查看12道真题和解析
