[AGC026D]Histogram Coloring
2021/9/1 23:09:26
本文主要是介绍[AGC026D]Histogram Coloring,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\ \begin{array}{|} \hline \color{pink}{\text{The principal is really a god}} \\ \color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\ \color{pink}{\text{holding a sharp pen to pierce the truth}} \\ \color{pink}{\text{Who can resist him? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{green}{\text{校長は本当に神であり、左側にトイレ、右側にヨンシェンがあり}} \\ \color{green}{\text{鋭いペンを持って真実を突き刺している。誰が彼に抵抗できるだろうか? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{lightblue}{\text{Le principal est vraiment un dieu}} \\ \color{lightblue}{\text{avec des toilettes à gauche et Yongshen à droite}} \\ \color{lightblue}{\text{tenant un stylo pointu pour percer la vérité}} \\ \color{lightblue}{\text{Qui peut lui résister ? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{purple}{\text{Der Direktor ist wirklich ein Gott}} \\ \color{purple}{\text{mit einer Toilette links und Yongshen rechts}} \\ \color{purple}{\text{der einen spitzen Stift hält}} \\ \color{purple}{\text{um die Wahrheit zu durchdringen.}} \\ \color{purple}{\text{Wer kann ihm widerstehen? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{cyan}{\text{Principalis deus est, Yongshen a dextris cum latrina}} \\ \color{cyan}{\text{acuto stylo ad perforandum veritatem: quis resistet ei? }} \\ \hline \end{array} \\ \color{red}{\text{对曰:“无人,狗欲当之,还请赐教!”}} \\ \newcommand\bra[1]{\left({#1}\right)} \newcommand\Bra[1]{\left\{{#1}\right\}} \newcommand\dx[0]{\text{dx}} \newcommand\string[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \newcommand\down[2]{{#1}^{\underline{#2}}} \newcommand\ddiv[2]{\left\lfloor\frac{#1}{#2}\right\rfloor} \newcommand\udiv[2]{\left\lceil\frac{#1}{#2}\right\rceil} \newcommand\lcm[0]{\operatorname{lcm}} \newcommand\set[1]{\left\{{#1}\right\}} \]壹、题目描述 ¶
传送门 to AtCoder.
贰、题解 ¶
看似好像很难,不过确实很难,我们无从下手。这提醒着我们,对此题挖掘性质。
记得做过类似的题,不难发现,当我们确定某个矩阵的三个点后,剩下的点也可以确定了,但是缺一个角的情况好像有点复杂,我们只考虑两个方块:
如果相邻两个方块同色,那么包含它的一个 \(2\times 2\) 的正方形的剩下两个方块只有一种涂法,而且这两个方块的颜色一样,都是前两个方块的颜色的反;
如果相邻两个方块不同色,那么包含它的一个 \(2\times 2\) 的正方形的剩下两个方块有两种涂法,只需要两个方块颜色不同即可;
那么,我们进一步拓展 —— 当某一层是交错填色,那么下一层也只需要交错填色,下一层可以有两种填法,但是,若该层并非严格交错填色,那么下一层无论如何,对应位置都只能是该层取反。
接下来我们就可以考虑建出笛卡尔树之后进行树 \(\rm DP\) 了。设 \(dp(u,1)\) 表示 \(u\) 管辖的区域是交错填色,\(dp(u,0)\) 表示 \(u\) 子树中合法填色方案,而 \(u\) 管辖的矩阵为 \(H\times W\),其中有 \(cnt_u\) 个和 \(u\) 是同一高度,那么
\[dp(u,1)=2^H\prod_{v\in son_u} dp(v,1) \\ dp(u,0)=2^{cnt_u}\prod_{v\in son_u}(dp(v,0)+dp(v,1))+(2^H-2)\prod_{v\in son_u} dp(v,1) \]第一个不用解释,解释一下第二个转移。
- 第一个部分考虑的是 \(u\) 管辖的矩阵的第一行随便填的情况,首先,由于和 \(u\) 同一高度的点不会包含在任何方阵中,所以他们可以任意填色,而剩下的部分就是儿子所管辖的部分,由于我们当前考虑的是当前随便填,显然,当前行与上一行完全取反是一种合法情况,至于为什么还要算上 \(dp(v,1)\) 呢?如果上一行是交错填数,那么当前行 “照抄” 上一行显然也是合法情况。至于除了第一行的剩下行?全部暴力按照上一行整体取反;
- 但是还剩下一部分?这部分就是全部都是交错填数的情况,这就要第二种来计算了。它的解释和 \(dp(u,1)\) 很像,不过为什么有 \(-2\) 呢?因为 \(dp(v,0)\) 亦包含 \(v\) 中交错填数的情况,我们在考虑非照抄部分的时候,是按照整体取反来做的,也就是说,在第一个部分中,第一行在某些特殊情况下也是交错颜色的,而 \(cnt_u\) 个任取的颜色也恰好是交错且整体是可以衔接的,后面行也是在上一行基础上取反,这导致后面也是颜色交错,这种情况一共有两种,减去即可;
按照这个转移即可。复杂度 \(\mathcal O(N\log H)\),因为有快速幂。
叁、参考代码 ¶
# include <cstdio> # include <algorithm> # include <cstring> # include <vector> using namespace std; # define NDEBUG # include <cassert> namespace Elaina { # define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i) # define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i) # define fi first # define se second # define mp(a, b) make_pair(a, b) # define Endl putchar('\n') # define mmset(a, b) memset(a, b, sizeof (a)) # define mmcpy(a, b) memcpy(a, b, sizeof (a)) typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; template <class T> inline T fab(T x) { return x<0? -x: x; } template <class T> inline void getmin(T& x, const T rhs) { x=min(x, rhs); } template <class T> inline void getmax(T& x, const T rhs) { x=max(x, rhs); } template <class T> inline T readin(T x) { x=0; int f=0; char c; while((c=getchar())<'0' || '9'<c) if(c=='-') f=1; for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48)); return f? -x: x; } template <class T> inline void writc(T x, char s='\n') { static int fwri_sta[55], fwri_ed=0; if(x<0) putchar('-'), x=-x; do fwri_sta[++fwri_ed]=x%10, x/=10; while(x); while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed); putchar(s); } } using namespace Elaina; const int maxn=100; const int mod=1e9+7; const int inf=0x3f3f3f3f; inline int qkpow(int a, int n) { int ret=1; for(; n>0; n>>=1, a=1ll*a*a%mod) if(n&1) ret=1ll*ret*a%mod; return ret; } int h[maxn+5], n; inline void input() { n=readin(1); rep(i, 1, n) h[i]=readin(1); } int rt, ncnt; int dp[maxn+5][2]; void solve(int& u, int l, int r, int c) { u=++ncnt; dp[u][0]=dp[u][1]=1; int mn=inf, cnt, lst, H; vector <int> son; rep(i, l, r) mn=min(mn, h[i]); rep(i, l, r) if(h[i]==mn) son.push_back(i); lst=l-1, cnt=son.size(), H=mn-c; son.push_back(r+1); /** push @p r+1 after update @p cnt */ for(int p: son) { if(lst+1<=p-1) { int v; solve(v, lst+1, p-1, mn); dp[u][1]=1ll*dp[u][1]*dp[v][1]%mod; dp[u][0]=1ll*dp[u][0]*(dp[v][0]+dp[v][1])%mod; } lst=p; } dp[u][0]=(1ll*dp[u][0]*qkpow(2, cnt)%mod+1ll*dp[u][1]*(qkpow(2, H)+mod-2)%mod)%mod; dp[u][1]=1ll*dp[u][1]*qkpow(2, H)%mod; } signed main() { input(); solve(rt, 1, n, 0); writc(dp[rt][0]); return 0; }
肆、关键 の 地方 ¶
真的是人类智慧题,这个性质太离谱了。不过,这再一次印证了笛卡尔树对于直方图有奇效。
这篇关于[AGC026D]Histogram Coloring的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享
- 2024-12-24uniapp 连接之后会被立马断开是什么原因?-icode9专业技术文章分享
- 2024-12-24cdn 路径可以指定规则映射吗?-icode9专业技术文章分享
- 2024-12-24CAP:Serverless?+AI?让应用开发更简单
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理,增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享