杂项 | 11490DX's Blog

AT_keyence2021_c

这种情况只能 dp。

首先考虑每一个格子都写了字母的情况（也就是普通情况）。

设这个格子坐标为，那么他的转移就为：

如果这个格子的字母为，那么加上，就是向右移动。
如果这个格子的字母为，那么加上，就是向下移动。
如果这个格子的字母为，那么和都加上，就是既可以向下走也可以向右走。

初始值设置，就可以算出结果，为。

现在再考虑空格子。我们给初始值设置为，就是所有情况的总数。

分析一下，发现每一个空格子的情况就是上面列举的那种。

所以在转移时，转移向每一个方向的值就应该为。

然后把上面的种情况综合一下，就变为了：

如果这个格子的字母为空，那么和都加上。

最后求出即可。

Code:

#include<bits/stdc++.h>
using namespace std;
#define add(x,y) ((x+y>=mod)?x+y-mod:x+y)
typedef long long ll;
const ll mod = 998244353;

ll ksm(ll bas, ll x){
    ll ans = 1;
    while(x){
        if(x&1) ans = ans * bas % mod;
        bas = bas * bas % mod;
        x >>= 1;
    }
    return ans;
}
int n, m, k;
const int N = 5004;
char s[N][N];
ll ans[N][N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>k;
    int x, y;
    for(int i=1;i<=k;i++){
        cin>>x>>y;
        cin>>s[x][y];
    }
    ll bas = ksm(3, n*m-k); //初始值
    ll inv3mul2 = ksm(3, mod-2)*2%mod; //这里把他综合到了一起。其实就是÷3×2。
    ans[1][1] = bas;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j] == 'D'){
                ans[i+1][j] = add(ans[i+1][j], ans[i][j]);
            }else if(s[i][j] == 'R'){
                ans[i][j+1] = add(ans[i][j+1], ans[i][j]);
            }else if(s[i][j] == 'X'){
                ans[i+1][j] = add(ans[i+1][j], ans[i][j]);
                ans[i][j+1] = add(ans[i][j+1], ans[i][j]);
            }else{
                ans[i][j+1] = add(ans[i][j+1], ans[i][j]*inv3mul2%mod);
                ans[i+1][j] = add(ans[i+1][j], ans[i][j]*inv3mul2%mod);
            }
        }
    }
    cout<<ans[n][m];
    return 0;
}

AT_abc381_f

看到，我们很自然的就会想到状态压缩。

我们要选一些数，两个数两个数的选，每一个数只能选次。于是我们就可以用一个二进制数来表示一种选项。这个数的第位上为就相当于选了数，第位上为就相当于是没有选这个数。而，所以并不会炸空间。

现在我们考虑如何转移。我们存一个数组，表示每一个状态的最小右端点位置。因为很显然的，这个右端点位置越往左，那么肯定是越优的。因为这会给其他的数留下更多的选择空间。

我们对于每一个状态，一个二进制数（表示哪些数已经被选过了）枚举的每一个数，记他为。那么当前加进去的状态就是。因为每一个数只能选一次，所以如果里面包含，也就是，那么就只能跳过，因为这个数已经被选过了。

然后因为我们要在状态后面选数，那么就只能在位置后面选头两个值为的数。这个可以用数组预处理。然后如果选不到后面的两个值为的数，那么就跳过。如果选到了，那么就把第二个的位置给提出来，设新的状态为状态和数合并起来的，那么。因为这个位置是可以被选的，然后最终答案。这里的指的就是一个二进制数里的个数，转换到集合上，就是选了几个数。最后输出即可。

最后看边界。先 memset dp 数组值为无穷大。首先我们设的。因为啥都不选的话，最小右端点位置肯定是。然后如果这个状态之前没有选，也就是值为无穷大的话，那么后面的也就不可能存在了。所以直接跳过。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+35;
int a[N];
int latest[N][21];
int n;
const int MAXN = (1<<21);
int ans[MAXN];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    memset(ans, 0x3f, sizeof ans);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=20;j++){
            latest[i][j] = latest[i+1][j];
        }
        latest[i][a[i]] = i;
    }
    int rans = 0;
    ans[0] = 0;
    for(int i=0;i<(1<<20);i++){
        if(ans[i] == 0x3f3f3f3f) continue;
        for(int j=1;j<=20;j++){
            int now = (1<<(j-1));
            if(now&i) continue;
            int fstpos = latest[ans[i]+1][j];
            int secpos = latest[fstpos+1][j];
            if(fstpos == 0 || secpos == 0)
                continue;
            int stat = i|now;
            ans[stat] = min(ans[stat], secpos); 
            rans = max(rans, __builtin_popcount(stat));
        }
    }
    cout<<rans * 2;
    return 0;
}