几道水题的题解

这篇文章包含了这几道简单题的题解：

逆序排列

给出 $2$ 个数 $n$ 和 $k$ ，求 $1~n$ 的全排列中，逆序数为 $k$ 的排列有多少种。每个测试点包含 $T$ 组数据。

$1 \leq T \leq 10000, 2 \leq n \leq 1000, 0 \leq k \leq 20000$

$1$ 到 $n$ 的全排列有 $n!$ 个，每个测试点的数据组数很多。考虑动态规划。

和1296 有限制的排列一样，假如以“当前考虑到 $1$ 到 $N$ 的全排列的第 $i$ 位，且逆序对数为 $j$ 的排列个数”来定义状态 $d[i][j]$ ，必然会困于如何去重。即使找到去除重复数字的方法，也会导致时间复杂度偏高。

因此我们这样简化状态：定义 $d[i][j]$ 为 $1$ 到 $i$ 的全排列中，逆序对数为 $j$ 的排列数。可以发现 $d[n][j]$ 仍然包含了所需要的状态。

如何由 $1$ 到 $(i-1)$ 的全排列转移到 $1$ 到 $i$ 的全排列？怎么保证没有重复的数字？假如新排列第 $i$ 位是 $j$ ，这些新排列和 $1$ 到 $(i-1)$ 的全排列的关系是什么？

借鉴 1296 有限制的排列的思想（这两道题的在思想上很相像），我们可以把每一个 $1$ 到 $(i-1)$ 的全排列通过以下方式变成一个长度为 $i$ ，且最后一位为 $j$ 的全排列：

将原排列中，大于等于 $j$ 的数加上1；
在最后添上 $j$ 。

可以发现每个 $1$ 到 $(i-1)$ 的全排列都可以转化为各不相同的长度为 $i$ ，且最后一位为 $j$ 的全排列。（从数学上理解，最后一位确定，前 $i-1$ 位的排列数为 $(i-1)!$ ，也就是 $1$ 到 $(i-1)$ 的全排列个数。）

在理解上述内容的基础上，我们可以得到状态转移方程:

$d[i][j]=\sum_{k=1}^i d[i-1][j-(i-1-k+1)] = \sum_{k=1}^i d[i-1][j-(i-k)]$

在给第 $i$ 位填上 $k$ 后，前面大于 $k$ 的 $i-k$ 个数就会和 $k$ 构成逆序对。因此需要满足在转移之前有 $j-(i-k)$ 个逆序对。注意，这里计算的大于 $k$ 的个数，是指新排列中大于 $k$ 的个数。即在长度为 $i-1$ 的原排列中大于等于 $k$ 的个数。

由于频繁求区间和，可以考虑维护前缀和。长度为 $i$ 的全排列的状态只与长度为 $i-1$ 的全排列的状态有关，所以考虑滚动数组。

时间复杂度 $O(nk+TlogT)$

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const long long maxn=1000,mod=1e9 + 7;
long long n,k,done=1;
long long ans[10*maxn+5];
long long sum[2][20005];
struct qst{
    long long n,k,id;
}Q[maxn*10+5];
inline void read(long long &x){
    x=0;char c;long long f=1;
    do{
        c=getchar();if(c=='-')f=-1;
    }
    while(c>'9'||c<'0');
    do{
        x=x*10+c-'0';c=getchar();
    }
    while(c>='0'&&c<='9');
    x*=f;
}
inline long long max(long long a,long long b){
    return a>b?a:b;
}
long long d[2][20005];
void work(){
    d[0][0]=1;
    sum[0][0]=1;
    for(register int i=1;i<=k;++i){
        sum[0][i]=1;
    }
    for(register long long i=1;i<=n;++i){
        for(register long long nk=0;nk<=k;++nk){
            d[i&1][nk]=0;
            d[i&1][nk]=(sum[(i-1)&1][nk]-(nk-i>=0?sum[(i-1)&1][nk-i]:0)+mod)%mod;
            if(i==Q[done].n&&nk==Q[done].k){
                ans[Q[done++].id]=d[i&1][nk];
            }
            sum[i&1][nk]=((nk?sum[i&1][nk-1]:0)+d[i&1][nk])%mod;
        }
    }
}
inline bool cmp(qst a,qst b){
    if(a.n!=b.n)return a.n<b.n;
    return a.k<b.k;
}
int main(){
    long long T;
    read(T);
    for(register long long i=1;i<=T;++i){
        read(Q[i].n);
        read(Q[i].k);
        n=max(n,Q[i].n);
        k=max(k,Q[i].k);
        Q[i].id=i;
    }
    sort(Q+1,Q+1+T,cmp);
    work();
    for(register long long i=1;i<=T;++i){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

最长递增路径

一个无向图，可能有自环，有重边，每条边有一个边权。你可以从任何点出发，任何点结束，可以经过同一个点任意次。但是不能经过同一条边2次，并且你走过的路必须满足所有边的权值严格单调递增，求最长能经过多少条边。

$1 \leq N \leq 50000, 0 \leq M \leq 50000, 0 \leq W \leq 10^9$

有点像最长上升子序列，只不过是在图上。

考虑将每条无向边拆成两条有向边，按照边的大小排序，由于一条路径走过后不能再走，所以没有后效性。

每次从边 $a$ 转移到边 $b$ ，需要满足两个条件：

$a$ 的终点是 $b$ 的起点。
$a$ 的长度必须严格小于 $b$ 的。

考虑用数组 $maxb[]$ 保存每个节点作为终点的，已经走过的最长的边数。那么通过某条边从一个点 $u$ 走向另一个点 $v$ 时，可以用 $maxb[u]+1$ 来更新 $maxb[v]$ 。为了满足第二点，我们可以以边长为标准分段，将某几条长度相同的边处理完之后，再一起更新这些边更新过的 $maxb[]$ 。

时间复杂度 $O(mlogm)$

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const int maxn=5e4;
struct line{
    int u,v,w;
}l[maxn*2+5];
int ans;
int d[maxn*2+5],maxb[maxn+5];
inline void read(int &x){
    x=0;char c;int f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
inline bool cmp(line a,line b){
    return a.w<b.w;
}
int n,m;

int main(){
    read(n);read(m);
    for(register int i=1;i<=m;++i){
        read(l[i].u);read(l[i].v);read(l[i].w);
        l[i+m].w=l[i].w;
        l[i+m].u=l[i].v;
        l[i+m].v=l[i].u;
    }
    sort(l+1,l+1+2*m,cmp);
    int lst=1;
    for(register int i=1;i<=2*m;++i){
        if(l[i].w!=l[lst].w){
            for(register int j=lst;j<i;++j){
                maxb[l[j].v]=std::max(maxb[l[j].v],d[j]);
            }
            lst=i;
        }
        d[i]=maxb[l[i].u]+1;
        if(d[i]>ans)ans=d[i];
    }
    printf("%d\n",ans);
    return 0;
}

选数字

当给定一个序列a[0],a[1],a[2],…,a[n-1] 和一个整数K时，我们想找出,有多少子序列满足这么一个条件：把当前子序列里面的所有元素乘起来恰好等于K。每个测试点包含不超过20组数据， $1 \leq n \leq1000,2 \leq K \leq 100000000$

很显然是一道动态规划题。

读入一个数字，就可以用它与前面的数字能构成的数来构成新的数（或者给已有的数增加方案数）。这算是最普通的做法。

给出一种优化：

读入 $a[i]$ 时，假如 $k \bmod a[i]\ne0$ ，则直接忽略，读入下一个数字。
用 $a[i]$ 与之前已经生成的某个数 $x$ 构成新的数时，若 $k \bmod (x*a[i])\ne0$ 则跳过。

这样我们就可以保证，所有存入的数都是尽可能对答案有帮助的。因为假如一个数不能整除 $k$ ，必然不可能对答案造成影响。

在 $a[i]$ 与已有的数来更新新的数时，应该将所有的修改都保存起来，等到更新完了之后再应用更新。什么意思呢？假如读入了一个数 $3$ ，之前已经有了 ${2,6,18}$ 这三个数，且构成这三个数的方案数分别为 ${1,2,3}$ 。由我们的推算可知，加入 $3$ 后，可以由 $2*3$ 来使构成 $6$ 的方案数加 $1$ ，由 $6*3$ 使构成 $18$ 的方案数加 $1$ ，由 $18*3$ 使构成 $54$ 的方案数加 $1$ 。加上 $3$ 本身，处理之后的已有数字和方案数分别为： ${2,3,6,18,54}$ 和 ${1,1,3,4,1}$ 。但是如果我们边处理边更新，会导致同一个 $3$ 被重复计算。给 $6$ 的方案数加1后，新增的这个已经用过 $3$ 的方案，又与 $3$ 一起更新了 $18$ 的答案。所以应该把每次要修改的操作保存起来，把所有的待更新数更新完毕后，再应用修改到方案数组中。

由于 $k$ 较大，可能出现的数字不定，所以可以通过 $STL map$ 来作为数组。

时间复杂度大概是 $O(n log k)$ 。

#include<cstdio>
#include<map>
using std::map;
const long long maxn=1e3;
const long long mod=1000000007;
long long n,k;
long long a[maxn+5];
map<long long,long long>d;
map<long long,bool> ment;
long long mentd[maxn+5];
struct addo{
    long long to,val;
    addo(long long to=0,long long val=0):to(to),val(val){}
}add[maxn+5];
inline void read(long long &x){
    x=0;char c;long long f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
void work(){
    for(register long long i=1;i<=n;++i){
        read(a[i]);
        if(k%a[i]!=0)continue;
        long long lmentd=mentd[0],tadd=0;
        for(register long long j=1,y;j<=lmentd;++j){
            if(k%(y=a[i]*mentd[j])!=0)continue;
            add[++tadd]=addo(y,d[mentd[j]]);
            if(!ment[y]){
                mentd[++mentd[0]]=y;
                ment[y]=true;
            }
        }
        for(register long long j=1;j<=tadd;++j){
            d[add[j].to]+=add[j].val;
            d[add[j].to]%=mod;
        }
        d[a[i]]++;
        d[a[i]]%=mod;
        if(!ment[a[i]]){
            mentd[++mentd[0]]=a[i];
            ment[a[i]]=true;
        }
    }
    printf("%lld\n",d[k]);
}
int main(){
    long long T;
    read(T);
    while(T--){
        read(n);read(k);
        work();
        if(T){
           ment.clear();
           mentd[0]=0;
        }
    }
    return 0;
}

整数划分

将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。

$1 \leq N \leq 50000$

当成一个0/1背包问题， $1$ 到 $N$ 每个数是一件物品，背包的容积为 $N$ 。把普通背包（求最大价值）改为求价值之和即可。

但是这种做法的时间复杂度为 $O(N^2)$ ，很显然过不了此题的数据范围。

考虑用 $g[i][j]$ 表示考虑用 $i$ 个数构成 $j$ 的方案数。要求用的数各不相同，所以应该保证构造的数不出现重复。

用 $g[i][j]$ 表示用 $j$ 个数构成i的方案数，由于每个数各不相同，最多的数的个数 $m$ 满足 $(1+2+...+m=n)$ 。计算得知 $m_{max}=316$ 。

用 $i$ 个数字来组成 $j$ ，假如不选择数字 $1$ ，那么方案数为 $g[i][j-i]$ ，也就是把构成 $j-i$ 的 $i$ 个数每个都加上 $1$ ；假如要选择数字 $1$ ，为了保证前面没有数字 $1$ （题目要求所有数不相同），我们需要把前面 $i-1$ 个数加上1，再给最后一位放一个 $1$ 。方案数就是 $g[i-1][j-i]$ （前 $i-1$ 位构成 $j-i$ ）。

选择 $1$ 和不选择 $1$ ，包含了所有的情况。

于是我们得到状态转移方程：

$g[i][j]=g[i-1][j-i]+g[i][j-i].$

答案就是 $\sum_{i=1}^{316} g[i][n].$

代码：

#include<cstdio>
#include<cmath>
const long long mod=1e9+7;
const long long maxn=5e4;
long long g[320][maxn+5];
long long ans;
long long n,m;
int main(){
    scanf("%lld",&n);
    g[0][0]=1;
    for(register int i=1;i<=319;++i){
        for(register int j=i;j<=n;++j){
            g[i][j]=(g[i][j-i]+g[i-1][j-i])%mod;
        }
    }
    for(register int i=1;i<=319;++i){
        ans+=g[i][n];
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}

几道水题的题解

逆序排列

最长递增路径

选数字

整数划分

留下评论

取消回复