欢迎你常来我网站玩，玩累了就直接睡觉，没问题的

之前python课程设计的作业
没有什么新意，就是用python写了个合成大罗马
不过自己对库的使用理解更深了

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

from pygame.draw import rect
import pymunk
import random
import pygame
import pickle
from moviepy.editor import VideoFileClip
import math
import time
from PIL import Image
from pymunk import pygame_util
import sys

from pymunk.vec2d import Vec2d

space = pymunk.Space()
space.gravity = (0,900)
Gsp = []
Fruit = [5, 10, 15, 21, 23, 29, 35, 37, 50, 59, 60, 78]
clock = pygame.time.Clock()

def initgame():
    pygame.font.init()
    pygame.init()
    pygame.mixer.init()
    screen = pygame.display.set_mode((640,800))
    pygame.display.set_caption("合成正统罗马")
    return screen

class CircleSprite(pygame.sprite.Sprite):
    def __init__(self, target):
        pygame.sprite.Sprite.__init__(self)
        self.image = None


class ball(CircleSprite):
    def __init__(self, num, position, space, friction=0.1):
        pygame.sprite.Sprite.__init__(self)
        self.mass = Fruit[num] * 2
        self.r = Fruit[num] * 2
        self.angle_degree = 0
        self.images = 'image\\罗马\\'+str(num)+'.png'
        self.image = pygame.image.load(self.images)
        self.image = pygame.transform.smoothscale(self.image, (self.r * 2, self.r * 2))
        self.rect = self.image.get_rect()
        self.rect.x,self.rect.y = position
        self.radius = num
        self.num = num
        self.position = position
        moment = pymunk.moment_for_circle(self.mass, 0, self.r)
        self.body = pymunk.Body(self.mass, moment)
        self.body.position = position
        self.shape = pymunk.Circle(self.body, self.r)
        self.shape.friction = friction
        self.elasticity = 0.95
        self.shape.collision_type = 1
        self.shape.sprite = self
        space.add(self.body, self.shape)
        self.space = space
        self.count = 0
        self.gameover = 0
        self.isclash = 0

    def draw(self, screen):
        screen.blit(self.image, (self.body.position.x - self.image.get_width() / 2, self.body.position.y - self.image.get_height() / 2))

    def update_position(self, x, y, angle_degree=0):
        self.rect.x = self.body.position[0]
        self.rect.y = self.body.position[1]
    def update(self):
        img2 = pygame.transform.rotate(self.image,-math.degrees(self.body.angle))
        self.update_position(self.position[0],self.position[1])
        screen.blit(img2, (self.body.position.x - img2.get_width() / 2, self.body.position.y - img2.get_height() / 2))
        if(self.body.position.y < 120):
            self.count += 1
def load_data():
    # 加载历史最高分
    file_path = "score.txt"
    with open(file_path, "r") as f:
        try:
            high_score = int(f.read())
        except:
            high_score = 0
    return high_score
    
lines = pygame.image.load("image\\line.png")

static_lines = [
        pymunk.Segment(space.static_body, (0, 0), (0, 1000), 0.0),
        pymunk.Segment(space.static_body, (640, 0), (640, 800), 0.0),
        pymunk.Segment(space.static_body, (0, 800), (640, 800), 0.0)
        ]

for line in static_lines:
            line.elasticity = 0.4  # 弹性系数
            line.friction = 0.2  # 摩擦系数
            space.add(line)

if __name__ == '__main__':
    screen = initgame()
    over = pygame.mixer.Sound("image\\ceddin deden.mp3")
    music = pygame.mixer.Sound("sound.wav")
    bg_img = pygame.image.load("back.png")
    rd = [2, 4, 8, 16, 32, 64]
    num = 1
    maxtype = 1
    flag = 0
    GaO = 0
    high_score = load_data()
    randomnum = 1
    count = 0
    ico = pygame.image.load("苏丹.ico")
    pygame.display.set_icon(ico) # 可以填img
    gameover = pygame.image.load('image\\GO.png')
    myfont = pygame.font.Font('Astrid.ttf', 60)
    clip = VideoFileClip('抬棺.mp4') #视频加载
    score = 0
    nextfruit = pygame.image.load('image\\罗马\\'+str(num)+'.png')
    while 1:
        if(GaO == 0):
            space.step(1/60) 
            if flag == 1:
                x,y = pygame.mouse.get_pos()
                b = ball(num, (x, 0), space)
                Gsp.append(b)
                flag = 0
            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    pygame.quit()
                    sys.exit()
                if event.type == pygame.MOUSEBUTTONDOWN:
                    flag = 1
                    num = randomnum
                    randomnum = random.randint(1,maxtype)
                    nextfruit = pygame.image.load('image\\罗马\\'+str(randomnum)+'.png')
            draw_options = pygame_util.DrawOptions(screen)
            scoreimage = myfont.render("score: " + str(score), True, (255,192,203))
            space.debug_draw(draw_options)
            screen.blit(bg_img, (0, 0))
            screen.blit(lines, (0,120))
            screen.blit(nextfruit, (0, 0))
            screen.blit(scoreimage, (270, 0))
            for i in range(0,len(Gsp)):
                Gsp[i].update()
                if(Gsp[i].radius > maxtype and maxtype<=5):
                    maxtype = Gsp[i].radius
                if Gsp[i].count > 100:
                    GaO = 1
            for i in Gsp:
                for j in Gsp:
                    det_x = j.body.position.x - i.body.position.x
                    det_y = j.body.position.y - i.body.position.y
                    if i != j and math.pow(det_x, 2) + math.pow(det_y, 2) < math.pow(i.r + j.r + 3, 2) and i.num == j.num and i.isclash==0 and j.isclash==0:
                        music.play()
                        score += i.num
                        i.isclash = 1 # 添加标记，标记过的就不再触发碰撞事件
                        j.isclash = 1
                        c = ball(i.num+1, i.body.position, space)
                        Gsp.append(c)
                        space.remove(i.body, i.shape) 
                        Gsp.remove(i) 
                        space.remove(j.body, j.shape)
                        Gsp.remove(j)     
        else:
            for i in Gsp:
                if i.isclash == 0:
                    # music.play() #结束音乐    
                    score += i.num
                    i.isclash = 1
                    space.remove(i.body, i.shape)
                    i.update()
                space.debug_draw(draw_options)
                screen.blit(bg_img, (0, 0))
            scoreimage = myfont.render("score: " + str(score), True, (255,255,255))
            screen.blit(gameover, (0, 0))
            # over.play() #结束图片
            clip.preview() #视频的播放
            if score > high_score:
                high_score = score
                screen.blit(myfont.render("New High Score: " + str(high_score), True, (255,255,255)),(85, 120))
                with open("score.txt", "w") as f:
                    f.write(str(high_score))
            else:
                screen.blit(myfont.render("High Score: " + str(high_score), True, (255,255,255)),(85, 120))
            screen.blit(scoreimage, (170, 50))       
        clock.tick(60)
        pygame.display.flip()

更改了一下，能够像是正常的贪吃蛇了。。。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

import pygame
import time
import random
from pygame.locals import *
caption_width = 500
caption_height = 500
white_color = (255, 255, 255)
black_color = (0, 0, 0)
get_title = 'Hello World'
cell = 10
snake_init_pos = [[250, 250], [240, 250], [230, 250], [220, 250]]
food_pos = [random.randrange(1, 50) * 10, random.randrange(1, 50) * 10]

pygame.init()
clock = pygame.time.Clock()
caption = pygame.display.set_mode((caption_width, caption_height))


def draw_rect(color, position):
    pygame.draw.rect(caption, color, pygame.Rect(position[0], position[1], cell, cell))


def hit_the_self():
    if snake_init_pos[0] in snake_init_pos[1:]:
        return True
    else:
        return False


def hit_the_wall(head_pos):
    if head_pos[0] >= caption_width or head_pos[0] < 0 or head_pos[1] >= caption_height or caption_height < 0:
        return True
    else:
        return False


def change_direction(head_pos):
    global food_pos
    snake_init_pos.insert(0, list(head_pos))
    if head_pos != food_pos:
        snake_init_pos.pop()
    else:
        food_pos = [random.randrange(1, 50) * 10, random.randrange(1, 50) * 10]

    if hit_the_self() or hit_the_wall(head_pos):
        print("Game Over")
        pygame.quit()


def main():
    for pos in snake_init_pos:
        draw_rect(white_color, pos)
    draw_rect(white_color, food_pos)
    pygame.display.update()
    head_pos = [250, 250]
    xcell = 0
    ycell = 0
    while 1:
        for event in pygame.event.get():
            if event.type == pygame.KEYDOWN:
                if event.key == pygame.K_LEFT:
                    print("left")
                    xcell = -cell
                    ycell = 0
                    # change_direction(head_pos)
                elif event.key == pygame.K_RIGHT:
                    print("right")
                    xcell = cell
                    ycell = 0
                    # change_direction(head_pos)
                elif event.key == pygame.K_UP:
                    print("up")
                    ycell = -cell
                    xcell = 0
                    # change_direction(head_pos)
                elif event.key == pygame.K_DOWN:
                    print("down")
                    ycell = cell
                    xcell = 0
                    # change_direction(head_pos)
                if event.key == pygame.KEYUP:
                    xcell = 0
                    ycell = 0
        if(xcell != 0):
            head_pos[0] += xcell
            change_direction(head_pos)
        if(ycell != 0):
            head_pos[1] += ycell
            change_direction(head_pos)
        caption.fill(black_color)
        draw_rect(white_color, food_pos)
        for pos in snake_init_pos:
            draw_rect(white_color, pos)

            pygame.display.update()
        clock.tick(10)


if __name__ == '__main__':
    main()

1. Database

1.1. 题目

链接：https://ac.nowcoder.com/acm/contest/11168/C
来源：牛客网

题目描述
给定一棵 n 个点的带点权的有根树，根节点为 1 。
要选出两个节点，满足任意一个不是另一个的祖先节点，最大化以两个节点为根的子树的点权和 。
如果选不出两棵合法的子树，则输出“Error”。
输入描述:
第一行一个正整数 n 。
第二行 n 个整数，分别表示 n 个点的点权 。
接下来 n - 1 行，每行两个正整数 u，v 表示 u 和 v 之间有一条连边 。
输出描述:
一个整数，表示最大的点权和

1.2. 样例输入&&样例输出

样例

1
2
3
4
5
6

5
10 -5 5 6 7
1 2
1 3
2 4
2 5

1

13

1.3. 思路

这题的题目的意思是要你找出两个父节点不一样的两个节点，使得他们的子树权和最大
这里使用dfs递归从底往上更新mx数组，mx数组的意思是mx以下的后代节点的点权和
而sum数组的意思是以u为根节点的子树权和
使用邻接表储存树即可
我们找出最大的和次大的即可

1.4. AC代码

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
52
53

#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<cstring>
#include<list>
#include<map>
#include<cstdio>
typedef long long ll;
typedef int64_t s64;
using namespace std;
const int maxn = 1e6;
ll m, n, minlen, len, cnt = 0, q,k,h;
const int MOD= 1e9 + 7;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define pre(i,r,l) for(int i=r;i>=l;i--)
const int INF=1e18;
int tot;
map<string,ll>mp;
vector<int>son[maxn];
ll w[maxn],mx[maxn],sum[maxn];
ll ans=-INF;
void dfs(int u,int fa){
    ll maxnum=-INF;sum[u]=w[u];
    for(int i=0;i<son[u].size();i++){
        int v=son[u][i];
        if(v==fa)continue;
        dfs(v,u);sum[u]+=sum[v];
        if(maxnum!=-INF)ans=max(ans,maxnum+mx[v]);
        maxnum=max(mx[v],maxnum);
    }
    mx[u]=max(maxnum,sum[u]);
}

int main(){
    int n;cin>>n;
    rep(i,1,n){
        cin>>w[i];
    }
    rep(i,1,n-1){
        int x,y;cin>>x>>y;
        son[x].push_back(y);
        son[y].push_back(x);
    }
    dfs(1,0);
    if(ans==-INF)cout<<"Error\n";
    else cout<<ans<<endl;
    system("pause");
    return 0;
}

1. 4 Values Whose Sum is Zero

1.1. 题目

链接：https://vjudge.z180.cn/problem/UVA-11054
来源：vjudge

As you may know from the comic “Asterix and the Chieftain’s Shield”, Gergovia consists of one street,
and every inhabitant of the city is a wine salesman. You wonder how this economy works? Simple
enough: everyone buys wine from other inhabitants of the city. Every day each inhabitant decides how
much wine he wants to buy or sell. Interestingly, demand and supply is always the same, so that each
inhabitant gets what he wants.
There is one problem, however: Transporting wine from one house to another results in work. Since
all wines are equally good, the inhabitants of Gergovia don’t care which persons they are doing trade
with, they are only interested in selling or buying a specific amount of wine. They are clever enough
to figure out a way of trading so that the overall amount of work needed for transports is minimized.
In this problem you are asked to reconstruct the trading during one day in Gergovia. For simplicity
we will assume that the houses are built along a straight line with equal distance between adjacent
houses. Transporting one bottle of wine from one house to an adjacent house results in one unit of
work.
Input
The input consists of several test cases. Each test case starts with the number of inhabitants n
(2 ≤ n ≤ 100000). The following line contains n integers ai (−1000 ≤ ai ≤ 1000). If ai ≥ 0, it
means that the inhabitant living in the i-th house wants to buy ai bottles of wine, otherwise if ai < 0,
he wants to sell −ai bottles of wine. You may assume that the numbers ai sum up to 0.
The last test case is followed by a line containing ‘0’.
Output
For each test case print the minimum amount of work units needed so that every inhabitant has his
demand fulfilled. You may assume that this number fits into a signed 64-bit integer (in C/C++ you
can use the data type “long long”, in JAVA the data type “long”).

1.2. 样例输入&&样例输出

1
2
3
4
5

5
5 -4 1 -3 1
6
-1000 -1000 -1000 1000 1000 1000
0

1
2

9
9000

1.3. 思路

把a+b+c+d=0的问题转化成a+b=-(c+d)问题
写一个map然后加起来即可

1.4. AC代码

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

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<sstream>
#include<map>
#include<unordered_map>
using namespace std;
const int maxn = 1000;
const int maxnn = 100000;
typedef long long ll;
int a[maxnn],b[maxnn],c[maxnn],d[maxnn];
int main() {
    int t;cin>>t;
    int kase=0;
    while(t--){
        if(kase==0)kase++;else cout<<endl;
        int n;cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
            cin>>b[i];
            cin>>c[i];
            cin>>d[i];
        }
        unordered_map<int,int>mp;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                mp[a[i]+b[j]]++;
            }
        }
        int cnt=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cnt+=mp[-(c[i]+d[j])];
            }
        }
        cout<<cnt<<endl;
    }
    system("pause");
    return 0;
}

1. Database

1.1. 题目

链接：https://vjudge.z180.cn/problem/UVA-210
来源：uva

题目描述
Programs executed concurrently on a uniprocessor system appear to be executed at the same time, but
in reality the single CPU alternates between the programs, executing some number of instructions from
each program before switching to the next. You are to simulate the concurrent execution of up to ten
programs on such a system and determine the output that they will produce.
The program that is currently being executed is said to be running, while all programs awaiting
execution are said to be ready. A program consists of a sequence of no more than 25 statements, one
per line, followed by an end statement. The statements available are listed below.
Statement Type Syntax
Assignment variable = constant
Output print variable
Begin Mutual Exclusion lock
End Mutual Exclusion unlock
Stop Execution end
A variable is any single lowercase alphabetic character and a constant is an unsigned decimal number less than 100. There are only 26 variables in
the computer system, and they are shared among
the programs. Thus assignments to a variable
in one program affect the value that might be
printed by a different program. All variables are
initially set to zero.
Each statement requires an integral number of time units to execute. The running program is
permitted to continue executing instructions for a period of time called its quantum. When a program’s
time quantum expires, another ready program will be selected to run. Any instruction currently being
executed when the time quantum expires will be allowed to complete.
Programs are queued first-in-first-out for execution in a ready queue. The initial order of the ready
queue corresponds to the original order of the programs in the input file. This order can change,
however, as a result of the execution of lock and unlock statements.
The lock and unlock statements are used whenever a program wishes to claim mutually exclusive
access to the variables it is manipulating. These statements always occur in pairs, bracketing one or
more other statements. A lock will always precede an unlock, and these statements will never be
nested. Once a program successfully executes a lock statement, no other program may successfully
execute a lock statement until the locking program runs and executes the corresponding unlock
statement. Should a running program attempt to execute a lock while one is already in effect, this
program will be placed at the end of the blocked queue. Programs blocked in this fashion lose any of their
current time quantum remaining. When an unlock is executed, any program at the head of the blocked
queue is moved to the head of the ready queue. The first statement this program will execute when
it runs will be the lock statement that previously failed. Note that it is up to the programs involved
to enforce the mutual exclusion protocol through correct usage of lock and unlock statements. (A
renegade program with no lock/unlock pair could alter any variables it wished, despite the proper use
of lock/unlock by the other programs.)

输入描述:
The input begins with a single positive integer on a line by itself indicating the number of the cases
following, each of them as described below. This line is followed by a blank line, and there is also a
blank line between two consecutive inputs.
The first line of the input file consists of seven integers separated by spaces. These integers specify
(in order): the number of programs which follow, the unit execution times for each of the five statements
(in the order given above), and the number of time units comprising the time quantum. The remainder
of the input consists of the programs, which are correctly formed from statements according to the
rules described above.
All program statements begin in the first column of a line. Blanks appearing in a statement should
be ignored. Associated with each program is an identification number based upon its location in the
input data (the first program has ID = 1, the second has ID = 2, etc.).

输出描述:
For each test case, the output must follow the description below. The outputs of two consecutive cases
will be separated by a blank line.
Your output will contain of the output generated by the print statements as they occur during the
simulation. When a print statement is executed, your program should display the program ID, a colon,
a space, and the value of the selected variable. Output from separate print statements should appear
on separate lines.

1.2. 样例输入&&样例输出

样例

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

3 3
3 1 1 1 1 1 1
a = 4
print a
lock
b = 9
print b
unlock
print b
end
a = 3
print a
lock
b = 8
print b
unlock
print b
end
b = 5
a = 17
print a
print b
lock
b = 21
print b
unlock
print b
end

1
2
3
4
5
6
7
8
9
10

1: 3
2: 3
3: 17
3: 9
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21

1.3. 思路

有很多坑点，这题的主要思想是模拟多线程运行程序，所以每一行指令要用数组来映射。。。
这题目理解难度（一定是我太菜了）还挺大的，理解了题目的要求还是有坑点，比如说lock如果没声明成全局变量也会wa
而且其实题目他是有多个样例的，但是vj和紫书上都没说，也挺坑的。。。不过写出代码后难度也就那样吧
加油！！

1.4. AC代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cmath>
#include<string>
#include<set>
#include<cstring>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define INF 9999999
#define maxn 100000
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d",x)
#define fr(i) for(i=0;i<10;i++);
queue <int>q;deque<int> dq;
int tm[5],num[maxn],h[maxn];
int n,Q;
bool lock=0;
vector<string> op[maxn];
void function(int x){
    int opt=Q;
    while(opt>0){
        string s=op[x][h[x]];
        if(s[2]=='='){
            opt-=tm[0];
            int v=s[4]-'0';
            if(s.size()==6)v=(v*10)+(s[5]-'0');
            num[s[0]]=v;
        }else if(s[2]=='i'){
            opt-=tm[1];
            cout<<x<<": "<<num[s[6]]<<endl;
        }else if(s[2]=='c'){
            opt-=tm[2];
            if(lock){
                q.push(x);
                return;
            }
            else lock=1;
        }else if(s[2]=='l'){
            lock=0;
            opt-=tm[3];
            if(!q.empty()){
                int v=q.front();
                q.pop();
                dq.push_front(v);
            }
        }
        else return;
        ++h[x];
    }
    dq.push_back(x);
}

int main() {
    int T;cin>>T;
    while(T--){
        cin>>n;
        for(int i=0;i<5;i++){
            cin>>tm[i];
        }
        cin>>Q;
        string s;
        for(int i=1;i<=n;i++){
            op[i].clear();
            while(getline(cin,s)){
                if(s=="")continue;
                op[i].push_back(s);
                if(s=="end")break;
            }
            dq.push_back(i);
        }
        memset(h,0,sizeof(h));
        memset(num,0,sizeof(num));
        while(!dq.empty()){
            int top=dq.front();
            dq.pop_front();
            function(top);
        }
        if(T)cout<<endl;
    }
	system("pause");
	return 0;
}

1. Database

1.1. 题目

链接：https://vjudge.z180.cn/problem/UVA-1592
来源：uva

题目描述
Peter studies the theory of relational databases. Table in the relational database consists of values that
are arranged in rows and columns.
There are different normal forms that database may adhere to. Normal forms are designed to
minimize the redundancy of data in the database. For example, a database table for a library might
have a row for each book and columns for book name, book author, and author’s email.
If the same author wrote several books, then this representation is clearly redundant. To formally
define this kind of redundancy Peter has introduced his own normal form. A table is in Peter’s Normal
Form (PNF) if and only if there is no pair of rows and a pair of columns such that the values in the
corresponding columns are the same for both rows.
How to compete in ACM ICPC Peter peter@neerc.ifmo.ru
How to win ACM ICPC Michael michael@neerc.ifmo.ru
Notes from ACM ICPC champion Michael michael@neerc.ifmo.ru
The above table is clearly not in PNF, since values for 2rd and 3rd columns repeat in 2nd and
3rd rows. However, if we introduce unique author identifier and split this table into two tables — one
containing book name and author id, and the other containing book id, author name, and author email,
then both resulting tables will be in PNF.
How to compete in ACM ICPC 1
How to win ACM ICPC 2
Notes from ACM ICPC champion 2
1 Peter peter@neerc.ifmo.ru
2 Michael michael@neerc.ifmo.ru
Given a table your task is to figure out whether it is in PNF or not.

输入描述:
Input contains several datasets. The first line of each dataset contains two integer numbers n and m
(1 ≤ n ≤ 10000, 1 ≤ m ≤ 10), the number of rows and columns in the table. The following n lines
contain table rows. Each row has m column values separated by commas. Column values consist of
ASCII characters from space (ASCII code 32) to tilde (ASCII code 126) with the exception of comma
(ASCII code 44). Values are not empty and have no leading and trailing spaces. Each row has at most
80 characters (including separating commas).

输出描述:
For each dataset, if the table is in PNF write to the output file a single word “YES” (without quotes).
If the table is not in PNF, then write three lines. On the first line write a single word “NO” (without
quotes). On the second line write two integer row numbers r1 and r2 (1 ≤ r1, r2 ≤ n, r1 ̸= r2), on
the third line write two integer column numbers c1 and c2 (1 ≤ c1, c2 ≤ m, c1 ̸= c2), so that values in
columns c1 and c2 are the same in rows r1 and r2

1.2. 样例输入&&样例输出

样例

1
2
3
4
5
6
7

3 3
How to compete in ACM ICPC,Peter,peter@neerc.ifmo.ru
How to win ACM ICPC,Michael,michael@neerc.ifmo.ru
Notes from ACM ICPC champion,Michael,michael@neerc.ifmo.ru
2 3
1,Peter,peter@neerc.ifmo.ru
2,Michael,michael@neerc.ifmo.ru

1
2
3
4

NO
2 3
2 3
YES

1.3. 思路

很好的题，学会了getline()以某字符为分割符的读取方式
使用方法需要使用到sstream,stringstream流ss,放置的字符串对象st,
getline(ss,st,分割符);
还有二级索引，使得比较的时间大幅度缩减，判断是否已经存在该键值，如果存在该键值则返回对应的数字键值
map<对象,int>index;
int getid(对象){
if(index.find(对象)==index.end())index[对象]=index.size();
return index[对象];
}
说起来都忘了find函数的用法了- -直接用的map对象的find函数，返回的it对象好像和普通的find函数差不多。。。
随意枚举列，成对的枚举，然后判断对应的行与列是否能够有匹配的键值，如果有相同的则输出NO
否则输出YES

1.4. AC代码

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

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cmath>
#include<string>
#include<set>
#include<stack>
#include<map>
#include<cstring>
#include<cstdio>
#include<sstream>
using namespace std;
int n, m;
string s, st;
map<string, int>index;
int getid(string s) {
    if (index.find(s) == index.end())index[s] = index.size();
    return index[s];
}

int main() {
    while (cin >> n >> m) {
        getchar(); vector<int>a[n+1]; index.clear();
        for (int i = 0; i < n; i++) {
            getline(cin, s); stringstream input(s);
            while (getline(input, st, ','))a[i].push_back(getid(st));
        }
        bool flag = 1;
        for (int i = 0; i < m - 1 && flag; i++) {//C1任意枚举两行
            map<pair<int, int>, int>pos;
            for (int j = i + 1; j < m && flag; j++) {//C2
                for (int k = 0; k < n; k++) {
                    if (pos.find({ a[k][i],a[k][j] }) == pos.end()) {//任意R,枚举C1,C2
                        pos[{a[k][i], a[k][j]}] = k;
                    }
                    else {
                        flag = 0;
                        cout << "No\n" << pos[{a[k][i], a[k][j]}] + 1 << " " << k + 1 << endl << i + 1 << " " << j + 1 << endl;
                    }
                }
            }
        }
        if (flag)cout << "Yes" << endl;
    }
    return 0;
}

1. Unix ls

1.1. 题目

链接：https://vjudge.z180.cn/problem/UVA-400
来源：uva

题目描述
The computer company you work for is introducing a brand new computer line and is developing a
new Unix-like operating system to be introduced along with the new computer. Your assignment is to
write the formatter for the ls function.
Your program will eventually read input from a pipe (although for now your program will read
from the input file). Input to your program will consist of a list of (F) filenames that you will sort
(ascending based on the ASCII character values) and format into (C) columns based on the length (L)
of the longest filename. Filenames will be between 1 and 60 (inclusive) characters in length and will be
formatted into left-justified columns. The rightmost column will be the width of the longest filename
and all other columns will be the width of the longest filename plus 2. There will be as many columns
as will fit in 60 characters. Your program should use as few rows (R) as possible with rows being filled
to capacity from left to right.

输入描述:
The input file will contain an indefinite number of lists of filenames. Each list will begin with a line
containing a single integer (1 ≤ N ≤ 100). There will then be N lines each containing one left-justified
filename and the entire line’s contents (between 1 and 60 characters) are considered to be part of the
filename. Allowable characters are alphanumeric (a to z, A to Z, and 0 to 9) and from the following set
{._-} (not including the curly braces). There will be no illegal characters in any of the filenames and
no line will be completely empty.
Immediately following the last filename will be the N for the next set or the end of file. You should
read and format all sets in the input file.

输出描述:
For each set of filenames you should print a line of exactly 60 dashes (-) followed by the formatted
columns of filenames. The sorted filenames 1 to R will be listed down column 1; filenames R + 1 to 2R
listed down column 2; etc.

1.2. 样例输入&&样例输出

样例

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

10
tiny
2short4me
very_long_file_name
shorter
size-1
size2
size3
much_longer_name
12345678.123
mid_size_name
12
Weaser
Alfalfa
Stimey
Buckwheat
Porky
Joe
Darla
Cotton
Butch
Froggy
Mrs_Crabapple
P.D.
19
Mr._French
Jody
Buffy
Sissy
Keith
Danny
Lori
Chris
Shirley
Marsha
Jan
Cindy
Carol
Mike
Greg
Peter
Bobby
Alice
Ruben

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

------------------------------------------------------------
12345678.123 size-1
2short4me size2
mid_size_name size3
much_longer_name tiny
shorter very_long_file_name
------------------------------------------------------------
Alfalfa Cotton Joe Porky
Buckwheat Darla Mrs_Crabapple Stimey
Butch Froggy P.D. Weaser
------------------------------------------------------------
Alice Chris Jan Marsha Ruben
Bobby Cindy Jody Mike Shirley
Buffy Danny Keith Mr._French Sissy
Carol Greg Lori Peter

1.3. 思路

主要是输出格式问题，🦅语不好的硬伤就是不太好懂题目
输入了n个整数后跟着n个字符串，直接sort一下，字典序
关键是行与列的公式
M为最长的字符串长度
cols=(maxcols-M)/(M+2)+1，rows=(n-1)/cols+1

1.4. AC代码

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

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int maxn = 1000;
typedef long long ll;
string a[maxn];
#define maxc 60

void print(const string &s,int len,char extra){
    cout<<s;
    for(int i=0;i<len-s.size();i++){
        cout<<extra;
    }
}

int main() {
    int n;
    while(cin>>n){
        int maxnn=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            maxnn=max(maxnn,(int)a[i].size());
           }
        int col=(maxc-maxnn)/(maxnn+2)+1,row=(n-1)/col+1;//关键点找出宽度长度按格式输出即可
        cout<<"------------------------------------------------------------"<<endl;
        sort(a,a+n);
        for(int r=0;r<row;r++){
            for(int c=0;c<col;c++){
                int index=c*row+r;
                if(index<n){
                    print(a[index],c==col-1?maxnn:maxnn+2,' ');
                }
            }
            cout<<endl;
        }
    }
    system("pause");
    return 0;
}

1. GCD

1.1. 题目

链接：https://ac.nowcoder.com/acm/problem/114066
来源：牛客网

题目描述
Some message encoding schemes require that an encoded message be sent in two parts. The first part,
called the header, contains the characters of the message. The second part contains a pattern that
represents the message. You must write a program that can decode messages under such a scheme.
The heart of the encoding scheme for your program is a sequence of “key” strings of 0’s and 1’s as
follows:
0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001, . . . , 1011, 1110, 00000, . . .
The first key in the sequence is of length 1, the next 3 are of length 2, the next 7 of length 3, the
next 15 of length 4, etc. If two adjacent keys have the same length, the second can be obtained from
the first by adding 1 (base 2). Notice that there are no keys in the sequence that consist only of 1’s.
The keys are mapped to the characters in the header in order. That is, the first key (0) is mapped
to the first character in the header, the second key (00) to the second character in the header, the kth
key is mapped to the kth character in the header. For example, suppose the header is:
AB#TANCnrtXc
Then 0 is mapped to A, 00 to B, 01 to #, 10 to T, 000 to A, …, 110 to X, and 0000 to c.
The encoded message contains only 0’s and 1’s and possibly carriage returns, which are to be ignored.
The message is divided into segments. The first 3 digits of a segment give the binary representation
of the length of the keys in the segment. For example, if the first 3 digits are 010, then the remainder
of the segment consists of keys of length 2 (00, 01, or 10). The end of the segment is a string of 1’s
which is the same length as the length of the keys in the segment. So a segment of keys of length 2 is
terminated by 11. The entire encoded message is terminated by 000 (which would signify a segment
in which the keys have length 0). The message is decoded by translating the keys in the segments
one-at-a-time into the header characters to which they have been mapped.

输入描述:
The input file contains several data sets. Each data set consists of a header, which is on a single line
by itself, and a message, which may extend over several lines. The length of the header is limited
only by the fact that key strings have a maximum length of 7 (111 in binary). If there are multiple
copies of a character in a header, then several keys will map to that character. The encoded message
contains only 0’s and 1’s, and it is a legitimate encoding according to the described scheme. That is,
the message segments begin with the 3-digit length sequence and end with the appropriate sequence of
1’s. The keys in any given segment are all of the same length, and they all correspond to characters in
the header. The message is terminated by 000.
Carriage returns may appear anywhere within the message part. They are not to be considered as
part of the message.

输出描述:
For each data set, your program must write its decoded message on a separate line. There should not
be blank lines between messages.

1.2. 样例输入&&样例输出

样例

1
2
3
4
5
6

TNM AEIOU
0010101100011
1010001001110110011
11000
$#**\
0100000101101100011100101000

1
2

TAN ME
##*\$

1.3. 思路

其实只要读懂readcode即可
readcode的核心思想其实就是
0
00 01 10
000 001 010 011 100 101 110
看到什么规律了吗？对的其实就是二进制而已
只不过前面多了些零，我们用二维数组即可

1.4. AC代码

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
52
53
54
55
56
57

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 300;
int vis[maxn];
int code[8][1<<8];

char readchar(){
    while(1){
        char ch=getchar();
        if(ch!='\n'&&ch!='\r')return ch;
    }
}

int readint(int n){
    int v=0;
    while(n--){
        v=v*2+readchar()-'0';
    }
    return v;
}

int readcode(){
    memset(code,0,sizeof(code));
    code[1][0]=readchar();
    for(int i=2;i<=7;i++){
        for(int j=0;j<(1<<i)-1;j++){
            int ch=getchar();
            if(ch==EOF)return 0;
            if(ch=='\n'||ch=='\r')return 1;
            code[i][j]=ch;
        }
    }
    return 1;
}


int main() {
    while(readcode()){
        while(1){
            int len=readint(3);
            if(len==0)break;
            while(1){
                int v=readint(len);
                if(v==(1<<len)-1)break;
                 cout<<(char)code[len][v];
            }
        }
        cout<<endl;
    }
    system("pause");
    return 0;
}