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;
}