讨论/题目交流/🏆 第 175 场力扣周赛/
🏆 第 175 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 检查整数及其两倍数是否存在
4 分 - 制造字母异位词的最小步骤数
5 分 - 推文计数
7 分 - 参加考试的最大学生数

叹为观止的流畅

这个是johnkram的代码。

class Solution {
    int o[256],f[9][256],a[9];
public:
    int maxStudents(vector<vector<char>>& seats) {
        int n=seats.size(),m=seats[0].size(),i,j,k,ans=0;
        for(i=1;i<256;i++)o[i]=o[i>>1]+(i&1);
        memset(f,128,sizeof(f));
        memset(a,0,sizeof(a));
        for(i=0;i<n;i++)for(j=0;j<m;j++)if(seats[i][j]=='#')a[i]|=1<<j;
        for(i=f[0][0]=0;i<n;i++)for(j=0;j<1<<m;j++)if(!(j&a[i])&&!(j&j>>1)&&!(j&j<<1))for(k=0;k<1<<m;k++)if(!(j&k>>1)&&!(j&k<<1))f[i+1][j]=max(f[i+1][j],f[i][k]+o[j]);
        for(i=0;i<1<<m;i++)ans=max(ans,f[n][i]);
        return ans;
    }
};

这是我的烂豆芽

#pragma GCC optimize("Ofast")
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pi>
#define vpl vector<pl>
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005
#define all(a) a.begin(),a.end()

#define F(i, a, b) for(int i=a;i<b;i++)
#define F0(i,a) for(int i=0;i<a;i++)
#define Tra(a, b) for(auto a: b)

int n,m;

class Solution {
    int dp[10][1<<10];
    int fit(int mask, vector<char> s)
    {
        F0(i, s.sz)
        {
            if(s[i]=='#' && (mask &(1<<i)) ) return 0;
        }
        return 1;
    }
    int count(int mask)
    {
        int ans =0;
        while(mask)
        {
            if(mask&1)ans++;
            mask>>=1;
        }
        return ans;
    }
    int ok_pre(int cur, int pre)
    {
        return !((cur&(pre>>1)) || (cur&(pre<<1)));
    }
public:
    int maxStudents(vector<vector<char>>& seats) {
        for(int i=0;i<10;i++)
            for(int j=0;j<(1<<10);j++)
                if(i==0)dp[i][j] = 0;
                else dp[i][j] = -1;
       
        n = seats.sz;
        m = seats[0].sz;
        int ans =0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<(1<<m);j++)
            {
                if(!fit(j, seats[i-1]) || (j&(j<<1)) || (j&(j>>1)) )continue;
                dp[i][j] = count(j);
                for(int k=0;k<(1<<m);k++)
                    if(dp[i-1][k]!=-1 && ok_pre(j,k)) dp[i][j] = max(dp[i][j], dp[i-1][k] + count(j));
                if(dp[i][j] ==5 )cout<<i<< " "<<j<<endl;
                ans = max(ans, dp[i][j]);
            }
        return ans;
    }
};

有以下几个收获:

  • count函数可以用o[i] = o[i>>1] + (i&1); 预处理出来
  • 合法的座位可以处理成bits出来然后位运算(其实我想到了但是想先提个函数出来再写就写丑了)
  • 记住优先级可以省括号,我的括号太多了。由高到低:算数,位移,==,!=,按位与或,与或
  • 初始化的dp数组 放到for(int i=f[0][0]=0...)中
2
展开全部 42 讨论