几道水题的题解

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

逆序排列

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

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

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

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

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

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

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

  1. 将原排列中,大于等于j的数加上1;
  2. 在最后添上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后,前面大于ki-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,需要满足两个条件:

  1. a的终点是b的起点。
  2. 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

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

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

给出一种优化:

  1. 读入a[i]时,假如k \bmod a[i]\ne0,则直接忽略,读入下一个数字。
  2. 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背包问题,1N每个数是一件物品,背包的容积为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-ii个数每个都加上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;
} 

留下评论

您的电子邮箱地址不会被公开。