6
22
2015
6

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: 932
Small_feed 评论 (6)
1
[回复]
Avatar_small
nbdhhzh 说:
2015年6月27日 22:11

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

3
[回复]
Avatar_small
hhw 说:
2015年8月07日 13:12

多半是老板娘大爷

4
[回复]
Avatar_small
hhw 说:
2015年8月07日 13:12

@nbdhhzh: 多半是老板娘

6
[回复]
Avatar_small
Grade 8 Result rajsh 说:
2022年8月28日 12:23

Bangladesh Education Board DPE has conducted the class 8th grade of Junior School Certificate Exam and Junior Dakhil Certificate Exam on 1st to 15th November 2022 at all centers in division wise under Ministry of Primary and Mass Education (MOPME), and the class 8th grade terminal examination tests are successfully conducted for all eligible JSC/JDC students for the academic year of 2022. Grade 8 Result rajshahi The Bangladesh government Minister of Secondary Education is going to announce the JSC Result 2022 in student wise for division students in education board wise, and the result documents will be submitted to the Prime Minister of the country after then the result with mark sheet will be announced to public to check the individual result.


登录 *


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