省选模拟赛day4

怎么说？发现自己越来越菜了到了不写题解写不出来题目的地步了。。

这次题目我都有认真思考尽管思考的时候状态不太好但是我想再多给我时间也思考不出来什么吧

所以写一份题解。

T1 n个点的有根树 1号点为根第i个点的点权为\(w_i\) \(1\leq w_i\leq L\) 定义一个长度为L的序列是完美的当且仅当\(\forall 1\leq i\leq L\)

都有\(w_{a_i}=i\)且\(\forall 1\leq k<i\) \(a_k\)为\(a_i\)的父亲。定义\(f_i\)为第i个点的父亲.

有m次修改对于第i次修改会把\(u=(i-1)%mod+n+1\)的点权修改为\(v_i\)

对于每次修改过后的答案乘上i 对1e9+7取模询问m次修改的答案和。\(L\leq n\leq 1e6\) \(m\leq 2e6\) \(1\leq f_i<i\)

显然有一个nm的dp 只不过放到了树上。

不难发现这个L很像我们的最长上升子序列如果该序列中存在最长上升子序列的话那这样求的就是最长上升子序列的方案数了。

不过每次有单点修改。往这个方向思考是无果的基本上我们最长上升子序列方案数不支持修改查询。

但是可以发现每次修改的点是有序的 1 2 3 4 5...n...1.... 同时看题目中关键的条件 \(f_i<i\)自己的父亲小于自己也就是说对于每个点在修改的时候自己的父亲已经被改过了这是这道题的关键之处修改并非无序修改。

做题的时候抓住题目中的条件来解决问题把题目中的条件都理解透了再思考问题的解决。

考虑对于链的怎么做其实就是序列了容易设出设\(f_i\)表示以i为结尾的方案数 \(g_i\)表示以i为开头的方案数。

一个点将会被修改掉我们需要-其在原本的答案中所占方案数+新产生的方案。

所占方案那显然是\(f_i\cdot g_i\) 考虑一个新的数字\(v_i\) 其产生的方案为 \((\sum\limits_{1\leq k<i,w_k=v_i-1}f_k)\cdot (\sum\limits_{i+1\leq k\leq L,w_k==v_i+1}g_k)\)

可以发现这正是我们新的f值和g值的相乘。

但是不可做的一点是由于存在修改我们一个点的f 和g容易得出但是其他点的f和g的值将会被扰乱导致下一个点再这样做的时候结果不正确。

当然这种修改是很难维护的尽管我们维护值域线段树想做出这样的修改也很不容易。

接下来利用题目中的条件自己的父亲比自己先修改这一条件。

可以发现我们当前点在修改过后对于新的f值我们利用父亲修改过后的再累计一个方案数维护。

对于g的维护可以发现还是旧的就行因为儿子不可能发生修改。

但是有多次轮回修改怎么解决。其实可以直接莽了每次树形dp处理一轮的问题。时间复杂度O(n) 同时也处理O(n)个问题。

那么有O(m)个问题显然我们时间复杂度就是O(m)的简单来讲就是 m/n轮处理每次时间复杂度O(n)故总时间复杂度O(m).

考虑在树上怎么做我们还是套用刚才的模型来做对于f显然可以这样做。

考虑g的维护发现处理完一个子树的g 这个子树的g由于对我们的父亲还有贡献我们不能将其清理掉所以可以进行桶差分一下即可超级好写。

综上我们解决了这个问题时间复杂度O(m).(真的不是什么LIS的方案数啊啊啊。

可以发现当自己认为问题不可被解决时 80%是自己没有认真读题。

···

int n,m,L,len,top;

int a[MAXN],v[MAXN];ll cf[MAXN],w[MAXN],b[MAXN],g[MAXN],cg[MAXN],f[MAXN],cnt,ans;

int lin[MAXN],ver[MAXN],nex[MAXN];

inline void add(int x,int y)

{

ver[++len]=y;

nex[len]=lin[x];

lin[x]=len;

}

inline void dp(int x)

{

ll ww=cg[v[x]+1];

ll w1=cg[a[x]+1];

//求出f数组 f数组表示以某个点为结尾的方案数更新过的v数组来求出

f[x]=cf[v[x]-1];

if(v[x]1)f[x]=1;

w[x]=cf[a[x]-1];

if(a[x]1)w[x]=1;

cf[v[x]]=(cf[v[x]]+f[x])%mod;

go(x)dp(tn);

cf[v[x]]=(cf[v[x]]-f[x])%mod;

//求出g数组 g数组表示以某个点为开头的方案数通过a数组求出

g[x]=(cg[v[x]+1]-ww)%mod;

if(v[x]L)g[x]=1;

b[x]=(cg[a[x]+1]-w1)%mod;

if(a[x]L)b[x]=1;

cg[a[x]]=(cg[a[x]]+b[x])%mod;

if(a[x]1)ans=(ans+b[x])%mod;

}

int main()

{

freopen("1.in","r",stdin);

//freopen("tree.out","w",stdout);

get(n);get(m);get(L);

rep(2,n,i)add(read(),i);

rep(1,n,i)v[i]=get(a[i]);

int st;

rep(1,m,i)

{

int x=(i-1)%n+1;

if(x1)st=i;

a[x]=v[x];

get(v[x]);

if(xn||im)

{

rep(1,n,j)cg[j]=cf[j]=0;

rep(x+1,n,j)a[j]=v[j];

ans=0;dp(1);

rep(1,x,j)

{

ans=(ans-w[j]b[j]+f[j]g[j])%mod;

cnt=(cnt+ans*st)%mod;++st;

}

}

}

printf("%lld\n",(cnt+mod)%mod);

return 0;

}

可以说这道题并非很难 失误之处在于没有抓住题目种给的条件。

巴特西

省选模拟赛day4

做题的时候抓住题目中的条件来解决问题把题目中的条件都理解透了再思考问题的解决。

最新文章

热门文章

巴特西

省选模拟赛day4

做题的时候抓住题目中的条件来解决问题 把题目中的条件都理解透了 再思考 问题的解决。

最新文章

热门文章

做题的时候抓住题目中的条件来解决问题把题目中的条件都理解透了再思考问题的解决。