[NOIP2015提高组复赛]总结

发表于 2015-11-17 分类于信息学，原创阅读次数：本文字数： 796 阅读时长 ≈ 1 分钟

概述

考试时太浮躁！不要心急打程序，一定要静下心来仔细思考算法。是否可行（时限能否过）。保证思考算法的时间。对于自己熟练地算法，要相信能想得出来就一定能最快的调出来。根据数据范围，大胆猜测考得是什么算法。有时候直接想暴力是不科学的，暴力有时非常的复杂，还会带乱对整道题的思绪。
对一些普通算法的应用还不够了解，看不出一道题考察的是什么算法。平时训练要多一些对算法的思考，能不看题解就不看题解，花多点时间在思考上。
DAY1

开考时有点小紧张，看到T1题目很长，就更紧张了！！！
T1:仔细读题，纯暴力。打完用了半个小时，又打了一个判断正确性的程序拍了一下，花了1个多小时，耗时较大，拖慢了后面的解题时间。

T2:紧张依旧挥之不去，随手画了个图，发现是找一个最小的环，然后就想到了tarjan缩点。就开打了。到了最后才发现，tarjan会爆栈，然而为时已晚。
考试时要及时测试小数据和大数据，不要嫌麻烦而只出随机数据。尽管大部分时候程序可以在随机数据下面表现良好。
考试时要冷静下来，仔细思考算法是否存在漏洞。

阅读全文 »

信息学程序模板

发表于 2015-11-06 分类于信息学，原创阅读次数：本文字数： 22k 阅读时长 ≈ 20 分钟

tarjan

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

const int N = 100000+10, M = 1000000+10;
int ans[N],e[2][N],rd[N],next[2][M],to[2][M],v[N],h[N];
int dfn[N],low[N],col[N],stack[N],sum[N],f[N],tot[2];
bool p[N],instack[N];
int n,m,k,Index,top,ctot;

bool cmp(int x,int y) {return x>y;}

void add(int x,int y,int kind)
{
	tot[kind] ++;
	to[kind][tot[kind]] = y;
	next[kind][tot[kind]] = e[kind][x];
	e[kind][x] = tot[kind];
}

int gf(int x)
{
	if (x!=h[x]) h[x] = gf(h[x]);
	return h[x];
}

void link(int x,int y)
{
	int i=gf(x), j=gf(y);
 	if (i!=j) h[i]=j;
}

void tarjan(int x,int kind)
{
	dfn[x] = low[x] = ++ Index;
	instack[x] = 1;
	stack[++ top] = x;
	for (int i=e[kind][x];i;i=next[kind][i])
	{
		int y = to[kind][i];
		if (col[y]) continue;
		if (instack[y]) low[x] = min(low[x],dfn[y]);
		else {tarjan(y,kind);low[x]=min(low[x],low[y]);}
	}
	if (dfn[x]==low[x])
	{
		int y;
		ctot ++;
		do
		{
			y = stack[top --];
			instack[y] = 0;
			sum[ctot] += v[y];
			col[y] = ctot;
		} while (y!=x);
	}
}

void work(int x,int kind)
{
	p[x] = 1;
	f[x] += sum[x];
	for (int i=e[kind][x];i;i=next[kind][i])
	{
		int y = to[kind][i];
		link(x,y);
		rd[y] --;
		f[y] = max(f[y],f[x]);
		if (rd[y]==0) work(y,kind);
	}

}

int main()
{
	freopen("azeroth.in","r",stdin);
	freopen("azeroth.out","w",stdout);


	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i ++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if (u==v) continue;
		add(u,v,0);
	}
	for (int i=1;i<=n;i ++)	scanf("%d",&v[i]);
	scanf("%d",&k);

	for (int i=1;i<=n;i ++) if (!col[i]) tarjan(i,0);


	for (int j=1;j<=n;j ++)
		for (int i=e[0][j];i;i=next[0][i])
		{
			int u = j,v = to[0][i];
			if (col[u]!=col[v])
			{
				add(col[u],col[v],1);
				rd[col[v]] ++;
			}
		}
	//构造新图
	for (int i=1;i<=ctot;i ++) h[i] = i;
	for (int i=1;i<=ctot;i ++)
		if (rd[i] == 0 && !p[i])
			work(i,1);
	for (int i=1;i<=ctot;i ++)
	{
		ans[gf(i)] = max(ans[gf(i)],f[i]);
	}
	sort(ans+1,ans+1+ctot,cmp);
	for (int i=1;i<=min(k+1,ctot);i ++)
		ans[0] += ans[i];
	printf("%d\n",ans[0]);

	return 0;
}

拓扑排序

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 1000000+5,M = 1000000+5;
struct node
{
	int y,next;
} h[M];
int n,m,tot,l,r;
int e[N],list[N],rd[N];

void add(int x,int y)
{
	tot ++;
	h[tot].y = y;
	h[tot].next = e[x];
	e[x] = tot;
	rd[y] ++;
}

int main()
{
	freopen("mikado.in","r",stdin);
	freopen("mikado.out","w",stdout);

	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i ++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	l = 1;r = 0;
	for (int i=1;i<=n;i ++)
		if (!rd[i]) list[++ r] = i;
	while (l<=r)
	{
		int now = list[l ++];
		for (int i=e[now];i;i=h[i].next)
		{
			int y = h[i].y;
			rd[y] --;
			if (!rd[y]) list[++ r] = y;
		}
	}
	printf("%d\n",r);

	return 0;
}