• 周三. 2月 28th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

义乌集训7.17 contest 10题解

admin

11月 28, 2021

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;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注