CF568C New Language 2 SAT

2022-09-22 21:55:04 字數 644 閱讀 2245

題意

我之前可能學了個假的2-sat,我一直不知道縮完點之後還要dfs

對於這個題按照要求建好圖之後

我們暴力從後向前列舉更改一個位置使得字典序變大,對於更改的位置 \(x\) ,1到 \(x-1\) 都使得字典序不小於給定串,\(x+1\) 到 \(n\) 直接取合法的字典序最小的方案

#includeusing namespace std;

namespace zzc

e[maxn<<2];

void add(int u,int v)

void dp(int rt,int x)

f[rt][1]+=s;

s=t=0;

for(int i=x;i!=rt;i=fa[i])

f[rt][0]+=max(s,t); }

void dfs(int u)

}for(int i=head[u];i;i=e[i].nxt)

}void work()

for(int i=1;i<=n;i++) cin>>f[i][1];

dfs(1);

printf("%d\n",max(f[1][0],f[1][1])); }}

int main()

CF568C New Language

一眼 texttt 。 然後不會了。 又看了一會兒,然後發現只要我們確定每個位置大於字典序的兩種最小的字母是啥,然後按位貪心,這個問題就解決了。 嗎?然後你發現限制很多 如果前幾位都和題目所給的字串一樣,你需要判斷接下來還能不能一樣。 如果有一位不同,那麼接下來的位你都不需要考慮字典序,只需要考慮...