小学五年级奥数染色问题？noip2008复答

本文目录

• 小学五年级奥数染色问题
• noip2008复答案
• 在n*n的方格中填入1*2的方块pascal，可以横着填，也可以竖着填，要求填满
• 染色赋值法是什么
• 拉姆齐(Ramsly)二染色定理是什么
• 二分图，完全图，树，连通图中一定可以进行黑白染色的有
• 单栈排序与双栈排序
• 证明 二分图的子图是二分图

小学五年级奥数染色问题

楼上的答案值得商榷。至少我没有看懂他在说什么。

这应该算是五年级的奥数里较难的题了。记得当初小学时，染色问题一直比较弱。现在依然如此，以至于这两题花了我较长的时间。

1、首先，说思路。既然题目已经告诉你要染色了，那其实就限制了思考范围，从而降低了难度。题目中最关键的是你要看见“往右”或“往上”本质是一样的，非常对称。但是“往左下”就不一样了。为什么这么说？因为考虑一下最普通的黑白相隔的染色方案，“往右”或“往上”都能保证每走一步会经过不同颜色的方格，但是“往左下”则保证每走这样一步都会经过相同颜色的方格。所以，他们是不同的。所以，从直觉上判断这里应该是本题的关键所在。

?

那么，怎么利用这一性质呢？其实问题没有那么复杂，所以不需要考虑太多的方法（我一开始就因为在几种不同的方案上徘徊导致了浪费时间）而只要直接考虑最普通的方案，即找一染色方案保证每走一步（不论是往右或往上或往左下）都会经过不同颜色的方格。

?

这样，目标其实很清楚了。我们需要三色去染这8*8的方格。如图。至于如何得到此图的染色过程其实不难，只要考虑对角线必须保证不同的颜色，然后又需要三色，这样依次“蓝黑白”地去染每条对角线，然后对于不同的对角线只需要保证相邻的对角线的染色正好错开了一格即可。

?

?

染色完成后，数一下。蓝色共22格，黑白各21格，出发点在黑格上。由于蓝色的比黑白两色的多出了1格，这就使我们联想到如果从左上角出发是否能完成遍历？稍作努力便容易知道，这的确可能。如图。这样就更明确了我们的方向，即玄机肯定在这蓝色比黑白两色多出1格的这特点上。

?

然后，就有这样的思考。出发点不算我们要经过63格，既然每步都会经过不同颜色的方格，而且从左上角的蓝色格出发正好经过了蓝黑白三色各21格（出发点的蓝色不算）正好能够走完，但是从左下角的黑色格出发会经过蓝22格，黑20格，白21格，而且是走不完的。那么这时自然地我们就会考虑如果能够保证“每三步”（任意的）正好经过了蓝黑白三色，那么的确从左下角出发是到达不了的，因为如果能保证“每三步”都经过了蓝黑白三色，那总共的63步就会保证经过蓝黑白三色各21次，但是显然从右下角出发经过的蓝黑数不同。矛盾。另一方面，从左上角的确保证了经过蓝黑白各21次，而且也的确能遍历。

?

所以，我们就想到是否能够保证“每三步”（任意的）正好经过了蓝黑白三色（顺序不一定）呢？答案是肯定的。原因从图上观察便知。要到达每一黑色格子唯一的方法是通过一白色的格子，而要到达任何的白色的格子只有通过蓝色的格子，而要到达蓝色的格子只有通过黑色的格子，这样循环。所以任何的三步都经过正好三色。从而63步经过三色各21次。与要经过蓝22格，黑20格，白21格矛盾，所以无法遍历。

noip2008复答案

1 word
这道题完全是送分题，只需要直接统计，再判断素数。
参考程序：
var
st:string;
max,min,i:longint;
a:arrayof longint;
ch:char;
function fun(n:longint):boolean;
var i:longint;
begin
if n《2 then begin fun:=false;exit;end;
for i:=2 to n-1 do
if n mod i=0 then begin fun:=false;exit;end;
fun:=true;
end;
begin
assign(input,’word.in’);
reset(input);
assign(output,’word.out’);
rewrite(output);
readln(st);
fillchar(a,sizeof(a),0);
for i:=1 to length(st) do
inc(a);
max:=0;
min:=101;
for ch:=’a’ to ’z’ do
if a》0 then
begin
if a;
if a;
end;
if fun(max-min) then
begin
writeln(’Lucky Word’);
writeln(max-min);
end
else
begin
writeln(’No Answer’);
writeln(0);
end;
close(input);
close(Output);
end.
2 matches
搜索题，由于输入的情况只有25种，所以打表也是一种可行的方法。在数据最大时，经过人工和电脑证明是不会到达四位数的，所以可以直接用O(1000*1000)的搜索算法
参考程序:
const
mat:arrayof longint=(6,2,5,5,4,5,6,3,7,6);
function fun(m:longint):longint;
var t:longint;
begin
t:=0;
while m》0 do
begin
inc(t,mat);
m:=m div 10;
end;
fun:=t;
end;
var a:array of longint;
n,i,j,ans:longint;
begin
assign(input,’matches.in’);
reset(input);
assign(output,’matches.out’);
rewrite(output);
readln(n);
if n《10 then begin writeln(0);close(output);exit;end;
a:=6;
for i:=1 to 1000 do
a:=fun(i);
dec(n,4);
for i:=0 to 1000 do
if a《n then
begin
for j:=0 to 1000-i do
if a=n then inc(ans);
end;
writeln(ans);
close(input);
close(output);
end.
3 message
DP题，两条路线必定一上一下，而且，当到达某一列后，前面对后面的不会有影响

扫码加微信详细咨询太和智慧养老产品和平台服务！

扫码加微信详细咨询太和智慧养老产品和平台服务！