M. 在Kem Kadrãn中移除硬币AI (CI翻译)（GLM 5.3 Flash）
题目描述
Andréh and his friend Andréas are board-game aficionados. They know many of their friends would love to go on a trip to Phuket, Thailand, and so they want to challenge them at Kem Kradãn, a traditional Thai board game.
Andréh 和他的朋友 Andréas 是桌游爱好者。他们知道许多朋友都想去泰国普吉岛旅行，因此他们想在 Kem Kradãn——一种传统的泰国桌游——中挑战他们。AI (CI翻译)（GLM 5.3 Flash）
Kem Kradãn (เกมกระดาน) has been played since the 2nd century AD. The game is played with N pieces where each piece has two faces, one of which is golden and the other is white. The game starts with all pieces arranged in a line on the board and they are numbered from 1 to N from left to right. When a piece numbered i has its golden face up, it can be removed from the board. When this is done, the pieces numbered i - 1 and i + 1 are flipped, if they're still there. The goal is to remove all game pieces.
Kem Kradãn（棋盘游戏）自公元 2 世纪起就有人游玩。该游戏使用 N 个棋子，每个棋子有两个面，一面是金色，另一面是白色。游戏开始时，所有棋子排成一行放在棋盘上，并从左到右编号为 1 到 N。当编号为 i 的棋子金色面朝上时，可以将其从棋盘上移除。这样做时，如果编号为 i - 1 和 i + 1 的棋子仍在棋盘上，则翻转它们。目标是将所有棋子移除。AI (CI翻译)（GLM 5.3 Flash）
Before challenging their friends, Andréh and Andréas want to make sure their initial configurations have a solution. To help them, given an initial configuration, you must determine if it is possible to remove all game pieces and, if so, you must show how to do it.
在向朋友们发起挑战之前，Andréh 和 Andréas 想确保他们的初始配置有解。为了帮助他们，给定一个初始配置，你必须判断是否可能移除所有游戏棋子；如果可能，你还必须展示如何做到。AI (CI翻译)（GLM 5.3 Flash）
输入格式
The first line has a single integer T, the number of test cases.
第一行有一个整数T，表示测试用例的数量。AI (CI翻译)（GLM 5.3 Flash）
Each test case is formed by a line containing an integer N, the number of pieces, followed by line containing a string of length N containing only the letters B (white face up) and D (golden face up), representing the initial state of the game.
每个测试用例由一行包含整数 N（棋子数量）以及随后一行包含长度为 N、仅由字母 B（白色面朝上）和 D（金色面朝上）组成的字符串构成，表示游戏的初始状态。AI (CI翻译)（GLM 5.3 Flash）
Limits
限制AI (CI翻译)（GLM 5.3 Flash）
1 ≤ T ≤ 100
1 ≤ T ≤ 100AI (CI翻译)（GLM 5.3 Flash）
1 ≤ N ≤ 105
1 ≤ N ≤ 105AI (CI翻译)（GLM 5.3 Flash）
The sum of N over all test cases will not exceed 5·105
所有测试用例中 N 的总和不会超过 5·105AI (CI翻译)（GLM 5.3 Flash）
输出格式
For each test case, print a line containing Y if it is possible to remove every piece from the board, or N otherwise. In case it is possible to remove all the pieces, you should also print on the next line a sequence of N integers each representing a piece number, indicating the order in which the pieces must be removed. If there is more than one possible sequence, you can print any of them.
对于每个测试用例，如果可以从棋盘上移除每个棋子，则输出一行 Y，否则输出 N。如果能够移除所有棋子，你还应在下一行输出一个由 N 个整数组成的序列，每个整数表示一个棋子编号，表示必须移除棋子的顺序。如果存在多个可能的序列，你可以输出其中任意一个。AI (CI翻译)（GLM 5.3 Flash）
样例
样例 1
4
3
BDB
5
DBDDB
5
DDBDD
6
DBBBBBY
2 3 1
Y
4 5 1 2 3
N
Y
1 2 3 4 5 6D. 泰国的随机游走AI (CI翻译)（GLM 5.3 Flash）
题目描述
Thailand is made up of a few hundred islands. In each reasonably-sized island there is an airport used by small aircraft. However, the transport system seems quite peculiar for visitors...
泰国由几百座岛屿组成。在每座规模尚可的岛屿上，都有一个供小型飞机使用的机场。然而，对于游客来说，这里的交通似乎相当奇特……AI (CI翻译)（GLM 5.3 Flash）
Ferry boats are very reliable. For instance, you can depart from Ko Khang Khao (เกาะคางคาว) and get to neighbouring islands for a reasonable price using ferry boats: Ko Sichang (เกาะสชง), Ko Kham Yai (เกาะขามใหญ), Ko Kham Noi (เกาะขามนอย), Ko Ram Dok Mai (เกาะรามดอกไม), Ko Prong (เกาะปรง)}, or Ko Yai Thao (เกาะใหญทาว) (Yes, Ko means island in Thai).
渡船非常可靠。例如，你可以从 Ko Khang Khao (เกาะคางคาว) 出发，以合理的价格乘坐渡船到达邻近岛屿：Ko Sichang (เกาะสชง)、Ko Kham Yai (เกาะขามใหญ)、Ko Kham Noi (เกาะขามนอย)、Ko Ram Dok Mai (เกาะรามดอกไม)、Ko Prong (เกาะปรง)}，或 Ko Yai Thao (เกาะใหญทาว)（是的，Ko 在泰语中意为岛）。AI (CI翻译)（GLM 5.3 Flash）
The airplane pilots, on the other hand, are very erratic. Once you pay the flight fare, the pilot will drop you off at a random island, each with the same probability, including the one you departed from. Even though the destination of the flight is random, the price is always K baht.
另一方面，飞机驾驶员非常反复无常。一旦你支付了机票费，驾驶员就会把你随机送到一个岛上，每个岛的概率相同，包括你出发的那个岛。尽管航班目的地是随机的，票价始终是 K 泰铢。AI (CI翻译)（GLM 5.3 Flash）
So when you want to go from one island to another you always have two options. Get a boat to a neighboring island, where the price varies according to the route, or get a flight.
所以，当你想从一个岛屿到另一个岛屿时，总是有两种选择。乘船前往相邻岛屿，价格根据路线而变化，或者乘飞机。AI (CI翻译)（GLM 5.3 Flash）
The islands are numbered from 1 to N. Your task is to determine the minimum expected price of a trip from island 1 to N.
岛屿从 1 到 N 编号。你的任务是确定从岛屿 1 到 N 的旅行的最小期望价格。AI (CI翻译)（GLM 5.3 Flash）
输入格式
The first line has a single integer T, the number of test cases.
第一行有一个整数 T，表示测试用例的数量。AI (CI翻译)（GLM 5.3 Flash）
The first line of each test case has 3 integers, N, M, and K, that represents the number of islands, the number of boats, and the cost of getting a flight, respectively.
每个测试用例的第一行有 3 个整数 N、M 和 K，分别表示岛屿的数量、船的数量以及乘坐航班的费用。AI (CI翻译)（GLM 5.3 Flash）
The next M lines contain 3 integers each, A, B, C, indicating that there exists a boat trip that costs C baht to go from island A to B or from B to A. There exists at most one boat servicing each pair of islands.
接下来的 M 行每行包含 3 个整数 A, B, C，表示存在一次船程，花费 C 泰铢，可以从岛屿 A 到 B 或从 B 到 A。每对岛屿之间至多有一艘船提供服务。AI (CI翻译)（GLM 5.3 Flash）
Limits
限制AI (CI翻译)（GLM 5.3 Flash）
1 ≤ T ≤ 20
1 ≤ T ≤ 20AI (CI翻译)（GLM 5.3 Flash）
1 ≤ N, M ≤ 105
1 ≤ N, M ≤ 105AI (CI翻译)（GLM 5.3 Flash）
1 ≤ C ≤ 103
1 ≤ C ≤ 103AI (CI翻译)（GLM 5.3 Flash）
1 ≤ K ≤ 103
1 ≤ K ≤ 103AI (CI翻译)（GLM 5.3 Flash）
输出格式
For each instance, print the minimum expected value of a trip from island 1 to island N. The error should not exceed 10 - 4.
对于每个实例，输出从岛屿 1 到岛屿 N 的旅行的最小期望值。误差不应超过 10^{-4}。AI (CI翻译)（GLM 5.3 Flash）
样例
样例 1
2
3 3 1
1 2 10
1 3 20
2 3 5
3 3 100
1 2 10
1 3 20
2 3 53.0000000000
15.0000000000