2016大连网络赛补题

#B Different GCD Subarray Query
现在已经口头AC了,我们就是区间不同颜色个数的升级版.我还需要处理一下…

#F Football Games
获得的分是一定的,然后判断一下不会超过最大值然后就可以了

#include <bits/stdc++.h>
using namespace std;
int a[50005];
int main()
{
	int t;
	while(~scanf("%d",&t))
	{
		while(t--)
		{
			int n,sum=0,f=0;
			scanf("%d",&n);
			for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
			for(int i=1;i<=n;i++)
			{
				sum+=a[i];
				if(a[i]>((n-1)*2))
				{
					f=1;
					break;
				}
			}
			if(sum!=(n*(n-1))||f)
			puts("F");
			else
			puts("T");
		}
	}
}

G Friends and Enemies

结论题，结论目前没有推….

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll x,y;
	while(~scanf("%lld%lld",&x,&y))
	{
		ll a=x/2,b=x-a;
		if(a*b<=y)
		puts("T");
		else
		puts("F");
	}
}

H Function

傻逼玩意暴力跑一遍一看数据就没有卡，就是一个随机数据，做法就是找出右边比他小的一个一个模就完事了我服了

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N],nex[N];

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
		nex[i]=n+1;
		for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		if(a[j]<=a[i])
		{
			nex[i]=j;
			break;
		}
		scanf("%d",&m);
		while(m--)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			int re=a[l];
			for(int i=nex[l];i<=r;i=nex[i])
			{
				if(a[i]==0)
				break;
				re%=a[i];
				if(re==0)
				break;
			}
			printf("%d\n",re);
		}
	}
}

I Sparse Graph

求补图最短路的好题.点多边少我们就bfs暴力找一波.但是也不是这么的暴力,维护两个set,如果原来没有边的话那么d[to]=d[p]+1,然后推入队列.

#include <bits/stdc++.h>
using namespace std;
const int N=200005;
struct edge
{
	int to,nex;
}E[N<<1];
int cnt,n,m,head[N],d[N];
void add(int x,int y)
{
	E[++cnt].to=y;E[cnt].nex=head[x];head[x]=cnt;
}
void bfs(int s)
{
	set<int> a,b;
	for(int i=1;i<=n;i++)
	if(i!=s)
	a.insert(i);
	memset(d,-1,sizeof(d));
	d[s]=0;
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		int p=q.front();
		q.pop();
		for(int i=head[p];i;i=E[i].nex)
		if(a.count(E[i].to))
		b.insert(E[i].to),a.erase(E[i].to);
		for(auto it=a.begin();it!=a.end();it++)
		d[*it]=d[p]+1,q.push(*it);
		a.swap(b);
		b.clear();
	}
	for(int i=1;i<=n;i++)
	if(i!=s)
	printf("%d%c",d[i],i==n?'\n':' ');
}
int main()
{
	int t;
	while(~scanf("%d",&t))
	{
		while(t--)
		{
			cnt=0;
			memset(head,-1,sizeof(head));
			int l,r,s;
			scanf("%d%d",&n,&m);
			while(m--)
			{
				scanf("%d%d",&l,&r);
				add(l,r);
				add(r,l);
			}
			scanf("%d",&s);
			bfs(s);
		}
	}
}

J-Weak Pair

也是够贱的这个还有0,就是我们dfs走的时候下面的完全可以直接查询上面的点,把ai*aj<=k转换一下成为ai<=k/aj所以直接查询k/aj就可以了.离散化的时候也得先把k/aj放进去要不会lower_bound出错,10/3=3直接lower_bound没有3的话会跑到前面去可能中间的点不记录了,其他的就是注意回溯的时候把相应的点删掉就行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
ll t[N],a[N],b[N],ans,head[N],n,k,jk,l,r,in[N],cnt;
struct edge
{
	ll nex,to;
}E[N<<1];
void insert(int x,int y)
{
	for(int i=x;i<=N;i+=i&(-i))
	t[i]+=y;
}
void add(ll x,ll y)
{
	E[++cnt].to=y;E[cnt].nex=head[x];head[x]=cnt;
}
ll sum(int x)
{
	ll ans=0;
	for(int i=x;i>0;i-=i&(-i))
	ans+=t[i];
	return ans;
}
void dfs(int p)
{
	ans+=sum(lower_bound(b+1,b+1+jk,k/a[p])-b);
	insert(lower_bound(b+1,b+1+jk,a[p])-b,1);
	for(int i=head[p];i!=-1;i=E[i].nex)
	dfs(E[i].to);
	insert(lower_bound(b+1,b+1+jk,a[p])-b,-1);
}
int main()
{
	ll tt;
	while(~scanf("%lld",&tt))
	{
		while(tt--)
		{
			jk=ans=cnt=0;
			memset(head,-1,sizeof(head));
			memset(in,0,sizeof(in));
			memset(t,0,sizeof(t));
			scanf("%lld%lld",&n,&k);
			for(int i=1;i<=n;i++)
			{
				scanf("%lld",&a[i]);
				b[++jk]=a[i];
				if(a[i])
				b[++jk]=k/a[i];
				else
				b[++jk]=n+1;
			}
			for(int i=1;i<n;i++)
			{
				scanf("%lld%lld",&l,&r);
				in[r]++;
				add(l,r);
			}
			sort(b+1,b+1+jk);
			jk=unique(b+1,b+1+jk)-b-1;
			for(int i=1;i<=n;i++)
			if(!in[i])
			{
				dfs(i);
				break;
			}
			printf("%lld\n",ans);
		}
	}
}