首页 > 和与或
开通博客写题解
头像 shyyhs
发表于 2020-07-30 20:35:09
..对于刚学dp的萌新十分不友好..题目描述:你一个数组R,包含N个元素,求有多少满足条件的序列A使得0≤A[i]≤R[i].A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]输出答案对1e9+9取模.首先知道等式成立的条件是对于每一位分配的A[i],不可能 展开全文
去ta的博客 赞 (12) 回复(0) 收起
头像 GensokyoLover
发表于 2020-11-16 15:11:07
题目描述给你一个数组R，包含N个元素，求有多少满足条件的序列A使得0 ≤ A[i] ≤ R[i]A[0]+A[1]+…+A[N-1]=A[0] or A[1]… or A[N-1]输出答案对1e9+9取模 数据范围 N<=10 ； A[i]<=1E18 记忆化搜索好题 分析 ：题目要求 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2021-01-28 20:28:26
传送门 也就是每一位二进制只能放在这个数中的某一个上面 每位数字不能超过,我们发现这非常像数位的过程 现在简化一下问题 求的对数满足且 很明显这就是一个数位,表示 枚举到二进制第位,卡不卡上界,卡不卡上界 然后只需要暴力考虑当前位二进制填还是填 填的话填在还是填在,然后更新上下界范围即可。 回到这 展开全文
去ta的博客 赞 (7) 回复(3) 收起
头像 (́安◞౪◟排‵)
发表于 2021-01-28 21:58:12
一道十分好的数位DP考虑二进制下每一位最多选1个1详细见代码注释 #include<bits/stdc++.h> #define int long long using namespace std; int n; int r[12]; int c[12][70]; int dp[70][ 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-01-29 16:26:36
题目描述 给你一个长度为的序列，问你最多可以构造多少个长度为的非负数序列，使得中每个位置都对应的相应位置并且小于等于它。并且序列还要满足。 。 。 Solution 首先看式子，涉及位运算转换二进制位看一下，通过草稿纸上推算一下我们就能得到，这个式子满足的条件是中元素相加不能产生二进制进位。也就是二 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 回归梦想
发表于 2021-01-29 11:19:57
题意： 给你一个数组R，包含N个元素，求有多少满足条件的序列A使得 0 ≤ A[i] ≤ R [ i ]A[0]+A[1]+…+A[N−1] =A[0] | ]A[1]… | A [ N − 1 ]输出答案对1e9+9取模 题解： 参考博客数位dp问题如果和等于或的话，说明两种情况： 多个数的该二 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2021-02-02 18:30:17
题意：有一个长度为N的数组R，求有多少满足条件的序列A使得0 ≤ A[i] ≤ R[i]A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]输出答案对1e9+9取模 思路：由于A的N个数和与或结果相等，所以每一位最多存在于这n个数中的其中一个数中。所以可以从高 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2021-01-29 18:53:00
做法：数位dp 思路： 由可知，如果，为0根据以上推论，可得同一位二进制位上不能有两个以上的1然后根据数位dp做法来求方案数 limit用二进制压缩一下状态来表示 代码 // Problem: 和与或 // Contest: NowCoder // URL: https://ac.nowcoder 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 已经不能更加糟糕了
发表于 2023-03-02 22:07:09
和与或 和与或 (nowcoder.com) solve 我们不断地枚举最终和地数字地前缀： 对于任意二进制串前缀： 当前位置为1时 ， 那么就要有一个A提供1。其它地位置提供0。 这样一直枚举下去。由乘法计数原理，所有情况都考虑齐全。 在此过程中 ， 观察是否有一些可以重复利用地信息。在枚 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”