6
22
2015
5

NOIP2014 提高组

D1

T1

水题一道。。随便搞搞

#include <cstdio>

using namespace std;

int G(int n,int m)
{
	if(n==m)return 0;
	if(n<m)return -G(m,n);
	switch(n)
	{
		case 1:
			return 1;
			break;
		case 2:
			if(m==0)return -1;
			if(m==1)return 1;
			break;
		case 3:
			switch(m)
			{
				case 0:
					return -1;
					break;
				case 1:
					return -1;
					break;
				case 2:
					return 1;
					break;
			}
			break;
		case 4:
			switch(m)
			{
				case 0:
					return 1;
					break;
				case 1:
					return 1;
					break;
				case 2:
					return -1;
					break;
				case 3:
					return -1;
					break;
			}
			break;
	}
}

int n,na,nb;
int a[210],b[210];
int num1=0,num2=0;

int main()
{
	scanf("%d%d%d",&n,&na,&nb);
	for(int i=0;i<na;++i)scanf("%d",a+i);
	for(int i=0;i<nb;++i)scanf("%d",b+i);
	for(int i=0;i<n;++i)
		{
			if(G(a[i%na],b[i%nb])==1)++num1;
			if(G(a[i%na],b[i%nb])==-1)++num2;
		}
	printf("%d %d\n",num1,num2);
	return 0;
}

T2

至于这题嘛。。。其实呢。。就是把每个节点作为一个奇妙的根节点找他子节点的子节点。
如果这样的话呢。。。可能会出一点小意外。。。
但是我们不怕!!!
我们用O(n)处理下,把每个节点相连的所有节点的值都加起来记录一下
然后呢= =|就可以懒懒的遍历一遍了。。

 

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

struct node
{
	int x,y;
};

struct node2
{
	int num,max1,max2;
};

int n,i,tot=0,maxx=0;
node rd[400010];
node2 num[200010];
int a[200010];

bool cmp(node xx,node yy)
{
	return(xx.x<yy.x);
}

int Max(int x,int y)
{
	if(x>y)return x;
	else return y;
}

int main()
{
	scanf("%d",&n);
	for(i=0;i<n-1;++i)scanf("%d%d",&rd[i].x,&rd[i].y);
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	for(i=0;i<n-1;++i)
	{
		num[rd[i].x].num+=a[rd[i].y];
		num[rd[i].y].num+=a[rd[i].x];
		num[rd[i].x].num%=10007;
		num[rd[i].y].num%=10007;
		
		num[rd[i].x].max2=Max(num[rd[i].x].max2,a[rd[i].y]);
		if(num[rd[i].x].max2>num[rd[i].x].max1)swap(num[rd[i].x].max2,num[rd[i].x].max1);
		num[rd[i].y].max2=Max(num[rd[i].y].max2,a[rd[i].x]);
		if(num[rd[i].y].max2>num[rd[i].y].max1)swap(num[rd[i].y].max2,num[rd[i].y].max1);
	}
	for(i=0;i<n-1;++i)
	{
		tot+=a[rd[i].x]*(num[rd[i].y].num-a[rd[i].x])+a[rd[i].y]*(num[rd[i].x].num-a[rd[i].y]);
		tot%=10007;
		int c;
		c=a[rd[i].x]%10007;
		if(num[rd[i].y].max1!=a[rd[i].x])maxx=Max(c*num[rd[i].y].max1,maxx);
			else maxx=Max(c*num[rd[i].y].max2,maxx);
		c=a[rd[i].y]%10007;
		if(num[rd[i].x].max1!=a[rd[i].y])maxx=Max(c*num[rd[i].x].max1,maxx);
			else maxx=Max(c*num[rd[i].x].max2,maxx);
	}
	printf("%d %d\n",maxx,tot);
	return 0;
}

这题CCF的数据太差了。。因为在之前%之后数字会变小,可能使做减法的时候出现负数就会被鏼掉


#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
struct node
{
    int x,y;
};
 
struct node2
{
    int num,max1,max2;
};
 
int n,i,tot=0,maxx=0;
node rd[400010];
node2 num[200010];
int a[200010];
 
bool cmp(node xx,node yy)
{
    return(xx.x<yy.x);
}
 
int Max(int x,int y)
{
    if(x>y)return x;
    else return y;
}
 
int OK(int num)
{
	while(num<0)num+=10007;
	return num%10007;
}
 
int main()
{
    scanf("%d",&n);
    for(i=0;i<n-1;++i)scanf("%d%d",&rd[i].x,&rd[i].y);
    for(i=1;i<=n;++i)scanf("%d",&a[i]);
    for(i=0;i<n-1;++i)
    {
        num[rd[i].x].num+=a[rd[i].y];
        num[rd[i].y].num+=a[rd[i].x];
        num[rd[i].x].num%=10007;
        num[rd[i].y].num%=10007;
         
        num[rd[i].x].max2=Max(num[rd[i].x].max2,a[rd[i].y]);
        if(num[rd[i].x].max2>num[rd[i].x].max1)swap(num[rd[i].x].max2,num[rd[i].x].max1);
        num[rd[i].y].max2=Max(num[rd[i].y].max2,a[rd[i].x]);
        if(num[rd[i].y].max2>num[rd[i].y].max1)swap(num[rd[i].y].max2,num[rd[i].y].max1);
    }
    for(i=0;i<n-1;++i)
    {
        tot+=a[rd[i].x]*OK(num[rd[i].y].num-a[rd[i].x])+a[rd[i].y]*OK(num[rd[i].x].num-a[rd[i].y]);
        tot%=10007;
        int c;
        c=a[rd[i].x]%10007;
        if(num[rd[i].y].max1!=a[rd[i].x])maxx=Max(c*num[rd[i].y].max1,maxx);
            else maxx=Max(c*num[rd[i].y].max2,maxx);
        c=a[rd[i].y]%10007;
        if(num[rd[i].x].max1!=a[rd[i].y])maxx=Max(c*num[rd[i].x].max1,maxx);
            else maxx=Max(c*num[rd[i].x].max2,maxx);
    }
    printf("%d %d\n",maxx,tot);
    return 0;
}

T3

当年扔的55分代码QAQ。。后来发现。。太™简单了。。QAQ。。还这么短

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

struct node
{
	int u,d;
};

struct node2
{
	int p,l,h;
};

int n,m,k,i,j,f;
node mv[10010];
node2 g[10010];
int dp[10010][1010];

int Max(int xx,int yy)
{
	if(xx>yy)return xx;
	return yy;
}

int Min(int xx,int yy)
{
	if(xx<yy)return xx;
	return yy;
}

bool cmp(node2 xx,node2 yy)
{
	return xx.p<yy.p;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=n;++i)scanf("%d%d",&mv[i].u,&mv[i].d);
	for(i=0;i<k;++i)scanf("%d%d%d",&g[i].p,&g[i].l,&g[i].h);
	memset(dp,0,sizeof(dp));
	for(i=1;i<=m;++i)dp[0][i]=1;
	sort(g,g+k,cmp);
	f=0;
	int s=1,ss,e=m,ee;
	for(i=1;i<=n;++i)
	{
		ss=m+1; ee=0;
		if(g[f].p==i)
		{
			for(j=Max(g[f].l,s+mv[i].u);j<g[f].h;++j)
				if(dp[i-1][j-mv[i].u])
				{
					ss=Min(ss,j); ee=Max(ee,j);
					dp[i][j]=dp[i-1][j-mv[i].u]+1;
				}
			for(j=Max(g[f].l,ss+mv[i].u);j<g[f].h;++j)
				if(dp[i][j-mv[i].u])
				{
					ss=Min(ss,j); ee=Max(ee,j);
					if(dp[i][j]!=0)
						dp[i][j]=Min(dp[i][j],dp[i][j-mv[i].u]+1);
					else dp[i][j]=dp[i][j-mv[i].u]+1;
				}
			for(j=g[f].l+1;j<min(g[f].h,e-mv[i].d+1);++j)
				if((j+mv[i].d<=m) && (dp[i-1][j+mv[i].d]))
				{
					ss=Min(ss,j); ee=Max(ee,j);
					if(dp[i][j]!=0)
						dp[i][j]=Min(dp[i][j],dp[i-1][j+mv[i].d]);
					else dp[i][j]=dp[i-1][j+mv[i].d];
				}
			if(ss==m+1 && ee==0)
			{
				printf("0\n%d\n",f);
				return 0;
			}
			++f;
		}
		else
		{
			for(j=s+mv[i].u;j<m;++j)
				if(dp[i-1][j-mv[i].u])
				{
					ss=Min(ss,j); ee=Max(ee,j);
					dp[i][j]=dp[i-1][j-mv[i].u]+1;
				}
			dp[i][m]=0x7fffffff;
			for(j=m-mv[i].u;j<=m;++j)
				if(dp[i-1][j])
				{
					ss=m; ee=m;
					if(dp[i][m]!=0)
						dp[i][m]=Min(dp[i][m],dp[i-1][j]+1);
					else dp[i][m]=dp[i-1][j]+1;
				}
			for(j=ss+mv[i].u;j<=g[f].h;++j)
				if(dp[i][j-mv[i].u])
				{
					ss=Min(ss,j); ee=Max(ee,j);
					if(dp[i][j]!=0)
						dp[i][j]=Min(dp[i][j],dp[i][j-mv[i].u]+1);
					else dp[i][j]=dp[i][j-mv[i].u]+1;
				}
			for(j=1;j<=e-mv[i].d;++j)
				if((j+mv[i].d<=m) && (dp[i-1][j+mv[i].d]))
				{
					ss=Min(ss,j); ee=Max(ee,j);
					if(dp[i][j]!=0)
						dp[i][j]=Min(dp[i][j],dp[i-1][j+mv[i].d]);
					else dp[i][j]=dp[i-1][j+mv[i].d];
				}
			if(ss==m+1 && ee==0)
			{
				printf("0\n%d\n",f);
				return 0;
			}
		}
		s=ss; e=ee;
	}
	int ans=0x7fffffff;
	for(i=1;i<=m;++i)
		if(dp[n][i])
			ans=Min(ans,dp[n][i]-1);
	printf("1\n%d\n",ans);
	return 0;
}
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

int n,m,k;
struct node{int u,d;}Cge[10010];
struct WALL{int p,l,g;}wall[10010];
int dp[10010][1010];
bool cmp(WALL xx,WALL yy){return xx.p<yy.p;}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;++i)scanf("%d%d",&Cge[i].u,&Cge[i].d);
	for(int i=1;i<=k;++i)scanf("%d%d%d",&wall[i].p,&wall[i].l,&wall[i].g);
	sort(wall+1,wall+1+k,cmp);
	int now=1;
	memset(dp,63,sizeof(dp)); memset(dp[0],0,sizeof(dp[0]));
	for(int i=1;i<=n;++i)
	{
		for(int j=Cge[i].u+1;j<m;++j)dp[i][j]=min(dp[i][j],min(dp[i][j-Cge[i].u]+1,dp[i-1][j-Cge[i].u]+1));
		for(int j=max(1,m-Cge[i].u);j<=m;++j)dp[i][m]=min(dp[i][m],min(dp[i][j]+1,dp[i-1][j]+1));
		for(int j=m-Cge[i].d;j>=1;--j)dp[i][j]=min(dp[i][j],dp[i-1][j+Cge[i].d]);
		if(wall[now].p==i)
		{
			for(int j=0;j<=wall[now].l;++j)dp[i][j]=dp[10001][1001];
			for(int j=wall[now].g;j<=m;++j)dp[i][j]=dp[10001][1001];
			bool f=true;
			for(int j=1;j<=m;++j)if(dp[i][j]<dp[10001][1001]){f=false;break;}
			if(f){printf("0\n%d\n",now-1);return 0;};
			++now;
		}
	}
	int ans=dp[10001][1001];
	for(int i=1;i<=m;++i)ans=min(dp[n][i],ans);
	if(ans==dp[10001][1001])printf("0\n%d\n",k);else printf("1\n%d\n",ans);
	return 0;
}

D2

T1

当时有点怕CCF评测机速率。。于是有点小优化
就是把方格左上角到[x,y]中所有值记录一下。然后轻松算出任意矩形的内部的所有值的和。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>

using namespace std;

int x,y,k;

int d,n;
int map[200][200];
int Max=0,tot=0,num;

int main()
{
	memset(map,0,sizeof(map));
	scanf("%d%d",&d,&n);
	for(int i=0;i<n;++i)
	{
		scanf("%d%d%d",&x,&y,&k);
		map[x+1][y+1]=k;
	}

	for(int i=1;i<=129;++i)
		for(int j=1;j<=129;++j)
			map[i][j]+=map[i-1][j]+map[i][j-1]-map[i-1][j-1];
	for(int i=1;i<=129;++i)
		for(int j=1;j<=129;++j)
		{
			int xx=i-d,yy=j-d,xxx=i+d,yyy=j+d;
			if(xx<1)xx=1; if(yy<1)yy=1;	if(xxx>129)xxx=129;	if(yyy>129)yyy=129;
			num=map[xxx][yyy]-map[xx-1][yyy]-map[xxx][yy-1]+map[xx-1][yy-1];
			if(num>Max)Max=num,tot=0;
			if(num==Max)++tot;
		}
	printf("%d %d\n",tot,Max);
	return 0;
}

 

 

Category: 比赛 | Tags: | Read Count: 511
Avatar_small
nbdhhzh 说:
2015年6月27日 22:11

55分不是30行以内轻松A吗

Avatar_small
hhw 说:
2015年8月07日 13:12

多半是老板娘大爷

Avatar_small
hhw 说:
2015年8月07日 13:12

@nbdhhzh: 多半是老板娘


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com