NIKKEI Programming Contest 2019 翻车记

2021-11-18 21:54:00

　　A：签到。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,a,b;

int main()

{

	/*freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);*/

	n=read(),a=read(),b=read();

	cout<<min(a,b)<<' '<<max(0,a+b-n);

	return 0;

}

　　B：签到。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

#define N 110

int n;

char a[N],b[N],c[N];

int main()

{

	/*freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);*/

	n=read();

	scanf("%s",a+1);scanf("%s",b+1);scanf("%s",c+1);

	int ans=0;

	for (int i=1;i<=n;i++)

	{

		if (a[i]==b[i]&&b[i]==c[i]) ;

		else if (a[i]==b[i]||a[i]==c[i]||b[i]==c[i]) ans++;

		else ans+=2;

	}

	cout<<ans;

	return 0;

}

　　C：考虑一种菜自己吃和对方吃的收益差，于是显然按a_i+b_i排序从大到小选即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

#define N 300010

#define ll long long

int n;

struct data

{

	int x,y;

	bool operator <(const data&a) const

	{

		return x+y<a.x+a.y;

	}

}a[N];

ll ans;

int main()

{

	/*freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);*/

	n=read();

	for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();

	sort(a+1,a+n+1);reverse(a+1,a+n+1);

	for (int i=1;i<=n;i++)

	if (i&1) ans+=a[i].x;

	else ans-=a[i].y;

	cout<<ans;

	return 0;

}

　　D：显然图仍是一个DAG，其中度数为0的点是原树的根。由于图中没有重边，瞎考虑一下容易发现，对于每一个点，由根到它的最长路上该点的前驱即为其在原树中的父亲。拓扑排序一下即可。开始写了个不知道啥玩意于是比E晚了10min。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

#define N 300010

#define ll long long

int n,m,p[N],fa[N],deep[N],degree[N],q[N],t,root;

bool flag[N];

struct data{int to,nxt;

}edge[N];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

void topsort()

{

	int head=0,tail=0;

	for (int i=1;i<=n;i++) if (!degree[i]) q[++tail]=i;

	while (tail<n)

	{

		int x=q[++head];

		for (int i=p[x];i;i=edge[i].nxt)

		{

			degree[edge[i].to]--;

			if (deep[x]+1>deep[edge[i].to])

			{

				deep[edge[i].to]=deep[x]+1;

				fa[edge[i].to]=x;

			}

			if (!degree[edge[i].to]) q[++tail]=edge[i].to;

		}

	}

}

int main()

{

	n=read(),m=read();

	for (int i=1;i<n+m;i++)

	{

		int x=read(),y=read();

		addedge(x,y);degree[y]++;

	}

	topsort();

	for (int i=1;i<=n;i++) printf("%d\n",fa[i]);

	return 0;

}

　　E：显然从大到小考虑每条边是否需要删即可，但删边的过程中难以维护连通块信息。注意到只有MST的边会对最后所得图的连通性产生影响。于是求出MST，然后可以从大到小删边用LCT维护，但这样显然比较毒瘤。事实上还可以建出kruskal重构树，从大到小考虑每条边，如果其在重构树的父亲不需要被删掉，显然其也不需要被删掉；否则此时其所在连通块即为其在重构树上的子树，判断一下是否需要删掉即可。这样就得到了最后的连通信息，最后再考虑每条边是否保留即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

#define N 400010

#define ll long long

int n,m,a[N],fa[N],id[N],cnt,ans;

bool isdel[N],flag[N];

ll value[N<<2];

struct data

{

	int x,y,z;

	bool operator <(const data&a) const

	{

		return z<a.z;

	}

}e[N];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

namespace kruskal_tree

{

	int p[N<<2],t,degree[N<<2],fa[N<<2];

	ll size[N<<2];

	struct data{int to,nxt;}edge[N<<2];

	void addedge(int x,int y){t++;degree[y]++;fa[y]=x;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

	void link(int x,int y,int i)

	{

		id[i]=++cnt;addedge(cnt,x),addedge(cnt,y);

	}

	void dfs(int k)

	{

		size[k]=a[k];

		for (int i=p[k];i;i=edge[i].nxt)

		{

			dfs(edge[i].to);

			size[k]+=size[edge[i].to];

		}

	}

	void build()

	{

		for (int i=1;i<=cnt;i++)

		if (!degree[i]) dfs(i);

	}

	void del()

	{

		isdel[0]=1;

		for (int i=m;i>=1;i--)

		if (flag[i]&&isdel[fa[id[i]]]&&e[i].z>size[id[i]]) isdel[id[i]]=1;

	}

}

void dfs(int k)

{

	for (int i=kruskal_tree::p[k];i;i=kruskal_tree::edge[i].nxt)

	{

		dfs(kruskal_tree::edge[i].to);

		if (!isdel[k]) fa[find(kruskal_tree::edge[i].to)]=k;

	}

}

int main()

{

	n=read(),m=read();

	for (int i=1;i<=n;i++) a[i]=read();

	for (int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].z=read();

	sort(e+1,e+m+1);

	for (int i=1;i<=4*n;i++) fa[i]=i;cnt=n;

	for (int i=1;i<=m;i++)

	{

		int p=find(e[i].x),q=find(e[i].y);

		if (p!=q) kruskal_tree::link(p,q,i),fa[p]=fa[q]=id[i],flag[i]=1;

	}

	kruskal_tree::build();

	kruskal_tree::del();

	for (int i=1;i<=cnt;i++) fa[i]=i;

	for (int i=1;i<=cnt;i++)

	if (!kruskal_tree::degree[i]) dfs(i);

	for (int i=1;i<=m;i++)

	if (find(e[i].x)==find(e[i].y)&&kruskal_tree::size[find(e[i].x)]>=e[i].z) ans++;

	cout<<m-ans;

	return 0;

}

　　result：rank 132 rating +84

码农公寓

相关文章