【NOIP2016 普及组题解分析总结】
莫名的呵呵，普及组考完了，就这么呵呵地考完了。。。心态放平静，肯定有人考的比你好，刚刚到洛谷去测了测点击打开链接（民间数据）惨淡的270 。。。。。啊啊啊啊啊shit来 开(xin) 心(hui) 快(yi) 乐(leng) 地分析一下吧
1.pencil
这道。。史无前例的water啊，小学生都能AC吧。。只不过判断一下整除啊，注意它是只买一种包装，3个价格乘以件数后取最小就可以了，记得赋初值什么的不知道为什么最近特别喜欢打句号啊。。。
-
#include<cstdio>
-
int min(int a,int b){return a<b?a:b;}
-
int main()
-
{
-
int n,a,b,s=100000001;
-
scanf(“%d”,&n);
-
for(int i=1;i<=3;i++)
-
{
-
scanf(“%d%d”,&a,&b);
-
if(n%a==0) b=n/a*b;
-
else b=(n/a+1)*b;
-
s=min(s,b);
-
}
-
printf(“%d”,s);
-
fclose(stdin);
-
fclose(stdout);
-
return 0;
-
}
2.date
。。。坑特别多啊，不得不说这道题真的很猥琐啊，不过还好我AC了~
我的策略就是把处在输入中间的那些年份枚举，一年一年加，然后判断由前四位数生成的这个回文日期是否合法，不过要特殊判断第一年和最后一年是否在给定范围内，注意闰年~
-
#include<cstdio>
-
const int t[14]={-4,31,28,31,30,31,30,31,31,30,31,30,31};
-
char n[15],m[15];
-
int a,b,s,c,q,w;
-
int xmy(int x)
-
{
-
int c=0,r=x;
-
for(int i=1;i<=4;x/=10,i++)
-
c=c*10+x%10;
-
if(c/100>12) return 0;
-
int o=t[c/100];
-
if(((r%4==0&&r%100!=0)||(r%400==0))&&c/100==2) o++;
-
if(c%100>o) return 0;
-
return 1;
-
}
-
bool xmy1(int x)
-
{
-
c=0;
-
int r=x;
-
for(int i=1;i<=4;x/=10,i++)
-
c=c*10+x%10;
-
if(c/100>12) return 0;
-
int o=t[c/100];
-
if(((r%4==0&&r%100!=0)||(r%400==0))&&c/100==2) o++;
-
if(c%100>o) return 0;
-
return 1;
-
}
-
int main()
-
{
-
scanf(“%s%s”,n,m);
-
for(int i=0;i<4;i++)
-
a=a*10+n[i]-’0′,b=b*10+m[i]-’0′;
-
for(int i=4;i<8;i++)
-
q=q*10+n[i]-’0′,w=w*10+m[i]-’0′;
-
for(int i=1;a+i<b;i++)
-
s+=xmy(a+i);
-
if(a==b)
-
{
-
if(xmy1(a)&&q<=c&&c<=w) s++;
-
}
-
else
-
{
-
if(xmy1(a)&&q<=c) s++;
-
if(xmy1(b)&&c<=w) s++;
-
}
-
printf(“%d”,s);
-
return 0;
-
}
3.port
我表示呵呵，这空间。。这时间。。嗯。。好，果断选择了70%，想了想，用数组的话肯定要炸，开100000的话直接0分，所以。。还是用队列吧，把每一艘船都push进去，如果和队首相差一天就把队首pop掉，再把vis[那艘船上的人的国籍]–；
-
int vis[100005];
-
struct node
-
{
-
int t,k,r[100005];
-
}h;
-
queue<node>a;
定义差不多就这样。。其实70分也挺水的。主要是后面超时。。可能也会爆空间
来继续分析正解吧，仔细审题，查找蹊跷之处，为什么题目只给出了k的总和的范围而没有说单个的k的范围？
是否有种算法只与K有关？so,看一看，k是指人的总数，那么，我们用队列存人怎么样？不用存船，把每个人的国籍和时间存进去就好了啊，而且时间复杂度不高，思路其实差不多，空间也最多600000。
实现比较简单，就是push(每个人)就可以了，上代码吧。
-
#include<cstdio>
-
#include<queue>
-
using namespace std;
-
int n,x,y,s,o;
-
int vis[100005];
-
struct node
-
{
-
int t,r;
-
}h,u;
-
queue<node>a;
-
int main()
-
{
-
scanf(“%d”,&n);
-
for(int i=1;i<=n;i++)
-
{
-
scanf(“%d%d”,&o,&y);
-
for(int j=1;j<=y;j++)
-
{
-
scanf(“%d”,&h.r);
-
h.t=o;
-
a.push(h);
-
if(!vis[h.r]) s++;
-
vis[h.r]++;
-
}
-
while(1)
-
{
-
u=a.front();
-
if(h.t-86400>=u.t)
-
{
-
vis[u.r]–;
-
if(!vis[u.r]) s–;
-
a.pop();
-
}
-
else break;
-
}
-
printf(“%d\n”,s);
-
}
-
fclose(stdin);
-
fclose(stdout);
-
return 0;
-
}
4.magic
我跪了。。。啊啊啊啊啊0分。。。看到分数我就懵逼了，我知道递归肯定超时，但不至于一分不得吧！后来。。我发现。。我就sort了一下就傻逼的忘了判断大小。神呐！！！让我加一个if吧！！！
唉~不要抱怨，总结一下吧，还是too young too simple，以为sort一下就不用管那个大于符号了，严格不等号啊，等于的情况没判断啊。。45分没了。。还是细节啊，题目一定要读透，把每个条件罗列在纸上，确保每一步都毫无遗漏的完成，才不留遗憾啊。做题，一定要稳！
现在来找找AC方式，首先，剖析题目，列出条件：Xa<Xb<Xc<Xd，Xb-Xa=2(Xd-Xc)，Xb-Xa<Xc-Xb/3
遇到这种有条件的题，通常把图形画出来比较直观。
如图所示，若把d点确定，设c-d距离为i，则a,b的距离就是2i，则b,c的距离>2*(a-b)也就是>6i，总距离大于9i，那么我们的外层循环就枚举i，再枚举d的位置，d的方案数就等于(前面所有a的方案)*(前面所有b的方案)*(当前c的方案数)，c的方案数=(前面所有a的方案)*(前面所有b的方案)*(当前d的方案数)，同理，枚举a的位置，也可以得到a与b的方案数。
当然，说了这么多估计你也可能是懵逼的，看看代码再结合一下分析吧。
先看看pascal
-
var
-
a,b,c,d,w:array[0..15005]of longint;//a,b,c,d，a[i]表示以魔法值i作为魔法阵中a元素的总方案数
-
i,j,n,m,x,y:longint;//定义变量
-
begin
-
readln(n,m);//读入n,m
-
for i:=1 to m do//begin,end相当于c++的{}
-
begin
-
read(h[i]);
-
inc(w[h[i]]);//w[h[i]]++;表示这个值的数增加了一个
-
end;
-
for i:=1 to n div 9 do//n div 9 == n/9（除数为整数）
-
begin
-
x:=1+9*i; y:=0;
-
for j:=2+9*i to n do//j->d
-
begin
-
y:=y+w[(j-x)]*w[j-x+i+i];//w[j-x]:魔法阵为a元素的个数，w[j-x+2*i]：b元素的个数，
-
//因为是至少为9*i+1，所以在枚举后面的d时，要将前面的所有a,b的情况累加起来
-
d[j]:=d[j]+y*w[j-i];//a*b*c==d
-
c[j-i]:=c[j-i]+y*w[j];//a*b*d==c,因为c与d的距离固定为i，所以确定d就可以确定c
-
end;
-
x:=8*i+1; y:=0;
-
for j:=n-9*i-1 downto 1 do//j->a
-
begin
-
y:=y+w[j+x]*w[j+x+i];//w[j+x]：魔法阵为c元素的个数，w[j+x+i]:d元素的个数
-
a[j]:=a[j]+y*w[j+i+i];//同理
-
b[j+i+i]:=b[j+i+i]+y*w[j];
-
end;
-
end;//上下两循环可以调换顺序，因为a,b,c,d只与i和w有关，和a[],b[],c[],d[]无关
-
for i:=1 to m do writeln(a[h[i]],’ ‘,b[h[i]],’ ‘,c[h[i]],’ ‘,d[h[i]]);//a[h[i]]:以物品一的魔法值作为法阵a元素的总方案数
-
close(input);close(output);
-
end.
pascal语言可能看不懂，看看我写的C++吧(分析自己看上面)
-
#include<cstdio>
-
#define M 15005
-
int a[M],b[M],c[M],d[M],w[3*M],h[3*M];
-
int n,m,i,j,x,s;//s就是上面的y，累加和
-
int main()
-
{
-
scanf(“%d%d”,&n,&m);
-
for(i=1;i<=m;i++)
-
{
-
scanf(“%d”,&h[i]);
-
w[h[i]]++;
-
}
-
for(i=1;9*i<n;i++)//注意是总长度>9*i，边界一定要考虑无误，想通为什么
-
{
-
x=9*i+1;s=0;//设边界最好画个草图自己算一算
-
for(j=9*i+2;j<=n;j++)
-
{
-
s+=w[j-x]*w[j-x+2*i];
-
d[j]+=s*w[j-i];
-
c[j-i]+=s*w[j];
-
}
-
s=0;
-
for(j=n-x;j>=1;j–)//注意循环不能顺序，因为s的累加和会改变,a[j]会加上后面的c,d，而不是前面的
-
{
-
s+=w[j+x]*w[j+x-i];
-
a[j]+=s*w[j+2*i];
-
b[j+2*i]+=s*w[j];
-
}
-
}
-
for(i=1;i<=m;i++)
-
printf(“%d %d %d %d\n”,a[h[i]],b[h[i]],c[h[i]],d[h[i]]);
-
}
奋斗，拼搏！