TopCoder SRM 694

250

  让把 n 个数(范围0~255)分成三份,每份全异或起来,使得三份的和最大。很容易想到三维256*256*256的dp。实际上需要省去一维才行,毕竟知道了前两维,可以算出第三维。
  然而比赛的时候我用的另一种写法。

#include <bits/stdc++.h>
using namespace std;

#define ll long long

struct node{
    short a,b,c;
    node(int a=0,int b=0,int c=0):a(a),b(b),c(c){

    }
    bool operator<(const node &other)const{
        if(a!=other.a){
            return a<other.a;
        }
        if(b!=other.b){
            return b<other.b;
        }
        return c<other.c;
    }
};

//开太大内存TC会出奇怪的问题。。 
node que[2][256*256*256];

class TrySail{
public:

    int get(vector<int> strength){
        int cur = 0;
        int pre = 1;
        int psz = 1;
        int csz = 0;
        que[pre][psz++] = node(0,0,0);
        int len = strength.size();

        for(int i=0;i<len;i++){
            int ss = strength[i];
            for(int j=0;j<psz;j++){
                que[cur][csz ++ ] = que[pre][j];
                que[cur][csz ++ ] = que[pre][j];
                que[cur][csz ++ ] = que[pre][j];

                que[cur][csz-1].a ^= ss;
                que[cur][csz-2].b ^= ss;
                que[cur][csz-3].c ^= ss;
            }

            sort(que[cur],que[cur]+csz);

            int newsz = 1;
            for(int k=1;k<csz;k++){
                if(que[cur][k-1] < que[cur][k]){
                    que[cur][newsz++] = que[cur][k];
                }
            }

            csz = newsz;
            swap(cur,pre);
            swap(csz,psz);
            csz = 0;
        }

        int ans = 0;
        for(int i=0;i<psz;i++){
            ans = max(ans,que[pre][i].a + que[pre][i].b + que[pre][i].c);
        }
        return ans;
    }
};

500

  一共有 n (1000)个人和 m (20)个问题,每个人对每个问题的回答是一个字母,给出 nm 的回答矩阵,问有多少问题的子集能区分出所有人。
  这题有助于开阔思路。。一直想着枚举 220 个子集,判断每个子集能否区分,但这个方向是不对的。应该枚举每2个人,然后枚举问题,如果存在两个人,若干问题的答案都一样,那么这些问题无法区分这两个人,自然也就无法区分所有人。实际上我们得到了若干无法区分所有人的最大子集,这些子集的子集,自然也无法区分。
  然后就是,当拿到这些最大子集以后,不要硬推它们的子集,因为运算量大,应该倒过来循环,一个一个元素去掉。

#include <bits/stdc++.h>
using namespace std;

#define ll long long


class DistinguishableSetDiv1{
public:
    bool vis[1<<20];
    int count(vector<string> answer){
        int n = answer.size();
        int m = answer[0].size();
        memset(vis,0,sizeof(vis));

        for(int i = 1;i<n;i++){
            for(int j=0;j<i;j++){
                int mask = 0;
                for(int k=0;k<m;k++){
                    if(answer[i][k] == answer[j][k]){
                        mask |= (1<<k);
                    }
                }
                vis[mask] = 1;
            }
        }

        int M = (1<<m) - 1;
        int ans = 0;

        for(int i = M;i>=0;i--){
            if(!vis[i]){
                ans++;
            }else{
                for(int k=0;k<m;k++){
                    if(i&(1<<k)){
                        vis[i^(1<<k)] = 1;
                    }
                }
            }
        }

        return ans;
    }
};
相关文章
相关标签/搜索