还是困，不过已经可以用脑子思考问题了
T1 数据恢复
没啥明确的算法，可以说是贪心？
考虑部分分，
链的直接扫，
对于菊花的发现只要根节点在第一个，剩下的点位置不重要
那么按照$a/b$排序，扫一遍就行。
这启发我们正解如何考虑祖先和儿子的关系
我们设$v=\frac{a}{b}$，那么还是贪心的选择$v$最小的最优
考虑父子关系
如果当前最优的点的父亲被选，那么直接选他更优
如果当前最优的点的父亲没选，那么选上他的父亲再选他更优
这样就可以使用并查集维护，每次找到$v$最小的点后把他和他父亲合在一起，
$a,b$也合并，然后把新的节点插进可重集内，并删掉原来的两个点。
关于答案的累加，直接在合并的时候累加一个$a_j*b_i,fa[j]=i$即可。
证明：
考虑$fa[j]=i$，设$j$后面的$a$的和为$sum$，设$i,j$合并后的大点叫$k$
原来这一部分的答案为$ans=b_j*sum+b_i*(a_j+sum)$
合并后若要计算答案为$ans=b_k*sum=b_j*sum+b_i*sum$，发现少了一项$b_i*a_j$
所以直接在合并时加这一项，剩下的那些答案也会在合并这个的时候被统计，所以直接加这个是正确的。
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=3e5+5;
15 int n,fa[NN],ans,f[NN],a[NN],b[NN];
16 bool vis[NN];
17 struct SNOW{
18 double v; int id; SNOW(){}
19 SNOW(double v,int id):v(v),id(id){}
20 bool operator<(const SNOW&x)const{
21 if(v==x.v) return id<x.id;
22 return v<x.v;
23 }
24 };multiset<SNOW> s;
25 inline int getfa(int x){return fa[x]=(fa[x]==x?x:getfa(fa[x]));}
26 inline void merge(int i,int j){//j向i合并
27 i=getfa(i); j=getfa(j);
28 if(i==j) return;
29 ans+=a[j]*b[i];
30 a[i]+=a[j];a[j]=0;
31 b[i]+=b[j];b[j]=0;
32 fa[j]=i;
33 }
34 namespace WSN{
35 inline short main(){
36 freopen("data.in","r",stdin);
37 freopen("data.out","w",stdout);
38 n=read();for(int i=2;i<=n;i++) f[i]=read();
39 vis[0]=1;
40 for(int i=1;i<=n;i++) fa[i]=i;
41 for(int i=1;i<=n;i++)
42 a[i]=read(),b[i]=read(),s.insert(SNOW(b[i]?1.0*a[i]/b[i]:0,i));
43 while(s.size()){
44 auto it=s.begin(); s.erase(it);
45 int ff=f[it->id],f2=getfa(ff);
46 vis[it->id]=1;
47 if(vis[f2]) merge(f2,it->id);
48 else{
49 s.erase(s.find(SNOW(1.0*a[f2]/b[f2],f2)));
50 merge(f2,it->id);
51 s.insert(SNOW(1.0*a[f2]/b[f2],f2));
52 }
53 }
54 write(ans);
55 return 0;
56 }
57 }
58 signed main(){return WSN::main();}
View Code
T2 下落的小球
考虑设$siz_i$表示子树大小，$w_i$表示$i$子树内叶子节点的$\sum a$，$r_i=w_i-siz_i$
那么这个$r_i$就是这颗子树可以让他的上面的那一条链掉球的数量。
那么直接对于$r$和$siz$做可重集排列就行。
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1e6+5,mod=1e9+7;
15 int n,fa[NN],h[NN],v[NN],w[NN],ans=1;
16 struct SNOW{int to,next;}e[NN<<1]; int head[NN],rp;
17 inline void add(int x,int y){e[++rp]=(SNOW){y,head[x]};head[x]=rp;}
18 inline int qmo(int a,int b,int ans=1){
19 int c=mod; a%=c;for(;b;b>>=1,a=a*a%c) if(b&1) ans=ans*a%c;
20 return ans;
21 }
22 inline void pre(){
23 h[0]=h[1]=1; v[0]=v[1]=1;
24 for(int i=2;i<NN;i++) h[i]=h[i-1]*i%mod;
25 v[NN-1]=qmo(h[NN-1],mod-2);
26 for(int i=NN-2;i>=2;i--) v[i]=v[i+1]*(i+1)%mod;
27 }
28 int siz[NN];
29 inline void dfs(int x){
30 siz[x]=1;int s1=0,s2=0;
31 for(int i=head[x];i;i=e[i].next){
32 int y=e[i].to; dfs(y);
33 siz[x]+=siz[y]; w[x]+=w[y];
34 s1+=w[y]-siz[y]; s2+=siz[y];
35 if(w[y]>=siz[y]) ans=ans*v[w[y]-siz[y]]%mod*v[siz[y]]%mod;
36 } if(w[x]<siz[x]) ans=0;
37 if(s1>0&&s2>0) ans=ans*h[s1]%mod*h[s2]%mod;
38 }
39 namespace WSN{
40 inline short main(){
41 freopen("ball.in","r",stdin);
42 freopen("ball.out","w",stdout);
43 n=read(); pre();
44 for(int i=2,a;i<=n;i++) a=read(),add(a,i);
45 for(int i=1;i<=n;i++) w[i]=read(); dfs(1);
46 write(ans);
47 return 0;
48 }
49 }
50 signed main(){return WSN::main();}
View Code
T3 消失的字符串
咕咕咕，只会$k=0$
T4 古老的序列问题
$n<=2000$预处理前缀和表示从$i$到$j$的$\sum \sum cost(i,j)$
然后每次询问$O(n^2)$
单调不降部分分，$\sum \sum a_l*a_r$，拆柿子预处理前缀和就行
然后不会了
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1e5+5,mod=1e9+7;
15 int n,m,s[NN],L,R,ans;
16 int sm[2005][2005];
17 inline void task1(){
18 for(int i=1;i<=n;i++){
19 int mn=0x3fffffff,mx=0;
20 for(int j=i;j<=n;j++){
21 mn=min(mn,s[j]);mx=max(mx,s[j]);
22 sm[i][j]=(sm[i][j-1]+mn*mx%mod)%mod;
23 }
24 }
25 while(m--){
26 L=read(),R=read(),ans=0;
27 for(int i=L;i<=R;i++) ans=(ans+sm[i][R])%mod;
28 write(ans);
29 }
30 }
31 int tmp,sum[NN],S[NN];
32 inline void task2(){
33 for(int i=1;i<=n;i++) sum[i]=(sum[i-1]+s[i])%mod;
34 for(int i=1;i<=n;i++) S[i]=(S[i-1]+s[i]*sum[i-1]%mod)%mod;
35 while(m--){
36 L=read(),R=read(),ans=0;
37 ans=(sum[R]*(sum[R]-sum[L-1]+mod)%mod-(S[R]-S[L-1]+mod)%mod+mod)%mod;
38 write(ans);
39 }
40 }
41 namespace WSN{
42 inline short main(){
43 freopen("sequence.in","r",stdin);
44 freopen("sequence.out","w",stdout);
45 n=read(); m=read();
46 for(int i=1;i<=n;i++) s[i]=read();
47 if(n<=2000) return task1(),0;
48 for(int i=2;i<=n;i++) if(s[i]-s[i-1]>=0) ++tmp;
49 if(tmp==n-1) return task2(),0;
50 return 0;
51 }
52 }
53 signed main(){return WSN::main();}
30
花了一节课大概听懂了战神做法，过于弱了。。。