小苯的排列构造
题目描述
运行代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define N 1000050 int i,j,k,n,m,t,a[N],b[N],f[N],l[N]; bool v[N]; int main(){ cin>>n; for(i=1;i<=n;i++) cin>>a[i]; v[0]=1; for(i=1;i<=n;i++){ if(a[i-1]%a[i]) { cout<<-1; return 0; } while(v[l[a[i]]]) l[a[i]]+=a[i]; v[l[a[i]]]=1; f[i]=l[a[i]]; } for(i=1;i<=n;i++) cout<<f[i]<<' '; }
代码思路
- 读取整数序列
a[1], a[2], ..., a[n]。 - 遍历序列，对于每个
a[i]，确保a[i]能够整除其前一个数a[i-1]（除了第一个数a[1]，因为它没有前一个数）。 - 使用一个数组
l来存储每个数x的当前可能位置或标签。例如，l[x]表示当前值为x的数应该被放置在哪个位置。 - 使用一个布尔数组
v来标记哪些位置已经被使用了。 - 对于每个
a[i]：如果a[i]不能整除其前一个数（除了第一个数a[1]），则输出-1并终止程序。否则，在l[a[i]]开始，向后查找第一个未被使用的位（即v[l[a[i]]]为false的位置）。将找到的位置标记为已使用（v[l[a[i]] + k*a[i]] = true，其中k是使得该位置未被使用的最小整数）。将f[i]设置为找到的位置l[a[i]] + k*a[i]。 - 输出所有的
f[i]。
小苯的01背包（easy）
题目描述
运行代码
#include <iostream> using namespace std; const int N = 2e5+5; int v[N],w[N]; int ans; void solve() { int n,k; cin>>n>>k; for(int i=0;i<n;i++) cin>>v[i]>>w[i]; for(int i=30;i>=0;i--){ int sum=ans|(1<<i); int v_sum=(1<<30)-1; for(int j=0;j<n;j++){ if((w[j]&sum)==sum) v_sum&=v[j]; } if(v_sum<=k) ans=sum; } cout<<ans<<endl; return; } int main() { int f= 1; while(f--) solve(); return 0; }
代码思路
- 输入处理：首先读取两个整数
n和k，表示物品数量和目标价值。然后读取每个物品的价值v[i]和属性w[i]。 - 位运算优化的动态规划：
- 外层循环从30（即二进制最高位）降到0，这是因为假设属性的位数最多为30位（由
(1<<30)-1暗示）。 - 对于当前位
i，计算当前最优解ans加上这一位后的值sum。 - 初始化
v_sum为(1<<30)-1，代表所有可能的属性集合。 - 遍历所有物品，检查当前物品的属性集合
w[j]是否包含sum的所有位（即w[j] & sum == sum），如果是，则将该物品的价值集合（视为一个二进制位集合）与v_sum进行按位与操作，这样可以逐步筛选出满足条件的最小价值集合。 - 如果经过上述筛选后得到的
v_sum小于等于目标价值k，说明加入这一位是可行的，更新当前最优解ans = sum。
- 输出结果：最后输出得到的最大属性集合所对应的二进制值
ans。 - 主函数：主函数中通过一个变量
f控制解决问题的次数，这里f=1意味着只解决一次问题，然后调用solve()函数执行上述逻辑。
小苯的01背包（hard）
题目描述
运行代码
#include <iostream> using namespace std; typedef long long ll; const int N=2e5+5; int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar(); while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return f * x; } int a[N], v[N], w[N], b[N], n, k; bool check(int x) { int tot = 0; for(int i = 1; i <= n; i++) if((x & w[i]) == x) b[++tot] = i; int c = (1 << 31) - 1; for(int i = 1; i <= tot; i++) c &= v[b[i]]; if(c <= k) return 1; return 0; } signed main() { n = read(), k = read(); for(int i = 1; i <= n; i++) v[i] = read(), w[i] = read(); int ans = 0; for(int i = 30; i >= 0; i--) { if(check(ans | (1 << i))) ans |= 1 << i; } cout << ans; }
代码思路
- 输入处理:
- 使用
read()函数自定义读取整数，支持负数，提高了输入效率。 - 读取项目数量
n和价值阈值k，以及每个项目的具体价值v[i]和属性w[i]。
- check函数:
- 输入一个整数
x，表示当前考虑的属性集合。 - 遍历所有项目，如果项目
i的属性集合w[i]是x的子集（即(x & w[i]) == x），则将该项目的索引存入数组b[]。 - 计算所有符合条件的项目价值集合的交集（通过按位与运算），并检查这个交集的值是否不大于
k。如果满足条件，返回true；否则，返回false。
- 主函数逻辑:
- 初始化答案
ans为0，表示当前考虑的最优属性集合。 - 从最高位到最低位遍历（即从第30位到第0位），对于每一位：尝试将这一位置为1（即在当前最优解基础上增加这一位的属性），然后检查这一改变是否仍然满足总价值不超过
k的条件，这通过调用check()函数完成。如果满足条件，就保留这一位的修改（即这一位在最终解中应为1）；如果不满足，就尝试下一位。 - 最终输出得到的属性集合的二进制表示
ans。
利用了位运算来高效地处理集合的合并与判断，通过逐位检查的方式构建出满足条件的最优属性集合，相比直接的暴力枚举或者传统动态规划方法，在处理大规模数据时能显著提高效率。
