题意：背包容量已知，每个物品的价值，容积，可取数量已知，求最大价值，无需装满
嗯呢~，典型的混合背包问题，但是今天看的时候有了新的想法——为什么不可以把混合背包变成多重背包？
多重背包：有n物品，每种物品可取数量一定
混合背包：有的物品只能取一个，有的能多个，有的无限
所以是否差异就在“无限取”这种物品上？
显然是的捏~
无限取，能取多少啊？（战术后仰）
我们不难想象最多也就只能拿 物品体积/背包容量（向上取整）个吧，所以实际上也能确定“无限取”能拿多少个
所以我们就有了这个ac代码
我看看是谁写多重背包不加二进制拆分
#include <iostream>
#include <stdio.h>
using namespace std;
#define N 10000+100
struct obj
{
int val,col,num;
};
obj tree[N];
int dp[N];
int main()
{
int h1,m1,h2,m2,n,h;
char c;
cin>>h1>>c>>m1>>h2>>c>>m2;
h=(h2-h1)*60+(m2-m1);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>tree[i].col>>tree[i].val>>tree[i].num;
if(tree[i].num==0)
{
tree[i].num=100000000;
}
}
for(int i=1;i<=n;i++)
{
int num=min(tree[i].num,h/tree[i].col);
for(int k=1;num>0;k<<=1)
{
if(k>num)
k=num;
num-=k;
for(int j=h;j>=tree[i].col*k;j--)
dp[j]=max(dp[j],dp[j-tree[i].col*k]+tree[i].val*k);
}
}
cout<<dp[h]<<endl;
return 0;
}
D. Make Them E
题意：给定初始数组a全1，目标状态数组b，和数组c，bi是ai的终末目标，达成目标获得ci个价值
ai可以花费一次代价变为ai+ai/x（向下取整，x任意取正整数）
思路：背包问题
坑1：预处理所有数从1到这个这个数的花费作为物品体积
坑2：最大容量不是k而是n*12，因为数值最大为1e3，不可能有超过数超过12次操作
#include <bits/stdc++.h>
using namespace std;
int b[1100],c[1100];
long long dp[12000+10];
int col[2100];
int main()
{
int t;
for(int i=2;i<=1000;i++)
col[i]=1e9;
for(int i=1;i<=1000;i++)
for(int j=1;j<=i;j++)
col[i+i/j]=min(col[i]+1,col[i+i/j]);//暴力处理
// freopen("in.txt","r",stdin);
for(cin>>t;t;t--)
{
int n,k;
cin>>n>>k;
for(int i=0;i<=n*12;i++)
dp[i]=0;
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=n;i++)
{
for(int j=n*12;j>=col[b[i]];j--)
{
dp[j]=max(dp[j],dp[j-col[b[i]]]+c[i]);
}
}
cout<<dp[min(k,n*12)]<<endl;
}
return 0;
}
线性基开篇思维题
给定2n+2个数，期中有n对数和两个单独的数，求这两个单独的数是什么数
思路：
1.整个数组异或和为t，t的二进制会有位是1，是1说明这一位出现分歧，按照分歧位的0或1把原数组分成两部分，这两部分再分别异或就形成了我们的ans1和ans2
#include <iostream>
using namespace std;
const int N = 1e5+100;
int a[N];
int main()
{
int n;
cin>>n;
int temp=0;
for(int i=1;i<=2*n+2;i++)
{
cin>>a[i];
temp^=a[i];
}
int pos1=-1;
for(int i=32;i>=0;i--)
{
if((temp>>i)&1)
{
pos1=i;
break;
}
}
int ans1=0,ans2=0;
for(int i=1;i<=2*n+2;i++)
{
if((a[i]>>pos1)&1)
ans1^=a[i];
else
ans2^=a[i];
}
cout<<ans1<<" "<<ans2<<endl;
return 0;
}
