#PU1515. USACO 2025 US Open Contest, Bronze — Problem 1. Hoof Paper Scissors Minus One

USACO 2025 US Open Contest, Bronze — Problem 1. Hoof Paper Scissors Minus One

USACO 2025 US Open Contest, Bronze — Problem 1. Hoof Paper Scissors Minus One

题目描述

Note: The time limit for this problem is 3s, 1.5x the default. In a game of Hoof Paper Scissors, Bessie and Elsie can put out one of NN (1≤N≤30001 \leq N \leq 3000) different hoof symbols labeled 1…N1\dots N, each corresponding to a different material. There is a complicated chart of how the different materials interact with one another, and based on that chart, either: One symbol wins and the other loses. The symbols draw against each other. Hoof Paper Scissors Minus One works similarly, except Bessie and Elsie can each put out two symbols, one with each hoof. After observing all four symbols that they have all put out, they each choose one of their two symbols to play. The outcome is decided based on normal Hoof Paper Scissor conventions. Given the MM (1≤M≤30001 \leq M \leq 3000) symbol combinations that Elsie plans to make across each game, Bessie wants to know how many different symbol combinations would result in a guaranteed win against Elsie. A symbol combination is defined as an ordered pair (L,R)(L,R) where LL is the symbol the cow plays with her left hoof and RR is the symbol the cow plays with her right hoof. Can you compute this for each game?

输入格式

The first line contains two space-separated integers NN and MM representing the number of hoof symbols and the number of games that Bessie and Elsie play. Out of the following NN lines of input, the iith line consists of ii characters ai,1ai,2…ai,ia_{i,1}a_{i,2}\ldots a_{i,i} where each ai,j∈{D,W,L}a_{i,j} \in \{\texttt D,\texttt W,\texttt L\}. If ai,j=Da_{i,j} = \texttt D, then symbol ii draws against symbol jj. If ai,j=Wa_{i,j} = \texttt W, then symbol ii wins against symbol jj. If ai,j=La_{i,j} = \texttt L, then symbol ii loses against symbol jj. It is guaranteed that ai,i=Da_{i,i} = \texttt D. The next MM lines contain two space separated integers s1s_1 and s2s_2 where 1≤s1,s2≤N1 \leq s_1,s_2 \leq N. This represents Elsie's symbol combination for that game.

输出格式

(见题面原文)

数据范围

Inputs 2-6: N,M≤100N,M\le 100 Inputs 7-12: No additional Problem credits: Suhas Nagar

样例

样例 1

3 3
D
WD
LWD
1 2
2 3
1 1
0
0
5
In this example, this corresponds to the
original Hoof Paper
Scissors
and we can let Hoof=1, Paper=2, and Scissors=3. Paper beats Hoof,
Hoof beats Scissors, and Scissors beats Paper. There is no way for Bessie to
guarantee a win against the combinations of Hoof+Paper or Paper+Scissors.
However, if Elsie plays Hoof+Hoof, Bessie can counteract with any of the
following combinations.
Paper+Paper
Paper+Scissors
Paper+Hoof
Hoof+Paper
Scissors+Paper
If Bessie plays any of these combinations, she can guarantee that she wins by
putting forward Paper.