2023 ICPC 网络预选赛补题 II

#include<bits/stdc++.h>
#define ld double
using namespace std;
const int maxn=1e6+5;
int a[maxn],b[maxn];
ld p[maxn],c[maxn];
int t,n;
bool cmp(ld a,ld b)
{
	return a<b;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]),
		cin>>p[i],
		c[i]=1.0*(a[i]+b[i])*p[i]+1.0*a[i]*(1.0-p[i]);
		sort(c+1,c+n+1);
		for(int i=1;i<=n;i++)
			c[i]+=c[i-1];
		ld ans=0;
		for(int i=1;i<=n;i++)
		ans+=c[i];
		printf("%.12lf\n",ans);	
	}
	return 0;
}

/*
1. 突破点：按行（或列）遍历，则每行（或列）至少选一个人。
2. 易错点：每行（或列）不是只能选一个人（这个人满足其pay为该行或列的最小值），所有的负 pay 无论是否为最小值均应被统计入答案。
*/
#include <iostream>
#define ll long long
using namespace std;
const int maxn=510;
int mi[2][maxn];
int a[maxn][maxn]; ll ans,ansi;
int n,t;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		ans=0,ansi=0;
		for(int i=1;i<=n;i++)
		{
			mi[0][i]=1e6+1;
			for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]),
			mi[0][i]=min(mi[0][i],a[i][j]);
		}
		for(int j=1;j<=n;j++)
		{
			mi[1][j]=1e6+1;
			for(int i=1;i<=n;i++)
			mi[1][j]=min(mi[1][j],a[i][j]);
		}
		for(int i=1;i<=n;i++)
		{
			bool flag=false;
			for(int j=1;j<=n;j++)
				if(a[i][j]<0)
				{
					if(a[i][j]==mi[0][i])
					{
						if(flag) ans+=a[i][j];
						else flag=true;
					} 
					else ans+=a[i][j];
				}
			ans+=mi[0][i];	
		}
		for(int j=1;j<=n;j++)
		{
			bool flag=false;
			for(int i=1;i<=n;i++)
				if(a[i][j]<0)
				{
					if(a[i][j]==mi[1][j])
					{
						if(flag) ansi+=a[i][j];
						else flag=true;
					} 
					else ansi+=a[i][j];
				}
			ansi+=mi[1][j];
		}
		printf("%lld\n",min(ans,ansi));
	}
	return 0;
}

/*
1. 正解：以根节点 1 为起点跑 BFS。
2. 突破点：发现结论——若节点 i 被访问过，则从根节点 1 到 i 的树链上所有的节点一定已被访问过。
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct edge
{
	int v,next;
}e[maxn<<1];
int cnt,head[maxn];
void add(int u,int v)
{
	e[++cnt]=(edge){v,head[u]};
	head[u]=cnt;
}
int n,m,anc[maxn][25];
vector<int> gop[maxn];
void dfs(int u,int fa)
{
	anc[u][0]=fa;
	int v;
	for(int i=head[u];i;i=e[i].next)
	{
		v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
	}
}
bool vis[maxn];
queue<int> q;
int dis[maxn];
void bfs()
{
	vis[0]=true;
	q.push(1),vis[1]=true;
	dis[1]=0;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=0;i<gop[u].size();i++)
		{
			int v=gop[u][i];
			if(vis[v]) continue;
			while(!vis[v]) 
				vis[v]=true,q.push(v),
				dis[v]=dis[u]+1,
				v=anc[v][0];              
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int x;
	for(int i=1;i<n;i++)
	{
		scanf("%d",&x);
		add(i+1,x),add(x,i+1);
	}
	int u,v;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		gop[u].push_back(v);
		gop[v].push_back(u);
	}
	dfs(1,0);
	for(int j=1;j<=20;j++)
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
	bfs();
	for(int i=2;i<=n;i++)
	cout<<(dis[i]==0?-1:dis[i])<<" ";
	return 0;
}

/*
1. 标签:贪心 枚举.
2. 突破点:若 i 为最优转移点，则当在 i 挑战失败回到 a_i 时，一定会再从 a_i 走到 i.
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN=int(5e5+5);
int a[MAXN],x[MAXN];
int main()
{
	int n,T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		for(int i=0;i<=n-1;i++)
			scanf("%d",&a[i]);
		for(int i=0;i<=n-1;i++)
			scanf("%d",&x[i]);
		double ans=n*1.0;
		for(int i=0;i<=n-1;i++) {
			double p=(double)x[i]/100000.0;
			double tp=(p==0.0)?MAXN*1.0:double(i-a[i]+1)/p;
			tp+=a[i];
			ans=min(ans,tp);
		}
		printf("%.12lf\n",ans);
	}
}