Cow Checkups
실버 II의견: 0
Farmer John's \(N\) (\(1 \leq N \leq 5 \cdot 10^5\)) cows are standing in a line,
with cow \(1\) at the front of the line and cow \(N\) at the back of the line. FJ's
cows also come in many different species. He denotes each species with an
integer from \(1\) to \(N\). The \(i\)'th cow from the front of the line is of species
\(a_i\) (\(1 \leq a_i \leq N\)).
FJ is taking his cows to a checkup at a local bovine hospital. However, the
bovine veterinarian is very picky and wants to perform a checkup on the \(i\)'th
cow in the line, only if it is species \(b_i\) (\(1 \leq b_i \leq N\)).
FJ is lazy and does not want to completely reorder his cows. He will perform
the following operation exactly once.
- Select two integers \(l\) and \(r\) such that \(1 \leq l \le r \leq N\). Reverse the order of the cows that are between the \(l\)-th cow and the \(r\)-th cow in the line, inclusive.
FJ wants to measure how effective this approach is. Find the sum of the number
of cows that are checked by the veterinarian over all \(N(N+1)/2\) possible
operations.
Problem credits: Chongtian Ma, Haokai Ma, and Alex Liang
SCORING
- Input 4: \(N\le 100\)
- Input 5: \(N\le 5000\)
- Inputs 6-9: \(a_i, b_i\) are all generated uniformly at random in the range \([1,N]\)
- Inputs 10-15: \(a_i, b_i\) are all generated uniformly at random in the range \([1,2]\)
- Inputs 16-23: No additional constraints.
Problem credits: Chongtian Ma, Haokai Ma, and Alex Liang
The first line contains an integer \(N\).
The second line contains \(a_1, a_2, \ldots, a_N\).
The third line contains \(b_1, b_2, \ldots, b_N\).
Output one line with the sum of the number of cows that are checked by the
veterinarian over all possible operations.
3
1 3 2
3 2 13If FJ chooses (\(l=1,r=1\)), (\(l=2,r=2\)), or (\(l=3,r=3\)) then no cows will be
checked. Note that those operations do not modify the location of the cows.
The following operations result in one cow being checked.
- \(l=1,r=2\): FJ reverses the order of the first and second cows so the species of each cow in the new lineup will be \([3,1,2]\). The first cow will be checked.
- \(l=2,r=3\): FJ reverses the order of the second and third cows so the species of each cow in the new lineup will be \([1,2,3]\). The second cow will be checked.
- \(l=1,r=3\): FJ reverses the order of the first, second, and third cows so the species of each cow in the new lineup will be \([2,3,1]\). The third cow will be checked.
The total number of cows checked over all six operations is \(0+0+0+1+1+1=3\).
3
1 2 3
1 2 312There are three possible operations that cause \(3\) cows to be checked:
(\(l=1,r=1\)), (\(l=2,r=2\)), and (\(l=3,r=3\)). The remaining operations each result
in \(1\) cow being checked. The total number of cows checked over all six
operations is \(3+3+3+1+1+1=12\).
7
1 3 2 2 1 3 2
3 2 2 1 2 3 160riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > January > Silver
평가 및 의견
Cow Checkups
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cow Checkups