NOIP【2016普及组】 考后有感(买铅笔,回文日期,海港,魔法阵)

普及组考试已落下大幕,但我们那扑通扑通等待成绩的心仍然无法平静,先来给四道题做一个总结:


一、 买铅笔

自评难度:1星

其实这道题没有什么难度,生命之题,满分必拿,100分,保底啦~(≧▽≦)/~


二、回文日期

自评难度:2星

我枚举两个年份之间的年份,再判断齐回文是否合法,再判断起点年和终点年的日期是否在范围之内


三、海港

自评难度:4星

这道题首先使用的队列存储船,结果内存超限╮(╯▽╰)╭,但愿竞赛数据很温柔~~


正规数据欺我老无力,忍能对面能坑分,公然坑分入竹去,唇焦舌燥呼不得,归来倚仗自叹息。

俄顷风定云墨色,秋天漠漠向昏黑,骗分多年早无用,竞赛恶坑踏里裂

安得分数超级高,大庇天下考生俱欢颜,风雨不动安如山。呜呼——何时眼前突兀见此分,吾独骗分不成死亦足!

————改自杜甫《茅屋为秋风所破歌》



后来则变成了用队列存储每个人,很好,分数提高,变成时间超限了~~

最后,我舍去循环,在每行数据输入时,就用 if 语句判断国家数,终于,在山寨数据下AC了

代码如下:

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
struct ill{
	int con,t;
}now,per;
queue<ill>a;
int v[100005];
int n,k,s;
void work()
{
	now=a.front();
	while(now.t<=per.t-86400)
	{
		a.pop();
		v[now.con]--;
		if(!v[now.con])s--;
		now=a.front();
	}
	printf("%d
",s);
}
void scan()
{
	int i,nn,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&per.t,&nn);
		for(j=1;j<=nn;j++)
		{
			scanf("%d",&per.con);
			a.push(per);
			v[per.con]++;
			k=max(k,per.con);
			if(v[per.con]==1)
				s++;
		}
		work();
	}
}
int main()
{
	scan();
}

╮(╯▽╰)╭,不容易呀


四、魔法阵

自评难度:5星

作为正规考试的最后一题,总是将所谓的此题的致命弱点暴露在外,一打开,里面则是一个血量巨高,双抗爆表,还带红蓝BUFF,没个满级神器打都打不动的BOSS,诶,没办法,跪了/(ㄒoㄒ)/~~


不过,即使无法就地斩杀,也要撕他几块肉下来,抱着这样的决心,我写出了暴力枚举程序,渴望能骗点分~~~

后来,看了大牛的代码,加上老师的讲解,软磨硬泡,终于解决了这个BOSS

其思想也在枚举,但过程大大加速:

我们可以将四个法球的公式,如下展现:


当 i 为正整数时,这几个点就可以满足所有条件

我们先将魔法值为 i 的法球,加入h[ i ]中,数组 h 表示魔法值为 i 的法球有多少个

这下子,只要枚举 i,在枚举 a 和 d 的位置,就可以确定 b 和 c 的位置

最后在再判断h[ a ],h[ b ],h[ c ],h[ d ]中有几个法球,相应处理就行了


代码如下:

#include<cstdio>
int a[15005],b[15005],c[15005],d[15005];
int h[45005],w[15005];
int n,m,x,y;
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&h[i]);
        w[h[i]]++;
    }
    for(i=1;i<=n/9;i++)
    {
        x=9*i+1;y=0;
        for(j=x+1;j<=n;j++)
        {
            y+=w[j-x]*w[j-x+i+i];
            d[j]+=y*w[j-i];
            c[j-i]+=y*w[j];
        }
        x=8*i+1;y=0;
        for(j=n-9*i-1;j>0;j--)
        {
            y+=w[j+x]*w[j+x+i];
            a[j]+=y*w[j+i+i];
            b[j+i+i]+=y*w[j];
        }
    }
    for(i=1;i<=m;i++)
        printf("%d %d %d %d
",a[h[i]],b[h[i]],c[h[i]],d[h[i]]);
}
有些细节,自己考究吧~~毕竟自己研究出来的结果才是最好的


普及组虽然考完了,成绩并不好看,但我们并不会放弃,加油↖(^ω^)↗,向明年的提高组进军!!!

原文地址:https://www.cnblogs.com/Darknesses/p/12002559.html