赛时成绩如下:
这应该是我力扣周赛的最好成绩了(虽然还是三题)
1. 两个数字的最大乘积
给定一个正整数
n。返回 任意两位数字 相乘所得的 最大 乘积。
注意：如果某个数字在
n中出现多次，你可以多次使用该数字。示例 1：
输入： n = 31
输出： 3
解释：
n的数字是[3, 1]。- 任意两位数字相乘的结果为：
3 * 1 = 3。- 最大乘积为 3。
示例 2：
输入： n = 22
输出： 4
解释：
n的数字是[2, 2]。- 任意两位数字相乘的结果为：
2 * 2 = 4。- 最大乘积为 4。
示例 3：
输入： n = 124
输出： 8
解释：
n的数字是[1, 2, 4]。- 任意两位数字相乘的结果为：
1 * 2 = 2,1 * 4 = 4,2 * 4 = 8。- 最大乘积为 8。
提示：
10 <= n <= 10^9
解题思路： 模拟, 把n的每个数位都取出来存的数组里面，然后对数组进行排序, 返回最后两个数的乘积即可
class Solution {
public:
int maxProduct(int n) {
vector<int> ans; int cnt=0;
while(n>0){
ans.push_back(n%10); n/=10;
cnt++;
}
sort(ans.begin(),ans.end());
return ans[cnt-1]*ans[cnt-2];
}
};2. 填充特殊网格
给你一个非负整数 N，表示一个 2^N x 2^N 的网格。你需要用从 0 到 2^2N - 1 的整数填充网格，使其成为一个 特殊 网格。一个网格当且仅当满足以下 所有 条件时，才能称之为 特殊 网格：
右上角象限中的所有数字都小于右下角象限中的所有数字。
右下角象限中的所有数字都小于左下角象限中的所有数字。
左下角象限中的所有数字都小于左上角象限中的所有数字。
每个象限也都是一个特殊网格。
返回一个 2^N x 2^N 的特殊网格。注意：任何 1x1 的网格都是特殊网格。
解题思路： 左上>左下>右下>右上，构造的网格是2^N*2^N, N=1时为2*2的网格，N=2时为4*4的网格...递归的进行划分即可, 2^N*2^N划分成4个子网格, 每个子网格大小为2^N-1*2^N-1大小，填充的时候我们就按 (左上>左下>右下>右上), 这个顺序进行填充每个子网格, 右上最小先填充右上, 递归参数分别为：(r, c)当前子网格的左上角坐标, size: 当前子网格的边长, or_grid: 当前子数组的起始填充数字, grid: 待填充的数组，
1. 右上：从(r,c+half) 开始，填充从or_grid数字开始的area个数字
2. 右下：从(r+half, c+half) 开始, 填充从or_grid+1*area数字开始的area个数字
3. 左下：从(r+half,c) 开始, 填充从or_grid+2*area数字开始的area个数字
4. 左上：从(r,c) 开始, 填充从or_grid+3*area数字开始的area个数字
如果你对递归熟练的话，其实很简单的，当然你递归参数也可以是上下左右边界，应该也是可以的
class Solution {
public:
void solve(int r, int c, int size, int or_grid, vector<vector<int>>& grid) {
if (size == 1) {
grid[r][c] = or_grid;
return;
}
int half = size / 2;
int area = half * half;
solve(r, c + half, half, or_grid + 0 * area, grid);
solve(r + half, c + half, half, or_grid + 1 * area, grid);
solve(r + half, c, half, or_grid + 2 * area, grid);
solve(r, c, half, or_grid + 3 * area, grid);
}
vector<vector<int>> specialGrid(int N) {
int size = 1 << N;
vector<vector<int>> grid(size, vector<int>(size,0));
solve(0, 0, size, 0, grid);
return grid;
}
};补充代码：
class Solution {
public:
void solve(int r, int c, int size, int or_grid, vector<vector<int>>& grid) {
if (size == 1) {
grid[r][c] = or_grid;
return;
}
int half = size / 2;
int area = half * half;
solve(r, c + half, half, or_grid + 0 * area, grid);
solve(r + half, c + half, half, or_grid + 1 * area, grid);
solve(r + half, c, half, or_grid + 2 * area, grid);
solve(r, c, half, or_grid + 3 * area, grid);
}
vector<vector<int>> specialGrid(int N) {
int size = 1 << N;
vector<vector<int>> grid(size, vector<int>(size,0)); int val=0;
auto dfs=[&](this auto&& dfs,int u,int d,int l,int r)->void{
if(d-u==1){
grid[u][l]=val; val++;
return;
}
int m=(d-u)/2;
dfs(u,u+m,l+m,r); //右上
dfs(u+m,d,l+m,r); //右下
dfs(u+m,d,l,l+m); //左下
dfs(u,u+m,l,l+m); //左上
};
dfs(0,size,0,size);
return grid;
}
};
// [0,2^N) [0,1,2,3,4) (0+2^N)/2, m即是左边子数组的右边界(开), 又是右边子数组的左边界(闭)3. 合并得到最小旅行时间
给你一个长度为
l公里的直路，一个整数n，一个整数k和 两个 长度为n的整数数组position和time。数组
position列出了路标的位置（单位：公里），并且是 严格 升序排列的（其中position[0] = 0且position[n - 1] = l）。每个
time[i]表示从position[i]到position[i + 1]之间行驶 1 公里所需的时间（单位：分钟）。你 必须 执行 恰好
k次合并操作。在一次合并中，你可以选择两个相邻的路标，下标为i和i + 1（其中i > 0且i + 1 < n），并且：
- 更新索引为
i + 1的路标，使其时间变为time[i] + time[i + 1]。- 删除索引为
i的路标。返回经过 恰好
k次合并后从 0 到l的 最小总旅行时间（单位：分钟）。
解题思路：这是一道划分划分型DP, 本来DP就弱，还好久没写类似的题了，第二题那个递归都写了十几分钟
在我们进行动态规划，设计状态的时候，原状态删除了一个数字，对后续子状态产生影响的话，那这个状态设计就是有问题的
l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]
[0,3]: 5(行驶一公里所用时间), [3,8]: 8, [8,10]: 3 [10,..]: 6
合并下标为 1 和 2 的路标，合并后：position=[0,8,10] , time=[5,11,6]
删除position[1], 此时我们把time[2]修改成8+3=11，对后续子状态产生影响了。
题目中说要进行k次合并，就会产生一个子数组，eg: time=[5,8,3,6] 合并一次后就变为[5],[8,3],[6], 恰好分成了n-k(4-1=3)个连续子数组，我们用区间[i.j] 来表示划分后的子数组。
对于两个相邻的子数组[i,j] ,[j+1,k], 我们需要从position[j] -> position[k], (i已经被删除了，选靠右的) ，每公里所需的时间为A的元素和。
设time的前缀和数组为prefix, 上述移动对答案的贡献为 (position[k]−position[j])* (s[j+1]−s[i])
eg: [5],[8,3],[6], A=[8,3], B=[6], 对应从position[2]=8, 移动到position[3]=10, 10-8=2, time=prefix[3]-prefix[1]=8+3-5=8+3=11, 所以这段的旅行的时间为2*11=22
在从左向右进行模拟的过程中，有当前子数组[i,j], 需要恰好left_K次合并操作
定义状态dfs(i,j,left_K), 完成剩余left_K 次合并后所需的最小总旅行时间
我们要枚举中间子数组已经了多少次合并操作，
枚举下一个子数组的右端点 k=j+1,j+2,…,min(n−1,j+1+leftK)，这意味着我们执行了 k−j−1 次合并操作，接下来要解决的问题变成：
1. 当前子数组为 [j+1,k]。
2. 还需执行恰好 leftK−(k−j−1) 次合并操作。
在上述情况下，完成剩余旅程需要的最小旅行时间，即 dfs(j+1,k,leftK−(k−j−1))。这两个子数组 [i,j] 和 [j+1,k] 对总旅行时间的贡献为 (position[k]−position[j])⋅(s[j+1]−s[i])。上述所有右端点k取最小值为某个阶段，递归边界：递归边界：当 j=n−1 时，必须有 leftK=0，所以 dfs(i,n−1,0)=0。
递归入口：dfs(0,0,k)，即答案。注意第一个子数组一定是 [0,0]。
补充如下：
class Solution {
public:
int minTravelTime(int l, int n, int k, vector<int>& position, vector<int>& time) {
vector<int> prefix(n,0);
for(int i=0;i<n-1;i++){
prefix[i+1]=prefix[i]+time[i];
}
vector<vector<vector<int>>> memo(n-1, vector<vector<int>>(n-1, vector<int>(k+1)));
return dfs(0,0,k,position,prefix,memo);
}
int dfs(int i,int j,int left_K, vector<int>& position,vector<int>& prefix,vector<vector<vector<int>>>& memo){
int n=position.size();
if(j==n-1){
return left_K>0?INT_MAX/2:0;
}
if(memo[i][j][left_K]>0){
return memo[i][j][left_K];
}
int res=INT_MAX;
int t=prefix[j+1]-prefix[i];
for(int k=j+1;k<min(n,j+2+left_K);k++){
int r=dfs(j+1,k,left_K-(k-j-1),position,prefix,memo)+(position[k]-position[j])*t;
res=min(res,r);
}
memo[i][j][left_K]=res;
return res;
}
};
// 1. [0,l]的道路, position数组为道路上路标的位置, 其中 position[0] = 0 且 position[n - 1] = l
// 2. time[i] 表示从 position[i](路标1) 到 position[i + 1](路标2), 行驶1km所需的时间
// 3. 你需要执行k次合并操作 -> 选择两个相邻的路标，下标为 i 和 i + 1, 删除i路标, times[i+1]=times[i]+times[i+1],(times[n-1]没用, 只用于合并{i和i+1})
// dfs(0,n-1)-> dfs(0,i)+dfs(i,n-1)
// 状态变量left,right,k, 额外维护一个preJAVA版：
class Solution {
public int minTravelTime(int l, int n, int k, int[] position, int[] time) {
int[] prefix=new int[n];
for(int i=0;i<n-1;i++){
prefix[i+1]=prefix[i]+time[i];
}
int[][][] memo = new int[n - 1][n - 1][k + 1];
return dfs(0, 0, k, position, prefix, memo); // 第一个子数组是 [0, 0]
}
private int dfs(int i, int j, int left_K, int[] position, int[] prefix, int[][][] memo) {
int n = position.length;
if (j == n - 1) {
return left_K > 0 ? Integer.MAX_VALUE / 2 : 0;
}
if (memo[i][j][left_K] > 0) {
return memo[i][j][left_K];
}
int res = Integer.MAX_VALUE;
int t = prefix[j + 1] - prefix[i];
for (int k = j + 1; k < Math.min(n, j + 2 + left_K); k++) {
int r = dfs(j + 1, k, left_K - (k - j - 1), position, prefix, memo) + (position[k] - position[j]) * t;
res = Math.min(res, r);
}
memo[i][j][left_K] = res; return res;
}
}4. 魔法序列的数组乘积之和
给你两个整数
一个整数序列M和K，和一个整数数组nums。seq如果满足以下条件，被称为 魔法 序列：
seq的序列长度为M。0 <= seq[i] < nums.length2seq[0] + 2seq[1] + ... + 2seq[M - 1]的 二进制形式 有K个 置位。这个序列的 数组乘积 定义为
prod(seq) = (nums[seq[0]] * nums[seq[1]] * ... * nums[seq[M - 1]])。返回所有有效 魔法 序列的 数组乘积 的 总和 。
由于答案可能很大，返回结果对
10^9 + 7取模。置位 是指一个数字的二进制表示中值为 1 的位。
解题思路：这题其实也很难，我过的很大一部分原因是洛谷有类似的题,
魔法序列的定义（题意）：
长度为 M 的序列 seq，其中每个元素 seq[i] 满足 0 <= seq[i] < nums.length
将序列中的每个元素作为 2 的幂次，即 2^seq[0] + 2^seq[1] + ... + 2^seq[M-1]，这个和的二进制表示中 1 的位数必须等于 K
序列的数组乘积是 nums[seq[0]] * nums[seq[1]] * ... * nums[seq[M-1]]
我们需要计算所有满足条件的魔法序列的数组乘积的总和，并对 1e9 + 7 取模
具体的思考过程如下：
seq的序列总共M个数, 每个元素seq[i] -> [0,N-1]
eg: M=7, 选出的seq序列为[0,0,0,1,1,1,1] -> prod(seq)=nums[0]^3*nums[1]^4
我们先不管题目中魔法序列的第3个条件, 假设上述选出的seq序列是符合条件的
那么它的全排列肯定也是符合条件的, 但是由于seq序列里面有重复的0和1,
因此, 7!/(3!*4!)个 nums[0]^3*nums[1]^4 的总和即为答案
总结式子: M!*(nums[0]^3/3!)*(nums[1]^4/4!) -> 我们选出的数(eg: nums[0]) 对答案的贡献值就是(nums[0]^3/3!)
eg: [0,0,0,1,1,1,1,2,2] [0,0,0,1,1,2,2,2,2]
上述两个seq序列可以写成{nums[0]^3/3!}*(nums[1]^4/4! * nums[2]^2/2! + nums[1]^2/2! * nums[2]^4/4!)
注：上述两个seq序列的后6位其实是一个子问题(类似于我们前面选了3个0, 后续每一位应该怎么选)
eg: A={00111.... 0011...}, B={00011122.. 00011222...}
当我们枚举（1个0/2个0...）的时候, (括号中的)情况是加法的关系, 但是单独一个序列(eg: 00011122..)后面(1/2), 的子问题是乘法的关系。状态设计：
我们接下来看[魔法 序列] 的第三个条件, eg: 0001111 -> 2^0+2^0+2^0+2^1+2^1+2^1+2^1
i: 现在选的是seq[i] -> [0,N-1]
2. seq序列总长: M
3. 序列总和的二进制位: S（二进制位中1的个数等于K）
dfs(i,left_M,S) 根据数据范围得知, S的总和太大了, 因此就上述设计就不太合适了。
我们经过观察得知, 2^i加到当前序列总和S中时, 它只会对i左侧的高位产生进位的影响, 不会对右侧的低位产生进位的影响。
此时，我们就可以在一边累计2^i的时候, 一边用ans_count去统计S低位中1的个数了。此时我们通过右移操作, 就可以将原状态个数进行缩减
原状态设计中的第三个参数, 就可以修改成S右移后的值, 增加第四个参数为, left_K: 低二进制位中1的个数
代码如下：
const int p=1e9 + 7;
const int MX=31;
long long F[MX]; //F[i] =i;
long long INV_F[MX]; //INV_F[i]=i!^-1
int quPow(long long a,int n){
int res=1;
while(n){
if(n&1) res=res*a%p;
a=a*a%p;
n>>=1;
}
return res;
}
void init(){
F[0] = 1;
for (int i = 1; i < MX; i++) {
F[i] = F[i - 1] * i % p;
}
INV_F[MX - 1] = quPow(F[MX - 1],p - 2);
for (int i = MX - 1; i; i--) {
INV_F[i - 1] = INV_F[i] * i % p;
}
}
class Solution {
public:
int magicalSum(int m, int k, vector<int>& nums) {
init();
int n = nums.size();
vector pow_v(n, vector<int>(m + 1));
for (int i = 0; i < n; i++) {
pow_v[i][0] = 1;
for (int j = 1; j <= m; j++) {
pow_v[i][j] = 1LL * pow_v[i][j - 1] * nums[i] % p;
}
}
vector memo(n, vector(m + 1, vector(m / 2 + 1, vector<int>(k + 1, -1))));
auto dfs = [&](this auto&& dfs, int i, int left_m, int x, int left_k) -> int {
int c1 =__builtin_popcount(x);
if (c1 + left_m < left_k) {
return 0;
}
if (i == n) {
return left_m == 0 && c1 == left_k;
}
int& res = memo[i][left_m][x][left_k];
if (res != -1) {
return res;
}
res = 0;
for (int j = 0; j <= left_m; j++) {
int bit = (x + j) & 1;
if (bit <= left_k) {
int r = dfs(i + 1, left_m - j, (x + j) >> 1, left_k - bit);
res = (res + 1LL * r * pow_v[i][j] % p * INV_F[j]) % p;
}
}
return res;
};
return 1LL * dfs(0, m, 0, k) * F[m] % p;
}
};
seq的序列总共M个数, 每个元素seq[i] -> [0,N-1]
eg: M=7, 选出的seq序列为[0,0,0,1,1,1,1] -> prod(seq)=nums[0]^3*nums[1]^4
我们先不管题目中魔法序列的第3个条件, 假设上述选出的seq序列是符合条件的
那么它的全排列肯定也是符合条件的, 但是由于seq序列里面有重复的0和1,
因此, 7!/(3!*4!)个 nums[0]^3*nums[1]^4 的总和即为答案
总结式子: M!*(nums[0]^3/3!)*(nums[1]^4/4!) -> 我们选出的数(eg: nums[0]) 对答案的贡献值就是(nums[0]^3/3!)
eg: [0,0,0,1,1,1,1,2,2] [0,0,0,1,1,2,2,2,2]
上述两个seq序列可以写成{nums[0]^3/3!}*(nums[1]^4/4! * nums[2]^2/2! + nums[1]^2/2! * nums[2]^4/4!)
注：上述两个seq序列的后6位其实是一个子问题(类似于我们前面选了3个0, 后续每一位应该怎么选)
eg: A={00111.... 0011...}, B={00011122.. 00011222...}
当我们枚举（1个0/2个0...）的时候, (括号中的)情况是加法的关系, 但是单独一个序列(eg: 00011122..)后面(1/2), 的子问题是乘法的关系。
状态设计：
我们接下来看[魔法 序列] 的第三个条件, eg: 0001111 -> 2^0+2^0+2^0+2^1+2^1+2^1+2^1
i: 现在选的是seq[i] -> [0,N-1]
2. seq序列总长: M
3. 序列总和的二进制位: S（二进制位中1的个数等于K）
dfs(i,left_M,S) 根据数据范围得知, S的总和太大了, 因此就上述设计就不太合适了。
我们经过观察得知, 2^i加到当前序列总和S中时, 它只会对i左侧的高位产生进位的影响, 不会对右侧的低位产生进位的影响。
此时，我们就可以在一边累计2^i的时候, 一边用ans_count去统计S低位中1的个数了。此时我们通过右移操作, 就可以将原状态个数进行缩减
原状态设计中的第三个参数, 就可以修改成S右移后的值, 增加第四个参数为, left_K: 低二进制位中1的个数
题目描述
给定整数 n,m,k，和一个长度为 m+1 的正整数数组 v0,v1,…,vm。
对于一个长度为 n，下标从 1 开始且每个元素均不超过 m 的非负整数序列 {ai}，我们定义它的权值为 va1×va2×⋯×van。当这样的序列 {ai} 满足整数 S=2a1+2a2+⋯+2an 的二进制表示中 1 的个数不超过 k 时，我们认为 {ai} 是一个合法序列。
计算所有合法序列 {ai} 的权值和对 998244353 取模的结果。
输入格式
输入第一行是三个整数 n,m,k。第二行 m+1 个整数，分别是 v0,v1,…,vm。
输出格式
仅一行一个整数，表示所有合法序列的权值和对 998244353 取模的结果。
两题的区别就是，数组起始索引不同，第一题是等于k, 第二题是<=k
感谢大家的点赞和关注，你们的支持是我创作的动力！(其他细节，有时间再补充...)
扫一扫
497
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
