AtCoder Beginner Contest 379

Toyota Programming Contest 2024#11（AtCoder Beginner Contest 379）

F - Buildings 2

有一排楼房，第 $i$ 栋高度为 $h_i$。有 $q$ 组询问 $(l_i,r_i)$，回答在 $r_i$ 右侧有多少楼房可以被 $l_i$ 和 $r_i$ 看到。楼房 $j$ 可以被楼房 $i$ 看到当且仅当 $i$ 与 $j$ 之间没有楼房比 $j$ 高。

对于每组询问，如果楼房可以被 $l_i$ 看到，那么它一定可以被 $r_i$ 看到。所以我们只需要考虑 $r_i$ 右侧有多少楼房可以被 $l_i$ 看到。

如果没有 $r_i$ 的限制，即只考虑 $l_i$ 右侧有多少楼房可以被看到，这是一个经典的问题，使用单调栈解决：即从右往左遍历，记当前楼房为 $i$ ，弹出栈内高度小于 $h_i$ 的元素，再将 $i$ 入栈，当前栈的大小就是 $i-1$ 的答案。

回到这个问题，同样很好解决：只需要对栈进行二分，求出栈内编号大于 $r_i$ 的元素个数即可。同时需要将询问离线下来，枚举到 $i$ 时处理以它为左端点的所有询问。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+5;
vector<pii> v[N];
int h[N],ans[N];
int tp,stk[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=q;i++)
    {
        int l,r;cin>>l>>r;
        v[l].push_back({r,i});
    }
    for(int i=n;i;i--)
    {
        for(auto j:v[i])
        {
            int k=j.first,idx=j.second;
            int l=0,r=tp;
            while(l<r)
            {
                int m=(l+r+1)/2;
                if(stk[m]>k) l=m;
                else r=m-1;
            }
            ans[idx]=l;
        }
        while(tp&&h[stk[tp]]<h[i]) tp--;
        stk[++tp]=i;
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}

G - Count Grid 3-coloring

有一个 $h\times w$ 的网格，每个格子为 $1,2,3,?$ 中的一种，$?$ 可以填上 $1,2,3$ 中的一个，求满足相邻格子的数不同的方案数。

好像是一道简单的轮廓线 dp，已经大概想到了状压的方向，不过还是差了一点。。。

首先一个观察是 $\min(h,w)\leq 14$，所以可以考虑状压。然后，对后续填法有影响的其实只有之前填的 $w$ 个格子，所以对这些格子进行状压就结束了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=998244353;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h,w;cin>>h>>w;
    vector<string> s(max(h,w));
    for(int i=0;i<h;i++) cin>>s[i];
    if(h<w)
    {
        vector<string> tmp(w);
        for(int j=0;j<w;j++)
            for(int i=0;i<h;i++) tmp[j]+=s[i][j];
        for(int i=0;i<w;i++) s[i]=tmp[i];
        swap(h,w);
    }
    ll B=pow(10,w-1);
    unordered_map<ll,ll> dp;dp[0]=1;
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
        {
            unordered_map<ll,ll> ndp;
            for(auto [mask,val]:dp)
            {
                for(int k=1;k<=3;k++)
                    if(s[i][j]==k+'0'||s[i][j]=='?')
                    {
                        int x=mask/B;
                        if(x==k) continue;
                        if(j>0)
                        {
                            int y=mask%10;
                            if(y==k) continue;
                        }
                        ll tmp=(mask*10+k)%(10*B);
                        ndp[tmp]=(ndp[tmp]+val)%p;
                    }
            }
            dp=ndp;
        }
    ll ans=0;
    for(auto i:dp) ans=(ans+i.second)%p;
    cout<<ans<<'\n';
    return 0;
}