企业官网建设流程全解析

分组计数(C++/Py/Java /Js/Go)题解

阿里研发岗 0523笔试 第一题

题目内容

给定nnn个人的权值序列a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​，保证aaa已按非降序排列。
需要将所有人分成若干组，每组人数只能为111或222。规则如下：

1. 单人一组不受限制。
2. 两人一组时，必须选择下标相邻的两个人(i−1,i)(i-1,i)(i−1,i)，并满足∣ai−ai−1∣≤K|a_i - a_{i-1}| \le K∣ai​−ai−1​∣≤K。
   请你计算共有多少种合法的分组方案，答案对109+710^9 + 7109+7取模。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T (1≤T≤105)T\ (1 \le T \le 10^5)T(1≤T≤105)表示数据组数，每组测试数据描述如下：
第一行输入两个整数n,K (1≤n≤2×105, 0≤K≤109)n, K\ (1 \le n \le 2 \times 10^5,\ 0 \le K \le 10^9)n,K(1≤n≤2×105,0≤K≤109)。
第二行输入nnn个整数a1,a2,…,an (∣ai∣≤1018)a_1,a_2,\dots,a_n\ (|a_i| \le 10^{18})a1​,a2​,…,an​(∣ai​∣≤1018)，并保证a1≤a2≤⋯≤ana_1 \le a_2 \le \dots \le a_na1​≤a2​≤⋯≤an​。
保证所有测试中nnn的总和不超过2×1052 \times 10^52×105。

输出描述

输出TTT行，每行输出一个整数，表示合法分组方案数对109+710^9 + 7109+7取模后的结果。

样例1

输入

3 4 1 1 2 4 10 4 0 1 2 3 4 5 2 1 1 2 4 7

输出

2 1 5

说明
第一组：只有相邻的(1,2)(1,2)(1,2)满足差值不超过KKK，因此方案为：全单人；或(1,2)(1,2)(1,2)配对其余单人，共222种。
第二组：相邻差均大于000，无法配对，只能全单人，答案为111。

题解和思路

思路

实现思路：动态规划

1. 定义dp其中dp[i]表示i分组之后可以得到的方案数。
2. 状态转移：
   • 当a[i] - a[i-1] <= k时， 状态转移dp[i] = dp[i-1] + dp[i -2]
   • 当a[i] - a[i-1] > k时， 状态转移dp[i] = dp[i-1]
3. 算法总体时间复杂度为O（n）

C++

#include<bits/stdc++.h>usingnamespacestd;constlongMOD=1e9+7;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn,k;cin>>n>>k;vector<long>a(n);for(inti=0;i<n;i++){cin>>a[i];}vector<long>dp(n+1,0);dp[0]=1;// 动态规划for(inti=1;i<=n;i++){dp[i]=dp[i-1];if(i>1&&a[i-1]-a[i-2]<=k){dp[i]=(dp[i]+dp[i-2])&MOD;}}cout<<dp[n]<<endl;}return0;}

Java

importjava.io.*;importjava.util.*;publicclassMain{staticfinallongMOD=1000000007L;publicstaticvoidmain(String[]args)throwsException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));intT=Integer.parseInt(br.readLine());while(T-->0){String[]strs=br.readLine().split(" ");intn=Integer.parseInt(strs[0]);intk=Integer.parseInt(strs[1]);long[]a=newlong[n];strs=br.readLine().split(" ");for(inti=0;i<n;i++){a[i]=Long.parseLong(strs[i]);}long[]dp=newlong[n+1];dp[0]=1;// 动态规划for(inti=1;i<=n;i++){dp[i]=dp[i-1];if(i>1&&a[i-1]-a[i-2]<=k){dp[i]=(dp[i]+dp[i-2])&MOD;}}System.out.println(dp[n]);}}}

python

MOD=1000000007T=int(input())for_inrange(T):n,k=map(int,input().split())a=list(map(int,input().split()))dp=[0]*(n+1)dp[0]=1# 动态规划foriinrange(1,n+1):dp[i]=dp[i-1]ifi>1anda[i-1]-a[i-2]<=k:dp[i]=(dp[i]+dp[i-2])&MODprint(dp[n])

Javascript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on("line",line=>input.push(line));rl.on("close",()=>{constMOD=1000000007;letidx=0;constT=Number(input[idx++]);constans=[];for(lett=0;t<T;t++){const[n,k]=input[idx++].split(" ").map(Number);consta=input[idx++].split(" ").map(Number);constdp=newArray(n+1).fill(0);dp[0]=1;// 动态规划for(leti=1;i<=n;i++){dp[i]=dp[i-1];if(i>1&&a[i-1]-a[i-2]<=k){dp[i]=(dp[i]+dp[i-2])&MOD;}}ans.push(dp[n]);}console.log(ans.join("\n"));});

Go

packagemainimport("bufio""fmt""os")constMODint64=1000000007funcmain(){in:=bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,&T)for;T>0;T--{varn,kintfmt.Fscan(in,&n,&k)a:=make([]int64,n)fori:=0;i<n;i++{fmt.Fscan(in,&a[i])}dp:=make([]int64,n+1)dp[0]=1// 动态规划fori:=1;i<=n;i++{dp[i]=dp[i-1]ifi>1&&a[i-1]-a[i-2]<=int64(k){dp[i]=(dp[i]+dp[i-2])&MOD}}fmt.Println(dp[n])}}