山东省第十届ACM浪潮杯补题

第一次参加省赛，可能也是最后一次了。。有点遗憾，但是收获还是很多的。济南大学真大，饭菜也很好吃，志愿者小姐姐也很漂亮。上来题出的很快，差不多不到一个半小时就出了五道题，然后wa了两发。后面三个半小时全程挂机，H和L题一直没出，思路有问题。最后五题拿铜。遗憾收场。要是五题出的在快点就是银牌了（毕竟是铜牌靠前，菜是原罪）
补题H和L。
H
Median
山东省第十届ACM浪潮杯补题
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4124
赛场上一直想拓扑排序，各种拓扑排序，然后想出各种不对的条件。一直wa，，，下了赛场才知道，不一定要是确定的，把所有不确定的找出来就行。啊啊啊。我们想一下，其实那个点可以作为中位数的条件就是大于或者小于这个数的个数都不大于n/2,就有可能作为中位数。其实就是正反各建一次边，正着反着找出各个点的子树（类似）节点数。边找边判断就可以了。唉，难受的一批

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

const int maxx=1e2+10;
int mp1[maxx][maxx];
int mp2[maxx][maxx];
int in[maxx];
int vis[maxx];
int n,m;

void init()
{
	memset(mp1,0,sizeof(mp1));
	memset(mp2,0,sizeof(mp2));
	memset(vis,0,sizeof(vis));
	memset(in,0,sizeof(in));
}

int dfs1(int cur)
{
	int ans=1;
	vis[cur]=1;
	for(int i=1;i<=n;i++)
	{
		if(mp1[cur][i]&&vis[i]==0)
		{
			vis[i]=1;
			ans+=dfs1(i);
		}
	}
	return ans;
}

int dfs2(int cur)
{
	int ans=1;
	vis[cur]=1;
	for(int i=1;i<=n;i++)
	{
		if(mp2[cur][i]&&vis[i]==0)
		{
			vis[i]=1;
			ans+=dfs2(i);
		}
	}
	return ans;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{ 
		scanf("%d%d",&n,&m);
		init();//初始化！！！！
		int x,y;
		int flag1=1;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d",&x,&y);
			mp1[x][y]=1;
			mp2[y][x]=1;
			in[y]++;
		}
		queue<int> p;
		for(int i=1;i<=n;i++)
		{
			if(in[i]==0)
			{
				p.push(i);	
			}
		}
		while(p.size())//判断环，如果有环，肯定不对的。。
		{
			int x=p.front();
			p.pop();
			if(vis[x]) continue;
			vis[x]=1;
			for(int i=1;i<=n;i++)
			{
				if(mp1[x][i])
				{
					in[i]--;
					if(in[i]==0)
					{
						p.push(i);
					}		
				}
			}
		}
		int flag=1;
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==0)
			{
				flag=0;
				break;
			}
		}
		if(flag==0)
		{
			for(int i=1;i<=n;i++) printf("0");
			printf("\n");
			continue;
		}
		for(int i=1;i<=n;i++)
		{
			memset(vis,0,sizeof(vis));
			int x=dfs1(i)-1;//小于
			memset(vis,0,sizeof(vis));
			int y=dfs2(i)-1;//大于
			if(x>n/2||y>n/2) printf("0");
			else printf("1");
		}
		printf("\n");
	}
	return 0;
}
/*4321
10 8
1 2
2 5
4 6
3 7
8 9
2 9
3 4
5 8*/

L Tokens on the Segments
山东省第十届ACM浪潮杯补题
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4120
赛场上的时候看出是贪心来了，按着左端点，右端点，区间长度都排序来找，但是一直wa，后来队友写了一发暴力，还是wa，嘤嘤嘤。后来知道用优先队列去贪心，想了想确实比单一的排一次序好得多。菜的想哭。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;

const int maxx=1e5+100;
struct node{
	ll l,r;
	node(ll a=0,ll b=0)
	{
		l=a;
		r=b;
	}
	bool operator < (const node &a)const
	{
		if(l!=a.l) return l>a.l;
		else return r>a.r;
	}
};
int n;

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		ll l,r;
		priority_queue<node> p; 
		for(int i=0;i<n;i++)
		{
			scanf("%lld%lld",&l,&r);
			p.push(node(l,r));
		}
		ll maxn=-1;
		ll ans=0;
		while(!p.empty())
		{
			node a;
			a=p.top();
			p.pop();
			if(a.l<=maxn&&a.l+1<=a.r) 
			{
				p.push(node(a.l+1,a.r));
				continue;
			}
			if(a.l>maxn)
			{
				ans++;
				maxn=max(maxn,a.l);
			}
		}
		printf("%lld\n",ans);
	}
}

后面还有蓝桥和南昌邀请赛。愿不忘初心，方得始终。加油！！！
努力加油a啊，(^o)/~

山东省第十届ACM浪潮杯补题

相关推荐