#CW79. 礼物交换(gift)
礼物交换(gift)
题目描述
有 头奶牛和 种礼物,编号均为 。第 头奶牛给出一个长度为 的排列作为愿望表;礼物在表中越靠前,奶牛越喜欢。最初奶牛 得到礼物 。
重新分配后,每头奶牛必须得到原礼物,或得到愿望表中排在原礼物之前的礼物;每种礼物恰好分配给一头奶牛。每头奶牛还标记为 H 或 G。查询给出一个长度为 的字符串,表示各奶牛标记。标记为 H 的奶牛只能在彼此之间交换礼物,标记为 G 的奶牛也只能在彼此之间交换,禁止跨组交换。请输出合法方案数。
输入格式
从 gift.in 文件中读入。
第一行是 ,满足 。接下来 行是愿望表排列。下一行是 ,满足 。接下来 行各有一个长度为 、只含 G 和 H 的字符串,且字符串互不相同。
输出格式
向 gift.out 文件中输出。
对每个查询输出一行合法重新分配方案数。
样例 1 输入
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG
样例 1 输出
2
1
1
2
2
样例 1 解释
奶牛 1 最喜欢礼物 1,因此它只能保留礼物 1。奶牛 2 可以接受礼物 1, 3, 2,奶牛 3 可以接受礼物 1, 2, 3。由于礼物 1 已被奶牛 1 占用,奶牛 2 和奶牛 3 必须分配礼物 2 和礼物 3,奶牛 4 也就只能保留礼物 4。
暂不考虑标记时,恰好有两种满足喜好要求的分配:奶牛 1, 2, 3, 4 依次得到礼物 ,或依次得到礼物 。前者始终合法;后者交换了奶牛 2 和奶牛 3 的礼物,只有这两头奶牛的标记相同时才合法。
因此,查询 HHHH、HGGG、GHHG 都有 2 种方案;查询 HHGG、GHGH 中奶牛 2 与奶牛 3 的标记不同,只有保留原礼物的 1 种方案。按查询顺序输出即为 2, 1, 1, 2, 2。
数据范围
所有输入数据均为整数。每行愿望表都是 的完整排列。
本题采用子任务捆绑计分:通过一个子任务的全部测试点,才能获得该子任务的分数。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 20 | ||
| 2 | 25 | ||
| 3 | |||
| 4 | 30 | 无额外限制 |