WC2021 题解
command_block
2021-04-08 22:12:36
# T1 [括号路径](https://www.luogu.com.cn/problem/P7323)
> 考场 40 分暴力。
记一条边 $u\rightarrow v:w$ 表示 $u$ 到 $v$ 有一条有向边，其中的括号编号为 $w$。
本题有一个非常关键的性质 ： $(u\rightarrow v:w)$ 和 $(v\rightarrow u:-w)$ 总是成对出现的。
联系本题是 T1 的事实，应当大胆发掘性质。
不难发现，任何一条合法的括号路径，反向后仍然存在对应的合法括号路径。即 ： 如果 $(u,v)$ 合法，那么 $(v,u)$ 也合法。
进一步地，若 $(a,b),(b,c)$ 合法，则 $(a,c)$ 也合法。
综上，我们只需求出图中有多少个联通块，连通块内部的任意点对都是合法的，其他点对均不合法。
若点 $u$ 存在两条出边 $u\rightarrow a:w,\ u\rightarrow b:w$ ，且 $w$ 是右括号（即 $w<0$），则 $a\leftrightarrow u\leftrightarrow b$ 是合法路径，于是可以将 $a,b$ 合并成一个点处理。
当找不到这样的路径时，显然图中不再有任何合法路径。
维护时，用动态开点线段树（按照 $w$）维护某个点的出边集合，合并时若叶子重叠则出发新合并。
复杂度为 $O((n+m)\log k)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define MaxN 300500
using namespace std;
struct UFS{
int f[MaxN],c[MaxN];
void Init(int n)
{for (int i=1;i<=n;i++)c[f[i]=i]=1;}
int find(int u)
{return f[u]==u ? u : f[u]=find(f[u]);}
bool merge(int u,int v){
if (u==v)return 0;
if (c[u]>c[v])swap(u,v);
c[f[u]=v]+=c[u];
return 1;
}
}T;
struct Node{int l,r;}a[MaxN*40];
queue<Node> q;
int tn,rt[MaxN],to,wfc;
void add(int l,int r,int &u)
{
if (!u)u=++tn;
if (l==r){
if (!a[u].l)a[u].l=a[u].r=wfc;
else q.push((Node){wfc,a[u].l});
return ;
}int mid=(l+r)>>1;
if (to<=mid)add(l,mid,a[u].l);
else add(mid+1,r,a[u].r);
}
int merge(int u,int v)
{
if (!u||!v)return u|v;
if (a[u].l==a[u].r)
q.push((Node){a[u].l,a[v].l});
else {
a[u].l=merge(a[u].l,a[v].l);
a[u].r=merge(a[u].r,a[v].r);
}return u;
}
int n,m,k;
int main()
{
scanf("%d%d%d",&n,&m,&k);
T.Init(n);
for (int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
to=w;wfc=u;
add(1,k,rt[v]);
}
while(!q.empty()){
int u=q.front().l,v=q.front().r;q.pop();
u=T.find(u);v=T.find(v);
if (T.merge(u,v))
rt[T.f[u]]=merge(rt[u],rt[v]);
}
long long ans=0;
for (int i=1;i<=n;i++)
if (T.f[i]==i)
ans+=1ll*T.c[i]*(T.c[i]-1)/2;
printf("%lld",ans);
return 0;
}
```
# T2 [表达式求值](https://www.luogu.com.cn/problem/P7324)
> 考场 AC。
两个数组的 $\min,\max$ 可以分位考虑，于是原问题可以拆分成 $n$ 个子问题，其中“数组”变为“单个数”。
观察到 $m$ 非常小但 $n$ 非常大，思考如何利用特殊的数据范围。
若我们将 $< x$ 的数改为 $0$ ，而 $\geq x$ 的数改为 $1$ ，若表达式的结果为 $1$ ，则说明 $ans\geq x$ ，否则 $ans< x$。
有经典结论 $ans=\sum\limits_{i=1}^{\infty}[ans\geq i]$ ，于是我们只需对每个 $i$ 求解上述问题。
这样，我们就把表达式转化为了 “输入 $m$ 个 $0/1$ ，输出一个 $0/1$” 的黑盒。
考虑真值表思想，记 $f[s]$ 表示输入状态为 $s$ 时，输出为 $1$ 的方案数。这可以在表达式树上进行简单 $\rm DP$ 得到。
预处理的复杂度为 $O(len2^m)$。
借助 $f[s]$ 的值，我们就能快速地回答询问。
将输入的 $m$ 个数 $x_0,x_1,...,x_m$**从大到小**排序，分别为 $x_{p_1},x_{p_2},...,x_{p_m}$。
对于 $i\in[x_{p_k},x_{p_{k+1}})$ 的 $i$ ，被设定为 $1$ 的输入即为 $p_{k+1}\sim p_m$ ，容易求出方案数。乘以区间长度求和即为对答案的贡献。
回答询问的复杂度为 $O(nm)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 50500
#define MaxS 1050
#define MaxM 12
using namespace std;
const int mod=1000000007;
struct Node{int l,r,op;}a[MaxN];
int tn,m,f[MaxN][MaxS],siz[MaxN],pw2[MaxN];
void dfs(int u)
{
if (a[u].l==a[u].r){
for (int s=0;s<(1<<m);s++)
f[u][s]=((s>>a[u].op)&1);
return ;
}
int l=a[u].l,r=a[u].r;
dfs(l);dfs(r);
siz[u]=siz[l]+siz[r]+(a[u].op==-3);
if (a[u].op==-1) // <
for (int s=0;s<(1<<m);s++)
f[u][s]=1ll*f[l][s]*f[r][s]%mod;
if (a[u].op==-2) // >
for (int s=0;s<(1<<m);s++)
f[u][s]=(pw2[siz[u]]-1ll*(pw2[siz[l]]-f[l][s])*(pw2[siz[r]]-f[r][s]))%mod;
if (a[u].op==-3) // ?
for (int s=0;s<(1<<m);s++)
f[u][s]=(pw2[siz[u]-1]-1ll*(pw2[siz[l]]-f[l][s])*(pw2[siz[r]]-f[r][s])+1ll*f[l][s]*f[r][s])%mod;
}
char str[MaxN];
int n,stk[MaxN],op[MaxN],top;
void build()
{
int len=strlen(str+1);
pw2[0]=1;
for (int i=1;i<=len;i++)pw2[i]=(pw2[i-1]<<1)%mod;
str[len+1]=')';
stk[0]=-4;
for (int i=1;i<=len+1;i++){
if (str[i]==')'){
int p=top;while(stk[p]!=-4)p--;
for (int k=p+2,las=stk[p+1];k<top;k+=2){
a[++tn].op=stk[k];
a[tn].l=las;a[tn].r=stk[k+1];
las=tn;
}stk[top=p]=tn;
}
if (str[i]=='(')stk[++top]=-4;
if ('0'<=str[i]&&str[i]<='9')
a[stk[++top]=++tn].op=str[i]-'0';
if (str[i]=='<')stk[++top]=-1;
if (str[i]=='>')stk[++top]=-2;
if (str[i]=='?')stk[++top]=-3;
}
}
int x[MaxM][MaxN],tx[MaxM],p[MaxM];
bool cmp(int A,int B){return tx[A]<tx[B];}
int main()
{
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++)
for (int j=1;j<=n;j++)
scanf("%d",&x[i][j]);
scanf("%s",str+1);
build();
dfs(tn);
int ans=0;
for (int i=1;i<=n;i++){
for (int k=0;k<m;k++)tx[p[k]=k]=x[k][i];
sort(p,p+m,cmp);sort(tx,tx+m);
for (int k=m-1,s=0;k>=0;k--){
s|=(1<<p[k]);
if (k)ans=(ans+1ll*f[tn][s]*(tx[k]-tx[k-1]))%mod;
else ans=(ans+1ll*f[tn][s]*tx[k])%mod;
}
}printf("%d",(ans+mod)%mod);
return 0;
}
```
# T3 [斐波那契](https://www.luogu.com.cn/problem/P7325)
> 考场 20 分暴力。
咕。