ZJNU 22-07-26 比赛心得

爆wa十一发垫底（

结果发现自己连dfs找元素个数都不会（数据结构白学了

ZJNU 22-07-26 - Virtual Judge (vjudge.net)

void dfs(int x){
	siz[x]=1;
	for (int i=0;i<ve[x].size();i++){
		dfs(ve[x][i]);
		siz[x]+=siz[ve[x][i]];
	}
}

常规dfs用法我居然想不出来。。

F - No Link, Cut Tree!

题意就是完全二叉树，给n-1父子链和权值，亮度定义为同深度权值和中的最大值，询问m次删掉一个节点和他的所有孩子，问删除后的亮度。

 因为给的链不是按照顺序给的，所以要通过孩子元素个数来建树。之后维护前后缀，删点就可以

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pii pair<int,int>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define nep(i,r,l) for (int i=r;i>=l;i--)
#define CIO std::ios::sync_with_stdio(false)
using namespace std;
const int N=2e5+5;
int tr[N],pos[N];
int pre[30][N];
int tre[30][N];
int ans[N];
vector<int> ve[N];
int siz[N],dfn[N],val[N];
void dfs(int x){
	siz[x]=1;
	for (int i=0;i<ve[x].size();i++){
		dfs(ve[x][i]);
		siz[x]+=siz[ve[x][i]];
	}
}
void DFS(int x,int idx){
	dfn[idx]=x;
	if (ve[x].size()==0) return;
	else if (ve[x].size()==1){
		DFS(ve[x][0],idx*2);
	}
	else{
		if (siz[ve[x][0]]>siz[ve[x][1]]){
			DFS(ve[x][0],idx*2);
			DFS(ve[x][1],idx*2+1);
		}
		else{
			DFS(ve[x][0],idx*2+1);
			DFS(ve[x][1],idx*2);
		}
	}
}
void work(){
	int n,m,w1;
	cin>>n>>m>>w1;
	tr[1]=w1;dfn[1]=1;
	int u,v,w;
	rep(i,2,n){
		cin>>u>>v>>w;
		ve[v].push_back(u);
		val[u]=w;
	}	
	dfs(1);
	DFS(1,1);
	rep(i,1,n){
		tr[i]=val[dfn[i]];
		pos[dfn[i]]=i;
	}
	tr[1]=w1;
	for (int i=0;(1<<i)<=n;i++){
		for (int j=(1<<i);j<=((1<<(i+1))-1);j++){
			pre[i][j]=pre[i][j-1]+tr[j];
		}
	}
	for (int i=0;(1<<i)<=n;i++){
		for (int j=(1<<(i+1))-1;j>=(1<<i);j--){
			tre[i][j]=tre[i][j+1]+tr[j];
		}
	}
	rep(i,1,m){
		cin>>u;
		if (ans[u]!=0){cout<<ans[u]<<endl;continue;}
		if (u==1){cout<<0<<endl;continue;}
		int c=0;
		int base=1;
		while (pos[u]>=base){
			base=base*2;
			c++;
		}
		base=base/2;
		c--;
		int l,r;
		int sum=w1;
		l=r=pos[u];
		int cnt=0;
		int b=1;
		while (b<base){
			cnt++;
			sum=max(sum,pre[cnt-1][b*2-1]);
			b=b*2;
		}
		while ((1<<cnt)<=n){
			sum=max(sum,pre[cnt][l-1]+tre[cnt][r+1]);	
			l=l*2;
			r=r*2+1;
			cnt++;
		}
		ans[u]=sum;
		cout<<sum<<endl;
	}
		
}
signed main(){
	CIO;
	{
		work();
	}
	return 0;
}

G - Hungry Canadian

完全没想到dp。。

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pii pair<int,int>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define nep(i,r,l) for (int i=r;i>=l;i--)
#define CIO std::ios::sync_with_stdio(false)
using namespace std;
const int N=2e5+5;
int p[30][30];
int dp[N][30];
void work(){
	int k;cin>>k;
	rep(i,1,26){
		rep(j,1,26){
			cin>>p[i][j];
		}
	} 
	memset(dp,0x3f,sizeof dp);
	for (int i=1;i<=26;i++) dp[1][i]=0;
	for (int i=1;i<=k;i++){
		for (int j=1;j<=26;j++){
			for (int l=1;l<=26;l++){
				dp[i][j]=min(dp[i][j],dp[i-1][l]+p[l][j]);
			}
		}
	}
	int ans=INT_MAX;
	for (int i=1;i<=26;i++){
		ans=min(ans,dp[k][i]);
	}
	cout<<ans<<endl;
}
signed main(){
	CIO;
	//int _;cin>>_;while(_--)
	{
		work();
	}
	return 0;
}