T1 打工

PS：本人比较懒就不发原题了（orz），网上查就有
想到了是DP但是转移有一点问题（雾…），然后只好特判+爆搜水过20分

题解：

30分做法：
首先我们发现得到的序列有一个性质，即 <nobr> a[i]<=max(a[j])+1　(j<i) </nobr>
根据这个性质我们可以暴力地枚举每种方案，判断给出的序列属于哪个方案
50分做法：
30分做法+特判两个特殊的点（递推）
70分做法：
记忆化搜索（同100分做法）
100分做法：
用 <nobr> f[i][j] </nobr>表示i待选时，前i-1个数的最大值为j时的方案数
易得 <nobr> f[i][j]=f[i−1][j]×j+f[i−1][j−1] </nobr>
枚举 <nobr> i </nobr>的同时维护一个前缀最大值 <nobr> max </nobr>，将与 <nobr> a </nobr>的前 <nobr> i−1 </nobr>位严格相同，第 <nobr> i </nobr>位为 <nobr> 1 </nobr>~ <nobr> a[i]−1 </nobr>的答案累加到 <nobr> f[i][max] </nobr>即可，答案就是 <nobr> ∑ni=1f[n][i] </nobr>
考虑到空间可能爆，滚动数组优化即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

const int N=10010,mod=1000007;
LL f[2][N];
int maxn,n,a[N];
LL ans;
int main()
{
// freopen("maou.in","r",stdin);
// freopen("maou.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    maxn=a[1];
    bool u=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
            f[u][j]=(f[!u][j]*j+f[!u][j-1])%mod;
        f[u][maxn]=(f[u][maxn]+a[i]-1)%mod;
// for(int k=1;k<=i;k++) cout<<f[u][k]<<" ";
// cout<<endl;
        maxn=max(maxn,a[i]);
        u=!u;       
    }
    for(int i=1;i<=n;i++)
        ans=(ans+f[!u][i])%mod;
    printf("%lld",ans+1);
    return 0;   
}

T2 破解

30分做法：
暴力枚举选择哪些区间，哈希判重
100分做法：
考虑一种特殊情况，如果所有的区间都不相互覆盖，那么设有 <nobr> m </nobr>个区间，可以得到的串数目就是 <nobr> 2m </nobr>个
对于每一个区间 <nobr> [L,R] </nobr>，连一条 <nobr> L </nobr>到 <nobr> R+1 </nobr>的边（手玩一下就知道为什么了）
那么这样一直加边，如果构成一个联通块（大小为 <nobr> size </nobr>），那么通过这个连通块的任意 <nobr> size−1 </nobr>条边代表的区间都能组成第 <nobr> size </nobr>条边代表的区间，那么这个区间其实是没有用的,而且从这个连通块中任意选若干条边都不会构成重复的区间，所以这个连通块对答案的贡献就是 <nobr> 2size−1 </nobr>,最后的答案就应该 <nobr> 2m−cnt </nobr>,其中 <nobr> cnt </nobr>为连通块个数
维护连通块的话并查集就好了，可以将询问的区间离散化一下，因为L,R都比较小不离散化也可以，注意一些细节就好

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

const int mod=1000000007;
int fa[10000005];
int n,ans,m;

int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];   
}

int main()
{
// freopen("steins.in","r",stdin);
// freopen("steins.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n+1;i++) fa[i]=i;//!!
        ans=1;
        for(int i=1,l,r;i<=m;i++)
        {
            scanf("%d%d",&l,&r);
            int r1=find(l),r2=find(r+1);
            if(r1!=r2) fa[r1]=r2,ans=(ans<<1)%mod;      
        }
        printf("%d\n",ans);
    }
    return 0;
}

T3 书稿

题解：
待更（本人现在还不会QAQ）……
各种二维差分的差分的前缀和的前缀和的前缀和乱搞