**1 **Qualification Rounds《状压典例》{

1. 题意：判断一组数组当中是否有一个问题子集使得所有组做过子集当中问题的个数不超过子集的一半

                2.思路：只有一两道题也可构成子集，所以只要先能找出所有组都没做过的题就可直接输出YES，否则还可以找第二道，使得所有组做过这两道题的个数为1或为0，因为队伍数至多有k个，所以最多有2^k种状态，因此当有两种相同状态同时为1时，直接输出YES，没找到则输出0

}

核心代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen("rtmrts.in", "r", stdin);
    freopen("rtmrts.out", "w", stdout);
    int n,k;
    cin>>n>>k;
    vector<int> exist(1<<k,0);
    for(int i=0;i<n;i++) {
        int x,state=0;
        for(int j=0;j<k;j++) {
            cin>>x;
            if(x==1) {
                state|=(1<<j);
            }
        }
        exist[state]=true;
    }
    int total=1<<k;
    for (int i=0;i<total;i++) {
        for (int j=0;j<total;j++) {
            if(exist[i]&&exist[j]&&(i&j)==0){
                cout<<"YES";
                return 0;
            }
        }
    }
    cout<<"NO";
    return 0;
}

**2 **Dima and a Bad XOR《签到题》{

1. 题意：找到一种组合使得选定元素的异或和严格大于0

2. 思路：只要两数不相等就一定可以成为答案，因此先计算第一列是否能成为答案，如果可以直接输出，不行则再另外考虑其他列，如果不相等就输出在原数组中的下标
}

核心代码：

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int ans[N][N];
int main(){
    freopen("badxor.in","r",stdin);
    freopen("badxor.out","w",stdout);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>ans[i][j];
    }
}
	int sum=0;
	for(int i=0;i<n;i++){
		 sum^=ans[i][0];
	}
	if(sum!=0){
		cout<<"TAK"<<endl;
		for(int i=0;i<n;i++) cout<<1<<' ';
		return 0;
	}
    for(int i=0;i<n;i++){
    	for(int j=1;j<m;j++){
    		if(ans[i][j]!=ans[i][0]){
    			cout<<"TAK"<<endl;
    			for(int k=0;k<n;k++){
    				if(k==i) cout<<j+1<<' ';
    				else cout<<1<<" ";
				}
				return 0;
			}
		}
	}
    cout<<"NIE";
}

**3 **Boboniu and Bit Operations{

       1.题意：在第二个数组中可重复选择数，使得与第一个数组中的元素按顺序取位与后的每个结果求位或和的结果最小

                2.思路：因为数组中的元素的最大值不超过2^9，而位与和位或的结果不会大于原数，所以位或最大也只能取到2^9，因此我们可以枚举0到512的值，然后再枚举第一个数组到第二个数组之间的元素，判断此数作为结果是否可行，如果能被此结果包含，说明可行，直接输出

}

#include <bits/stdc++.h>
using namespace std;
const int N=205;
int a[N],b[N];
int n,m;
bool check(int mask){
    for(int i=1;i<=n;i++){
        bool flag=false;
      for(int j=1;j<=m;j++){
           if(((a[i]&b[j])|mask)==mask) flag=true;
    }
        if(flag==false) return false;
}
    return true;
}
int main(){
    freopen("bit.in","r",stdin);
    freopen("bit.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=0;i<=512;i++){
        if(check(i)){
             cout<<i;
             return 0;
        }
    }
}

**4 **Factorials and Powers of Two{

1. 题意：判断一个数能写成各个2的次幂数或阶乘数相加的最小相加个数，无则输出-1

              2.思路：因为任何自然数都可写成二进制形式，而二进制中的1代表2的次幂数，因此不存在输出-1的情况，所以先初始化一个数的二进制形式中1的个数，代表初始的2的次幂数的个数，而阶乘数可以代替若干个2次幂数，所以我们需要先列出合法范围内的阶乘数，从1到14依次枚举，超过合法范围则停止，大于3时则加入答案，随后一个一个累加，算上原数减去现在的阶乘数的二进制形式中有多少个1被代替，取最小值

}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    freopen("factorials.in","r",stdin);
    freopen("factorials.out","w",stdout);
    int t;
    cin>>t;
   ll x=1;
    vector<ll> fac;
    for(int i=1;i<=14;i++){//直接统计可用的阶乘子集
        x*=i;
        if(x>(ll)1e12) break;//大了就退出
        if(i>=3) fac.push_back(x);//满足的就加入
    }
    while(t--){
        ll n;
        cin>>n;
        int ans=__builtin_popcountll(n);//原始二进制中所需的2次幂数
        for(int mask=0;mask<(1<<(int)fac.size());mask++){
            ll sum=0;
            for(int j=0;j<fac.size();j++){
                if(mask>>j&1) sum+=fac[j];//如果第j位是1才加
            }
                if(sum<=n){//计算加上此时的阶乘数后的sum还需多少个2次幂数
                    ans=min(ans,__builtin_popcount(mask)+__builtin_popcountll(n-sum));
                }
        }
        cout<<ans<<endl;
    }
}

5 Party Lemonade{

1. 题意：有一组柠檬水，每个值ai元，且体积随i增加呈2^i增长，求买够L升柠檬水的最少价格

2. 思路：因为这题元素最高高达1e9，所以不能用完全背包去做，但是由于体积是呈2的次方级上涨，因此可以考虑将L替换成2进制形式，又因为L是呈2的指数级上涨，因此只要买前面的一瓶两次就一定可以代替现在的这一瓶的容积，所以我们只需要在现在的这一瓶的价格和上一瓶的价格×2之间取最小值就可以实现价格转换，最后计算答案时，只需要看L的二进制形式中有1时直接加上现在价格再取最小值即可

}

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
long long c[N],num[N];
int main(){
	 freopen("party.in","r",stdin);
    freopen("party.out","w",stdout);
	long long n,l,ans=0,cnt=0;
	cin>>n>>l;
	while(l!=0){
		num[cnt++]=l%2;
		l/=2;
	}
	cin>>c[0];
	for(int i=1;i<n;i++){
		cin>>c[i];
		c[i]=min(c[i],c[i-1]*2);
	}
	for(int i=n;i<cnt;i++){
		c[i]=c[i-1]*2;
	}
	for(int i=0;i<max(n,cnt);i++){
		ans=min(ans,c[i]);
		if(num[i]==1) ans+=c[i];
	}
	cout<<ans;
	return 0;
}

**6 **XOR, Expression and Two Binary Numbers《异或性质》{

1. 题意：一个二进制数组，最开始只有左端点和右端点有值，现在规定每个端点的中间被填充的数的值为两端的异或值，求最终数组中的每一项中1的数量和0的数量的乘机的和

              2.思路：我们设最开始的左端点的字符串为s，右端点的字符串为t，所以中间填充的值为s^t，再让中点和左端点进行异或可以发现，值又变回了右端点的值，因此无论怎么填充，状态有且仅有s,t和s^t三种，所以只要能够求出三种状态中的0和1的值，再递归模拟填充过程，找到三种状态的个数，最后相加就能得到答案

}

个人感觉听完思路以后没那么难，可考场上为什么想不出来呢？

附√码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    freopen("binary.in","r",stdin);
    freopen("binary.out","w",stdout);
    int t;
    cin>>t;
    while(t--){
    int n,m;
    string s,t;
    cin>>n>>m>>s>>t;
    ll onea=0,oneb=0,onec=0,ans=0;
    for(int i=0;i<n;i++){
        onea+=(s[i]=='1');//统计A为1个数
        oneb+=(t[i]=='1');//统计B为1个数
        onec+=(s[i]!=t[i]);//统计A与B不等个数
    }
   ll end=1,mid=0;
    for(int i=0;i<m;i++){//递归填充过程
        int nend=mid+end;
        int nmid=end*2-1;
        end=nend;
        mid=nmid;
    }
    ans+=end*onea*(n-onea);//计算cnt[A]*num(s)+cnt[B]*num(t)+cnt[C]*num(s^t);
    ans+=end*oneb*(n-oneb);
    ans+=mid*onec*(n-onec);
    cout<<ans<<endl;
    }
}