課件教案信息學problems

1、Problem 1. How many primes?Input le: Output le: Time limit:prime.in prime.out 1 second求 1, 2, . . . , N 中素數(shù)的個數(shù)。Input1 個整數(shù) N 。Output1 個整數(shù)，表示素數(shù)的個數(shù)。SampleNote對于 40% 的數(shù)據(jù)，1 N 106；對于 80% 的數(shù)據(jù)，1 N 107；對于 100% 的數(shù)據(jù)，1 N 108。prime.inprime.out104Problem 2. How many rooks?Input le: Output le: Time limit:rook.in r

2、ook.out 1 secondN N 的國際象棋棋盤上有 K 個車，第 i 個車位于第 Ri 行，第 Ci 列。求至少被一個車的格子數(shù)量。Input第 1 行，2 個整數(shù) N, K。接下來 K 行，每行 2 個整數(shù) Ri, Ci。Output1 個整數(shù)，表示被Sample的格子數(shù)量。Note對于 30% 的數(shù)據(jù)，1 N 103, 1 K 103；對于 60% 的數(shù)據(jù)，1 N 106, 1 K 106；對于 100% 的數(shù)據(jù)，1 N 109, 1 K 106, 1 Ri, Ci N 。rook.inrook.out3 21 22 27Problem 3. How many colorings?

3、Input le: Output le: Time limit:coloring.in coloring.out 3 seconds有一顆 N 個節(jié)點的樹，節(jié)點用 1, 2, . . . , N。你要給它染色，使得相鄰節(jié)點的顏色不同。有 M 種顏。每個節(jié)點可以染 M 種顏色中的若干種，求不同染色方案的數(shù)量除以 (109 + 7)色，用 1, 2, . . . , M的余數(shù)。Input第 1 行，2 個整數(shù) N, M 。接下來 N 行，第 i 行表示節(jié)點 i 可以染的顏色。第 1 個整數(shù) ki，表示可以染的顏色數(shù)量。接下來 ki 個整數(shù)，表示可以染的顏色。最后 (N 1) 行，每行 2 個整數(shù) Ai, Bi，表示邊 (Ai, Bi)。Output1 個整數(shù)，表示所有的數(shù)。SampleNote對于 30% 的數(shù)據(jù)，1 N 10, 1 M 4；對于 60% 的數(shù)據(jù)，1 N 200, 1 M 200；對于 100% 的數(shù)據(jù)，1 N