说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

以下内容均为个人理解。
MRO: Method Resolution Order 方法解析顺序

如果不用super：

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class A:
    def fun(self):
        print('A.fun')

class B(A):
    def fun(self):
        A.fun(self)
        print('B.fun')

class C(A):
    def fun(self):
        A.fun(self)
        print('C.fun')

class D(B , C):
    def fun(self):
        B.fun(self)
        C.fun(self)
        print('D.fun')

D().fun()

输出结果： 发现A被实例化了两次

A.fun
B.fun
A.fun
C.fun
D.fun

如果用super：

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class A:
    def fun(self):
        print('A.fun')

class B(A):
    def fun(self):
        super(B , self).fun()
        print('B.fun')

class C(A):
    def fun(self):
        super(C , self).fun()
        print('C.fun')

class D(B , C):
    def fun(self):
        super(D , self).fun()
        print('D.fun')

D().fun()

输出结果： 发现A没有被重复实例化，这时由于Python继承中的MRO机制

A.fun
C.fun
B.fun
D.fun

查资料：

在每个类声明之后，Python都会自动为创建一个名为“ mro
”的内置属性，这个属性就是Python的MRO机制生成的，该属性是一个tuple，定义的是该类的方法解析顺序（继承顺序），当用super调用父类的方法时，会按照__mro__属性中的元素顺序去挨个查找方法。我们可以通过“类名.
mro ”或“类名.mro()”来查看上面代码中D类的__mro__属性值

举例：

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class A(object):
    pass

class B(object):
    pass

class C(object):
    pass

class D(A,B):
    pass

class E(B, C):
    pass

class F(D, E):
    pass

print(F.__mro__)

输出结果：

(<class ‘ main.F’>, <class ‘ main.D’>, <class ‘ main.A’>,<class
‘ main.E’>, <class ‘ main.B’>, <class ‘ main.C’>,<class
‘object’>)

个人猜测MRO机制的顺序为：在深度优先的基础上，避免重复调用，且尽可能晚调用。
即 F->D->A->Object->B->Object->E->B->Object->C->Object
变为F->D->A->E->B->C->Objcet

super(type , obj)
obj是type或type子类 的 一个实例，一般是self
super(type , obj)表示obj【按MRO 第一个排在type后面】的父类
如：F->D->A->E->B->C->Objcet 中 super(B , F()).function() 调用的使C类的function方法。
super()
相当于super( class , self)

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

0. tkinter.Tk（） 零基础建议从1开始看别从0

主窗口的一些方法

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import tkinter as tk

root=tk.Tk()

def exit():
    root.quit()                 #退出
def update():
    root.update()               #刷新界面

root.title('标题名称就叫这个')
root.geometry('250x150')        #主窗体的大小
root.resizable(20,0)             #框体大小可调性，分别表示x,y方向的可变性,第一个参数为x，第二个为y
                                
bt1=tk.Button(root,text='exit',command=exit)
bt1.pack(side=tk.BOTTOM)
bt2=tk.Button(root,text='update',command=update)
bt2.pack(side=tk.BOTTOM)

tk.mainloop()

1. Lable Button

显示时间

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14

from tkinter import *
import time

#给button按钮用的函数
def refresh_time():
    timestring.set('%s'%time.ctime())
    complexLabel.update()

root=Tk()

frame1=Frame(root)
frame1.pack()
frame2=Frame(root)
frame2.pack()

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#Label
timestring=StringVar()              #建立StringVar类对象
timestring.set('%s'%time.ctime())   #初始化StringVar对象的值
img=PhotoImage(file='theimg.png')   #建立PhotoImage类对象
complexLabel=Label(frame1,
                #text='天王盖地虎，\n小鸡炖蘑菇。',  #文本
                textvariable=timestring,            #可变文本
                image=img,                          #图像

                justify=RIGHT,      #对齐方式 每行文字都会向这个方向对齐，默认CENTER居中
                anchor=None,          #文字在Label框内的方位 N,S,E,W,NE,NW,SE,SW(东南西北)
                compound=CENTER,    #组合方式 LEFT图左文右，RIGHT图右文左，CENTER图文重合

                height=360,width=640,   #Label的宽高  单位：以系统默认的中文的一个字体宽高为单位
                padx=20,pady=10,        #边距  单位是像素
                fg='blue',bg=None,      #颜色  fg：字体颜色，bg：字体背景色
                font=('华文行楷',35),    #字体名+大小

                relief='raised',         #边框样式 flat,sunken,raised,ridge
                bd=15                    #边框大小
                )
complexLabel.pack()

#Button
button=Button(frame2,
            text='刷新时间',
            image=None,         #Button的大小根据图片大小确定

            justify=None,   
            anchor=None,          
            compound=None,      #这些在Button里同样适用    

            font=('华文行楷',15),   
            fg='red',bg=None,
            width=20,height=1,
            padx=10,pady=5,

            bd=8,
            relief='sunken',    #flat groove ridge raised solid sunken

            cursor='hand2' ,    #鼠标  有pencil,circle,hand1,hand2

            command=refresh_time  #点击时触发函数 传参数用lambda:函数(参数)的形式
            )
button.pack()

mainloop()

​

效果图
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200501165700545.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)

2. Checkbutton Raidobutton

随便敲了个屑作

​

1
2
3
4
5
6
7
8
9
10
11
12
13

from tkinter import *

root=Tk()

v1=IntVar()
v2=IntVar()
v3=IntVar()
var=IntVar()

frame1=LabelFrame(root,bg='brown',text='Checkbutton部分',labelanchor=NE)
frame1.place(relx=0.2,rely=0.2,relwidth=0.3,relheight=0.3)
frame2=LabelFrame(root,bg='green',text='Raidobutton部分',labelanchor=NW)
frame2.place(relx=0.5,rely=0.5,relwidth=0.4,relheight=0.4)

​
​

1
2
3
4
5
6

check1=Checkbutton(frame1,text='流浪汉',variable=v1,fg='blue',bg='green')
check1.grid(row=0,column=0)
check2=Checkbutton(frame1,text='高中生',variable=v2,fg='black',bg='green')
check2.grid(row=1,column=0)
check3=Checkbutton(frame1,text='穿越者',variable=v3,fg='red',bg='green')
check3.grid(row=2,column=0)

​
​

1
2
3
4
5
6
7
8
9
10
11
12
13
14

radio1=Radiobutton(frame2,text='流浪汉',variable=var,value=1)
radio1.grid(row=0,column=0)
radio2=Radiobutton(frame2,text='掠夺者',variable=var,value=1)
radio2.grid(row=0,column=1)
radio3=Radiobutton(frame2,text='高中生',variable=var,value=2)
radio3.grid(row=1,column=0)
radio4=Radiobutton(frame2,text='初中生',variable=var,value=2)
radio4.grid(row=1,column=1)
radio5=Radiobutton(frame2,text='穿越者',variable=var,value=3)
radio5.grid(row=2,column=0)
radio6=Radiobutton(frame2,text='龙傲天',variable=var,value=3)
radio6.grid(row=2,column=1)

mainloop()

​

效果图
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200501165729478.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)

3. Entry 及复习前面

简易计算器

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

from tkinter import *

def changeop(value):
    oplst=['+','-','*','/']
    opstr.set(oplst[value])

def calcu():
    oplst=[lambda:v1.get()+v2.get(),lambda:v1.get()-v2.get(),lambda:v1.get()*v2.get(),lambda:v1.get()/v2.get()]
    try:
        v3.set(oplst[opvar.get()]())
        errstr.set('')
    except ZeroDivisionError:
        errstr.set('除零错误')
    except TclError:
        errstr.set('输入错误')
    except IndexError:
        errstr.set('无运算符')
    except:
        errstr.set('未知错误')
        
def clear():
    v1.set(0)
    v2.set(0)
    v3.set(0)
    opvar.set(5)
    opstr.set('')
    errstr.set('')

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

root=Tk()

#定义变量
v1=IntVar()
v2=IntVar()
v3=IntVar()
errstr=StringVar()
opstr=StringVar()
opvar=IntVar()
opvar.set(5)

frame=LabelFrame(root,text='计算器',labelanchor=NW)
frame.pack()

#三个数字
add1=Entry(frame,textvariable=v1,bg='lightgrey',width=8)
add1.grid(row=0,column=0)
add2=Entry(frame,textvariable=v2,bg='lightgrey',width=8)
add2.grid(row=0,column=2)
result=Label(frame,textvariable=v3,bg='lightgrey',width=8,anchor=W)
result.grid(row=0,column=4)

#运算符和等号
ch1=Label(frame,textvariable=opstr)
ch1.grid(row=0,column=1)
ch2=Label(frame,text='=')
ch2.grid(row=0,column=3)

#错误提示
errlabel=Label(frame,textvariable=errstr,fg='red')
errlabel.grid(row=0,column=5)

#运算符选项
op1=Radiobutton(frame,text='+',value=0,variable=opvar,command=lambda:changeop(opvar.get()))
op1.grid(row=1,column=0)
op1=Radiobutton(frame,text='-',value=1,variable=opvar,command=lambda:changeop(opvar.get()))
op1.grid(row=1,column=1)
op1=Radiobutton(frame,text='*',value=2,variable=opvar,command=lambda:changeop(opvar.get()))
op1.grid(row=1,column=2)
op1=Radiobutton(frame,text='/',value=3,variable=opvar,command=lambda:changeop(opvar.get()))
op1.grid(row=1,column=3)

#两个按钮
btcalcu=Button(frame,text='计算',command=calcu,width=8)
btcalcu.grid(row=1,column=4)
btclear=Button(frame,text='清除',command=clear,width=8)
btclear.grid(row=1,column=5)

​

1

mainloop()

​

效果图

4. Listbox Scrollbar 少量Text

Listbox Scrollbar Text 的简单应用

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import tkinter as tk
root=tk.Tk()

lst=['幽灵弯刀','学术剽窃','苔丝格雷迈恩','迈拉的不稳定元素','弑君','蜡烛巨龙','团伙劫掠','阿卡玛','灵魂之境',
    '炎魔之王拉格纳罗斯','光耀之主拉格纳罗斯','索瑞森大帝','厄运信天翁','露娜的口袋银河','观星者露娜','拉祖尔',
    '火车王埃利诺','卡扎库斯','了不起的杰弗里斯','铜须布莱恩','伊利斯逐星','雷诺杰克逊','芬利忘了爵士']
#可以用for循环添加一些项目
var=tk.StringVar()
#StringVar类变量存放Listbox中的所有项目，以空格隔开
var.set('1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20')

frame1=tk.LabelFrame(root,bg='lightgrey',text='Listbox',labelanchor=tk.NW)
frame1.pack(side=tk.LEFT)
frame2=tk.LabelFrame(root,bg='lightgrey',text='Text',labelanchor=tk.NW)
frame2.pack(side=tk.RIGHT)

scrbar=tk.Scrollbar(frame1,command=None)    #仅仅这样用户拖动滚动条是不能实现Listbox的上下移动的，下文通过config方法改变了command的值
scrbar.pack(side=tk.LEFT,fill=tk.Y)        

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

lstbx=tk.Listbox(frame1,
                height=8,                   #显示8行
                fg='blue',
                yscrollcommand=scrbar.set,  #设置y方向滚动条

                selectbackground='green',    #选中时的背景色
                selectforeground='red',      #选中时的前景色
                selectborderwidth=5,        #选中时的边框宽度 默认是由selectbackground指定的颜色填充，没有边框 如果设置了此选项，Listbox 的每一项会相应变大，被选中项为 "raised" 样式
                
                selectmode=tk.SINGLE,       #选择模式 SINGLE 单选 BROWSE 单选，可鼠标和方向键改变选项
                                            #       MULTIPLE 多选 EXTENDED 多选，需要配合shift crtl 或拖动光标实现
                
                cursor='hand2',             #鼠标选在Listbox上的样式，pencil,circle,hand1,hand2

                exportselection=False,      #指定文本是否可以被复制到剪贴板

                listvariable=var            #StringVar类变量存放Listbox中的所有项目，以空格隔开
                )
lstbx.pack(side=tk.LEFT,fill=tk.BOTH)

for i in lst:
    lstbx.insert(tk.END,i)

scrbar.config(command=lstbx.yview)          #Listbox组件的yview方法用于在垂直方向上滚动 Listbox 组件的内容
                                            
#Listbox的方法以及Scrollbar的参数和方法 这里没有记录

def add():
    text.insert(tk.END,lstbx.get(tk.ACTIVE)+'\n')   #在Text的末尾-END位置-写入Listbox的选中项

button1=tk.Button(frame1,text='删除',command=lambda x=lstbx:x.delete(tk.ACTIVE))    #Listbox.delete(tk.ACTIVE)删除选中
button1.pack(side=tk.BOTTOM)
button2=tk.Button(frame1,text='加入',command=add)
button2.pack(side=tk.BOTTOM)

text=tk.Text(frame2)
text.pack()

tk.mainloop()

​

Listbox的方法以及Scrollbar的参数和方法有很多没有记录，也暂时没有学习，学习的时候找到这位了博主发过的一些比较详细的资料
https://blog.csdn.net/qq_41556318/article/list

效果图
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200501165914516.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)

5. Text 之 mark与tag

关于mark的简单知识

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import tkinter as tk

root=tk.Tk()

scrbar=tk.Scrollbar(root)
scrbar.pack(side=tk.LEFT,fill=tk.Y)

text1=tk.Text(root,width=50,height=15)
text1.pack(side=tk.LEFT)
text2=tk.Text(root,width=50,height=15)
text2.pack(side=tk.RIGHT)

text1.config(yscrollcommand=scrbar.set) #关联text1和滚动条
scrbar.config(command=text1.yview)

​

1
2
3
4
5
6
7
8
9
10
11
12
13

text1.insert(tk.INSERT,'在Insert位置插入这段话+换行\n')     #汉字只占一列的位置
text2.insert(tk.INSERT,'在Insert位置插入这段话+换行\n')

text1.mark_set('thismark','1.5')        #创建一个新mark，若mark存在，则是移动mark到指定位置
text2.mark_set('thismark','1.5')        

text2.mark_gravity('thismark',tk.LEFT)  #体会gravity为LEFT和RIGHT的不同(默认是RGHIT)
                                        #insert操作之后mark会保持在插入内容的gravity的方向

text1.insert('thismark','(第一Giao)')
text1.insert('thismark','(第二Giao)')
text2.insert('thismark','(第一Giao)')
text2.insert('thismark','(第二Giao)')

​

1
2
3
4
5
6
7
8
9
10
11

text1.insert(tk.END,'\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n')
text1.insert(tk.END,text1.mark_names())                
#mark_names()方法返回Text的所有mark(返回tuple类型) 包括INSERT CURRENT 注意END不是mark是特殊索引

text1.insert(tk.END,'\n'+text1.mark_next(0.1)+'\n')     #mark_next()方法返回index位置后的第一个mark，若没有，返回None
text1.insert(tk.END,type(text1.mark_previous(0.1)))     #mark_previous()方法返回index位置前的第一个mark，若没有，返回None

text1.mark_unset('thismark')
text2.mark_unset('thismark')        #封印mark

tk.mainloop()

​

效果图
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200502141505911.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200502141505910.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)

关于tag的简单知识

​

1
2
3
4
5
6
7
8
9
10

import tkinter as tk

root=tk.Tk()

text=tk.Text(root,width=50,height=15)
text.pack()

text.insert(tk.INSERT,'abdcefghijklmnopqrstuvwxyz')

text.tag_config(tk.SEL,background='black',foreground='white')   #SEL是预定义的特殊tag，表示对应的选中内容

​

1
2
3
4
5
6

text.tag_add('thistag','1.5','1.9','1.14','1.18','1.0','1.1','1.20') #连续的两个参数表示范围，一个表示一个位置
text.tag_config('thistag',background='lightgrey',foreground='green')

text.tag_raise(tk.SEL)      
#新建tag会覆盖较为旧的tag的相同选项
#用tag_raise()或tag_lower()可以调整tag优先级

​

1

tk.mainloop()

效果图

![在这里插入图片描述](https://img-blog.csdnimg.cn/2020050214152292.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)

6. Canvas

暂时不想学，放在这里吃灰吧

7. Menu 相关的一些简单知识

简单实现了 Menu Menubotton OptionMenu 组件

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import tkinter as tk

root=tk.Tk()

menu=tk.Menu(root,tearoff=False)        #建立一个Menu menu  rearoff=true表示这个菜单可“撕下”(单独变成一个小窗口)
root.config(menu=menu)

filemenu=tk.Menu(menu,tearoff=False)    #建立另一个Menu filemenu
filemenu.add_command(label='打开')
filemenu.add_command(label='保存')
filemenu.add_separator()                #一道线
filemenu.add_command(label='退出',command=root.quit)
menu.add_cascade(label='文件',menu=filemenu)    #添加一个父菜单

frame=tk.Frame(root,width=500,height=200)
frame.pack()
def popup(event):
    filemenu.post(event.x_root,event.y_root)

frame.bind('<Button-3>',popup)              #通过绑定事件（右击）使filemenu出现

1
2
3
4
5
6
7
8

#--------------------------------------------------------------------------------------------------
#Menubutton
menubutton=tk.Menubutton(root,text='click me',relief=tk.RAISED)
menubutton.pack()

second_filemenu=tk.Menu(menubutton)
second_filemenu.add_command(label='giaogiao')
menubutton.config(menu=second_filemenu)

1
2
3
4
5
6
7

#--------------------------------------------------------------------------------------------------
#OptionMenu（M大写）
options=['624','625','626','010','1437','4369','777']
var=tk.StringVar()
var.set(options[0])
optmenu=tk.OptionMenu(root,var,*options) 
optmenu.pack()

1

tk.mainloop()

​

效果图
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200502191209144.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)

8. Message Spinbox简单知识拓展

Message使Label的变体，支持多行文本消息和自动
Spinbox是Entry的变体， 从一些固定值中选择一个，可以通过 1.范围 2.元组 指定内容

​
​ import tkinter as tk
​
​ root=tk.Tk()
​
frame1=tk.LabelFrame(root,text=‘message’,labelanchor=tk.NW)
frame1.pack(side=tk.LEFT)
frame2=tk.LabelFrame(root,text=‘spinbox’,labelanchor=tk.NW)
frame2.pack(side=‘right’)

#Message使Label的变体，支持多行文本消息和自动
msg1=tk.Message(frame1,text='我是一个massage',width=150)
msg1.pack()
msg2=tk.Message(frame1,text='我是一个巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨长的message',width=200)
msg2.pack()

#Spinbox是Entry的变体， 从一些固定值中选择一个，可以通过 1.范围 2.元组 指定内容
#1.指定范围
spb1=tk.Spinbox(frame2,from_=0,to=15)
spb1.pack(side=tk.LEFT)
#2.指定元组
lst=['奥雷利亚诺布恩迪亚','何塞阿尔卡蒂奥布恩迪亚','乌尔苏拉','梅尔基亚德斯','蕾梅黛丝','赫里内勒多马尔克斯','丽贝卡','阿马兰妲','加西亚马尔克斯']
spb2=tk.Spinbox(frame2,values=lst)
spb2.pack()

tk.mainloop()

效果图

9. Toplevel

实现顶级窗口

​
​ import tkinter as tk
​
​ root=tk.Tk()
​ root.title(‘root里面放按钮’)
​ num=0
​
def create():
global num
num+=1

    top=tk.Toplevel()         #创建Top窗口
    top.title('第'+str(num)+'窗')
    top.attributes('-alpha',0.7)    #设置窗口不透明度为0.7
    
    msg=tk.Message(top,text='第%d个窗口成功创建!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!'%num,width=300)
    msg.pack()

​
​ tk.Button(root,text=‘创建一个Toplevel窗口’,width=70,command=create,relief=tk.RAISED,bd=10).pack()
​
​ tk.mainloop()

效果图
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200503163759839.PNG?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)
在学习过程中，发现这位博主有关于Toplevel 和Tk 方法，以及attributes函数 的较详细内容
https://blog.csdn.net/sinat_41104353/article/details/79320155

10. 事件绑定 简单知识

可以把事件和组件或窗口（可能表述会有问题）绑定起来以形如
窗口.bind(事件序列,函数)的形式，回调函数时会带着Event（事件）对象作为参数

事件序列的语法描述为（举个栗子，表示同时ctrl+shift+小写h）详情见下面链接

学习时发现其他博主发的资料：
事件序列：https://blog.csdn.net/nkd50000/article/details/77319659
Event对象的属性及含义：https://blog.csdn.net/nkd50000/article/details/77319760

。
简单试水

​
​ import tkinter as tk
​
​ lst=[
​ ‘’,
​ ‘’,
​ ‘’,
​ ‘’,
​ ‘’,
​ ‘<Alt_L>’,
​ ‘’,
​ ‘<Shift_L>’,
​ ‘’,
​ ‘’,
​ ‘’,
​ #’’
​ ]
​
root=tk.Tk()

frame=tk.Frame(root,width=250,height=50,bg='blue')
frame.pack()
frame.focus_set()

def function(event):
    top=tk.Toplevel()
    tk.Message(top,text=event.type).pack()

for each in lst:
    frame.bind(each,function)
#frame.bind('<KeyPress>',function)
#frame.bind('<KeyPress-Y>',function)

​
​
​ tk.mainloop()

11. 标准对话框

massage简单实现

​
​ import tkinter.messagebox as tkmsg
​ import tkinter as tk

​
​ root=tk.Tk()
​
​ v=tk.StringVar()
​ lb=tk.Message(root,textvariable=v)
​ lb.pack()
​
#返回 字符串 yes no
res=tkmsg.askquestion(
‘askquestion’,
‘随便写点什么12’,
default=tkmsg.NO,
#default定义按下回车的默认选项（默认值为一个按钮）
#CANCEL IGNORE OK NO RETRY YES
icon=tkmsg.ERROR,
#icon 指定框内显示的图标，一般不要乱指定，用默认
#ERROR INFO QUESTION WARNNING

                #对话框默认显示在根窗口，通过parent参数 如parent=w  可以显示在子窗口
                ) 
v.set(res)

#返回 bool值 True False
res=tkmsg.askyesno('askyesno','随便写点什么3244231423')
v.set(res)
res=tkmsg.askretrycancel('askretrycancel','随便写点什么3454345')
v.set(res)
res=tkmsg.askokcancel('askokcancel','随便写点什么56765')
v.set(res)

#返回 字符串 ok
res=tkmsg.showerror('showerror','随便写点什么rtfdx')
v.set(res)
res=tkmsg.showinfo('showinfo','随便写点什么3r4eds')
v.set(res)
res=tkmsg.showwarning('showwarning','随便写点什么d gfgdsgr')
v.set(res)

​
​ tk.mainloop()

filedialog模块

导入模块：import tkinter.filedialog
选择文件对话框的格式：
tkinter.filedialog.asksaveasfilename():选择以什么文件名保存，返回文件名
tkinter.filedialog.asksaveasfile():选择以什么文件保存，创建文件并返回文件流对象
tkinter.filedialog.askopenfilename():选择打开什么文件，返回文件名
tkinter.filedialog.askopenfile():选择打开什么文件，返回IO流对象
tkinter.filedialog.askdirectory():选择目录，返回目录名
tkinter.filedialog.askopenfilenames():选择打开多个文件，以元组形式返回多个文件名
tkinter.filedialog.askopenfiles():选择打开多个文件，以列表形式返回多个IO流对象

12. 布局管理器

举个栗子

​
​ import tkinter as tk
​
​ root=tk.Tk()
​
frame1=tk.Frame(root,width=200,height=150,bg=‘lightgrey’)
frame1.pack(side=tk.LEFT,fill=tk.Y)
frame2=tk.Frame(root,width=200,height=150,bg=‘yellow’)
frame2.pack(side=tk.LEFT)
frame3=tk.Frame(root,width=200,height=150,bg=‘purple’)
frame3.pack(side=tk.RIGHT,fill=tk.BOTH)

lb1=tk.Label(frame1,text='123123',bg='green')
lb1.place(relx=0.1,rely=0.1,relwidth=0.4,relheight=0.4)

lb2=tk.Label(frame2,text=369396,bg='blue')
lb2.place(relx=0.1,rely=0.1,relwidth=0.8,relheight=0.8)

​
​ bt1=tk.Button(frame3,text=‘aoe’)
​ bt1.grid(row=0,column=0)
​ bt2=tk.Button(frame3,text=‘iuv’)
​ bt2.grid(row=1,column=1)
​
​ tk.mainloop()

少量拾遗

tkinter.Text.yview_moveto(1)移至最低端

tkinter.Text的state参数为’disabled’时不允许修改 state的默认参数为’normal’

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

def initial(req = False):
    global order, vis , arr_lft, arr_need, arr_max, arr_alc, cnt
    MAX = [
        [0,0,4,4]
        ,[2,7,5,0]
        ,[3,6,10,10]
        ,[0,9,8,4]
        ,[0,6,6,10]
    ]
    ALC = [
        [0,0,3,2]
        ,[1,0,0,1]
        ,[1,3,5,4]
        ,[0,3,3,2]
        ,[0,0,1,4]
    ]
    NEED = [1,6,2,2]
    cnt = 0
    arr_lft = np.array(NEED)
    arr_max = np.array(MAX)
    arr_alc = np.array(ALC)
    arr_need = arr_max - arr_alc
    arr_need[arr_need < 0] = 0
    vis = [False for i in range(5)]
    order = []
    if req == True:
        arr_lft -= np.array([1,2,2,2])
        arr_alc[2] += np.array([1,2,2,2])
def dfs():
    global order, vis , arr_lft, arr_need, arr_max, arr_alc, cnt
    if vis.count(False) == 0:
        print(order)
        cnt += 1
        return
    for i in range(len(vis)):
        if vis[i] == False and True not in (arr_lft - arr_need[i] < 0 ):
            vis[i] = True
            order.append(i)
            arr_lft += arr_alc[i]
            dfs()
            vis[i] = False
            arr_lft -= arr_alc[i]
            order.remove(i)
def solve(req = False):
    initial(req)
    dfs()
    if cnt != 0: 
        print('共有序列',cnt,'种')
    else:
        print('死锁')
def main():
    print('第一问:')
    solve()
    print('\n第二问')
    solve(True)
if __name__ == '__main__':
    main()

样例为：《计算机操作系统》——翟一鸣等老师 课后题2.13

第一问:
[0, 3, 1, 2, 4]
[0, 3, 1, 4, 2]
[0, 3, 4, 1, 2]
共有序列 3 种
空格
第二问
死锁

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

https://vjudge.net/contest/387870#problem/A

题目描述

Imagine you are standing inside a two-dimensional maze composed of square
cells which may or may not be filled with rock. You can move north, south,
east or west one cell at a step. These moves are called walks.
One of the empty cells contains a box which can be moved to an adjacent free
cell by standing next to the box and then moving in the direction of the box.
Such a move is called a push. The box cannot be moved in any other way than by
pushing, which means that if you push it into a corner you can never get it
out of the corner again.

One of the empty cells is marked as the target cell. Your job is to bring the
box to the target cell by a sequence of walks and pushes. As the box is very
heavy, you would like to minimize the number of pushes. Can you write a
program that will work out the best such sequence?
![在这里插入图片描述](https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai56MTgwLmNuLzk2MTQ4YTA0MzgzZDlmZTI2MzBhM2FjNzcyZjEyMjYx?x-oss-
process=image/format,png#pic_center)

输入

The input contains the descriptions of several mazes. Each maze description
starts with a line containing two integers r and c (both <= 20) representing
the number of rows and columns of the maze.

Following this are r lines each containing c characters. Each character
describes one cell of the maze. A cell full of rock is indicated by a #' and an empty cell is represented by a.’. Your starting position is symbolized by
S', the starting position of the box byB’ and the target cell by `T’.

Input is terminated by two zeroes for r and c.

输出

For each maze in the input, first print the number of the maze, as shown in
the sample output. Then, if it is impossible to bring the box to the target
cell, print ``Impossible.’’.

Otherwise, output a sequence that minimizes the number of pushes. If there is
more than one such sequence, choose the one that minimizes the number of total
moves (walks and pushes). If there is still more than one such sequence, any
one is acceptable.

Print the sequence as a string of the characters N, S, E, W, n, s, e and w
where uppercase letters stand for pushes, lowercase letters stand for walks
and the different letters stand for the directions north, south, east and
west.

Output a single blank line after each test case.

样例输入

1 7
SB…T
1 7
SB…#.T
7 11
###########
#T##…#
#.#.#…####
#…B…#
#.######…#
#…S…#
###########
8 4
…
.##.
.#…
.#…
.#.B
.##S
…
###T
0 0

样例输出

Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS

自己加一组样例输入

6 5
…T
.S…
#B###
…
…
…

自己加的样例的输出

Maze #1
SSesswNNNNwnEEE

瞎翻译

这是一个推箱子游戏。人要把箱子推到终点，我们需要输出人走的路径（方向用nswe或NSWE表示，人不推箱子只走路时路径用小写字母nswe表示，人推箱子走路时路径用大写字母NSWE表示）

先输入两个整数row和col，表示地图大小

之后输入一个row行col列的char类型矩阵，其中#代表墙，.代表路，S代表人的起始位置，B代表箱子起始位置，T代表终点（箱子要被推到的位置）

题解

1.
先设想箱子会自己动，想象一下如何用简单的bfs求得“箱子自己动”情况下的答案
2.
在”箱子自己动“的代码基础上加入人：
假设箱子要往右动，那么先对人进行bfs，让人从自己的位置走到箱子的左边的位置，如果人可以走过去，则箱子可以往右移动。
2.5
记得人推箱子的时候人也要动，而不是仅仅箱子移动（人与箱子往相同方向移动，或者直接把人移动到箱子的上一个位置）。
3.
这是笔者自己犯的一个错误：
不能仅仅用形如visb[][]的二维数组标记箱子到过的位置，因为在某些情况下人想推箱子到终点，是需要【箱子折返】的（箱子有可能去一个地方两次或多次，可以见我自己加的输入样例）
所以要用三维数组：visb[][][4],第三维记录箱子来时的方向

4.
在箱子移动的bfs函数中嵌套人移动的bfs函数完成求解

​
#include
#include
#include
#include
#include
#include

int row,col,counter;
const int maxn=25;
char cell[maxn][maxn];
bool visb[maxn][maxn][4],visp[maxn][maxn];  //visb记录箱子，visp记录人去过的位置
//人的标记方式为：先在原地标记一次，之后去了哪标哪
//箱子的标记方式为：不在原地标记，只有从一个方向（假设为2）移动到某一格（假设为i，j），则标记visb[i][j][2]为true

int step[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char adir[5]="snew",Adir[5]="SNEW";         //两个dir都对应step的四个方向
struct Pos
{
    int x,y;            //表示位置，若是人，只会用到这两个和path
    int mx,my;          //表示人的位置，表示箱子的变量用的，表示人的变量用不着
    std::string path;   //记录路径
}mpre,mnxt,tar,bpre,bnxt,to;
//mpre-man pre人的当前位置（或解释为人的上一个位置）mnxt-man next人的下一个位置
//bpre和bnxt表示箱子的当前位置和下一个位置
//tar表示终点位置
//to表示箱子要移动到某个位置时，人要移动到的位置

​
​
//判断这个点是否在地图可行走范围之中
bool cango(int x,int y)
{
if(x>=0 && x<row && y>=0 && y<col && cell[x][y]!=’#’)
return true;
return false;
}

//人从自己所在的位置，移动到to.x,to.y的位置，简单bfs
bool bfsMan()
{
    memset(visp,false,sizeof(visp));
    std::queue<Pos> q;
    mpre.path="";
    mpre.x=bnxt.mx,mpre.y=bnxt.my;
    q.push(mpre);
    visp[mpre.x][mpre.y]=true;
    while(!q.empty())
    {
        mpre=q.front(); q.pop();
        if(mpre.x==to.x && mpre.y==to.y) return true;
        for(int i=0; i<4; i++)
        {
            mnxt=mpre;
            mnxt.x+=step[i][0],mnxt.y+=step[i][1];
            if(cango(mnxt.x,mnxt.y) && !visp[mnxt.x][mnxt.y] && !(mnxt.x==bpre.x && mnxt.y==bpre.y))
            {
                visp[mnxt.x][mnxt.y]=true;
                mnxt.path+=adir[i];
                q.push(mnxt);
            }
        }
    }
    return false;

}

//对箱子的bfs，其中嵌套了对人的bfs
void bfs()
{
    std::queue<Pos> q;
    bpre.path="";
    bpre.mx=mpre.x,bpre.my=mpre.y;
    q.push(bpre);//让最初箱子的位置入队，记得给箱子结构体赋值人的位置
    while(!q.empty())
    {
        bpre=q.front(); q.pop();
        for(int i=0; i<4; i++)  //开始四个方向的遍历
        {
            bnxt=bpre;
            bnxt.x+=step[i][0],bnxt.y+=step[i][1];
            if(cango(bnxt.x,bnxt.y) && !visb[bnxt.x][bnxt.y][i])
            {
                to=bpre;
                to.x-=step[i][0],to.y-=step[i][1];
                if(cango(to.x,to.y))    //初步检查这一点是否可以达到
                {
                    if(bfsMan())
                    {
                        //一定要bfsMan（）返回true时才标记visb为true
                        //因为若人不能到达特定的推箱子位置，箱子就不能访问到要去的位置
                        visb[bnxt.x][bnxt.y][i]=true;
                        bnxt.path+=mpre.path;               //路径末尾加入人上一次移动的路径
                        bnxt.path+=Adir[i];                 //路径末尾加入箱子移动的路径
                        //如果到了终点，直接输出
                        if(bnxt.x==tar.x && bnxt.y==tar.y)
                        {
                            std::cout << "Maze #" << counter++ << std::endl;
                            std::cout << bnxt.path << std::endl << std::endl;
                            return ;
                        }
                        bnxt.mx=bpre.x,bnxt.my=bpre.y;      //记得记录箱子在这个位置时对应的人的位置，然后入队
                        q.push(bnxt);
                    }
                }
            }
        }
    }
    std::cout << "Maze #" << counter++ << std::endl;
    std::cout << "Impossible." << std::endl << std::endl;
}

​
int main()
{
counter=1;
while(std::cin >> row >> col && !(row0 && col0))
{
memset(visb,false,sizeof(visb));
for(int i=0; i<row; i++)
{
std::cin >> cell[i];
for(int j=0; j<col; j++)
{
if(cell[i][j]‘S’) mpre.x=i,mpre.y=j;
else if(cell[i][j]‘B’) bpre.x=i,bpre.y=j;
else if(cell[i][j]==‘T’) tar.x=i,tar.y=j;
}
}
bfs();
}

    return 0;
}

​

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

题面

HDU7136 不放了

思路

把所有的点按照权值从小到大排序， 依次用并查集维护
每次更新一个点， 把此点与其相邻的枚举过的点并为一个集合， 这样每次更新可以使这个集合的点的遍历数量都+1
用num[]记录一个点可以合法遍历的点的数量， 且num[]仅对代表元生效
用gap[]记录一个点于其代表元的差值, 非代表元的答案为 num[] - gap[] (因为代表元的gap[] = 0)
记得路径压缩， 不路径压缩——反正我没试过， 会T吧

变量&数组 解释

建图存图用的 ：

head[], idx, u, v, edg[]

输入数据相关

input[] 输入数据
node[] 输入数据 结构体 {输入数值 + 编号} 后按照输入数值排序

并查集相关

sset[] 并查集
gap[]每个元素与其代表元素的差值
num[]从该元素开始可以合法遍历的点的数量
num[]只对代表元生效， 所有节点可合法遍历的点的数量 都可以由 num[] - gap[]计算

其他

boss 在每加入一个点时， 作为这一轮的唯一代表元

代码

时间826MS 空间5688K

​
#include <bits/stdc++.h>
const int N = 1e5 + 5;
int t, n, u, v, idx, boss;
int head[N], sset[N], gap[N], num[N], inpt[N];
struct AAAA{
int id, w;
bool operator < (const AAAA &a) const{
return w < a.w;
}
} node[N];
struct Edge{ int to, nxt; }edg[N << 1];
inline void addE(int fr, int to){
edg[++ idx] = (Edge) {to, head[fr]};
head[fr] = idx;
}
int ffind(int x){
if(sset[x] == x) return x;
int fa = sset[x];
int xx = ffind(fa);
gap[x] += gap[fa];
sset[x] = xx;
return xx;
}
inline void mmerge(int fa, int x){
int ff = ffind(fa), xx = ffind(x);
sset[xx] = ff;
gap[xx] = num[ff] - num[xx];
}
int main(){
scanf("%d", &t);
while(t --){
idx = 1;
scanf("%d", &n);
for(int i=0; i<=n; i++) sset[i] = i;
for(int i=1; i<n; i++){
scanf("%d%d", &u, &v);
addE(u, v), addE(v, u);
}
for(int i=1; i<=n; i++){
scanf("%d", &inpt[i]);
node[i].w = inpt[i];
node[i].id = i;
}
std::sort(node + 1, node + 1 + n);
for(int i=1, x, y; i<=n; i++){
boss = x = node[i].id;
for(int e=head[x]; e; e=edg[e].nxt){
y = edg[e].to;
if(inpt[y] < inpt[x]){
if(boss == x){
boss = y;
mmerge(boss, x);
}
else{
mmerge(boss, y);
}
}
}
num[ffind(boss)] += 1;
}
for(int x=1, xx; x<=n; x++){
xx = ffind(x);
printf("%d\n", num[xx] - gap[x]);
}
memset(num, 0, sizeof(int) * (n + 1));
memset(gap, 0, sizeof(int) * (n + 1));
memset(head, 0, sizeof(int) * (n + 1));
}
return 0;
}

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

刚开始查阅资料看别人的贪吃蛇代码，看得一头雾水，比如：
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), c);
这是个什么玩意儿？
于是只能先去查阅一些资料。

1.技术支持

在稍微了解了控制台API函数后，发现这一堆巨长的字母也就是这么回事，虽然没背过，但拿过来用还是可以的。

移动光标的函数
个人感觉这个算比较重要的

​
void Gotoxy(int x, int y)
{
COORD position = { y, x };
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), position);
}

更改字体颜色的函数
这个可以不要，纯粹是为了好看

​
int color(int c)
{
//SetConsoleTextAttribute是API设置控制台窗口字体颜色和背景色的函数
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), c);
return 0;
}

隐藏光标的函数
在制作的过程中发现光标一闪一闪的很碍眼，最初的操作是在不需要在地图上打印东西时把光标移动到（0，0），但发现有时候光标还是会在地图内闪烁，于是加入了这个函数（这里对我来说有一个问题，会在“遗留问题部分说明”）

​
void cursor_visible(int size,int visible)
{
CONSOLE_CURSOR_INFO cursor_info;
cursor_info.bVisible=visible;
cursor_info.dwSize=size;
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}

其他
笔者自己的理解：
fflush(stdin);清空缓冲区
system(“cls”);刷屏
_kbhit() 相应键盘输入
getch() 接收字符

2.前期设定

设置一些基本的要素，如一些宏定义，全局变量，蛇与食物的结构体，函数声明，下面的代码中有一些时一开始就写上的，有一些是边写边加的（做完之后发现相较于最初的设想，改了好多东西）。
我把它们写在了自己的头文件head.h里：

​
#ifndef HEAD_H_INCLUDED
#define HEAD_H_INCLUDED
#define TALL 30//地图高度
#define DBW 68//地图宽度
#define SNAKE_MAXLEN 500//蛇的极限长度（用于定义数组）
#define SNAKE_INI_LEN 4
#define SNAKE_INI_DELAY 200
void cursor_visible(int,int);
int color(int);
void Gotoxy(int,int);
void welcome(void);
void printboard(void);
void printnotes(void);
void printsnake(void);
void printfood(void);
void snakemove(void);
int jgameover(void);
void gameover(int);
int jeat(void);
void repr_info(void);
int score;
struct
{
int x[SNAKE_MAXLEN];
int y[SNAKE_MAXLEN];
int delay;
int len;//目前蛇的长度
int dire;//direction蛇的移动方向
}snake;
struct
{
int x;
int y;
}food;
#endif // HEAD_H_INCLUDED

看别人写的贪吃蛇都没有用数组来记录蛇的位置，（猜）可能是因为数组会占用连续的空间，这样不太好。
（2020.04.15更新：他们都用的链表，当时我都没听过这东西）

3.着手实现

显示最初界面的函数

​
void welcome(void)
{
color(6);
Gotoxy(3,10);
printf(“欢迎来到真·终极蛇皮上帝视角之皮死人不偿命之来回咕畜之贪吃蛇！”);
Gotoxy(6,10);
printf(“不温馨的提示：请先把游戏窗口调整至"足够大”，否则后果自负");
Gotoxy(9,10);
printf(“按E可赛艇… 我是指按任意键开始游戏。”);
Gotoxy(12,10);
color(7);
system(“pause”);
}

效果图
![效果图](https://img-blog.csdnimg.cn/2020020420582644.png?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)
画地图
发现代码写得好粗啊，浪费资源

​
void printboard(void)
{
int i,j;
system(“cls”);
color(9);
for(i=0;i<=TALL;i++)
for(j=0;j<=DBW;j+=2)
if(i0||iTALL||j0||jDBW)
{
Gotoxy(i,j);
printf(“■”);
}
color(7);
}

显示地图之外的一些信息

​
void printnotes(void)
{
color(2);
Gotoxy(3,74);
printf(“当前得分：%d”,score);
Gotoxy(4,74);
printf(“当前蛇长：%d节”,SNAKE_INI_LEN);
Gotoxy(8,74);
printf(“当前难度：较为平和”);
Gotoxy(9,74);
printf(“等待延迟：%d ms（最小为20ms）”,SNAKE_INI_DELAY);
//Gotoxy(12,74);
//printf(“历史最高分为：”);
color(7);
}

画静态蛇

​
void printsnake(void)
{
snake.x[0]=TALL/2;
snake.y[0]=DBW/2;
snake.delay=SNAKE_INI_DELAY;
snake.len=SNAKE_INI_LEN;
snake.dire=‘w’;
Gotoxy(snake.x[0],snake.y[0]);
printf(“⊙”);
for(int i=1;i<4;i++)
{
snake.x[i]=snake.x[i-1];
snake.y[i]=snake.y[i-1]+2;
Gotoxy(snake.x[i],snake.y[i]);
printf(“■”);
}

随机生成食物
要通过一些措施保证食物在地图之内，而且还不能出现在蛇的身上。（这里也存在一个问题，会在之后的“遗留问题”部分说明。）
需要注意一个细节，‘■’会横向占用两个字节，所以要让它们统一在偶数坐标生成

​
void printfood(void)
{
food.x=rand()%(TALL-2)+1;
food.y=rand()%(DBW-4)+2;
if(food.y%2)
food.y++;
int notput=1;
while(notput)
{
for(int i=0;i<snake.len;i++)
{
if(!(food.xsnake.x[i]&&food.ysnake.y[i]))
{
Gotoxy(food.x,food.y);
printf(“奥”);
notput=0;
break;
}
}
}
}

蛇的移动
思路是先记录蛇最后一节的位置，用“
”（两个空格）覆盖蛇尾，在蛇的移动方向的下一个位置画蛇头，如果蛇吃到了食物，则在擦去的地方给蛇补充一节，一些相应的信息也要作改变
查阅资料得到了_kbhit()和getch()的用法，_kbhit()可以响应键盘输入（大概），getch()可以接收字符，由于作者的了解也不深入，所以不多说。
PS:隐藏光标的操作是后来加上的，导致某些移动光标的操作纯属多余

​
void snakemove(void)
{
int lastx=snake.x[snake.len-1],lasty=snake.y[snake.len-1];
if(_kbhit())
{
fflush(stdin);
snake.dire=getch();
}
for(int i=snake.len-1;i>0;i–)
{
snake.x[i]=snake.x[i-1];
snake.y[i]=snake.y[i-1];
}
switch(snake.dire)
{
case ‘w’:
case ‘W’:
snake.x[0]-=1;
break;
case ‘S’:
case ‘s’:
snake.x[0]+=1;
break;
case ‘A’:
case ‘a’:
snake.y[0]-=2;
break;
case ‘D’:
case ‘d’:
snake.y[0]+=2;
break;
}
Gotoxy(snake.x[1],snake.y[1]);
printf(“■”);
Gotoxy(snake.x[0],snake.y[0]);
printf(“⊙”);
if(jeat())
{
score++;
if(snake.len<SNAKE_MAXLEN)
snake.len++;
if(snake.delay>=22)
snake.delay-=2;
snake.x[snake.len-1]=lastx;
snake.y[snake.len-1]=lasty;
printfood();
repr_info();
}
else
{
Gotoxy(lastx,lasty);
printf(" ");
}
Gotoxy(0,0);
}

在蛇吃到食物后，改变一些显示信息
reprint information

​
void repr_info(void)
{
Gotoxy(3,84);
color(2);
printf("%d",score);
Gotoxy(4,84);
printf("%d",snake.len);
Gotoxy(8,84);
if(snake.delay>=170)
printf(“较为平和”);
else if(snake.delay>=120)
printf(“略高一筹”);
else if(snake.delay>=90)
printf(“考验手速”);
else if(snake.delay>=50)
printf(“高能预警”);
else if(snake.delay>=22)
printf(“终极蛇皮”);
else
printf("MAX “);
Gotoxy(9,84);
printf(”%d ",snake.delay);
color(7);
}

检验是否吃到食物
judge eat

​
int jeat(void)
{
if(food.xsnake.x[0]&&food.ysnake.y[0])
return 1;
return 0;
}

检验蛇是否死亡

​
int jgameover(void)
{
if(snake.x[0]==TALL||snake.x[0]==0||snake.y[0]==0||snake.y[0]==DBW)
return 1;
for(int i=1;i<snake.len;i++)
{
if(snake.x[0]==snake.x[i]&&snake.y[0]==snake.y[i])
return 2;
}
return 0;
}

打印死亡后显示的一些东西

​
void gameover(int j)
{
Gotoxy(20,75);
printf(“Game over\n”);
Gotoxy(21,73);
if(j1)
printf(“死因：铁齿铜牙与头铁”);
else if(j2)
printf(“死因：我吃我自己”);
}

以下是所有代码

头文件

​
#ifndef HEAD_H_INCLUDED
#define HEAD_H_INCLUDED
#define TALL 30//地图高度
#define DBW 68//地图宽度
#define SNAKE_MAXLEN 500//蛇的极限长度（用于定义数组）
#define SNAKE_INI_LEN 4
#define SNAKE_INI_DELAY 200
void cursor_visible(int,int);
int color(int);
void Gotoxy(int,int);
void welcome(void);
void printboard(void);
void printnotes(void);
void printsnake(void);
void printfood(void);
void snakemove(void);
int jgameover(void);
void gameover(int);
int jeat(void);
void repr_info(void);
int score;
struct
{
int x[SNAKE_MAXLEN];
int y[SNAKE_MAXLEN];
int delay;
int len;//目前蛇的长度
int dire;//direction蛇的移动方向
}snake;
struct
{
int x;
int y;
}food;

​
#endif // HEAD_H_INCLUDED

​
​

源文件

主函数单独写了

​
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <unistd.h>
#include <time.h>
#include <string.h>
#include “head.h”
void cursor_visible(int size,int visible)
{
CONSOLE_CURSOR_INFO cursor_info;
cursor_info.bVisible=visible;
cursor_info.dwSize=size;
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}
int color(int c)
{
//SetConsoleTextAttribute是API设置控制台窗口字体颜色和背景色的函数
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), c);
return 0;
}
void Gotoxy(int x, int y)
{
COORD position = { y, x };
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), position);
}
void welcome(void)
{
color(6);
Gotoxy(3,10);
printf(“欢迎来到真·终极蛇皮上帝视角之皮死人不偿命之来回咕畜之贪吃蛇！”);
Gotoxy(6,10);
printf(“不温馨的提示：请先把游戏窗口调整至"足够大”，否则后果自负");
Gotoxy(9,10);
printf(“按E可赛艇… 我是指按任意键开始游戏。”);
Gotoxy(12,10);
color(7);
system(“pause”);
}
void printboard(void)
{
int i,j;
system(“cls”);
color(9);
for(i=0;i<=TALL;i++)
for(j=0;j<=DBW;j+=2)
if(i0||iTALL||j0||jDBW)
{
Gotoxy(i,j);
printf(“■”);
}
color(7);
}
void printnotes(void)
{
color(2);
Gotoxy(3,74);
printf(“当前得分：%d”,score);
Gotoxy(4,74);
printf(“当前蛇长：%d节”,SNAKE_INI_LEN);
Gotoxy(8,74);
printf(“当前难度：较为平和”);
Gotoxy(9,74);
printf(“等待延迟：%d ms（最小为20ms）”,SNAKE_INI_DELAY);
//Gotoxy(12,74);
//printf(“历史最高分为：”);
color(7);
}
void printsnake(void)
{
snake.x[0]=TALL/2;
snake.y[0]=DBW/2;
snake.delay=SNAKE_INI_DELAY;
snake.len=SNAKE_INI_LEN;
snake.dire=‘w’;
Gotoxy(snake.x[0],snake.y[0]);
printf(“⊙”);
for(int i=1;i<4;i++)
{
snake.x[i]=snake.x[i-1];
snake.y[i]=snake.y[i-1]+2;
Gotoxy(snake.x[i],snake.y[i]);
printf(“■”);
}

}
void printfood(void)
{
    food.x=rand()%(TALL-2)+1;
    food.y=rand()%(DBW-4)+2;
    if(food.y%2)
        food.y++;
    int notput=1;
    while(notput)
    {
        for(int i=0;i<snake.len;i++)
        {
            if(!(food.x==snake.x[i]&&food.y==snake.y[i]))
            {
                Gotoxy(food.x,food.y);
                printf("奥");
                notput=0;
                break;
            }
        }
    }
}
void snakemove(void)
{
    int lastx=snake.x[snake.len-1],lasty=snake.y[snake.len-1];
    if(_kbhit())
    {
        fflush(stdin);
        snake.dire=getch();
    }
    for(int i=snake.len-1;i>0;i--)
    {
        snake.x[i]=snake.x[i-1];
        snake.y[i]=snake.y[i-1];
    }
    switch(snake.dire)
    {
    case 'w':
    case 'W':
        snake.x[0]-=1;
        break;
    case 'S':
    case 's':
        snake.x[0]+=1;
        break;
    case 'A':
    case 'a':
        snake.y[0]-=2;
        break;
    case 'D':
    case 'd':
        snake.y[0]+=2;
        break;
    }
    Gotoxy(snake.x[1],snake.y[1]);
    printf("■");
    Gotoxy(snake.x[0],snake.y[0]);
    printf("⊙");
    if(jeat())
    {
        score++;
        if(snake.len<SNAKE_MAXLEN)
            snake.len++;
        if(snake.delay>=22)
            snake.delay-=2;
        snake.x[snake.len-1]=lastx;
        snake.y[snake.len-1]=lasty;
        printfood();
        repr_info();
    }
    else
    {
        Gotoxy(lastx,lasty);
        printf("  ");
    }
    Gotoxy(0,0);
}
int jgameover(void)
{
    if(snake.x[0]==TALL||snake.x[0]==0||snake.y[0]==0||snake.y[0]==DBW)
        return 1;
    for(int i=1;i<snake.len;i++)
    {
        if(snake.x[0]==snake.x[i]&&snake.y[0]==snake.y[i])
            return 2;
    }
    return 0;
}
void gameover(int j)
{
    Gotoxy(20,75);
    printf("Game over\n");
    Gotoxy(21,73);
    if(j==1)
        printf("死因：铁齿铜牙与头铁");
    else if(j==2)
        printf("死因：我吃我自己");
}
int jeat(void)
{
    if(food.x==snake.x[0]&&food.y==snake.y[0])
        return 1;
    return 0;
}
void repr_info(void)
{
    Gotoxy(3,84);
    color(2);
    printf("%d",score);
    Gotoxy(4,84);
    printf("%d",snake.len);
    Gotoxy(8,84);
    if(snake.delay>=170)
        printf("较为平和");
    else if(snake.delay>=120)
        printf("略高一筹");
    else if(snake.delay>=90)
        printf("考验手速");
    else if(snake.delay>=50)
        printf("高能预警");
    else if(snake.delay>=22)
        printf("终极蛇皮");
    else
        printf("MAX     ");
    Gotoxy(9,84);
    printf("%d  ",snake.delay);
    color(7);
}

​

主函数

​
int main()
{
cursor_visible(25,0);
score=0;
srand(time(NULL));
welcome();
printboard();
printnotes();
printsnake();
printfood();
while(1)
{
int j;
snakemove();
if(j=jgameover())
{
gameover(j);
break;
}
Sleep(snake.delay);
}
Gotoxy(TALL+1,0);
cursor_visible(25,1);
system(“pause”);
return 0;
}

​

游戏效果图
![游戏效果图](https://img-blog.csdnimg.cn/20200204215133333.png?x-oss-
process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dsZGNtenk=,size_16,color_FFFFFF,t_70)

遗留问题

1.关于随机生成食物（程序问题）
笔者认为已经对食物的出现未知作出了判断，但在实际操作过程中还是会出现食物生成在蛇身上的状况

2.关于光标隐藏（知识盲点）
笔者最早的光标移动函数是这么写的

​
void cursor_visible(int visible)
{
CONSOLE_CURSOR_INFO cursor_info;
cursor_info.bVisible=visible;
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}

但发现通过cursor_visible(0);这个操作并不能隐藏光标。
本着一本正经乱改的心态改成了这样

​
void cursor_visible(int size,int visible)
{
CONSOLE_CURSOR_INFO cursor_info;
cursor_info.bVisible=visible;
cursor_info.dwSize=size;
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}

笔者认为调节光标尺寸应该与是否隐藏光标没什么关系，然而事实却是即使使用光标的默认尺寸25（即不对光标尺寸做更改），通过cursor_visible(25，0);也可以隐藏光标。

3.当快速连续有效输入（程序问题）
当快速连续按下方向键，比如“sdsdsdsdsdsdsdsdsdsdsd”，（猜）可能有大量的字符留在缓冲区，使蛇“延迟”，不听操作，但笔者暂时不会修正这个bug。

4.蛇可以直接反向撞自己导致死亡
可能需要加入一些限制，比如snake.dire=‘w’时不能直接反向改变其值为’s’

5.可能还存在众多未发现的问题

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

我只会看题解和抄题解

普通搜索在这道题中存在的问题

一共最多有40场比赛，每一场比赛有看和不看2种选择，如果求看40场比赛一共有多少选择，最多有2^40种可能性，时间复杂度太高。

折半搜索思路

1.把这40场比赛拆开，看成2个20场的比赛分别进行常规搜索。但是这两次常规搜索得到的所有的可能性所花费的金钱都要用数组记录下来。（
数组中记录的是所有的可能性所花费的金钱，若金钱有相同的，也会重复记录下来，因为我们不是要找到所有的花费数目，而是找到所有的看比赛的可能性花费的金钱）
2.把其中一个用于记录的数组排序。
3.遍历另一个没排序的数组,假设其为s[]。s[i]表示在s[]数组涵盖的一半的场次中的第i个可能性所花费的金钱，m-s[i]表示当第i个的可能性发生时可以花费在另外一半的场次中的金钱。于是可以对排过序的数组折半查找m-s[i]这个数。找到的位置前面有多少个元素，一半场次的第i个可能性便在所有的场次中拥有几种可能性。

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
typedef long long int LL;
LL s1[2000000],s2[2000000];
int n;
LL m;
LL qu[45];
int cnt1,cnt2;
LL ans;

void dfs(int l,int r,int &cnt,LL total,LL s[])
{
   if(m < total) return;
   if(l>r){
      s[++cnt] = total;
      //std::cout << "cnt=" << cnt << " s[" << cnt << "]=" << s[cnt] << std::endl;
      return ;
   }
   dfs(l+1,r,cnt,total,s);
   dfs(l+1,r,cnt,total+qu[l],s);
}

int main()
{
   scanf("%d%lld",&n,&m);
   for(int i=1; i<=n; i++){
      scanf("%lld",&qu[i]);
   }
   int mid = (1+n) >> 1;
   cnt1 = cnt2 = ans = 0;
   dfs(1,mid,cnt1,0,s1);
   dfs(mid+1,n,cnt2,0,s2);
   std::sort(s1+1,s1+cnt1+1);
   for(int i=1; i<=cnt2; i++){
      LL left = m-s2[i];
      if(left >= 0 ){
      //最开始忘了加等号，导致当s2[i]=m(金钱上限)时，不会统计在s2看m块钱，不在s1看的情况
      //其实这个if不用要，刚开始啥也不会，就瞎写的。
         int ii = std::upper_bound(s1+1,s1+1+cnt1,left)-(s1+1);
         //std::cout << "s2[" << i << "]有" << ii << "种情况" << std::endl;
         ans += ii;
      }
   }
   printf("%lld",ans);

   return 0;
}

​

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

Tree and Permutation HUD6446

题目大意

给你一颗n个点的树， 有边权，求这个东西：
Σ i = 1 n Σ j = 1 n d i s [ i t o j ] ∗ ( n − 1 ) ! \Sigma_{i = 1} ^n
\Sigma_{j = 1}^n dis[i_toj] * (n - 1) ! Σi=1n​Σj=1n​dis[i to j]∗(n−1)!

换根dp

用换根dp算前面一坨， 然后 * (n - 1)!
先dfs（类似树形dp）求任意一个点a到所有点的距离part[a]。
然后可以由已知点x的答案part[x]做简单变换， 推导出与x相邻的未知答案的点集Y (向量)的答案part[Y] (向量)， 所以又是一次DFS
然后对所有part求Sigma， 再乘 (n-1)! 记得取模。 完毕。

代码

​
#include <bits/stdc++.h>
const int N = 1e5 + 4, MOD = 1e9 + 7;
int n, u, v, ipart = 1, idx;
int size[N], head[N];
long long dis[N], part[N], re, w;
struct Edge{ int to, nxt; long long w; }edg[N << 1];
inline void addE(int fr, int to, long long w){
edg[++ idx] = (Edge){to, head[fr], w}; head[fr] = idx;
edg[++ idx] = (Edge){fr, head[to], w}; head[to] = idx;
}
void dfs(int x, int fa){
size[x] = 1;
for(int e=head[x]; e; e=edg[e].nxt){
int y = edg[e].to;
if(y == fa) continue;
dis[y] = dis[x] + edg[e].w;
dfs(y, x);
size[x] += size[y];
}
part[ipart] = (part[ipart] + dis[x]) % MOD;
}
void dfsN(int x, int fa){
re = (re + part[x]) % MOD;
for(int e=head[x]; e; e=edg[e].nxt){
int y = edg[e].to;
if(y == fa) continue;
part[y] = part[x] + (n - (size[y] << 1)) * edg[e].w;
dfsN(y, x);
}
}
int main(){
while(scanf("%d", &n) != EOF){
idx = 1, re = 0, part[ipart] = 0;
memset(head, 0, sizeof(head));
memset(size, 0, sizeof(size));
memset(dis, 0, sizeof(dis));
for(int i=1; i<n; i++){
scanf("%d%d%d", &u, &v, &w);
addE(u, v, w);
}
dfs(ipart, -1);
dfsN(ipart, -1);
re = (re + MOD) % MOD;
for(int i=n-1; i>=1; i–) re = re * i % MOD;
printf("%lld\n", re);
}
return 0;
}

描述

There are N vertices connected by N−1 edges, each edge has its own length.
The set { 1,2,3,…,N } contains a total of N! unique permutations, let’s say
the i-th permutation is Pi and Pi,j is its j-th number.
For the i-th permutation, it can be a traverse sequence of the tree with N
vertices, which means we can go from the Pi,1-th vertex to the Pi,2-th vertex
by the shortest path, then go to the Pi,3-th vertex ( also by the shortest
path ) , and so on. Finally we’ll reach the Pi,N-th vertex, let’s define the
total distance of this route as D(Pi) , so please calculate the sum of D(Pi)
for all N! permutations.

Input

There are 10 test cases at most.
The first line of each test case contains one integer N ( 1≤N≤105 ) .
For the next N−1 lines, each line contains three integer X, Y and L, which
means there is an edge between X-th vertex and Y-th of length L (
1≤X,Y≤N,1≤L≤109 ) .

Output

For each test case, print the answer module 109+7 in one line.

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

洛谷 P2602 [ZJOI2010]数字计数

​
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

洛谷 P2657 [SCOI2009] windy 数

抄完数字计数之后照葫芦画瓢做的这道题，遂去看了题解。
离AC只差一句题解上抄来的 if(std::abs(dig[i+1]-dig[i]) <= 1)
break;，因为函数的参数可能就是一个非windy数，你需要找出这个比这个非windy数小的所有的的windy数，当if(std::abs(dig[i+1]-dig[i])
<= 1) break;这个条件满足时，之后找到的就必然时非windy数了，自然不需要继续找。
之前我自己的类似的判断思路错了，写题解的人yyds

​
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

说明 - 2022-05-05

本篇博客为本人原创, 原发布于CSDN, 在搭建个人博客后使用爬虫批量爬取并挂到个人博客, 出于一些技术原因博客未能完全还原到初始版本(而且我懒得修改), 在观看体验上会有一些瑕疵 ,若有需求会发布重制版总结性新博客。发布时间统一定为1111年11月11日。钦此。

<https://pintia.cn/problem-
sets/994805046380707840/problems/994805048482054144>

#L3-014 周游世界 (30分)

周游世界是件浪漫事，但规划旅行路线就不一定了……
全世界有成千上万条航线、铁路线、大巴线，令人眼花缭乱。所以旅行社会选择部分运输公司组成联盟，每家公司提供一条线路，然后帮助客户规划由联盟内企业支持的旅行路线。本题就要求你帮旅行社实现一个自动规划路线的程序，使得对任何给定的起点和终点，可以找出最顺畅的路线。所谓“最顺畅”，首先是指中途经停站最少；如果经停站一样多，则取需要换乘线路次数最少的路线。

输入格式：

输入在第一行给出一个正整数N（≤100），即联盟公司的数量。接下来有N行，第i行（i=1,⋯,N）描述了第i家公司所提供的线路。格式为：

M S[1] S[2] ⋯ S[M]

其中M（≤100）是经停站的数量，S[i]（i=1,⋯,M）是经停站的编号（由4位0-9的数字组成）。这里假设每条线路都是简单的一条可以双向运行的链路，并且输入保证是按照正确的经停顺序给出的
——
也就是说，任意一对相邻的S[i]和S[i+1]（i=1,⋯,M−1）之间都不存在其他经停站点。我们称相邻站点之间的线路为一个运营区间，每个运营区间只承包给一家公司。环线是有可能存在的，但不会不经停任何中间站点就从出发地回到出发地。当然，不同公司的线路是可能在某些站点有交叉的，这些站点就是客户的换乘点，我们假设任意换乘点涉及的不同公司的线路都不超过5条。

在描述了联盟线路之后，题目将给出一个正整数K（≤10），随后K行，每行给出一位客户的需求，即始发地的编号和目的地的编号，中间以一空格分隔。

输出格式：

处理每一位客户的需求。如果没有现成的线路可以使其到达目的地，就在一行中输出“Sorry, no line is
available.”；如果目的地可达，则首先在一行中输出最顺畅路线的经停站数量（始发地和目的地不包括在内），然后按下列格式给出旅行路线：

Go by the line of company #X1 from S1 to S2.
Go by the line of company #X2 from S2 to S3.
…
其中Xi是线路承包公司的编号，Si是经停站的编号。但必须只输出始发地、换乘点和目的地，不能输出中间的经停站。题目保证满足要求的路线是唯一的。

输入样例：

4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
4
3011 3013
6666 2001
2004 3001
2222 6666

输出样例：

2
Go by the line of company #3 from 3011 to 3013.
10
Go by the line of company #4 from 6666 to 1306.
Go by the line of company #3 from 1306 to 2302.
Go by the line of company #2 from 2302 to 2001.
6
Go by the line of company #2 from 2004 to 1204.
Go by the line of company #1 from 1204 to 1306.
Go by the line of company #3 from 1306 to 3001.
Sorry, no line is available.

解析：

这道题要求的是 最少换乘最短路 ，且题目告诉答案唯一，不同时存在多个正确答案。

bfs找最短路很简单，最少换乘最短路只需要在普通的找最短路的基础上修改亿点点。
。
。
。

在普通找最短路的基础上加入ch[10005]数组表示“到这个点所需要的最少的换乘次数”，开局全初始化为非常大；加入sta[10005][6]数组，sta[i]数组表示负责
“ 从出发站到站点i 有最短路径 的路线的 与站点i相邻 的一段路 ” 的公司
（假设a，b，c路线都可以从始发站到达i，但是a，b路线上只有三个点，c路线上有4个点，则sta[i]数组中只存负责路线a的公司和负责路线b的公司）

（建边时，边要记录这条边是哪一个公司负责的）
在bfs遍历无向图的同时，检查边的起点的sta数组是否存有这个公司，如果有，则边的终点的ch数组继承起点ch数组的值，如果没有，则ch[终点]=ch[起点]+1
对于这条理论，除了始发站不满足之外，其他的站点都满足，而始发站到任何一点都会不管三七二十一直接计一次换乘，所以要设置ch[始发站]=-1（因为sta是在bfs中构建的，当然也可以先填充始发站sta）

因为题目告诉我们答案唯一，所以bfs完之后直接以终点站为起点进行反向搜索，只需要满足最短路径和最短换乘，就一定能得到答案。
最短路径好说，最小换乘为：若站点换乘 要求 ch[a]+1=ch[b] 否则要求ch[a]=ch[b]

代码

​
#include
#include
#include
#include
const int maxn=10005;

struct Edge
{
    int to,nxt,id;
}edge[maxn<<1];

int n,m,vv1,vv2;
int idx,cnt,base,nums;
int head[maxn],tm[maxn],ch[maxn],sta[maxn][6];
int ans[maxn][3];

​
void pr(int x)
{
if(x<10) std::cout << “000” << x;
else if(x<100) std::cout << “00” << x;
else if(x<1000) std::cout << “0” << x;
else std::cout << x;
}

void init()
{
    idx=-1;
    memset(head,-1,sizeof(head));
}

​
void addEdge(int fr,int to,int id)
{
edge[++idx].id=id;
edge[idx].to=to;
edge[idx].nxt=head[fr];
head[fr]=idx;
}

​
​
void solve(int st,int ed)
{
std::queueq;
cnt=-1;
memset(tm,1,sizeof™);
memset(ch,1,sizeof(ch));
memset(sta,0,sizeof(sta));
tm[st]=0;
ch[st]=-1;
q.push(st);
int cur,to;
while(!q.empty())
{
cur=q.front(); q.pop();
for(int i=head[cur]; i!=-1; i=edge[i].nxt)
{
to=edge[i].to;
if(tm[cur]+1 <= tm[to])
{
tm[to]=tm[cur]+1;
//--------------------------------------------------------------------
int r;
for(r=1; r<=sta[cur][0]; r++) if(edge[i].idsta[cur][r]) break;
if(r>sta[cur][0]) ch[to]=std::min(ch[cur]+1,ch[to]);
else ch[to]=std::min(ch[cur],ch[to]);
for(r=1; r<=sta[to][0]; r++) if(edge[i].idsta[to][r]) break;
if(r>sta[to][0])
{
sta[to][0]+=1;
sta[to][sta[to][0]]=edge[i].id;
}
if(toed) continue;
//--------------------------------------------------------------------
q.push(to);
}
}
}
q.push(ed);
base=ed;
nums=-1;
while(!q.empty())
{
nums+=1;
cur=q.front(); q.pop();
if(curst)
{
std::cout << nums << std::endl;
//忘记了输出要逆序，螺旋暴毙
//站点是由四位数字组成的，如果开头是0，则需要补0，忘了这事直接永恒暴毙
for(int i=cnt; i>=0; i–)
{
std::cout << “Go by the line of company #” << ans[i][0] << " from ";
pr(ans[i][1]);
std::cout << " to ";
pr(ans[i][2]);
std::cout << “.” << std::endl;
}

            return;
        }
//这里for循环中第三部分写成了i++，当场暴毙
        for(int i=head[cur]; i!=-1; i=edge[i].nxt)
        {
            to=edge[i].to;
            if(to==st)
            {
                ans[++cnt][0]=edge[i].id;
                ans[cnt][1]=to;
                ans[cnt][2]=base;
                q.push(to);
                break;
            }
//这里下一行的最短路径判断忘了加了，再次暴毙
            if(tm[to]+1==tm[cur])
            {
                int r;
                for(r=1; r<=sta[to][0]; r++) if(sta[to][r]==edge[i].id) break;
                if(r>sta[to][0])
                {
                    if(ch[to]+1==ch[cur])
                    {
                        ans[++cnt][0]=edge[i].id;
                        ans[cnt][1]=to;
                        ans[cnt][2]=base;
                        base=to;
                        q.push(to);
                        break;
                    }
                }
                else
                {
                    if(ch[to]==ch[cur])
                    {
                        q.push(to);
                        break;
                    }
                }
            }
        }
    }
    std::cout << "Sorry, no line is available." << std::endl;
}

​
int main()
{
init();
std::cin >> n;
for(int i=1; i<=n; i++)
{
std::cin >> m >> vv1;
for(int j=2; j<=m; j++)
{
std::cin >> vv2;
addEdge(vv1,vv2,i);
addEdge(vv2,vv1,i);
vv1=vv2;
}
}
std::cin >> n;
while(n–)
{
std::cin >> vv1 >> vv2;
solve(vv1,vv2);
}
return 0;
}

​