阿里巴巴 算法岗 笔试真题 5月23号-分组计数

分组计数(C/Py/Java /Js/Go)题解阿里研发岗 0523笔试 第一题题目内容给定nnn个人的权值序列a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​保证aaa已按非降序排列。需要将所有人分成若干组每组人数只能为111或222。规则如下单人一组不受限制。两人一组时必须选择下标相邻的两个人(i−1,i)(i-1,i)(i−1,i)并满足∣ai−ai−1∣≤K|a_i - a_{i-1}| \le K∣ai​−ai−1​∣≤K。请你计算共有多少种合法的分组方案答案对109710^9 71097取模。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数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行每行输出一个整数表示合法分组方案数对109710^9 71097取模后的结果。样例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。题解和思路思路实现思路动态规划定义dp其中dp[i]表示i分组之后可以得到的方案数。状态转移当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]算法总体时间复杂度为OnC#includebits/stdc.husingnamespacestd;constlongMOD1e97;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn,k;cinnk;vectorlonga(n);for(inti0;in;i){cina[i];}vectorlongdp(n1,0);dp[0]1;// 动态规划for(inti1;in;i){dp[i]dp[i-1];if(i1a[i-1]-a[i-2]k){dp[i](dp[i]dp[i-2])MOD;}}coutdp[n]endl;}return0;}Javaimportjava.io.*;importjava.util.*;publicclassMain{staticfinallongMOD1000000007L;publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intTInteger.parseInt(br.readLine());while(T--0){String[]strsbr.readLine().split( );intnInteger.parseInt(strs[0]);intkInteger.parseInt(strs[1]);long[]anewlong[n];strsbr.readLine().split( );for(inti0;in;i){a[i]Long.parseLong(strs[i]);}long[]dpnewlong[n1];dp[0]1;// 动态规划for(inti1;in;i){dp[i]dp[i-1];if(i1a[i-1]-a[i-2]k){dp[i](dp[i]dp[i-2])MOD;}}System.out.println(dp[n]);}}}pythonMOD1000000007Tint(input())for_inrange(T):n,kmap(int,input().split())alist(map(int,input().split()))dp[0]*(n1)dp[0]1# 动态规划foriinrange(1,n1):dp[i]dp[i-1]ifi1anda[i-1]-a[i-2]k:dp[i](dp[i]dp[i-2])MODprint(dp[n])Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,lineinput.push(line));rl.on(close,(){constMOD1000000007;letidx0;constTNumber(input[idx]);constans[];for(lett0;tT;t){const[n,k]input[idx].split( ).map(Number);constainput[idx].split( ).map(Number);constdpnewArray(n1).fill(0);dp[0]1;// 动态规划for(leti1;in;i){dp[i]dp[i-1];if(i1a[i-1]-a[i-2]k){dp[i](dp[i]dp[i-2])MOD;}}ans.push(dp[n]);}console.log(ans.join(\n));});Gopackagemainimport(bufiofmtos)constMODint641000000007funcmain(){in:bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,T)for;T0;T--{varn,kintfmt.Fscan(in,n,k)a:make([]int64,n)fori:0;in;i{fmt.Fscan(in,a[i])}dp:make([]int64,n1)dp[0]1// 动态规划fori:1;in;i{dp[i]dp[i-1]ifi1a[i-1]-a[i-2]int64(k){dp[i](dp[i]dp[i-2])MOD}}fmt.Println(dp[n])}}