文件名是abcd的逆天考试（

算术（a）

题面：
给定一个长度为\(n\)的整数数列\(a_1,\dots,a_n\)，求有多少个有序对\((i,j)\)满足\(i<j\wedge a_ia_j<a_i+a_j\)
题解：
枚举\(j\)，有\(a_i(a_j-1)<a_j\)，对\(a_j\)分类讨论。
当\(a_j>1\)，\(a_i<a_j/(a_j-1)\)，即\(a_i\le 1\)。
当\(a_j=1\)，\(0<1\)，即\(a_i\)取任意值。
当\(a_j=0\)，\(a_i>0\)，即\(a_i\ge1\)。
当\(a_j>1\)，\(a_i<a_j/(a_j-1)\)，即\(a_i\ge1\)。
在枚举的同时统计前面有多少个\(\le1\)和\(\ge1\)的即可。
代码

#include<cstdio>
#define int long long
int n,a,ans;
signed main(){
    freopen("a.in","r",stdin),freopen("a.out","w",stdout),scanf("%lld",&n);
    for(int i=1,cntle1=0,cntme1=0;i<=n;i++){
        scanf("%lld",&a);
        if(a>1)ans+=cntle1;
        else if(a==1)ans+=i-1;
        else ans+=cntme1;
        if(a<=1)cntle1++;
        if(a>=1)cntme1++;
    }
    return printf("%lld\n",ans),fflush(stdout),fclose(stdin),fclose(stdout),0;
}

刷墙（b）

题面：
有\(n\)种颜色的刷子，每个刷子可以刷\([l_i,r_i]\)，新颜色会覆盖旧颜色，可以选择刷子的顺序，求墙上最多有多少种颜色。
题解：
因为点数较小，先离散化，然后动态规划。
状态：\(f(i,j)\)表示区间\([i,j]\)内最多有多少种颜色。
辅助函数：\(s(i,j)\)表示区间\([i,j]\)包含了多少种刷子。
转移方程:

在\([l,r]\)有中经过\([k,k+1]\)的刷子才能更新\(f(l,r)\)。
代码

#include<cstdio>
#include<algorithm>
const int N=605;
int n,t[N],cnt,l[N],r[N],s[N][N],f[N][N];
inline int find(int x){return std::lower_bound(t+1,t+cnt+1,x)-t;}
inline void tomax(int&x,int y){x<y&&(x=y);}
int main(){
    freopen("b.in","r",stdin),freopen("b.out","w",stdout),scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",l+i,r+i),t[++cnt]=l[i],t[++cnt]=r[i];
    std::sort(t+1,t+cnt+1),cnt=std::unique(t+1,t+cnt+1)-t-1;
    for(int i=1;i<=n;i++)l[i]=find(l[i]),r[i]=find(r[i]),s[l[i]][r[i]]++;
    for(int len=2;len<=cnt;len++)for(int l=1,r=len;r<=cnt;l++,r++){
        s[l][r]+=s[l+1][r]+s[l][r-1]-s[l+1][r-1];
        for(int i=l;i<r;i++)if(s[l][i]+s[i+1][r]<s[l][r])tomax(f[l][r],f[l][i]+f[i+1][r]+1);
    }
    return printf("%d\n",f[1][cnt]),fflush(stdout),fclose(stdin),fclose(stdout);
}