T1 宝物筛选（P1776）

未优化，当成多重背包做。

#include <iostream>
#include <stdio.h>
using namespace std;
int v[1005],w[1005],s[1005],dp[1005];
int main(){
	freopen("P1776_4.in","r",stdin);
	int N,V;
	cin>>N>>V;
	for(int i=1;i<=N;i++){
		cin>>w[i]>>v[i]>>s[i];
	}
	for(int i=1;i<=N;i++){
		for(int k=V;k>=1;k--){
			for(int l=0;l<=s[i]&&l*v[i]<=k;l++){
				cout<<k<<' '<<k-l*v[i]<<' ';
				dp[k]=max(dp[k],dp[k-l*v[i]]+l*w[i]);
			}
		}
	}
	cout<<dp[V];
	return 0;
}

二进制优化后（节省了大量空间）

#include <iostream>
#include <stdio.h>
using namespace std;
const int maxx=1e7+5;
int N,V;
int v[12005],w[12006],dp[maxx];
int main(){
//	freopen("P1776_4.in","r",stdin);
	cin>>N>>V;
	int count=0;
	//分成2^0(1),2^1(2),2^2(4),2^3(8)...余数组。
	//O(n^3)->O(n^2logS）
	for(int i=1;i<=N;++i){
		int z,x,c;
		cin>>z>>x>>c;
		for(int k=1;k<=c;k*=2){
			count++;
			v[count]=x*k;//fu gai.?
			w[count]=z*k;
			c-=k;
		}
		if(c>0){
			count++;
			v[count]=x*c;
			w[count]=z*c;
		}
	}
	//拿1024次苹果或者拿10次。（7次？
	for(int i=1;i<=count;++i){
		for(int k=V;k>=1;k--){
			if(k>=v[i])
			dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
		}
	}
	cout<<dp[V];
	return 0;
}

---

T2 尴尬的数字（P1555）

#include <iostream>
using namespace std;
string a,b;
int cvs(string x){
	int yu,temp=0;
	for(int i=0;i<x.length();i++){
		yu=x[i]-'0';
		temp*=10;
		temp+=yu;
	}
	return temp;
}//转换数据类型
string er_shi(string x){
	int len=x.length(),baka;
	int i=0;
	if(x[i]!='0')
		baka=x[0]-'0';
	else{
		baka=x[1]-'0';
		i++;
	}
	i++;
	for(;i<len;i++){
		baka*=2;
		baka+=x[i]-'0';
	}
	string back;
	char temp;
	while(baka){
		temp=(baka%10)+'0';
		back=temp+back;
		baka/=10;
	}
	return back;
}//二进制转十进制
string shi_san(string x){
	string back;
	int num=cvs(x);//
	int yu;
	char temp;
	while(num){
		yu=num%3;
		temp=yu+'0';
		back=temp+back;
		num/=3;
	}
	return back;
}//十进制转三进制
bool cmp(string x){
	if(x.length()!=b.length())
		return false;
	int cnt=0;
	for(int i=0;i<b.length();i++){
		if(x[i]!=b[i])
			cnt++;
	}
	if(cnt==1) return true;
	return false;
}//判断函数
void change(int x){
	if(a[x]=='1') a[x]='0';
	else a[x]='1';
}
int main(){
	cin>>a>>b;
	for(int i=0;i<a.length();i++){
		if(i==0){
			change(i);
		}
		else{
			change(i-1);
			change(i);
		}//更换数字
		//此时是二进制字符串
		int ans=-1;
		ans=cvs(er_shi(a));//保存答案
		if(cmp(shi_san(er_shi(a)))){
			cout<<ans;
			return 0;
		}
		else continue;
	}
	return 0;
}

---

T3 小卡和质数（P8845）

#include <iostream>
int main(){
	int t,a,b;
	std::cin>>t;
	while(t--){
		std::cin>>a>>b;
		if((a==1&&b==2)||(a==2&&b==1)) std::cout<<"Yes"<<std::endl;
		else std::cout<<"No"<<std::endl;
	}
	return 0;
}

---