菜鸡的补题之路
这场好菜呀，呗两个队友带了三题，可能是太久没有刷题了吧，最近一直在复习和实训。
赛后补了几题，写下题解，之后继续补，继续写。

首先看到J题两分钟有人就a了，就跑去看了，然后就是一个签到，丢给大一的大佬写了个py过了，赛后自己用__int128 写了下。 


	
	

		#include <bits/stdc++.h>
	


	

		usingnamespacestd;
	


	

		typedeflonglongll;
	


	

		intmain()
	


	

		{
	


	

		    ll a,b,x,y;
	


	

		    while(cin>>x>>a>>y>>b){
	


	

		        if((__int128)x*b < (__int128)y*a) cout<<"<"<<endl;
	


	

		        elseif((__int128)x*b > (__int128)y*a) cout<<">"<<endl;
	


	

		        elsecout<<"="<<endl;
	


	

		    }
	


	

		    return0;
	


	

		}

然后是F题，还是丢人呀，不断的试，终于试出来了，面积的22倍，但是如果证明还没看懂，看懂了再补。
还有一种方法是叉姐直播时说的，撒点，比赛的时候怎么就没想到呢。

然后是a题。
题意就是给你两个数组，问两个数组的最长前缀是多少时满足，两个数组前缀在任意区间内最小值的位置相同。
比赛时想了几个方法，都有反例，然后最合理的就是找当前位置的值和上一个比上升还是下降，如果两个数组的单调性相反就不成立，或者是两个都同时下降就要比较比当前值小的一个树的位置。但是没想起单调栈，就一直没出，2h后，然后学弟就想暴力n方莽一下，就™莽过了。。。当时就自闭了（没道理啊，凭什么呀，那我不是白痴吗。。。
赛后用了单调栈就过了，题解说的笛卡尔树大概去了解了一下，大概就是这个意思。


然后贴两份代码，一份是学弟的暴力，一份是单调栈。 

	#include <iostream>





	#include <stdio.h>





	usingnamespacestd;





	intn,a[100010],b[100010];





	 





	intmain()





	{





	    while(~scanf("%d",&n))





	    {





	        for(inti=1;i<=n;i++) scanf("%d",&a[i]);





	        for(inti=1;i<=n;i++) scanf("%d",&b[i]);





	        intans=n;





	        for(inti=1;i<=n;i++)





	        {





	            intflag=1;





	            for(intj=i-1;j>0;j--)





	            {





	                if(a[j]>a[i]&&b[j]<b[i]||a[j]<a[i]&&b[j]>b[i])





	                {





	                    flag=0;





	                    break;





	                }





	                elseif(a[j]<a[i]&&b[j]<b[i]) break;





	            }





	            if(flag==0)





	            {





	                ans=i-1;





	                break;





	            }  





	        }





	        printf("%d\n",ans);





	    }





	    return0;





	}

单调栈 

	#include <bits/stdc++.h>





	usingnamespacestd;





	intmain()





	{





	    intn,m;





	    stack<int>a,b;





	    intnum[100005],num1[100005];





	    while(cin>>n){





	        for(inti=1;i<=n;i++) cin>>num[i];





	        for(inti=1;i<=n;i++) cin>>num1[i];





	        while(!a.empty()) a.pop();





	        while(!b.empty()) b.pop();





	        a.push(1);





	        b.push(1);





	        intans=n;





	        for(inti=1;i<=n;i++){





	            intpa=0,pb=0;





	            while(!a.empty()&&num[a.top()]>num[i]){





	                    a.pop();





	            }





	            if(!a.empty()) pa=a.top();





	            a.push(i);





	            while(!b.empty()&&num1[b.top()]>num1[i]){





	                    b.pop();





	            }





	            if(!b.empty()) pb=b.top();





	            b.push(i);





	            if(pa!=pb){





	                ans=i-1;





	                break;





	            }





	        }





	        cout<<max(1,ans)<<endl;





	    }





	    return0;





	}
但是但是。。。竟然
学弟的暴力跑的比单调栈还快

然后是B题，赛后看着题解，慢慢推的。
推了好久啊。
总结大概是裂项，乘法变加法，然后化简，求不定积分 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
long long power_mod(long long a, long long b, long long mod)
{
    long long ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    int n,m;
    ll num[1005];
    ios::sync_with_stdio(false);
    while(cin>>n){
        for(int i=1;i<=n;i++) cin>>num[i];
        ll sum=0;
        for(int i=1;i<=n;i++){
            ll ans=2*num[i];
            for(int j=1;j<=n;j++)
                if(i!=j) ans=(ans*(num[j]*num[j]%mod-num[i]*num[i]%mod+mod)%mod)%mod;
            sum=(sum+power_mod(ans,mod-2,mod))%mod;
        }
        cout<<sum<<endl;
    }
    return 0;
}

E题， 感觉解法挺多的，还有大佬画线格图，推排列组合的。
但是大多数还是直接dp，我是dp的A和B的个数的。
只有当ab没够的时候，或者是ba中少a的时候将a的个数加一就行
具体实现看代码吧 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int dp[2005][2005];
int main()
{
    int n,m;
    while(cin>>n>>m){
        for(int i=0;i<=n+m;i++){
            for(int j=0;j<=n+m;j++){
                dp[i][j]=0;
            }
        }
        dp[0][0]=1;
        for(int i=0;i<=n+m;i++){
            for(int j=0;j<=n+m;j++){
                if(i<n||(i-n)<min(j,m))
                    dp[i+1][j]=(dp[i][j]+dp[i+1][j])%mod;
                if(j<m||(j-m)<min(i,n))
                    dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
            }
        }
        /*
        for(int i=0;i<=n+m;i++){
            for(int j=0;j<=n+m;j++){
                cout<<dp[i][j]<<' ';
            }
            cout<<endl;
        }
        */
        cout<<dp[n+m][n+m]<<endl;
    }
    return 0;
}