2021.7.17 Contest 题解
T1:
Description:
凌晨 (0:00)，白云躺在了床上，但是怎么都睡不着。
过了一会儿，它看到了墙上挂的钟出现了一个非常有趣的情况：时针和分针重合了。
于是，它想到了一个问题：从凌晨 (0:00) 到 (hh:mm) 这段时间内，时针和分针一共重合了多少次。
Input:
仅一行，(hh:mm)
Output:
仅一行，表示重合次数。
Sample1 Input:
01:05
Sample1 Output:
1
Sample2 Input:
08:36
Sample2 Output:
8
Sample3 Input:
03:16
Sample3 Output:
3
Hint:
对于 100% 的数据, (0 leq hh < 24, 0 leq mm < 60)
题目分析：
小学奥数题（这不就是个追及问题吗？。答案显然等于((h*60+m)*11/720+1)
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int h,m,ans;char s[10];
struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
scanf("%s",s+1),h=(s[1]-'0')*10+(s[2]-'0'),m=(s[4]-'0')*10+(s[5]-'0'),cout<<(h*60+m)*11/720+1<<'
';return 0;
}
T2:
Description:
白云开着飞机带白兔来到了一座城市，这座城市有 (n) 个景点。
这座城市的道路非常有意思，每个景点都恰好存在一条通往其它某个节点的单向道路。
现在白云可以把飞机降落在任何一个景点，然后让白兔独自旅行。当白兔旅行结束时，白云会到白兔所在的景点来接它。而在旅行的中途，白兔只能靠城市的道路来移动。
现在白兔想制定一个旅游的顺序，按照这个顺序依次前往每一个景点。在每个景点游玩会消耗白兔一定的体力值。为了让白兔有充足的信心，我们的这个方案必须满足：每次游览景点所消耗的体力值必须 严格 比前一个景点消耗的体力值要小。
白兔想知道它最多能去几个景点游玩。
Input:
第一行，一个数 (n)，表示景点的个数。
第二行 (n) 个数，表示每个景点游玩需要消耗的体力值。 第三行 (n) 个数 (p_1 · · · p_n)，表示存在一条从 (i) 到 (p_i) 的路径。
Output:
输出最多能玩几个景点。
Sample1 Input:
5
1 2 3 5 2
2 3 1 1 3
Sample1 Output:
4
Hint:
data range:
每个景点消耗的体力值在 ([0, 10^9 ]) 范围内
对于 $ 30%$ 的数据，(n leq 1000)；
对于 $ 50%$ 的数据，(n leq 10000)；
对于 (100\%) 的数据，(n leq 100000)；
sample explaination:
我们先去 (5) 号景点，然后去 (3) 号景点，接下来去 (2) 号景点，最后去 (1) 号景点，这样一共能在 (4) 个景点游玩
题目分析：
可以发现给定的图是一个基环树森林（每个点有 (1) 条出边
于是我们直接跑个树上DP，用线段树或树状数组维护，支持撤销即可。当然，比赛时我没考虑图的性质，想复杂了，大力直接写了一个线段树合并（线段树优化DP），可以在图较稀疏的情况下做更加复杂的图。
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 100005
#define LL long long
#define inf 2147483647
#define INF 2147483647114
using namespace std;
int n,m,cc,top,tot,num,H,T,ans,sz[N],q[N],f[N],st[N],a[N],rt[N],rd[N],dfn[N],low[N],col[N],fir[N],nxt[N],son[N],trl[N*200],trr[N*200],Max[N*200];vector<int> g,G[N],F[N]; inline void add(int x,int y){son[++tot]=y,nxt[tot]=fir[x],fir[x]=tot;}
inline void tarjan(int x){st[++top]=x,dfn[x]=low[x]=++tot;for(register int i=fir[x];i;i=nxt[i]) if(!dfn[son[i]]) tarjan(son[i]),low[x]=min(low[x],low[son[i]]);else if(!col[son[i]]) low[x]=min(low[x],dfn[son[i]]);if(dfn[x]==low[x]){col[x]=++cc,G[cc].push_back(a[x]);while(st[top]^x) G[cc].push_back(a[st[top]]),col[st[top--]]=cc;top--;}}
inline void U(int &x,int l,int r,int pos,int v){++num,trl[num]=trl[x],trr[num]=trr[x],Max[num]=max(Max[x],v),x=num;if(l==r) return;int mid=l+r>>1;if(mid>=pos) U(trl[x],l,mid,pos,v);else U(trr[x],mid+1,r,pos,v);}
inline int Q(int x,int l,int r,int ll,int rr){if(!x||ll>rr) return 0;if(l>=ll&&r<=rr) return Max[x];int mid=l+r>>1,res=0;if(mid>=ll) res=Q(trl[x],l,mid,ll,rr);if(mid<rr) res=max(res,Q(trr[x],mid+1,r,ll,rr));return res;}
inline void M(int &x,int lst,int l,int r){if(!x){x=lst;return;} Max[x]=max(Max[x],Max[lst]);if(l==r) return;int mid=l+r>>1;if(trl[lst]) M(trl[x],trl[lst],l,mid);if(trr[lst]) M(trr[x],trr[lst],mid+1,r);} inline void get(int x){
int sx=G[x].size(),SX=F[x].size(),W=0;for(register int i=0;i<SX;i++) if(sz[F[x][i]]>sz[W]) W=F[x][i];rt[x]=rt[W];for(register int i=0;i<SX;i++) if(F[x][i]^W) M(rt[x],rt[F[x][i]],1,m);
for(register int i=sx-1;i>=0;i--){int xx=G[x][i],tmp=Q(rt[x],1,m,xx+1,m)+1;ans=max(ans,tmp),U(rt[x],1,m,xx,tmp);}
}
struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
fin>>n;for(register int i=1;i<=n;i++) fin>>a[i],g.push_back(a[i]);for(register int i=1;i<=n;i++) fin>>f[i],add(i,f[i]);
sort(g.begin(),g.end()),g.erase(unique(g.begin(),g.end()),g.end());for(register int i=1;i<=n;i++) a[i]=lower_bound(g.begin(),g.end(),a[i])-g.begin()+1;m=g.size();
tot=0;for(register int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);tot=0;for(register int i=1;i<=cc;i++) sz[i]=G[i].size(),sort(G[i].begin(),G[i].end()),fir[i]=0;for(register int i=1;i<=n;i++){if(col[i]!=col[f[i]]) add(col[i],col[f[i]]),rd[col[f[i]]]++;}
for(register int i=1;i<=cc;i++) if(!rd[i]) q[++T]=i,ans=1,get(i);while(H<T){int x=q[++H];for(register int i=fir[x];i;i=nxt[i]){int to=son[i];sz[to]+=sz[x],F[to].push_back(x),rd[to]--;if(!rd[to]) get(to),q[++T]=to;}}cout<<ans<<'
';return 0;
}
T3:
Description:
白兔有一棵 (n) 个结点带边权的树。定义 (g(x, y)) 为 (x) 和 (y) 两个点路径上所有边权最大值。特别地，(g(x, x) = 0)。
白云想构造一个序列 (p_1 · · · p_n)，一个序列的价值为 (min^{n} _{i=1} g(i, p_i))。同时，白兔给了白云一个限制：任何一个数 (x) 在序列中不得超过 (s_x) 次。
白云想知道满足要求的所有序列的最大价值。
Input:
第一行一个数 (n)。
接下来 (n − 1) 行，每一行三个数 ((u, v, w)) 表示一条 ((u, v)) 之间权值为 (w) 的边。 最后一行 (n) 个数表示 (s_1 · · · s_n)
Output:
求最大价值。
Sample1 Input:
4
1 2 1
2 3 2
3 4 3
1 1 1 1
Sample1 Output:
2
Hint:
data range:
对于 (30\%) 的数据，(n leq 10)；
对于 (60\%) 的数据，(n leq 1000)；
对于 (100\%) 的数据，(n leq 10^5,w leq 10^9,1 leq s_i leq n)；
sample explaination:
一个最佳的序列 (P) 为 (4, 3, 2, 1)。
题目分析：
一看到这种 (min(max)) 问题首先考虑的就是二分。我们二分一个最大价值 (w)，那么我们可以 (O(n)) dfs 一遍找出所有大于 (w) 的边。这些边将整棵树划分为若干个连通块，两两连通块间可以满足条件。
于是问题转化为对于任意一个连通块，连通块的大小是否小于等于其余连通块的 (s_i) 之和，如果存在一个连通块不满足条件，则答案比 (w) 小；反之，答案大于等于 (w)。
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int n,tot,s[N],c[N],cc[N],f[N],fir[N],nxt[N<<1],son[N<<1],w[N<<1];LL SS,S[N],ss[N];vector<int> g;
inline void add(int x,int y,int z){son[++tot]=y,nxt[tot]=fir[x],fir[x]=tot,w[tot]=z;} inline void DFS(int x){for(register int i=fir[x];i;i=nxt[i]) if(son[i]^f[x]) f[son[i]]=x,DFS(son[i]);}
inline void dfs(int x,int y){S[x]=s[x],c[x]=1;for(register int i=fir[x];i;i=nxt[i]) if(son[i]^f[x]){int to=son[i];dfs(to,y);if(w[i]>=y) cc[++tot]=c[to],ss[tot]=S[to];else c[x]+=c[to],S[x]+=S[to];}}
inline bool check(int x){tot=0,dfs(1,x),cc[++tot]=c[1],ss[tot]=S[1];for(register int i=1;i<=tot;i++) if(SS-ss[i]<cc[i]) return 0;return 1;} struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
fin>>n;for(register int i=1,x,y,z;i<n;i++) fin>>x>>y>>z,add(x,y,z),add(y,x,z),g.push_back(z);DFS(1),sort(g.begin(),g.end()),g.erase(unique(g.begin(),g.end()),g.end());
for(register int i=1;i<=n;i++) fin>>s[i],SS+=(LL)s[i];int l=0,r=g.size()-1,ans=0;while(l<=r){int mid=l+r>>1;if(check(g[mid])) ans=max(ans,g[mid]),l=mid+1;else r=mid-1;}cout<<ans<<'
';return 0;
}
T4:
Description:
白云有一棵 (n) 个结点的树，以 (1) 号结点为根，这棵树的每个结点有一个权值 (val_i)。
定义一个连通块的喜爱度为块内所有结点权值的乘积。
白兔有很多疑问，每个疑问有两个参数 (k), (s)，表示询问所有经过点 (k) 的大小为 (s) 的连通块的喜爱度之和。
白云会定期对树做一些修改。
Input:
第一行 (2) 个整数 (n, Q)，表示树的结点个数和事件个数。
第二行 (n) 个整数表示 (val_{1...n})。
第三行 (n − 1) 个整数表示 (2 . . . n) 号结点的父亲。
接下来 (Q) 行，第一个数为 (op in {0, 1})，如果 (op = 0) 表示白云要对某个结点的权值进行修改，接下来两个数 (k), (c) 表示把结点 (k) 的权值修改为 (c)。如果 (op = 1) 表示白兔的疑问， 接下来两个数 (k), (s)。
Output:
对于 (op = 1)，每行一个数表示答案。答案对 (10^9 + 7) 取模。
Sample1 Input:
15 15
6 4 8 6 8 9 10 9 2 9 8 3 3 6 2
1 1 1 3 1 3 6 5 3 10 9 7 9 13
1 13 8
1 2 4
1 12 8
1 11 2
0 2 9
0 11 4
1 3 6
0 4 5
1 13 7
1 8 2
1 7 6
1 7 8
0 5 5
0 1 7
1 1 6
Sample1 Output:
128592000
11304
35520768
72
10402608
16325280
81
6030720
359079840
8686888
Hint:
对于 (100\%) 的数据，满足 (1leq n,Qle 10^5)，(1leq val_i < 10^9+7)，(s leq 10)，结点 (k) 的父亲为 (1 . . . k − 1) 的一个均匀随机整数。
题目分析：
树上换根背包，我们考虑对于每一个节点 (i) 先预处理出 (f_{i,j}) 表示仅考虑 (i) 的子树的时候经过 (i) 大小为 (j) 的连通块的喜爱度之和。
每次修改操作只会修改这个点 (k) 到根的这一条路径上的每个节点的 (f_{i,j})，修改权值可以看成删掉一个权值，再重新加入一个权值，加入操作反着跑背包，撤销操作正着跑背包，由于树随机生成暴力更新即可。（ 树高 ≈ (log_2n) ）
每次查询，从根到查询的节点跑一遍换根DP，然后合并答案即可。
事实上，由于 (s) 很小，树不需要随机生成，每次修改只会影响与 (k) 距离小于等于 (s) 的节点，因此只需要往上更新 (s) 个节点即可。
代码如下(马蜂很丑，不喜勿喷)——
#include<bits/stdc++.h>
#define N 200005
#define inf 2147483647
#define LL long long
using namespace std;
int n,q,tot,O,fir[N],nxt[N],son[N],a[N],F[N],f[N][15],ff[2][15];const int p=1e9+7;
inline void add(int x,int y){son[++tot]=y,nxt[tot]=fir[x],fir[x]=tot;} inline int power(int x,int y){int z=1;while(y){if(y&1) z=1ll*z*x%p;y>>=1,x=1ll*x*x%p;}return z;}
inline void A(int x,int y){for(register int i=10;i;i--) for(register int j=1;j<i;j++) f[x][i]=((LL)f[x][i]+1ll*f[x][j]*f[y][i-j])%p;}
inline void D(int x,int y){for(register int i=2;i<=10;i++) for(register int j=1;j<i;j++) f[x][i]=(f[x][i]-1ll*f[x][j]*f[y][i-j]%p+p)%p;}
inline void dfs(int x){f[x][1]=a[x];for(register int i=fir[x];i;i=nxt[i]) dfs(son[i]),A(x,son[i]);}
inline void U1(int x){if(x==1) return;A(F[x],x),U1(F[x]);} inline void U2(int x){if(x==1) return;U2(F[x]),D(F[x],x);}
inline void U(int x,int y){U2(x);int inv=power(a[x],p-2);for(register int i=1;i<=10;i++) f[x][i]=1ll*f[x][i]*inv%p*y%p;a[x]=y,U1(x);} inline void W(int x){
if(x==1){for(register int i=1;i<=10;i++) ff[O][i]=0;return;}W(F[x]);O^=1;for(register int i=1;i<=10;i++) ff[O][i]=f[F[x]][i];for(register int i=2;i<=10;i++) for(register int j=1;j<i;j++) ff[O][i]=(ff[O][i]-1ll*ff[O][j]*f[x][i-j]%p+p)%p;
for(register int i=10;i;i--) for(register int j=1;j<i;j++) ff[O][i]=((LL)ff[O][i]+1ll*ff[O][j]*ff[O^1][i-j])%p;
}
inline int Q(int x,int y){W(x);int res=f[x][y];for(register int i=1;i<y;i++) res=((LL)res+1ll*ff[O][i]*f[x][y-i])%p;return res;}
struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
template<typename T>FastIO& operator >> (T&ret){
ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
}
FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
template<typename T>FastIO& operator << (T x){
if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
fin>>n>>q;for(register int i=1;i<=n;i++) fin>>a[i];for(register int i=2;i<=n;i++) fin>>F[i],add(F[i],i);
dfs(1);while(q--){int op,x,y;fin>>op>>x>>y;if(!op) U(x,y);else fout<<Q(x,y)<<'
';}return 0;
}