P4098 [HEOI2013]ALO

野性酷女 2021-12-20 07:33 130阅读 0赞

# [题意分析][Link 1] #

# 题目链接 #

这里借鉴了\\(Youngsc\\)以及\\(hzwer\\)的思路

首先由于涉及到了区间异或最值的问题

所以我们需要使用到\\(01Trie\\)树

这里贴一道[板子题][Link 2]

然后对一个位置\\(x\\)

我们维护四个位置\\(l\_1,l\_2,r\_1,r\_2\\)

\\(l\_1\\) 从\\(x\\)往左数第一个大于\\(x\\)的位置

\\(l\_2\\) 从\\(x\\)往左数第二个大于\\(x\\)的位置

\\(r\_1\\) 从\\(x\\)往右数第一个大于\\(x\\)的位置

\\(r\_2\\) 从\\(x\\)往右数第二个大于\\(x\\)的位置

那么\\(x\\)作为次大值的区间就是\\(\[l\_1+1,r\_2-1\]\\)以及\\(\[l\_2+1,r\_1-1\]\\)

至于维护这四个位置 我们使用\\(set\\)就可以了

把位置按照权值从大到小排序

然后依次插入 就可以了

# CODE: #

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<string> #include<queue> #include<map> #include<stack> #include<list> #include<set> #include<deque> #include<vector> #include<ctime> #define ll long long #define inf 0x7fffffff #define N 1008 #define IL inline #define M 1008611 #define D double #define mod 1000000007 #define R register using namespace std; template<typename T>IL void read(T &_) { T __=0,___=1;char ____=getchar(); while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();} while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();} _=___ ? __:-__; } char getch() { char ch = getchar(); while(ch != '<' && ch != '>') ch = getchar(); return ch; } /*-------------OI使我快乐-------------*/ int T,n,tot; int to[N<<1],nex[N<<1],head[N<<1],w[N<<1]; int siz[N]; ll C[N][N],dp[N][N],tmp[N]; IL void add(int x,int y,int z) {to[++tot]=y;nex[tot]=head[x];head[x]=tot;w[tot]=z;} IL void dp_cdy(int now,int v) { for(R int i=1;i<=n;++i) tmp[i]=dp[now][i],dp[now][i]=0; for(R int i=1;i<=siz[now];++i) for(R int j=i;j<=i+siz[v]-1;++j) dp[now][j]=(dp[now][j]+C[j-1][i-1]*C[siz[now]+siz[v]-j][siz[now]-i]%mod*tmp[i]%mod*(dp[v][siz[v]]-dp[v][j-i]+mod)%mod)%mod; } IL void dp_wzy(int now,int v) { for(R int i=1;i<=n;++i) tmp[i]=dp[now][i],dp[now][i]=0; for(R int i=1;i<=siz[now];++i) for(R int j=i+1;j<=siz[v]+i;++j) dp[now][j]=(dp[now][j]+C[j-1][i-1]*C[siz[now]+siz[v]-j][siz[now]-i]%mod*tmp[i]%mod*dp[v][j-i]%mod)%mod; } IL void dfs(int now,int fat) { siz[now]=1;dp[now][1]=1; for(R int i=head[now];i;i=nex[i]) { int v=to[i]; if(v==fat) continue; dfs(v,now); if(w[i]) dp_cdy(now,v); else dp_wzy(now,v); siz[now]+=siz[v]; } for(R int i=1;i<=siz[now];++i) dp[now][i]=(dp[now][i]+dp[now][i-1])%mod; } int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); read(T); for(R int i=0;i<=1000;++i) C[i][0]=1; for(R int i=1;i<=1000;++i) for(R int j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; // for(R int i=1;i<=6;++i) // for(R int j=1;j<=i;++j) // printf("%lld%c",C[i][j],(j==i ? '\n':' ')); while(T--) { read(n);tot=0; memset(dp,0,sizeof dp); memset(head,0,sizeof head); for(R int i=1,x,y;i<n;++i) { char z; read(x);z=getch();read(y);++x;++y; add(x,y,z=='<');add(y,x,z=='>'); // printf("%d %c %d\n",x,z,y); } dfs(1,0); // for(R int i=1;i<=n;++i) printf("%d%c",siz[i],(i==n ? '\n':' ')); printf("%lld\n",dp[1][n]); } // fclose(stdin); // fclose(stdout); return 0; }

# *HEOI 2019 RP++* #

转载于:https://www.cnblogs.com/LovToLZX/p/10616752.html

[Link 1]: https://www.luogu.org/problemnew/show/P4098
[Link 2]: https://www.luogu.org/problemnew/show/P4735