Python Crash Course

About Python

Python is an interpreted language that is widely used throughout the world. It provides efficient high-level data structures, supports simple and effective object-oriented programming, and can also be used in programming contests.

Advantages of Python

• Python is an interpreted language: Python does not require compilation and linking, which can reduce the number of steps to some extent.
• Python is an interactive language: the Python interpreter supports interactive operation, so commands can be entered and executed directly in a terminal.
• Python is easy to learn and use: it provides many data structures and also supports the development of large programs.
• Python has strong compatibility: it supports the Windows, macOS, and Unix operating systems.
• Python is highly practical: from simple input and output to scientific computing and even large WEB applications, suitable Python programs can be written for all of them.
• Python programs are concise and readable: Python code is usually shorter than code implementing the same functionality in other languages.
• Python supports extension: Python has a C implementation (namely CPython), and supports linking the Python interpreter with applications developed in C, extending and controlling those applications with Python.

Notes on learning Python

• The main versions of Python currently in use are Python 3.7 and later. Python 2 and Python 3.6 and earlier are unsupported, although some old systems and code still use them. This article introduces newer versions of Python. If you encounter Python 2 code, you can try the 2to3 program to convert it to Python 3 code.
• Python's design philosophy and syntax differ considerably from those of some other languages. They hide many low-level details, giving Python a practical and elegant style.
• Python is a highly dynamic interpreted language, so its programs run relatively slowly, especially when its built-in for loop statement is used. When using Python, prefer built-in functions such as filter and map, or use list-comprehension syntax to improve program performance.

Setting up the environment

See Python 3, or:

• Windows: Python can also be obtained quickly and free of charge from the Microsoft Store.

• macOS/Linux: in most cases, most Linux distributions already include Python. If you only plan to learn Python syntax and have no other development needs, you do not need to install Python separately.

  ???+ warning "Note" On systems where Python is installed by default (that is, installed with a package manager), such as Unix systems, run python3 in the terminal to open the Python 3 interpreter. ¹

Python toolchains and packages can also be managed with tools such as venv, conda, and Nix, creating isolated virtual environments and avoiding dependency problems.

As an interpreted language, Python is executed differently from C++. This difference is often not apparent when programming with an IDE, so the different ways of running a program need to be emphasized here.

When you type python3 at the command line or have just opened IDLE, you have entered an interactive programming environment, also called a “REPL” (a “read-evaluate-print” loop). Beginners can enter statements here and see the results immediately, which makes it extremely easy to verify some syntax; we will also use this form extensively below.

However, to write a complete program, it is better to create a text file (usually with the .py extension), and then execute python3 filename.py at the command line to run the code and see the result.

Python versions provided by some platforms

The main domestic mirrors for source code are the Beijing Jiaotong University Free and Open Source Software Mirror and the Huawei Open Source Mirror. You can try downloading Python installation files from them.

Installing third-party libraries with pip

Much of Python's vitality comes from its rich collection of third-party libraries. “Using a library” is routine when writing practical programs, and pip is the preferred program for installing third-party libraries. Since Python 3.4, it has been included by default in the Python binary installer.

Third-party libraries in pip are mainly stored on the Python Package Index (PyPI), and users can also specify other platforms that host third-party libraries. For usage, see guides such as Help for using the pypi mirror - Tsinghua University Open Source Software Mirror. You can find more PyPI mirrors on MirrorZ.

pip install -i https://mirrors.tuna.tsinghua.edu.cn/pypi/web/simple <some-package>

Basic syntax

Python has concise and easy-to-understand syntax, as well as many official and third-party documents and tutorials. This section only introduces language features that are relatively useful to OIers; more Python tutorials are available on sites such as the Python documentation and the Python Wiki.

Comments

Adding comments does not affect how code runs, but comments can make code easier to understand and use.

# A single-line comment starts with #

"""
Multiline strings are enclosed in triple quotes
(three single quotes or three double quotes)
and are also commonly used as documentation.
"""

Adding comments to code does not affect the code. We encourage adding comments to make code easier to understand and use.

Basic data types

Everything is an object

In Python, you do not need to declare a variable name or its type in advance; assigning a value directly creates a variable of the corresponding type:

>>> x = -3  # No semicolon is needed at the end of a statement
>>> x
-3
>>> f = 3.1415926535897932384626; f  # You can add a semicolon if you really want; it saves a line here
3.141592653589793
>>> s1 = "O"
>>> s1  # In Python, double and single quotation marks have the same effect
'O'
>>> b = 'A' == 65  # 'A' and 65 are not the same data type, so they are not equal
>>> b  # True and False both start with uppercase letters
False
>>> True + 1 == 2 and not False != 0  # Python expressions mostly use words, but symbols are also supported
True

This does not mean that Python has no concept of types. In fact, the interpreter automatically infers variable types from assignments or operations, and you can use the built-in function type() to inspect them:

>>> type(x)
<class 'int'>
>>> type(f)
<class 'float'>
>>> type(s1)  # Be careful not to name a string str, or the str object will be overwritten
<class 'str'>
>>> type(b)
<class 'bool'>

As we have seen, Python has integer, floating-point, string, and Boolean types, which can be compared with int, float, string, and bool in C++. There are some obvious differences, such as the lack of a char character type and a double type (float actually corresponds to double precision in C). If more precise floating-point computation is needed, the standard-library decimal module can be used. If complex numbers are needed, Python also has a built-in complex type (which also means that it is best not to name a variable complex). These types can be seen to begin with class, which is a key difference between Python and C++. All data in a Python program is represented by objects or relationships between objects; functions are objects, and types themselves are also objects:

>>> type(int)
<class 'type'>
>>> type(pow)  # Built-in function for exponentiation; it will be introduced later
<class 'builtin_function_or_method'>
>>> type(type)  # type() is also a built-in function, but somewhat special; look it up if interested
<class 'type'>

You may feel that these concepts are difficult to understand and not very useful at first, so we will not go deeper for now. You may gradually appreciate them in the examples below: Python objects provide powerful methods, and when programming we should prioritize operating around objects rather than processes, which makes our code more compact and clear.

Numeric operations

Some people say that the Python installed on your system can serve as a general-purpose calculator; this is true.
In interactive mode, you can enter an expression after the >>> prompt and use operators such as +, -, *, /, and % on numbers just as in most other languages (such as C++). You can also use () for grouping according to associativity. Readers can experiment on their own; here we show only parts that differ substantially from C++:

>>> 5.0 * 6  # The result of floating-point arithmetic is a floating-point number
30.0
>>> 15 / 3  # Unlike C/C++, division always returns the floating-point type float
5.0
>>> 5 / 100000  # The result has too many digits, so it is displayed in scientific notation
5e-05
>>> 5 // 3 # Integer division (floor division) rounds down and outputs an integer
1
>>> -5 // 3 # This follows the floor-rounding rule; note that it differs from C/C++
-2
>>> 5 % 3 # Modulo
2
>>> -5 % 3 # The modulo of a negative number is always nonnegative, which also differs from C/C++; both nevertheless satisfy (a//b)*b+(a%b)==a
1
>>> x = abs(-1e4)  # Built-in function for taking an absolute value
>>> x += 1  # There are no increment/decrement operators
>>> x  # Scientific notation is float by default
10001.0

The examples above show that division (/) always returns a floating-point type (it returned an integer in Python 2). If an integer or floor-divided result is wanted, use integer division (//). Similarly, you can use modulo (%) as in C++ to calculate a remainder, and scientific notation has the same form.

In particular, Python uses ** for exponentiation, and its built-in pow(a, b, mod) provides an efficient implementation of binary exponentiation.

>>> 3 ** 4 # Exponentiation
81
>>> 2 ** 512
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
>>> pow(2, 512, int(1e4)) # The fast implementation of 2**512 % 10000; 1e4 is a float, so it must be converted to int
4096
>>> 2048 ** 2048 # Try a large integer in IDLE
>>> 0.1 + 0.1 + 0.1 - 0.3 == 0.  # As in C/C++, note that floating-point numbers cannot be compared directly for equality
False

Determining data types

For a variable, type(object) can return its type; for example, the values of type(8) and type('a') are <class 'int'> and <class 'str'>, respectively.

Basic input and output

Input and output in Python are mainly handled by the built-in functions input() and print(), and the use of print() is quite intuitive:

>>> a = [1,2,3]; print(a[-1])  # Printing adds a newline at the end by default
3
>>> print(ans[0], ans[1])  # Any number of variables can be output, separated by spaces by default
1 2
>>> print(a[0], a[1], end='')  # Set end='' so that no newline is added at the end
1 2>>>
>>> print(a[0], a[1], sep=', ')  # Set sep=', ' to change the separator style
1, 2
>>> print(str(a[0]) + ', ' + str(a[1]))  # The output is the same as above, but the strings are concatenated manually

The behavior of input() is close to C++'s getline(): it reads a whole line as a string without the trailing newline.

>>> s = input('Enter a sequence of numbers: '); s  # When debugging, you can pass a string to input() as the prompt
Enter a sequence of numbers: 1 2 3 4 5 6
'1 2 3 4 5 6'

Strings

Python 3 provides a powerful Unicode-based string type. It is used similarly to C++'s string, and concepts such as escape characters are also similar. In addition to concatenation with a plus sign and index access, it additionally supports repeating strings with multiplication * and the in operator.

>>> s1 = "O"  # Both single and double quotation marks can enclose strings and may save escape characters
>>> s1 += 'I-Wiki'  # Double quotation marks are recommended for consistency with C++
>>> 'OI' in s1  # Substring testing is convenient
True
>>> len(s1)  # Similar to C++'s s.length(), but more general
7
>>> s2 = """ Thanks for reading
... Contributions welcome!"""  # A string using triple quotes can span multiple lines
>>> s1 + s2
'OI-Wiki Thanks for reading\nContributions welcome!'
>>> print(s1 + s2)  # The print() function is used here to print a string
OI-Wiki Thanks for reading
Contributions welcome!
>>> s2[1:7] + s2[-1]  # Negative indices count from the right; -1 selects the final character
'Thanks!'
>>> s1[0] = 'o'  # str is immutable and cannot be modified in place; += actually creates a new object as well
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

Python supports several compound data types that can combine different values. The most commonly used list is a group of values marked with square brackets and separated by commas. For example, [1, 2, 3] and ['a','b','c'] are both lists.

In addition to indexing, strings support slicing. Its design is ingenious, with the format s[左闭索引:右开索引:步长]:

>>> s = 'OI-Wiki Thanks for reading\nContributions welcome!'
>>> s[:8]  # Omitting the left-closed index starts from the beginning
'OI-Wiki '
>>> s[8:26]  # The left-closed, right-open slice has length 26-8=18 and follows the preceding string
'Thanks for reading'
>>> s[-8:]  # Omitting the right-open index continues to the end
'welcome!'
>>> s[8:26:2]  # The step is 2
'Tak o edn'
>>> s[::-1]  # With a step of -1, the reversed string is obtained
'!emoclew snoitubirtnoC\ngnidaer rof sknahT ikiW-IO'
>>> s  # The original string is not changed
'OI-Wiki Thanks for reading\nContributions welcome!'

In the latest versions of Python 3, strings are encoded in Unicode, meaning that Python strings support multiple languages. ² In Python, the built-in function ord() converts a Unicode character to its corresponding Unicode code point, while the reverse conversion uses chr(). In C/C++, the char type can likewise be converted to and from the corresponding ASCII code.

To convert a number to the corresponding string, use the built-in function str(); conversely, use int() and float(). You can compare this with type conversion in C/C++, except that the parentheses enclose the argument as part of a function rather than being placed after a type.

Python's string type provides many powerful methods, including computing the index and occurrence count of a character and changing case. They are not listed one by one here; it is strongly recommended to read the official documentation to become familiar with commonly used methods, and to consider these methods first rather than implementing string operations from scratch.

Creating arrays

Students coming from C++ may be confused about how to create arrays in Python. This section introduces the syntax for creating “arrays” in Python; it is important to emphasize that what we introduce are actually several sequence types, fundamentally different from C arrays and closer to C++'s vector.

Using list

The list (list) is probably Python's most commonly used and most powerful sequence type. A list can contain elements of any type, including nested lists, which agrees with the definition of a “generalized list” in data structures. Be careful not to confuse it with the doubly linked list list in C++ STL; therefore, this article uses “list” as the English name rather than the list token to avoid misunderstanding.

>>> []  # Create an empty list; note that lists use square brackets
[]
>>> nums = [0, 1, 2, 3, 5, 8, 13]; nums  # Initialize a list; the whole list can be printed directly
[0, 1, 2, 3, 5, 8, 13]
>>> nums[0] = 1; nums  # Supports indexed access and modifying elements
[1, 1, 2, 3, 5, 8, 13]
>>> nums.append(nums[-2]+nums[-1]); nums  # append() is like vector's push_back(), and neither returns a value
[1, 1, 2, 3, 5, 8, 13, 21]
>>> nums.pop()  # Pop and return the last element; the list can be used as a stack, and a position can also be specified, with the last position as the default
21
>>> nums.insert(0, 1); nums  # Like vector's insert(position, val)
[1, 1, 1, 2, 3, 5, 8, 13]
>>> nums.remove(1); nums  # Remove an element by value (only the first occurrence); raise an error if it does not exist
[1, 1, 2, 3, 5, 8, 13]
>>> len(nums)  # Find the list length, similar to vector's size(), but len() is a built-in function
7
>>> nums.reverse(); nums  # Reverse in place
[13, 8, 5, 3, 2, 1, 1]
>>> sorted(nums)  # Obtain the sorted list
[1, 1, 2, 3, 5, 8, 13]
>>> nums  # The original list is not sorted
[13, 8, 5, 3, 2, 1, 1]
>>> nums.sort(); nums  # Sort in place; the key parameter can be specified as the sorting criterion
[1, 1, 2, 3, 5, 8, 13]
>>> nums.count(1)  # Similar to std::count()
2
>>> nums.index(1)  # Return the index of the first occurrence; raise an error if it does not exist
0
>>> nums.clear(); nums  # Like vector's clear()

The examples above show the similarities between lists and vector. Common operations on vector generally have corresponding methods on lists, but some methods such as len() and sorted() appear as built-in functions, while functions in STL algorithms such as find(), count(), max_element(), sort(), and reverse() become object methods in Python. Take care to distinguish them when using them; see the official documentation's list tutorial for more methods. The following shows some powerful features of lists as Python's basic sequence type:

Python supports several compound data types that can combine different values. The most commonly used list is a group of values marked with square brackets and separated by commas. For example, [1, 2, 3] and ['a','b','c'] are both lists.

>>> lst = [1, '1'] + ["2", 3.0]  # Adding lists directly creates a new list
>>> lst  # The different types here only demonstrate that this is possible; it is not good practice
[1, '1', '2', 3.0]
>>> 3 in lst  # A useful membership test; strings also support it and additionally support substring tests
True
>>> [1, '1'] in lst  # Only individual membership is tested; a “subsequence” will not be found
False
>>> lst[1:3] = [2, 3]; lst  # Slice and assign; the original list is modified
[1, 2, 3, 3.0]
>>> lst[::-1]  # Obtain a new reversed list
[3.0, 3, 2, 1]
>>> lst *= 2; lst  # Concatenate by multiplying
[1, 2, 3, 3.0, 1, 2, 3, 3.0]
>>> del lst[4:]; lst  # This can also be written as lst[4:] = []; the del statement is not limited to deleting elements from sequences
[1, 2, 3, 3.0]

The examples above show common operations on lists as sequences. Many operations, such as slicing, are shared with strings, but strings are “immutable sequences” while lists are “mutable sequences”, so slicing can be used to modify lists flexibly. In C/C++, character arrays are often processed with loops; the following shows how to use “list comprehensions” to convert between strings and lists:

>>> # Create an integer array in the interval [65, 70); range is also a type and can be viewed as a left-closed, right-open interval, with the third argument (the step) optional
>>> nums = list(range(65,70))  # Remember to wrap range in another list()
[65, 66, 67, 68, 69]
>>> lst = [chr(x) for x in nums]  # The typical structure of a list comprehension: [exp for var in iterable if cond]
>>> lst  # The preceding two lines can be combined as [chr(x) for x in range(65,70)]
['A', 'B', 'C', 'D', 'E']
>>> s = ''.join(lst); s # Join the elements of the list with the empty string '' to create a new string
'ABCDE'
>> list(s)  # Create a character list from a string
['A', 'B', 'C', 'D', 'E']
>>> # If you do not know about the s.lower() method, you might write the following reinvented expression
>>> ''.join([chr(ord(ch) - 65 + 97) for ch in s if ch >= 'A' and ch <= 'Z'])  
'abcde'

The following demonstrates some situations more common in OI, such as two-dimensional “arrays”:

>>> vis = [[0] * 3] * 3  # Create a 3*3 array filled with zeros
>>> vis 
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> vis[0][0] = 1; vis  # Why were the other rows modified too?
[[1, 0, 0], [1, 0, 0], [1, 0, 0]]
>>> # First, look at assignment for a one-dimensional list
>>> a1 = [0, 0, 0]; a2 = a1; a3 = a1[:]  # A list can also be assigned directly to a new variable
>>> a1[0] = 1; a1  # Modify list a1; this seems normal
[1, 0, 0]
>>> a2  # Why was a2 changed too?
[1, 0, 0]
>>> a3  # a3 did not change
[0, 0, 0]
>>> id(a1) == id(a2) and id(a1) != id(a3)  # The built-in function id() gives an object's “identity value”, which can be compared with an address; the same address means the same object
True
>>> vis2 = vis[:]  # Copy a two-dimensional list
>>> vis[0][1] = 2; vis  # vis is modified in bulk
>>> [[1, 2, 0], [1, 2, 0], [1, 2, 0]]
>>> vis2  # Although vis2 is a slice copy, it was changed too
>>> [[1, 2, 0], [1, 2, 0], [1, 2, 0]]
>>> id(vis) != id(vis2)  # vis and vis2 are not the same object
True
>>> # Although vis2 is not a reference to vis, its corresponding rows point to the same objects
>>> [id(vis[i]) == id(vis2[i]) for i in range(3)]
[True, True, True]
>>> # Look back at the two-dimensional list itself
>>> [id(x) for x in vis]  # The exact numbers differ here, but the three values must be the same, showing that they are the same object
[139760373248192, 139760373248192, 139760373248192]

There is an important fact: assignment in Python passes a reference rather than creating a new value. You can create variables of different types and assign them to new variables, and verification shows that their identity values are the same. So far, however, we have introduced only the mutable type list; assigning a new value to immutable types such as numbers and strings actually creates new objects, so the two variables before and after are independent. Lists are mutable, though, so modifying an element of one list also modifies the other list when both refer to the same object. Creating a two-dimensional array is similar: multiplying to create a two-dimensional list repeats the one-dimensional list [0]*3 three times, so an operation involving one list also affects the other two. Worse, when a two-dimensional list is assigned to another variable, even a slice copy is only a “shallow copy”, whose elements still refer to the same objects. This can be solved with the standard-library deepcopy, or by avoiding assigning the entire two-dimensional list whenever possible. Fortunately, avoiding repeated lists when creating a two-dimensional list is fairly simple; just use a “list comprehension”:

>>> vis1 = [[0] * 3 for _ in range(3)]  # It is conventional to name an unused loop counter with an underscore _
>>> # In the REPL, however, _ refers to the result of the previous expression by default, so double underscores can also be used
>>> vis1
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> [id(x) for x in vis1]  # The exact numbers differ here, but the three values must be different, showing that they are different objects
[139685508981248, 139685508981568, 139685508981184]
>>> vis1[0][0] = 1
[[1, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> a2[0][0] = 10  # Access and assign a two-dimensional array

We introduce list comprehensions before explaining loops because Python is a highly dynamic interpreted language, and its programs therefore have considerable overhead. In particular, for loops run extremely slowly in Python. To obtain high performance, try to use list comprehensions or built-in functions such as filter and map to operate directly on the whole sequence and avoid loops, although the appropriate choice still depends on the specific problem.

Using NumPy

The following code shows how to use NumPy to create and access multidimensional arrays.

>>> import numpy as np  # Search for the meaning and usage of import yourself
>>> np.empty(3) # Create an empty array with capacity 3; note that it is not initialized to 0
array([0.00000000e+000, 0.00000000e+000, 2.01191014e+180])
>>> np.zeros((3, 3)) # Create a 3*3 array and initialize it to 0
array([[0., 0., 0.],
       [0., 0., 0.],
       [0., 0., 0.]])
>>> a1 = np.zeros((3, 3), dtype=int) # Create a 3×3 integer array
>>> a1[0][0] = 1 # Access and assign
>>> a1[0, 0] = 1 # A friendlier syntax
>>> a1.shape # The shape of the array
(3, 3)

>>> a1[:2, :2] # Take the submatrix consisting of the first two rows and columns, without copying
array([[1, 0],
       [0, 0]])

>>> a1[:, [0, 2]] # Get columns 1 and 3, without copying
array([[1, 0],
       [0, 0],
       [0, 0]])
>>> np.max(a1) # Get the maximum value of the array
1
>>> a1.flatten() # Flatten the array
array([1, 0, 0, 0, 0, 0, 0, 0, 0])

>>> np.sort(a1, axis = 1) # Sort the array along the row direction and return the sorted result
array([[0, 0, 1],
       [0, 0, 0],
       [0, 0, 0]])
>>> a1.sort(axis = 1) # Sort the array in place along the row direction

Using array

array is an efficient numeric array provided by Python's standard library. It can represent arrays of primitive-type values compactly, but it does not support nested arrays and is rarely used, so it is only mentioned here in passing.

Unless otherwise specified, “array” below generally refers to a “list”.

Input and output

Input and output in Python are mainly handled by the built-in functions input() and print(). They were introduced above; this section presents advanced usage.

Formatted output

Programming contests generally involve only basic numeric and string output, for which print() is sufficient. Formatted string output is needed only when controlling the number of digits in a floating-point value. There are three methods: the first and oldest is the printf()-style % operator; the second uses the format function; the third is the f-string added in Python 3.6, which is the most concise but is not guaranteed to be supported by the Python version in a contest environment. For a detailed explanation, see this page. Although the format() method is recommended, the old-style method similar to printf() is demonstrated below to provide an experience closer to C:

>>> pi = 3.1415926; print('%.4f' % pi)   # The format is %[flags][width][.precision]type
3.1416
>>> '%.4f - %8f = %d' % (pi, 0.1416, 3)  # Enclose multiple arguments on the right in (); they are actually a “tuple”, as will be seen later
'3.1416 - 0.141600 = 3'

The split() function

The behavior of input() is close to C++'s getline(): it reads a whole line as a string without the trailing newline. However, a common input form in programming contests is multiple values on one line, so the string method split() must be combined with a list comprehension to obtain a list of numeric values. The following example reads n numbers and computes their average:

>>> s = input('Enter a sequence of numbers: '); s  # When debugging, you can pass a string to input() as the prompt
Enter a sequence of numbers: 1 2 3 4 5 6
'1 2 3 4 5 6'
>>> a = s.split(); a
['1', '2', '3', '4', '5', '6']
>>> a = [int(x) for x in a]; a
[1, 2, 3, 4, 5, 6]
>>> # The input process above can be written in one line as a = [int(x) for x in input().split()]
>>> sum(a) / len(a)  # sum() is a built-in function
3.5

Sometimes a problem inputs a fixed number of values on each line, such as the endpoints and weight of an edge. With the method above, the line could only be read into a list and then assigned by index. Python's “unpacking” feature can instead assign multiple variables at once:

>>> u, v, w = [int(x) for x in input().split()]
1 2 4
>>> print(u,v,w)
1 2 4

Problems often input N lines, but we have not yet introduced the basic loop statements. Python's powerful sequence operations can handle multiple lines without using a loop; suppose that the starts, ends, and weights of all edges are to be read into three arrays:

>>> N = 4; mat = [[int(x) for x in input().split()] for i in range(N)]
1 3 3 
1 4 1 
2 3 4 
3 4 1 
>>> mat  # First read the two-dimensional array row by row
[[1, 3, 3], [1, 4, 1], [2, 3, 4], [3, 4, 1]]
>>> u, v, w = map(list, zip(*mat))   
# * Unpack mat to obtain the inner lists
# zip() groups corresponding elements of multiple lists into tuples and returns an iterator
# map(list, iterable) converts elements of the sequence (tuples here) into lists
>>> print(u, v, w)  # Unpack the iterator returned by map() directly and assign its values to u, v, and w
[1, 1, 2, 3] [3, 4, 3, 4] [3, 1, 4, 1]

The program above is equivalent to first reading an N-row, 3-column matrix and then transposing it into a 3-row, N-column matrix. In other words, the outer list contains three nested lists, and the three lists representing the start, end, and weight are assigned to u, v, and w. The built-in function zip() combines corresponding elements of equal-length sequences into “tuples” to form a new sequence. map() is an operation from functional programming: it applies a given function to the elements of the sequence produced by zip(), here using list() to turn tuples into lists. You can practice using *, zip(), and map() to understand their meanings. Note that in Python 3, zip() and map() no longer return lists but iterators. Their differences are not discussed here; you can think of an iterator as producing the elements of a list, and wrapping it with list() generates a list.

File reading and writing

Python's built-in function open() is used for file reading and writing. To prevent errors during reading or writing from leaving a file improperly closed, this section introduces only the safe method using the with statement:

a = []
with open("in.txt") as f:
    N = int(f.readline())  # Read N from the first line
    a[len(a) :] = [[int(x) for x in f.readline().split()] for i in range(N)]

with open("out.txt", "w") as f:
    f.write("1\n")

There are many functions for file reading and writing, each suited to different situations. Since OI contests do not yet support Python, they are omitted here.

Control flow

Although we have learned many Python features, all Python code shown so far has consisted of single-line statements, hiding major differences between the coding styles of Python and C. First, Python uses indentation rather than {} to represent blocks; misaligned indentation causes an immediate error, as does mixing tabs and spaces. Second, the ends of lines introducing block structures such as if and for must have a colon :. This improves readability, but you may miss C's freedom, since manually realigning code after lost indentation during copy and paste is annoying.

Loop structures

List comprehensions can complete batch operations efficiently on one line, but sometimes our attempts to shorten code become excessive, and loops are still necessary in many situations. We therefore use reading multiple lines as an example to show how loops are written in Python:

# Note that we no longer use the REPL from this point on; copy the multiple lines of data yourself
u, v, w = ([] for i in range(3))  # Multiple-variable assignment
for i in range(4):  # Assume that four lines of data are input here
    _u, _v, _w = [int(x) for x in input().split()]
    u.append(_u), v.append(_v), w.append(_w)
    # An operation like cin >> u[i] >> v[i] >> w[i] cannot be used because it will necessarily exceed the current list length
    # You can of course initialize an all-zero list of length MAXN, but remember the actual length and delete the extra elements
print(u, v, w)

Note that Python's for loop differs substantially from C/C++. Its role is similar to the range-based for loop introduced in C++11; it iterates over the elements of a sequence. For example, iterating over array indices requires iterating over range(len(lst)), rather than truly defining a start and end condition, so it is less flexible than C/C++.

The following uses a while loop to show how to input an unknown number of lines:

u, v, w = [], [], []  # Multiple-variable assignment, as above
s = input()  # Note that assignment statements cannot be placed in conditional expressions in Python
while s:  # This cannot be written as while(!scanf()) as in C
    # Use slice concatenation to avoid append(); note that the list comprehension contains another list
    u[len(u) :], v[len(v) :], w[len(w) :] = [[int(x)] for x in s.split()]
    s = input()
# After Python 3.8 introduced the walrus operator, two lines can be saved, but the contest environment may not support it
while s := input():
    u[len(u) :], v[len(v) :], w[len(w) :] = [[int(x)] for x in s.split()]
print(u, v, w)

Selection structures

They are largely similar to C/C++, with some syntactic differences shown in the examples below. Also note that assignment operators are not allowed in conditional expressions (Python 3.8 and later provide :=), and that Python has no switch statement.

# There are no parentheses around the conditional expression
if 4 >= 3 > 2 and 3 != 5 == 5 != 7:
    print("Relational operators can be chained")
    x = None or [] or -2
    print("&&  ||  !", "AND  OR  NOT", "and or not", sep="\n")
    print("Using and/or well can save lines")
    if not x:
        print("Negative numbers are also True, so this line is not executed")
    elif x & 1:
        print("Use elif instead of else if\n" "Bitwise operators resemble C; even & 1 is 0, so this line is not executed")
    else:
        print("A conditional expression is also available") if x else print("Note the structure")

Exception handling

Although C++ has a try block for exception handling, it is generally not used in contests. Python commonly uses the EAFP style, so code may use try-except statements extensively. They will also appear later when the dict structure is introduced; here is an example:

s = "OI-wiki"
pat = "NOIP"
x = s.find(pat)  # find() returns -1 when it cannot find a match
try:
    y = s.index(pat)  # index() raises an error when it cannot find a match
    print(y)  # This line is skipped
except ValueError:
    print("Not found")
    try:
        print(y)  # y is not defined at this point, so another error is raised
    except NameError as e:
        print("Cannot print y")
        print("Reason:", e)

Built-in containers

Python has many powerful built-in container types. Only by using them proficiently and understanding their characteristics can Python truly be useful in programming contests. In addition to the list discussed above, there are tuple, dict, and set.

A tuple can be understood simply as an immutable list, but the meaning of “immutable” deserves attention. If an element of a tuple is a mutable type such as a list, that list can still be modified: the tuple stores a reference to the list, so the tuple itself has not changed. Tuples have low overhead and are “hashable”, which is useful when creating dictionaries and sets.

tup = tuple([[1, 2], 4])  # Obtain a tuple from a list
# Equivalent to tup = ([1,2], 4)
tup[0].append(3)
print(tup)
a, b = 0, "I-Wiki"  # Multiple-variable assignment is actually tuple unpacking
print(id(a), id(b))
b, a = a, b
print(id(a), id(b))  # You should see that the id values of a and b have now been exchanged
# This further shows that variables in Python are more like names, and assignment merely makes them refer to objects

A dictionary is like C++ STL's map (note the distinction from Python's built-in function map()) and stores key-value pairs. Its form resembles JSON, but JSON keys must be strings enclosed in double quotation marks, whereas dictionaries are more flexible and powerful: any hashable object can be a dictionary key. Note that several Python version updates have changed dictionary behavior, including the order of its elements; explore these changes yourself.

dic = {"key": "value"}  # Basic form
dic = {chr(i): i for i in range(65, 91)}  # Mapping uppercase letters to their corresponding ASCII codes; note the punctuation
dic = dict(zip([chr(i) for i in range(65, 91)], range(65, 91)))  # Same effect as above
dic = {dic[k]: k for k in dic}  # Reverse the key-value pairs; for k in dic iterates over its keys
dic = {v: k for k, v in dic.items()}  # Same effect as the preceding line; dic.items() stores each key-value pair as a tuple
dic = {
    k: v for k, v in sorted(dic.items(), key=lambda x: -x[1])
}  # Sort the dictionary in descending order by value, using a lambda expression

print(dic["A"])  # Return the item in dic with 'A' as its key; its value here is 65
dic["a"] = 97  # Set d[key] to value; if key was absent, this directly inserts it
if "b" in dic:  # LBYL (Look Before You Leap) style
    print(dic["b"])  # An error occurs if the key is absent, so check first
else:
    dic["b"] = 98

# Classic case: count occurrences
# The new key is absent from the original dictionary and requires extra handling
try:  # EAFP (Easier to Ask for Forgiveness than Permission) style
    cnter[key] += 1
except KeyError:
    cnter[key] = 1

A set is like C++ STL's set; it does not store duplicate elements and can be viewed as a dictionary that stores only keys. Note that sets and dictionaries are both enclosed in {}, but {} alone creates an empty dictionary rather than an empty set, so no example is given here.

Writing functions

Python function definitions do not require parameter or return-value types, which implicitly reduces the amount of code for OI competitors.

def add(a, b):
    return a + b  # An advantage of dynamic typing; a and b can also be strings

def add_no_swap(a, b):
    print("in func #1:", id(a), id(b))
    a += b
    b, a = a, b
    print("in func #2:", id(a), id(b))  # a and b have been swapped
    return a, b  # Return multiple values, which is actually returning a tuple that can be received by unpacking

lst1 = [1, 2]
lst2 = [3, 4]
print("outside func #1:", id(lst1), id(lst2))
add_no_swap(lst1, lst2)
# Outside the function, lst1 and lst2 have not been swapped
print("outside func #2:", id(lst1), id(lst2))
# The values have nevertheless changed
print(lst1, lst2)

Default parameters

Python function parameters are very flexible, with keyword parameters and variable-length parameters, among others. These features are not very useful in programming contests, so only default parameters are introduced here. C++ also has default parameters, and using default parameters in Python can easily lead to pitfalls. Consider the following code.

def append_to(element, to=[]):
    to.append(element)
    return to

lst1 = append_to(12)
lst2 = append_to(42)
print(lst1, lst2)

# You might expect the output to be [12] [42]
# But the actual output is [12, 42] [12, 42]

The result above occurs because a default parameter is assigned a value only once, when the function is defined. For mutable objects such as lists, dictionaries, and sets, all calls share the same object, so lst1 and lst2 actually point to the same default list in memory. Consequently, after the second call, the contents of this shared list become [12, 42]. A function's default parameter should therefore be an immutable object; using None as a placeholder is a best practice:

def append_to(element, to=None):
    if to is None:
        to = []
    to.append(element)
    return to

lst1 = append_to(12)
lst2 = append_to(42)
print(lst1, lst2)

# The output is [12] [42]

Type annotations

Python is a dynamically type-checked language that handles types flexibly and implicitly. The Python interpreter checks types only at runtime and allows a variable's type to change at runtime. As the saying goes, “dynamic typing is pleasant for a moment, but refactoring code is like a funeral”; some errors in a program may not appear until runtime:

>>> if False:
...     1 + "two"  # This line never runs, so no TypeError is raised
... else:
...     1 + 2
...
3

>>> 1 + "two"  # Now this is type checked, and a TypeError is raised
TypeError: unsupported operand type(s) for +: 'int' and 'str'

Python 3.5 introduced type annotations, which allow types to be specified for function parameters and return values. However, they serve only as hints and impose no actual restrictions; a static-checking tool is needed to rule out such errors (for example, PyCharm and Mypy). Thus they are somewhat limited in practice, and for OIers it is enough to be familiar with them. Type annotations can be set for function parameters and return values as follows:

def headline(
    text,  # type: str
    width=80,  # type: int
    fill_char="-",  # type: str
):  # type: (...) -> str
    return f"{text.title()}".center(width, fill_char)

print(headline("type comments work", width=40))

Besides function parameters, variables can also have type annotations. You can call __annotations__ to view all type annotations in a function. Variable annotations give Python a property of statically typed languages, separating declaration from assignment:

>>> nothing: str
>>> nothing
NameError: name 'nothing' is not defined

>>> __annotations__
{'nothing': <class 'str'>}

Decorators

A decorator is a function that accepts a function or method as its sole argument and returns a new function or method that incorporates the decorated function or method together with some additional functionality. In short, it can add functionality without modifying the function's code. See the official documentation for related information.

Some decorators are very useful in competitions. For example, lru_cache can automatically add memoization to a function and is very useful in recursive algorithms:

@lru_cache(maxsize=128,typed=False)

• It takes two arguments: maxsize and typed. If they are omitted, the default value of maxsize is 128 and the default value of typed is False.
• The maxsize argument specifies the capacity of the LRU cache, that is, the maximum number of results that the decorated method can cache. If its value is 128, the decorated method can cache at most 128 return values; if maxsize is None, an unlimited number of results can be cached.
• If typed is set to True, function arguments of different types are cached separately. For example, f(3) and f(3.0) are cached twice.

Here is an example of using lru_cache to optimize the computation of the Fibonacci sequence:

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Common built-in libraries

Here are some built-in libraries that may be useful when writing algorithms. You can search for specific usage or read the official documentation.

Comparing C++ and Python using an example problem

Declaring constants

C++

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
constexpr int N = 1e5 + 5, M = 2e5 + 5;

Python

try:  # Import the priority-queue module
    import Queue as pq  # python version < 3.0
except ImportError:
    import queue as pq  # python3.*

N = int(1e5 + 5)
M = int(2e5 + 5)
INF = 0x3F3F3F3F

Declaring the forward-star structure and other variables

C++

struct qxx {
  int nex, t, v;
};

qxx e[M];
int h[N], cnt;

void add_path(int f, int t, int v) { e[++cnt] = qxx{h[f], t, v}, h[f] = cnt; }

using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
int dist[N];

Python

class qxx:  # Forward-star class (structure)
    def __init__(self):
        self.nex = 0
        self.t = 0
        self.v = 0

e = [qxx() for i in range(M)]  # Linked list
h = [0 for i in range(N)]
cnt = 0

dist = [INF for i in range(N)]
q = pq.PriorityQueue()  # Define a priority queue; by default, the first element is a min-heap

def add_path(f, t, v):  # Add an edge to the forward-star structure
    # Use global to declare variables if global variables are to be modified
    global cnt, e, h
    # Output statement for debugging; multiple variables use a tuple
    # print("add_path(%d,%d,%d)" % (f,t,v))
    cnt += 1
    e[cnt].nex = h[f]
    e[cnt].t = t
    e[cnt].v = v
    h[f] = cnt

Dijkstra's algorithm

C++

void dijkstra(int s) {
  memset(dist, 0x3f, sizeof(dist));
  dist[s] = 0, q.push(make_pair(0, s));
  while (q.size()) {
    pii u = q.top();
    q.pop();
    if (dist[u.second] < u.first) continue;
    for (int i = h[u.second]; i; i = e[i].nex) {
      const int &v = e[i].t, &w = e[i].v;
      if (dist[v] <= dist[u.second] + w) continue;
      dist[v] = dist[u.second] + w;
      q.push(make_pair(dist[v], v));
    }
  }
}

Python

def nextedgeid(u):  # A generator that can be used in a for loop
    i = h[u]
    while i:
        yield i
        i = e[i].nex

def dijkstra(s):
    dist[s] = 0
    q.put((0, s))
    while not q.empty():
        u = q.get()  # The get function also removes the corresponding element from the heap
        if dist[u[1]] < u[0]:
            continue
        for i in nextedgeid(u[1]):
            v = e[i].t
            w = e[i].v
            if dist[v] <= dist[u[1]] + w:
                continue
            dist[v] = dist[u[1]] + w
            q.put((dist[v], v))

Main function

C++

int n, m, s;

int main() {
  scanf("%d%d%d", &n, &m, &s);
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add_path(u, v, w);
  }
  dijkstra(s);
  for (int i = 1; i <= n; i++) printf("%d ", dist[i]);
  return 0;
}

Python

if __name__ == "__main__":
    # Read multiple integers on one line. Note that the entire line is read
    n, m, s = map(int, input().split())
    for i in range(m):
        u, v, w = map(int, input().split())
        add_path(u, v, w)

    dijkstra(s)

    for i in range(1, n + 1):
        print(dist[i], end=" ")

    print()

Complete code

C++

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
constexpr int N = 1e5 + 5, M = 2e5 + 5;

struct qxx {
  int nex, t, v;
};

qxx e[M];
int h[N], cnt;

void add_path(int f, int t, int v) { e[++cnt] = qxx{h[f], t, v}, h[f] = cnt; }

using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
int dist[N];

void dijkstra(int s) {
  memset(dist, 0x3f, sizeof(dist));
  dist[s] = 0, q.push(make_pair(0, s));
  while (q.size()) {
    pii u = q.top();
    q.pop();
    if (dist[u.second] < u.first) continue;
    for (int i = h[u.second]; i; i = e[i].nex) {
      const int &v = e[i].t, &w = e[i].v;
      if (dist[v] <= dist[u.second] + w) continue;
      dist[v] = dist[u.second] + w;
      q.push(make_pair(dist[v], v));
    }
  }
}

int n, m, s;

int main() {
  scanf("%d%d%d", &n, &m, &s);
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add_path(u, v, w);
  }
  dijkstra(s);
  for (int i = 1; i <= n; i++) printf("%d ", dist[i]);
  return 0;
}

Python

try:  # Import the priority-queue module
    import Queue as pq  # python version < 3.0
except ImportError:
    import queue as pq  # python3.*

N = int(1e5 + 5)
M = int(2e5 + 5)
INF = 0x3F3F3F3F

class qxx:  # Forward-star class (structure)
    def __init__(self):
        self.nex = 0
        self.t = 0
        self.v = 0

e = [qxx() for i in range(M)]  # Linked list
h = [0 for i in range(N)]
cnt = 0

dist = [INF for i in range(N)]
q = pq.PriorityQueue()  # Define a priority queue; by default, the first element is a min-heap

def add_path(f, t, v):  # Add an edge to the forward-star structure
    # Use global to declare variables if global variables are to be modified
    global cnt, e, h
    # Output statement for debugging; multiple variables use a tuple
    # print("add_path(%d,%d,%d)" % (f,t,v))
    cnt += 1
    e[cnt].nex = h[f]
    e[cnt].t = t
    e[cnt].v = v
    h[f] = cnt

def nextedgeid(u):  # A generator that can be used in a for loop
    i = h[u]
    while i:
        yield i
        i = e[i].nex

def dijkstra(s):
    dist[s] = 0
    q.put((0, s))
    while not q.empty():
        u = q.get()
        if dist[u[1]] < u[0]:
            continue
        for i in nextedgeid(u[1]):
            v = e[i].t
            w = e[i].v
            if dist[v] <= dist[u[1]] + w:
                continue
            dist[v] = dist[u[1]] + w
            q.put((dist[v], v))

# Execute this command if you run this Python code directly (rather than call it as a module)
if __name__ == "__main__":
    # Read multiple integers on one line. Note that the entire line is read
    n, m, s = map(int, input().split())
    for i in range(m):
        u, v, w = map(int, input().split())
        add_path(u, v, w)

    dijkstra(s)

    for i in range(1, n + 1):
        # Both output syntaxes can be used
        print("{}".format(dist[i]), end=" ")
        # print("%d" % dist[i],end=' ')

    print()  # Newline at the end

References

1. Python Documentation
2. Official Python Chinese tutorial
3. Learn Python3 In Y Minutes
4. Real Python Tutorials
5. Liaoxuefeng's Python tutorial
6. GeeksforGeeks: Python Tutorials

References and notes