本文目录
- 小学五年级奥数染色问题
- 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题，两条路线必定一上一下，而且，当到达某一列后，前面对后面的不会有影响，符合动态规划的无后效性，方程如下：
用dp表示当到达I列时，上路线在j行到，下路线在k行到的最大值。
另外加一个预处理，sum表示在第I列j1到j2行的数加起来的和。
边界条件：
dp;
递推方程:
dp) {j《=j2《k《=k2}
答案：
max(dp)
参考程序：
const maxn=10;
var
a:arrayof longint;
dp,sum:arrayof longint;
n,m,i,j,k,i1,i2,j1,j2,k1,k2:longint;
function max(a,b:longint):longint;
begin
if a》b then max:=a else max:=b;
end;
begin
assign(input,’message.in’);
reset(input);
assign(output,’message.out’);
rewrite(output);
readln(m,n);
for i:=1 to m do
begin
for j:=1 to n do
read(a);
readln;
end;
for i:=1 to m do
begin
for i1:=1 to n do
begin
sum;
for i2:=i1+1 to n do
sum;
end;
end;
fillchar(dp,sizeof(dp),255);
for i:=2 to n do
dp;
for i:=2 to m-1 do
for j:=1 to n-1 do
for k:=j+1 to n do
if dp》-1 then
begin
for j2:=j to k-1 do
for k2:=k to n do
dp);
end;
k:=0;
for i:=1 to n-1 do
k:=max(k,dp);
writeln(k);
close(input);
close(output);
end.
4.twostack
这道题大概可以归结为如下题意:
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n《=1000),为1~n的某个排列.
现在支持如下四种操作:
a操作,将 q1的首元素提取出并加入s1的栈顶.
b操作,将s1的栈顶元素弹出并加入q1的队列尾.
c操作,将 q1的首元素提取出并加入s2的栈顶.
d操作,将s2的栈顶元素弹出并加入q1的队列尾.
请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.
这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法.
注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图.
第一步需要解决的问题是,判断是否有解.
考虑对于任意两个数q1.
首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证.
假设这两个数压入了同一个栈,那么在压入q1的时候栈内情况如下:
…q1…
因为q1没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了).
而之后,无论其它的数字在什么时候被弹出,q1,这显然是不正确的.
接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是“如果不满足条件p,那么这两个数一定可以压入同一个栈.“
不满足条件p有两种情况:一种是对于任意i《j《k且q1.
第一种情况下,很显然,在q1没有影响).
第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈.
这样,原命题的逆否命题得证,所以原命题得证.
此时,条件p为q1不能压入同一个栈的充要条件也得证.
这样,我们对所有的数对(i,j)满足1《=i《j《=n,检查是否存在i《j《k满足p1不能压入同一个栈.此时想到了什么?那就是二分图~
二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈中.
此时我们只考虑检查是否有解,所以只要o(n)检查出这个图是不是二分图,就可以得知是否有解.
此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解.
实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号小的结点优先压入s1.
又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1并从它开始dfs染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~
还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得p1就可以了.
附代码(除去注释不到100行),带注释.代码中的a数组对应文中的队列p1.
已经过掉所有标准数据,以及5 7 2 4 1 6 3这组让很多贪心程序挂掉的数据~
#include 《iostream》
using namespace std;
const int nn = 1002, mm = nn * 2, inf = 1000000000;
int n, tot, now;
int a;
int adj;
int stack;
bool result;
void addedge(int x, int y) //加边
{
++ tot;
adj = y;
next;
head = tot;
}
bool dfs(int i) //dfs染色,检查图是否是二分图的经典算法
{
int temp = head;
while (temp) //邻接表,检查每一条边
{
if (! color) //如果与当前结点的结点还未染色
{
color; //进行染色
dfs(adj); //dfs
}
if (color) return false;
//如果两个相邻结点染色相同,说明此图不是二分图,返回无解
temp = next;
}
return true;
}
int main()
{
freopen(“twostack.in“, “r“, stdin);
freopen(“twostack.out“, “w“, stdout);
//输入
scanf(“%d“, n);
for (int i = 1; i 《= n; ++ i) scanf(“%d“, a);
//预处理b数组
b = inf;
for (int i = n; i 》= 1; -- i) b); //“min“ in stl
//枚举数对(i,j)并加边
tot = 0;
for (int i = 1; i 《= n; ++ i)
for (int j = i + 1; j 《= n; ++ j)
if (b)
{
addedge(i, j);
addedge(j, i);
}
//dfs染色
memset(color, 0, sizeof(color));
result = true;
for (int i = 1; i 《= n; ++ i) //每次找当前未染色的编号最小的结点,并染颜色1
if (! color) //当前位置尚未被染色
{
color = 1;
if (! dfs(i)) //染色时出现矛盾,此时图不是一个二分图,即无法分配到两个栈中
{
result = false; //记录无解
break;
}
}
if (! result) //无解
printf(“0“);
else //有解
{
//模拟求解
now = 1;
for (int i = 1; i 《= n; ++ i)
{
//将当前数字压入对应的栈
if (color == 1)
printf(“a “);
else
printf(“c “);
stack ++;
stack = 0
//循环检查,如果可以的话就从栈顶弹出元素
while (stack == now)
{
if (stack == now)
{
printf(“b “);
stack --;
}
else if (stack == now)
{
printf(“d “);
stack --;
}
now ++;
}
}
}
}
在n*n的方格中填入1*2的方块pascal，可以横着填，也可以竖着填，要求填满
您求的是方案数还是最大能够填的方块数？
方案数：
状压DP：设f。通常都用的这个办法。即按行DP。预处理出所有j-》k的方案(可以通过搜索等方法)，然后直接转移。
最大能够填的方块数：
网络流：
设格子内某个点的坐标为(x,y)
从原点向所有(x+y)为奇数的点连一条容量为1的边。
从所有(x+y)为奇数的点向四周{(x-1,y),(x+1,y),(x,y-1),(x,y+1)}一条容量为1的边。
从所有(x+y)为偶数的点向汇点连一条容量为1的边。
然后跑网络流算法。最大流即为结果。
染色赋值法是什么
我也是在网上无意看到的，希望这些对你有用
第12讲 染色和赋值
染色方法和赋值方法是解答数学竞赛问题的两种常用的方法。就其本质而言，染色方法是一种对题目所研究的对象进行分类的一种形象化的方法。而凡是能用染色方法来解的题，一般地都可以用赋值方法来解，只需将染成某一种颜色的对象换成赋于其某一数值就行了。赋值方法的适用范围要更广泛一些，我们可将题目所研究的对象赋于适当的数值，然后利用这些数值的大小、正负、奇偶以及相互之间运算结果等来进行推证。
一、染色法
将问题中的对象适当进行染色，有利于我们观察、分析对象之间的关系。像国际象棋的棋盘那样，我们可以把被研究的对象染上不同的颜色，许多隐藏的关系会变得明朗，再通过对染色图形的处理达到对原问题的解决，这种解题方法称为染色法。常见的染色方式有：点染色、线段染色、小方格染色和对区域染色。
例1 用15个“T”字形纸片和1个“田”字形纸片（如下图所示），能否覆盖一个8×8的棋盘？
解：如下图，将 8×8的棋盘染成黑白相间的形状。如果15个“T”字形纸片和1个“田”字形纸片能够覆盖一个8×8的棋盘，那么它们覆盖住的白格数和黑格数都应该是32个，但是每个“T”字形纸片只能覆盖1个或3个白格，而1和3都是奇数，因此15个“T”字形纸片覆盖的白格数是一个奇数；又每个“田”字形纸片一定覆盖2个白格，从而15个“T”字形纸片与1个“田”字形纸片所覆盖的白格数是奇数，这与32是偶数矛盾，因此，用它们不能覆盖整个棋盘。
例2 如左下图，把正方体分割成27个相等的小正方体，在中心的那个小正方体中有一只甲虫，甲虫能从每个小正方体走到与这个正方体相邻的6个小正方体中的任何一个中去。如果要求甲虫只能走到每个小正方体一次，那么甲虫能走遍所有的正方体吗？
解：甲虫不能走遍所有的正方体。我们如右上图将正方体分割成27个小正方体，涂上黑白相间的两种颜色，使得中心的小正方体染成白色，再使两个相邻的小正方体染上不同的颜色。显然，在27个小正方体中，14个是黑的，13个是白的。甲虫从中间的白色小正方体出发，每走一步，方格就改变一种颜色。故它走27步，应该经过14个白色的小正方体、13个黑色的小正方体。因此在27步中至少有一个小正方体，甲虫进去过两次。由此可见，如果要求甲虫到每一个小正方体只去一次，那么甲虫不能走遍所有的小正方体。
例3 8×8的国际象棋棋盘能不能被剪成7个2×2的正方形和9个4×1的长方形？如果可以，请给出一种剪法；如果不行，请说明理由。
解：如下图，对8×8的棋盘染色，则每一个4×1的长方形能盖住2白2黑小方格，每一个2×2的正方形能盖住1白3黑或3白1黑小方格。推知7个正方形盖住的黑格总数是一个奇数，但图中的黑格数为32，是一个偶数，故这种剪法是不存在的。
例4 在平面上有一个27×27的方格棋盘，在棋盘的正中间摆好81枚棋子，它们被摆成一个9×9的正方形。按下面的规则进行游戏：每一枚棋子都可沿水平方向或竖直方向越过相邻的棋子，放进紧挨着这枚棋子的空格中，并把越过的这枚棋子取出来。问：是否存在一种走法，使棋盘上最后恰好剩下一枚棋子？
解：如下图，将整个棋盘的每一格都分别染上红、白、黑三种颜色，这种染色方式将棋盘按颜色分成了三个部分。按照游戏规则，每走一步，有两部分中的棋子数各减少了一个，而第三部分的棋子数增加了一个。这表明每走一步，每个部分的棋子数的奇偶性都要改变。
因为一开始时，81个棋子摆成一个9×9的正方形，显然三个部分的棋子数是相同的，故每走一步，三部分中的棋子数的奇偶性是一致的。
如果在走了若干步以后，棋盘上恰好剩下一枚棋子，则两部分上的棋子数为偶数，而另一部分的棋子数为奇数，这种结局是不可能的，即不存在一种走法，使棋盘上最后恰好剩下一枚棋子。
例5 图1是由数字0，1交替构成的，图2是由图1中任选 减1，如此反复多次形成的。问：图2中的A格上的数字是多少？
解：如左下图所示，将8×8方格黑白交替地染色。
此题允许右上图所示的6个操作，这6个操作无论实行在哪个位置上，白格中的数字之和减去黑格中的数字之和总是常数。所以图1中白格中的数字之和减去黑格中的数字之和，与图2中白格中的数字之和减去黑格中的数字之和相等，都等于32，由（31＋A）-32=32，得出A=33。
例6 有一批商品，每件都是长方体形状，尺寸是1×2×4。现在有一批现成的木箱，内空尺寸是6×6×6。问：能不能用这些商品将木箱填满？
解：我们用染色法来解决这个问题。先将6×6×6的木箱分成216个小正方体，这216个小正方体，可以组成27个棱长为2的正方体。我们将这些棱长为2的正方体按黑白相间涂上颜色（如下图）。
容易计算出，有14个黑色的，有13个白色的。现在将商品放入木箱内，不管怎么放，每件商品要占据8个棱长为1的小正方体的空间，而且其中黑、白色的必须各占据4个。现在白色的小正方体共有8×13=104（个），再配上104个黑色的小正方体，一共可以放26件商品，这时木箱余下的是8个黑色小正方体所占据的空间。这8个黑色的小正方体的体积虽然与一件商品的体积相等，但是容不下这件商品。因此不能用这些商品刚好填满。
例7 6个人参加一个集会，每两个人或者互相认识或者互相不认识。证明：存在两个“三人组”，在每一个“三人组”中的三个人，或者互相认识，或者互相不认识（这两个“三人组”可以有公共成员）。
证明：将每个人用一个点表示，如果两人认识就在相应的两个点之间连一条红色线段，否则就连一条蓝色线段。本题即是要证明在所得的图中存在两个同色的三角形。
设这六个点为A，B，C，D，E，F。我们先证明存在一个同色的三角形：
考虑由A点引出的五条线段AB，AC，AD，AE，AF，其中必然有三条被染成了相同的颜色，不妨设AB，AC，AD同为红色。再考虑△BCD的三边：若其中有一条是红色，则存在一个红色三角形；若这三条都不是红色，则存在一个蓝色三角形。
下面再来证明有两个同色三角形：不妨设△ABC的三条边都是红色的。若△DEF也是三边同为红色的，则显然就有两个同色三角形；若△DEF三边中有一条边为蓝色，设其为DE，再考虑DA，DB，DC三条线段：若其中有两条为红色，则显然有一个红色三角形；若其中有两条是蓝色的，则设其为DA，DB。此时在EA，EB中若有一边为蓝色，则存在一个蓝色三角形；而若两边都是红色，则又存在一个红色三角形。
故不论如何涂色，总可以找到两个同色的三角形。
二、赋值法
将问题中的某些对象用适当的数表示之后，再进行运算、推理、解题的方法叫做赋值法。许多组合问题和非传统的数论问题常用此法求解。常见的赋值方式有：对点赋值、对线段赋值、对区域赋值及对其他对象赋值。
例8 一群旅游者，从A村走到B村，路线如下图所示。怎样走才能在最短时间内到达B村？图中的数字表示走这一段路程需要的时间（单位：分）。
解：我们先把从A村到各村的最短时间标注在各村的旁边，从左到右，一一标注，如下图所示。
由此不难看出，按图中的粗黑线走就能在最短时间（60分钟）内从A村走到B村。
例9 把下图中的圆圈任意涂上红色或蓝色。问：有无可能使得在同一条直线上的红圈数都是奇数？请说明理由。
解：假设题中所设想的染色方案能够实现，那么每条直线上代表各点的数字之和便应都是奇数。一共有五条直线，把这五条直线上代表各点的数字之和的这五个奇数再加起来，得到的总和数仍应是一个奇数。但是，由观察可见，图中每个点都恰好同时位于两条直线上，在求上述总和数时，代表各点的数字都恰被加过两次，所以这个总和应是一个偶数。这就导致矛盾，说明假设不成立，染色方案不能实现。
例10 平面上n（n≥2）个点A1，A2，…，An顺次排在同一条直线上，每点涂上黑白两色中的某一种颜色。已知A1和An涂上的颜色不同。证明：相邻两点间连接的线段中，其两端点不同色的线段的条数必为奇数。
证明：赋予黑点以整数值1，白点以整数值2，点Ai以整数
值为ai，当Ai为黑点时，ai=1，当Ai为白点时，ai=2。再赋予线段AiAi+1以整数值ai+ai+1，则两端同色的线段具有的整数值为2或4，两端异色的线段具有的整数值为3。
所有线段对应的整数值的总和为
（a1＋a2）＋（a2＋a3）＋（a3＋a4）＋…＋（an-1＋an）
＝a1＋an＋2（a2＋a3＋…＋an-1）
＝2＋1＋2（a2＋a3＋…＋an-1）＝奇数。
设具有整数值2，3，4的线段的条数依次为l，m，n，则
2l＋m＋4n=奇数。
由上式推知，m必为奇数，证明完毕。
例11 下面的表1是一个电子显示盘，每一次操作可以使某一行四个字母同时改变，或者使某一列四个字母同时改变。改变的规则是按照英文字母的顺序，每个英文字母变成它的下一个字母（即A变成B，B变成C……Z变成A）。问：能否经过若干次操作，使表1变为表2？如果能，请写出变化过程，如果不能，请说明理由。
S O B R K B D S
T Z F P H E X G
H O C N R T B S
A D V X C F Y A
表1 表2
解：不能。将表中的英文字母分别用它们在字母表中的序号代替（即A用1，B用2……Z用26代替）。这样表1和表2就分别变成了表3和表4。
每一次操作中字母的置换相当于下面的置换：
1→2，2→3，…，25→26，26→1。
19 15 2 18
20 26 6 16
8 15 3 14
1 4 22 24
表3
11 2 4 19
8 5 24 7
18 20 2 19
3 6 25 1
表4
容易看出，每次操作使四个数字改变了奇偶性，而16个数字的和的奇偶性没有改变。因为表3中16个数字的和为213，表4中16个数字的和为174，它们的奇偶性不同，所以表3不能变成表4，即表1不能变成表2。
例12 如图（1）～（6）所示的六种图形拼成右下图，如果图（1）必须放在右下图的中间一列，应如何拼？
解：把右上图黑、白相间染色（见上图）。其中有11个白格和10个黑格，当图形拼成后，图形（2）（4）（5）（6）一定是黑、白各2格，而图形（3）必须有3格是同一种颜色，另一种颜色1格。因为前四种图形，黑、白已各占2×4=8（格），而黑格总共只有10格，所以图形（3）只能是3白1黑。由此知道图（1）一定在中间一列的黑格，而上面的黑格不可能，所以图（1）在中间一列下面的黑格中。
那么其它图形如何拼呢？为了说明方便，给每一格编一个数码（见左下图）。
因为图（3）是3白1黑，所以为使角上不空出一格，它只能放在（1，3，4，5）或（7，12，13，17）或（11，15，16，21）这三个位置上。
若放在（1，3，4，5）位置上，则图（6）只能放在（7，12，13，18）或（15，16，19，20）或（2，7，8，13）这三个位置，但是前两个位置是明显不行的，否则角上会空出一格。若放在（2，7，8，13）上，则图（2）只能放在（12，17，18，19）位置上，此时不能同时放下图（4）和图（5）。
若把图（3）放在（7，12，13，17）位置上，则方格1这一格只能由图（2）或图（6）来占据。如果图（2）放在（1，2，3，4），那么图（6）无论放在何处都要出现孤立空格；如果把图（6）放在（1，4，5，10），那么2，3这两格放哪一图形都不合适。
因此，图形（3）只能放在（11，15，16，21）。其余图的拼法如右上图。
练习12
1.中国象棋盘的任意位置有一只马，它跳了若干步正好回到原来的位置。问：马所跳的步数是奇数还是偶数？
2.右图是某展览大厅的平面图，每相邻两展览室之间都有门相通。今有人想从进口进去，从出口出来，每间展览厅都要走到，既不能重复也不能遗漏，应如何走法？
3.能否用下图中各种形状的纸片（不能剪开）拼成一个边长为99的正方形（图中每个小方格的边长为1）？请说明理由。
4.用15个1×4的长方形和1个2×2的正方形，能否覆盖8×8的棋盘？
5.平面上不共线的五点，每两点连一条线段，并将每条线段染成红色或蓝色。如果在这个图形中没有出现三边同色的三角形，那么这个图形一定可以找到一红一蓝两个“圈”（即封闭回路），每个圈恰好由五条线段组成。
6.将正方形ABCD分割成n2个相等的小正方格，把相对的顶点A，C染成红色，B，D染成蓝色，其他交点任意染成红、蓝两种颜色之一。试说明：恰有三个顶点同色的小方格的数目是偶数。
7.已知△ABC内有n个点，连同A，B，C三点一共（n＋3）个点。以这些点为顶点将△ABC分成若干个互不重叠的小三角形。将A，B，C三点分别染成红色、蓝色和黄色。而三角形内的n个点，每个点任意染成红色、蓝色和黄色三色之一。问：三个顶点颜色都不同的三角形的个数是奇数还是偶数？
8.从10个英文字母A，B，C，D，E，F，G，X，Y，Z中任意选5个字母（字母允许重复）组成一个“词”，将所有可能的“词”按“字典顺序”（即英汉辞典中英语词汇排列的顺序）排列，得到一个“词表”：
AAAAA，AAAAB，…，AAAAZ，
AAABA，AAABB，…，ZZZZY，ZZZZZ。
设位于“词”CYZGB与“词”XEFDA之间（这两个词除外）的“词”的个数是k，试写出“词表”中的第k个“词”。
练习12
1.偶数。
解：把棋盘上各点按黑白色间隔进行染色（图略）。马如从黑点出发，一步只能跳到白点，下一步再从白点跳到黑点，因此，从原始位置起相继经过：白、黑、白、黑……要想回到黑点，必须黑、白成对，即经过偶数步，回到原来的位置。
2.不能。
解：用白、黑相间的方法对方格进行染色（如图）。若满足题设要求的走法存在，必定从白色的展室走到黑色的展室，再从黑色的展室走到白色的展室，如此循环往复。现共有36间展室，从白色展室开始，最后应该是黑色展室。但右图中出口处的展室是白色的，矛盾。由此可以判定符合要求的走法不存在。
3.不能。
解：我们将 99×99的正方形中每个单位正方形方格染上黑色或白色，使每两个相邻的方格颜色不同，由于 99×99为奇数，两种颜色的方格数相差为1。而每一种纸片中，两种颜色的方格数相差数为0或3，如果它们能拼成一个大正方形，那么其中两种颜色之差必为3的倍数。矛盾！
4.不能。
解：如图，给8×8的方格棋盘涂上4种不同的颜色（用数字1，2，3，4表示）。显然标有1，2，3，4的小方格各有16个。每个1×4的长方形恰好盖住标有1，2，3，4的小方格各一个，但一个2×2的正方形只能盖住有三种数字的方格，故无法将每个方格盖住，即不可能有题目要求的覆盖。
5.证：设五点为A，B，C，D，E。考虑从A点引出的四条线段：如果其中有三条是同色的，如AB，AC，AD同为红色，那么△BCD的三边中，若有一条是红色，则有一个三边同为红色的三角形；若三边都不是红色，则存在一个三边同为蓝色的三角形。这与已知条件是矛盾的。
所以，从A点出发的四条线段，有两条是红色的，也有两条是蓝色的。当然，从其余四点引出的四条线段也恰有两条红色、两条蓝色，整个图中恰有五条红色线段和五条蓝色线段。
下面只看红色线段，设从A点出发的两条是AB，AE。再考虑从B点出发的另一条红色线段，它不应是BE，否则就有一个三边同为红色的三角形。不妨设其为BD。再考虑从D点出发的另一条红色线段，它不应是DE，否则从C引出的两条红色线段就要与另一条红色线段围成一个红色三角形，故它是DC。最后一条红色线段显然是CE。这样就得到了一个红色的“圈”：
A→B→D→C→E→A。
同理，五条蓝线也构成一个“圈”。
6.证：将红点赋值为0，蓝点赋值为1。再将小方格四顶点上的数的和称为这个小方格的值。若恰有三顶点同色，则该小方格的值为奇数，否则为偶数。在计算所有n2个小方格之值的和时，除A，B，C，D只计算一次外，其余各点都被计算了两次或四次。因为A，B，C，D四个点上的数之和是偶数，所以n2个小方格之值的和是偶数，从而这n2个值中有偶数个奇数。
7.奇数。
解：先对所有的小三角形的边赋值：边的两端点同色，该线段赋值为0，边的两端点不同色，该线段赋值为1。
然后计算每个小三角形的三边赋值之和，有如下三种情况：
（1）三个顶点都不同色的三角形，赋值和为3；
（2）三个顶点中恰有两个顶点同色的三角形，赋值和为2；
（3）三个顶点同色的三角形，赋值和为0。
设所有三角形的边赋值总和为S，又设（1）（2）（3）三类小三角形的个数分别为a，b，c，于是有
S=3a+2b+0c=3a+2b。（*）
注意到在所有三角形的边赋值总和中，除了AB，BC，CA三条边外，都被计算了两次，故它们的赋值和是这些边赋值和的2倍，再加上△ABC的三边赋值和3，从而S是一个奇数，由（*）式知a是一个奇数，即三个顶点颜色都不同的三角形的个数是一个奇数。
8.EFFGY。
解：将A，B，C，D，E，F，G，X，Y，Z分别赋值为0，1，2，3，4，5，6，7，8，9，则
CYZGB=28961，_XEFDA=74530。
在28961与74530之间共有74530-28961-1=45568（个）数，词表中第45568个词是EFFGY。
拉姆齐(Ramsly)二染色定理是什么
Ramsey定理：
Ramsey(1903~1930)是英国数理逻辑学家,他把抽屉原理加以推广，得出广义抽屉原理，也称为Ramsey定理。 Ramsey定理（狭义）的内容：任意六个人中要么至少三个人认识，要么至少三个不认识 证明如下：首先，把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设：如果两个人识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色。由抽屉原则可知：这五条线段中至少有三条是同色的。不妨设AB、AC、AD为红色。若BC或CD为红色，则结论显然成立。若BC和CD均为蓝色，则若BD为红色，则一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识。
希望采纳，谢谢o(∩_∩)o
二分图，完全图，树，连通图中一定可以进行黑白染色的有
这个二分图只有唯一的染色方法，最大独立集是4（下面4个）但黑白均只有3个点。（最大匹配此时就是2）
单栈排序与双栈排序
单栈排序
Tom最近在研究一个有趣的排序问题:有一个1~n的输入序列和1个栈S，Tom希望借助以下2种操作实现将输入序列升序排序。
操作a：如果输入序列不为空，将第一个元素压入栈S1
操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
如果一个1-n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可单栈排序排列”。
【输入】第一行是一个整数n。第二行有n个用空格隔开的正整数，构成一个1~n的排列。
【输出】输出文件共一行，如果输入的排列不是“可单栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
------------------------------
定理：考虑对于任意两个数q。
充分性证明：即如果满足上述条件,那么q一定不能压入同一个栈：
反证法:假设这两个数压入了同一个栈,那么在压入q的时候栈内情况如下:
+----+
|q |
+----+
|... |
+----+
|q |
+----+
因为q,这显然是不正确的.
必要性证明：如果两个数不可以压入同一个栈,那么它们一定满足上述条件。
证明逆否命题：也就是“如果不满足上述条件,那么这两个数一定可以压入同一个栈.“ 不满足上述条件有两种情况:
情况1：对于任意i《j《k且q;
情况2：对于任意i《j,q.
第一种情况：在q没有影响)。 第二种情况：可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈. 这样,原命题的逆否命题得证,所以原命题得证。
由此得出有解的判断方法：对所有的数对(i,j)满足1≤i《j≤n,检查是否存在i《j《k满足q。
var
n,top,i,j,k:longint;{序列长度为n，栈指针为top}
ans:string;{操作序列}
st:array of longint;{栈}
begin
read(n);{读序列长度}
top:=0;j:=1;ans:=’’;{栈和输出序列空，从1开始输出}
for i:=1 to n do{依次处理每个数字}
begin
read(k);ans:=ans+’a ’;inc(top);st:=k;{读当前数字，进行a操作，该数字入栈}
while st=j do {若栈顶满足递增要求，则出栈（进行b操作），下一个输出数字应+1，这一过程反复进行，直至不满足条件为止}
begin dec(top);inc(j);ans:=ans+’b ’end end;
if j《=n {若未输出1¨n，则失败退出；否则输出操作序列}
then writeln(0)
else writeln(copy(ans,1,length(ans)-1))
end.
================================================================
双栈排序
【问题描述】Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。
操作a：如果输入序列不为空，将第一个元素压入栈S1
操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c：如果输入序列不为空，将第一个元素压入栈S2
操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列
+--------------------
s1 |
+--------------------
+--------------------
s2 |
+--------------------
如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。
例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列：《a,c,c,b,a,d,d,b》
(这个图网上有，你自己找找吧）
当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，《a,c,c,b,a,d,d,b》是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
【输入】输入文件twostack.in的第一行是一个整数n。第二行有n个用空格隔开的正整数，构成一个1~n的排列。
【输出】输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
========================================
简述题意
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2)。最初的时候,q2,s1和s2都为空,而q1中有n个数(n≤1000),为1~n的某个排列. 现在支持如下四种操作: a操作,将 q1的首元素提取出并加入s1的栈顶； b操作,将s1的栈顶元素弹出并加入q2的队列尾；
c操作,将 q1的首元素提取出并加入s2的栈顶； d操作,将s2的栈顶元素弹出并加入q2的队列尾； 请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.
1、判断是否有解和任意两个数能否压入同一个栈
⑴、对任意两个数q，则这两个数分别入s1栈和s2栈
⑵、将s1栈和s2栈中的数字组合成两个顶点子集，同一顶点子集内不会出现任何连边,即不能压入同一个栈的所有数字被分到了两个栈中。任两个不在同一栈的数字间连边。此时我们只考虑检查是否有解,所以只要化O(n)时间检查这个图是不是二分图,就可以得知是否有解了。
======================================================
二分图及二分图的匹配
二分图是一种特殊类型的图：图中的顶点集被划分成X与Y两个子集,图中每条边的两个端点一定是一个属于X而另一个属于Y。二分图的匹配是求边的一个子集，该子集中的任意两条边都没有公共的端点。
======================================================
找字典序最小的解
1、确定每个数字入哪个栈，即构造二分图
把二分图染成1和2两种颜色,染色为1的结点被压入s1栈, 染色为2结点被压入s2栈。为了字典序尽量小,我们希望让编号小的结点优先压入s1栈。 由于二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1，并从它开始DFS染色,直到所有结点都被染色为止。这样,我们就得到了每个结点应该压入哪个栈中。
2、从数字1开始，按照目标序列的递增顺序构造操作序列
先处理入栈：按照搜索递增顺序每个顶点：若顶点i的颜色为1，则进行a操作，q1入s2栈。
后处理出栈：若s1栈的栈顶元素为目标序列的当前数字k，则进行b操作，数字k出s1栈；若s2栈的栈顶元素为目标序列的当前数字k，则进行d操作，数字k出s2栈。
然后k+1,继续模拟，直至k为n为止。
==========================================================
数据结构
var
a,b,head,next,point,color:array}(i《=k《=n)；邻接表的表首顶点为head，后继指针为next，顶点序列为point，顶点的涂色序列为color}
s:array}
n,p,i,j,last:longint;{序列长度为n，当前应取数字为last}
procedure badend;{输出失败信息}
begin
writeln(0);close(output);halt;
end;
procedure addedge(a,b:longint);{（a,b）进入邻接表}
var t:longint;
begin
inc(p);point:=b;{增加顶点b}
if head=0 {（a,b）进入邻接表}
then head:=p
else begin
t:=head;
while next;
next:=p;
end;
end;
procedure dfs(now:longint);
var t:longint;
begin
t:=head;{搜索与顶点now相邻的所有顶点}
while t《》0 do
begin
if color未涂色，则该顶点涂互补色，沿该顶点递归下去}
then begin
color);
end;
if color涂相同色，则失败退出}
t:=next;{访问与顶点now相邻的下一个顶点}
end;
end;
begin
assign(input,’twostack.in’);reset(input);{输入文件读准备}
assign(output,’twostack.out’);rewrite(output);{输出文件写准备}
fillchar(s,sizeof(s),0);fillchar(a,sizeof(a),0);{两栈空}
readln(n);{读入排列}
for i:=1 to n do read(a);
b:=maxlongint;p:=0;
for i:=n downto 1 do{计算b= }
begin
b;
if a;
end;
for i:=1 to n do
for j:=i+1 to n do
if (b不能不能压入同一个栈，则(i,j)和(j,i)进入邻接表}
then begin addedge(i,j);addedge(j,i);end;
for i:=1 to n do{所有未涂色的顶点涂颜色1，递归}
if color:=1;dfs(i);end;
last:=1;{目标序列初始化}
for i:=1 to n do{模拟输出序列}
begin
if color栈}
then write(’a ’)
else write(’c ’);
inc(s;
while (s=last) do
begin{将s栈顶的数字last取出}
if s栈顶的last取出}
if s栈顶的last取出}
inc(last);{按递增要求取下一个数字}
end;
end;
close(input);close(output);{关闭输入输出文件}
end.
证明 二分图的子图是二分图
二分图的充分必要条件是可以二染色,而二分图去掉若干点不会影响二染色的条件,所以二分图的子图是二分图.
