2018-2019 ACM-ICPC Pacific Northwest Regional Contest - 部分水题题解

A - Exam

原题面

描述

Your friend and you took a true/false exam of questions. You know your answers, your friend’s answers, and that your friend got questions correct.
Compute the maximum number of questions you could have gotten correctly.

输入

The first line of input contains a single integer .
The second line contains a string of () characters, the answers you wrote down. Each letter is either a ‘T’ or an ‘F’.
The third line contains a string of n characters, the answers your friend wrote down. Each letter is either a ‘T’ or an ‘F’.
The input will satisfy .

输出

Print, on one line, the maximum number of questions you could have gotten correctly.

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
3 FTFFF TFTTT	2
6 TTFTFFTFTF TTTTFFTTTT	9

题解

题意

已知自己的和朋友的判断题每题所选的答案，以及朋友的答案中正确的个数（具体是哪些题未知），求自己最多可能答对了多少道判断题。

思路

• 首先需要保证自己与朋友答案一致的题目（数量记为）为朋友所答对的，因为若有一题朋友答对了而自己的答案与之相反，则自己一定答错了。
• 若，则需要保证自己与朋友答案一致的其中有题答对，不一致的题目全为自己对。此时问题答案为。
• 若，则需要保证自己与朋友答案一致的两者全答对，不一致的题目中有道题朋友答对了（即朋友没答对的题全为自己答对了）。此时答案为。
• 故最终答案为。

时间复杂度

代码

k, a, b = int(input()), input(), input()
n = len(a)
s = sum([int(a[i] == b[i]) for i in range(n)])
print(n - abs(k - s))

C - Contest Setting

原题面

描述

A group of contest writers have written problems and want to use of them in an upcoming contest. Each problem has a difficulty level. A contest is valid if all of its problems have different difficulty levels.
Compute how many distinct valid contests the contest writers can produce. Two contests are distinct if and only if there exists some problem present in one contest but not present in the other.
Print the result modulo .

输入

The first line of input contains two space-separated integers and ().
The next line contains n space-separated integers representing the difficulty levels. The difficulty levels are between and (inclusive).

输出

Print the number of distinct contests possible, modulo .

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
5 2 1 2 3 4 5	10
5 2 1 1 1 2 2	6
12 5 3 1 4 1 5 9 2 6 5 3 5 8	316

题解

题意

有道不同的题目，每个题目有一个难度值，组织一场比赛需要从这道题目中选出道难度值互不相同的题目，求方案数。

思路

• 将题目的难度值离散化，因为只需要考虑一共有多少种不同的难度值。设第种难度值对应有个题目。
• 考虑动态规划。定义表示前种难度值中挑选出种难度值互不相同的题的方案数。
• 对于每一种难度值的题，有选一道或不选两种情况。
• 若从该种难度值的题目中选出一道，则需要保证前种难度中恰好选了种互不相同的难度值，故。
• 若不选该种难度值的题目，则需要保证前前种难度中恰好已经选了种互不相同的难度值，故。
• 故转移方程为。

时间复杂度

代码

from collections import Counter

MOD = 998244353
n, k = [int(_) for _ in input().split()]
counter = Counter([int(_) for _ in input().split()])
n = len(counter)
dp = [[1] + [0] * k for _ in range(n + 1)]
for _i, cnt in enumerate(counter):
    i = _i + 1
    for j in range(1, k + 1):
        dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * counter[cnt]) % MOD
print(dp[n][k])

H - Repeating Goldbachs

原题面

描述

The Goldbach Conjecture states that any even number can be expressed as the sum of two primes. It can be verified that the conjecture is true for all .
Define a Goldbach step as taking (), finding primes and (with ) that sum to , and replacing with . If there are multiple pairs of primes which sum to , we take the pair with the largest difference. That difference must be even and less than . Therefore, we can repeat more Goldbach steps, until we can reach a number less than .
Given , find how many Goldbach steps it takes until reaching a number less than .

输入

The input will consist of a single integer ().

输出

Print, on a single line, the number of Goldbach steps it takes to reach a number less than .

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
20	3
30	4
40	5
50	6
60	7
70	8

题解

题意

给定正整数，每次寻找两个差值最大的质数和，满足且，然后将替换为。重复该步骤直至。输出执行的次数。

思路

• 根据题意模拟该过程即可。
• 注意要将以内的质数预处理出来。

时间复杂度

整个过程理论上是，但由于每次都很小，寻找和的开销并不大。

代码

#include <cstdio>
int x, primes[1000006], primecnt = 0, cnt = 0, p, q;
bool vis[1000006] = {false};
int main() {
    freopen("a.txt", "w", stdout);
    scanf("%d", &x);
    for (int i = 2; i <= x; ++i) {
        if (!vis[i])
            primes[++primecnt] = i;
        for (int j = 1; i * primes[j] <= x; ++j) {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
    vis[1] = true; // 1 is not a prime
    while (x >= 4) {
        for (int i = 1; i <= primecnt; ++i)
            if (!vis[x - primes[i]]) {
                p = primes[i];
                q = x - primes[i];
                break;
            }
        printf("%d\n", p);
        x = q - p;
        ++cnt;
    }
    printf("%d\n", cnt);
    return 0;
}

I - Greedy Scheduler

原题面

描述

A store has cashiers numbered sequentially from to , with customers in a queue. A customer at the front of the queue is constantly assigned to the first unoccupied cashier, i.e., cashier with the smallest number. The th customer’s shopping cart takes seconds to process.
Find which cashier will process each customer’s shopping cart.

输入

The first line of input contains two space-separated integers and (). The second line of input contains space-separated integers , representing the length of time required to handle that customer.

输出

Output a single line containing space-separated integers, each with the cashier number that handles that customer.

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
3 10 406 424 87 888 871 915 516 81 275 578	1 2 3 3 1 2 3 1 2 1

题解

题意

个顾客需要按顺序在个收银员处结账，每个顾客结账需要时间，求为每个顾客结账的收银员编号。

思路

• 维护每个收银员的下一个空闲的时间点。
• 对于每个顾客，寻找编号最小的空闲收银员。
• 可以利用优先队列加速寻找最小编号收银员的速度。

时间复杂度

代码

from queue import PriorityQueue

n, c = [int(_) for _ in input().split()]
t = [int(_) for _ in input().split()]
q = PriorityQueue()
for i in range(n):
    q.put((0, i + 1))
opt = list()
for time in t:
    ava = q.get()
    opt.append(str(ava[1]))
    q.put((ava[0] + time, ava[1]))
print(" ".join(opt))

J - House Numbers

原题面

描述

Peter was walking down the street, and noticed that the street had houses numbered sequentially from to . While standing at a particular house , he also noticed that the sum of the house numbers behind him (numbered from to ) equaled the sum of the house numbers in front of him (numbered from to ).
Given , and assuming there are at least three houses total, find the lowest such that this is possible.

输入

Input consists of a single line containing the integer ().

输出

On a single line, print , , and , in order, separated by spaces.
It is guaranteed that there will be a solution with less than or equal to .

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
1	1 6 8
11	11 49 68
999999	999999 1317141 1571535
999000	999000 1000000 1000999

题解

题意

给定正整数，求满足的最小正整数解，同时需要保证，使得。

思路

• 将求和符号展开，得。
• 展开，整理，得。
• 变形，得。将右边记为。
• 从小到大遍历，当上述方程中有正整数解时即为问题答案。
• 若需要保证精度，可采用二分答案法求的解，避免浮点数运算。此时时间复杂度为，也可接受。

时间复杂度

代码

#include <cstdio>
#include <cmath>
long long m, x, n, C;
int main() {
    scanf("%lld", &m);
    n = m + 1;
    while (true) {
        ++n;
        C = m * m - m + n * n + n;
        if (C & 1)
            continue;
        C >>= 1;
        x = (long long)sqrt((double)C);
        if (x * x == C)
            break;
    }
    printf("%lld %lld %lld\n", m, x, n);
    return 0;
}

M - Liars

原题面

描述

There are n people in a circle, numbered from to , each of whom always tells the truth or always lies.
Each person makes a claim of the form: “the number of truth-tellers in this circle is between and , inclusive.”
Compute the maximum number of people who could be telling the truth.

输入

The first line contains a single integer (). Each of the next lines contains two space-separated integers and ().

输出

Print, on a single line, the maximum number of people who could be telling the truth. If the given set of statements is inconsistent, print -1 instead.

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
3 1 1 2 3 2 2	2
8 0 1 1 7 4 8 3 7 1 2 4 5 3 7 1 8	-1

题解

题意

个人中一部分永远说真话，剩下一部分永远说假话。给出每个人对永远说真话的人数区间的描述，计算最多可能的说真话的人数。

思路

• 由于输入的较小，因此可以直接枚举最多可能的说真话的人数。
• 对于每个可能的人数，检查每个人的描述，可以得出某个人是否说了真话，统计个数，与枚举的人数比较即可。

时间复杂度

代码

n = int(input())
claims = list()
for i in range(n):
    claims.append([int(_) for _ in input().split()])
ans = -1
for i in range(1, n + 1):
    cnt = 0
    for claim in claims:
        if claim[0] <= i <= claim[1]:
            cnt += 1
    if cnt == i:
        ans = i
print(ans)

O - Pizza Deal

原题面

描述

There’s a pizza store which serves pizza in two sizes: either a pizza slice, with area and price P 1 , or a circular pizza, with radius and price .
You want to maximize the amount of pizza you get per dollar. Should you pick the pizza slice or the whole pizza?

输入

The first line contains two space-separated integers and .
Similarly, the second line contains two space-separated integers and .
It is guaranteed that all values are positive integers at most . We furthermore guarantee that the two will not be worth the same amount of pizza per dollar.

输出

If the better deal is the whole pizza, print ‘Whole pizza’ on a single line.
If it is a slice of pizza, print ‘Slice of pizza’ on a single line.

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
8 4 7 9	Whole pizza
9 2 4 7	Whole pizza
841 108 8 606	Slice of pizza

题解

题意

比较扇形披萨和圆形披萨的单位价格的披萨面积。

思路

直接计算即可。

时间复杂度

代码

import math

a1, p1 = [int(_) for _ in input().split()]
r, p2 = [int(_) for _ in input().split()]
a2 = math.pi * r ** 2
if a1 / p1 > a2 / p2:
    print("Slice of pizza")
else:
    print("Whole pizza")

Q - Poker Hand

原题面

描述

You’re given a five-card hand drawn from a standard -card deck. Each card has a rank (one of ), and a suit (one of ).
The strength of your hand is defined as the maximum value such that there are cards in your hand that have the same rank.
Find the strength of your hand.

输入

The input consists of a single line, with five two-character strings separated by spaces.
The first character in each string will be the rank of the card, and will be one of A23456789TJQK. The second character in the string will be the suit of the card, and will be one of CDHS.
It is guaranteed that all five strings are distinct.

输出

Output, on a single line, the strength of your hand.

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
AC AD AH AS KD	4
2C 4D 4H 2D 2H	3
AH 2H 3H 4H 5H	1

题解

题意

统计五张扑克牌中点数相同的最大张数。

思路

直接统计即可。

时间复杂度

代码

from collections import Counter

counter = Counter([card[0] for card in input().split()])
print(counter.most_common(1)[0][1])

R - Random Index Vectors

原题面

描述

A Random Index Vector (RIV) is a data structure that can represent very large arrays where most elements are zero. Here, we consider a version of RIVs which can contain only , , and as elements. There are three basic operations on RIVs:

• Addition of two RIVs and ; the resulting RIV is defined by . The values are clamped at , i.e., we define and .
• Multiplication of two RIVs and ; the resulting RIV is defined by .
• Rotation of an RIV by some integer ; this shifts all of the values in to the left by indices. The first values at the start of go to the end of the array and become the rightmost values.

An RIV is written in its condensed form. This representation is a list that starts with the number of nonzero values, followed by a sorted list of indices (-indexed) that have nonzero values, where the indices are negated if the values there are .
For example, consider an RIV representing an array . There are nonzero elements at indices , , and , and the values at and are , so the condensed form of this RIV is .
Given two RIVs in condensed form, add them, multiply them, and rotate them both. Output the results in condensed form.

输入

The first line of input contains two space-separated integers and (), where is the full (uncondensed) length of the RIVs and is the number of indices to rotate by.
Each of the next two lines contains a condensed form of an RIV, starting with an integer (), followed by space-separated indices . Each index is a nonzero integer between and (inclusive).

输出

Output four vectors, one per line, in condensed form:

• Sum of the two input RIVs.
• Product of the two input RIVs.
• First RIV rotated by .
• Second RIV rotated by .

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
30 13 6 6 -9 -13 18 22 26 8 -1 3 7 11 13 19 20 -27	12 -1 3 6 7 -9 11 18 19 20 22 26 -27 1 -13 6 5 9 13 23 -26 -30 8 6 7 -14 -18 20 24 28 30
20 4 9 -2 -4 -8 -11 -12 15 18 19 20 7 4 5 -10 11 15 18 -20	8 -2 5 -8 -10 -12 15 18 19 5 -4 -11 15 18 -20 9 -4 -7 -8 11 14 15 16 -18 -20 7 1 -6 7 11 14 -16 20

题解

题意

计算两个RIV的和、积，以及两者分别位移位后的结果。

思路

• 和：筛选出所有非零位相加后保留所有非零位。
• 积：筛选出所有非零位相乘后保留所有非零位。
• 位移：所有非零位下标减，若小于则再加。

时间复杂度

代码

from collections import defaultdict

def resD_show(resD):
    if isinstance(resD, dict):
        res = sorted([(1 if resD[x] > 0 else -1) * x for x in resD if resD[x] != 0], key=abs)
    else:
        res = sorted(resD, key=abs)
    print(len(res), end="")
    for x in res:
        print("", x, end="")
    print()

def Operate(op):
    A = defaultdict(int)
    B = defaultdict(int)
    pos = set()
    for x in a:
        A[abs(x)] = 1 if x > 0 else -1
        pos.add(abs(x))
    for x in b:
        B[abs(x)] = 1 if x > 0 else -1
        pos.add(abs(x))
    resD = dict()
    for p in pos:
        resD[p] = op(A[p], B[p])
    resD_show(resD)

def Shift(lst):
    for i in range(len(lst)):
        sig = 1 if lst[i] > 0 else -1
        lst[i] = abs(lst[i]) - k
        if lst[i] <= 0:
            lst[i] += n
        lst[i] *= sig
    resD_show(lst)

n, k = [int(_) for _ in input().split()]
na, *a = [int(_) for _ in input().split()]
nb, *b = [int(_) for _ in input().split()]
Operate(lambda x, y: 1 if x + y == 2 else -1 if x + y == -2 else x + y)
Operate(lambda x, y: x * y)
Shift(a)
Shift(b)

S - Time Limits

原题面

描述

A contest setter wants to determine the time limits for a given problem. There are model solutions, and solution takes milliseconds to run on the test data. The contest setter wants the time limit to be an integer number of seconds, and wants the time limit to be at least times larger than the slowest model solution. Compute the minimum time limit the contest setter can set.

输入

The first line of input contains two space-separated integers and ( and ).
The second line of input contains space-separated integers ( for all ).

输出

Print, on one line, the minimum time limit (in seconds) as a single integer.

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
2 5 200 250	2
3 4 47 1032 1107	5

题解

题意

输出最大运行时间的倍向上取整到最小的整数秒数。

思路

直接计算即可。

时间复杂度

代码

from math import ceil

n, s = [int(_) for _ in input().split()]
slowest = max([int(_) for _ in input().split()])
print(ceil(slowest * s / 1000))