起床困难综合症(贪心or数位dp)

题目：

从中选出一个整数，经次操作转化后得到一个最大的数，问这个数是多少。
操作：一个、一个、一个。

做法：

类操作对于每一个二进制位都是独立影响的。所以我们先预处理一下每一位选或经转化后能否得到。然后问题就转化成了：求每位选取情况形成的二进制数在以内的最大价值。
可以写一个很简单的数位dp，也可以花点心思贪心。
介绍一下贪心的思路：设一个高位限制位，为表示当前确定的位和的高位都是一致的，这代表后面的位的选取要满足的限制。这时候能选的尽量选。当为，即限制解除时，就不受限制，有贡献就直接加进来。

代码：

贪心：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
pair<int,int> op[N];
int s[30], a[30];
int main(void){
    IOS;
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        string s; cin >> s;
        int x; cin >> x;
        if (s == "AND") op[i] = make_pair(0, x);
        else if (s == "OR") op[i] = make_pair(1, x);
        else op[i] = make_pair(2, x);
    }
    s[0] = 0, s[1] = (1<<30)-1;
    for (int i = 1; i <= n; ++i){
        if (op[i].first == 0) s[0] &= op[i].second, s[1] &= op[i].second;
        else if (op[i].first == 1) s[0] |= op[i].second, s[1] |= op[i].second;
        else s[0] ^= op[i].second, s[1] ^= op[i].second;
    }
    for (int i = 0; i < 30; ++i) a[i] = (m>>i)&1;
    int ans = 0, flag = 1;
    for (int i = 29; i >= 0; --i){
        if (flag){
            if (a[i] == 0){
                if ((s[0]>>i)&1) ans |= (1<<i);
            }else{
                if ((s[0]>>i)&1) ans |= (1<<i), flag = 0;
                else if ((s[1]>>i)&1) ans |= (1<<i);
                else flag = 0;
            }
        }else{
            if ((s[0]>>i)&1 || (s[1]>>i)&1) ans |= (1<<i);
        }
    }
    cout << ans << endl;
    return 0;
}

数位dp：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
pair<int,int> op[N];
int s[30], a[30], dp[30];
int dfs(int now, int lim){
    if (now == -1) return 0;
    if (!lim && dp[now] != -1) return dp[now];
    int ans = 0;
    int up = lim ? a[now] : 1;
    for (int i = 0; i <= up; ++i){
        ans = max(ans, dfs(now-1, lim&&(i==up)) + (((s[i]>>now)&1)<<now));
    }
    if (!lim) dp[now] = ans;
    return ans;
}
int main(void){
    IOS;
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        string s; cin >> s;
        int x; cin >> x;
        if (s == "AND") op[i] = make_pair(0, x);
        else if (s == "OR") op[i] = make_pair(1, x);
        else op[i] = make_pair(2, x);
    }
    s[0] = 0, s[1] = (1<<30)-1;
    for (int i = 1; i <= n; ++i){
        if (op[i].first == 0) s[0] &= op[i].second, s[1] &= op[i].second;
        else if (op[i].first == 1) s[0] |= op[i].second, s[1] |= op[i].second;
        else s[0] ^= op[i].second, s[1] ^= op[i].second;
    }
    for (int i = 0; i < 30; ++i) a[i] = (m>>i)&1;
    memset(dp, -1, sizeof dp);
    cout << dfs(29, 1) << endl;
    return 0;
}