https://codeforces.com/contest/1971
pythoncf_2">前5题python题解（cf翻译代码符号可能变中文）
1.My First Sorting Problem
题面翻译
有 t t t 组数据，每组数据给你两个整数 x x x 和 y y y 。
输出两个整数： x x x 和 y y y 中较小的那个，然后是 x x x 和 y y y 中较大的那个。
题目描述
You are given two integers $ x $ and $ y $ .
Output two integers: the minimum of $ x $ and $ y $ , followed by the maximum of $ x $ and $ y $ .
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases.
The only line of each test case contains two space-separated integers $ x $ and $ y $ ( $ 0 \leq x, y \leq 9 $ ).
输出格式
For each test case, output two integers: the minimum of $ x $ and $ y $ , followed by the maximum of $ x $ and $ y $ .
样例 #1
样例输入 #1
10
1 9
8 4
1 4
3 4
2 0
2 4
6 9
3 3
0 0
9 9
样例输出 #1
1 9
4 8
1 4
3 4
0 2
2 4
6 9
3 3
0 0
9 9
题意：输入x,y将他们两个从小到大输出思路：签到题
python">t=int(input())
for i in range(t):x,y=map(int,input().split())if x>y:x,y=y,xprint(x,y)
2.Different String
题面翻译
题目描述
给定一个以小写字母构成的字符串 s s s。
现在你的任务是，重新排列 s s s 的字符以形成一个不等于 s s s 的新字符串 r r r。
输入格式
本题单个测试点内包含多组测试数据。
第一行包含一个整数 t t t（ 1 ≤ t ≤ 1000 1\leq t\leq 1000 1≤t≤1000），表示测试数据组数。
每个测试用例的唯一一行包含一个字符串 s s s，长度最多为 10 10 10，由小写英文字母组成。
输出格式
对于每个测试用例，如果不存在语句中描述的字符串 r r r，则输出NO。
否则，输出YES。然后，输出一行一个字符串 r r r，由字符串 s s s 的字母组成。
你可以以任何大小写形式输出YES和NO。
如果可以有多个答案，则可以输出其中任何一个。
题目描述
You are given a string $ s $ consisting of lowercase English letters.
Rearrange the characters of $ s $ to form a new string $ r $ that is not equal to $ s $ , or report that it’s impossible.
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases.
The only line of each test case contains a string $ s $ of length at most $ 10 $ consisting of lowercase English letters.
输出格式
For each test case, if no such string $ r $ exists as described in the statement, output “NO” (without quotes).
Otherwise, output “YES” (without quotes). Then, output one line — the string $ r $ , consisting of letters of string $ s $ .
You can output “YES” and “NO” in any case (for example, strings “yEs”, “yes”, and “Yes” will be recognized as a positive response).
If multiple answers are possible, you can output any of them.
样例 #1
样例输入 #1
8
codeforces
aaaaa
xxxxy
co
d
nutdealer
mwistht
hhhhhhhhhh
样例输出 #1
YES
forcodesec
NO
YES
xxyxx
YES
oc
NO
YES
undertale
YES
thtsiwm
NO
提示
In the first test case, another possible answer is $ \texttt{forcescode} $ .
In the second test case, all rearrangements of $ \texttt{aaaaa} $ are equal to $ \texttt{aaaaa} $ .
题意：输入一个字符串，如果变化排序可以变成新的字符串，就输出yes和随机一个字符串结果，反之输出no思路：1.做一个判断特例：只有一个字符和一个字符串中的字符全部 一样的，输出no 2.其他处理生成随机字符串，因为只要生成任意一种结果，所以生成方式有很多，这里是将第一个字符放到最后一个。
python">t=int(input())
for i in range(t):s=input()if len(s)==1 or len(set(s))==1:print('no')else:print('yes')s1=''s2=''for j in s:if len(set(s2))==0:s2+=jelse:s1+=jprint(s1+s2)3.Clock and Strings
题面翻译
输入 t ( 1 ≤ t ≤ 5940 ) t(1\le t\le 5940) t(1≤t≤5940) 行，每行 4 4 4 个整数 a , b , c , d ( 1 ≤ a , b , c , d ≤ 12 ) a,b,c,d(1\le a,b,c,d\le 12) a,b,c,d(1≤a,b,c,d≤12)，表示钟面上 a , b a, b a,b 和 c , d c, d c,d 两条线段的四个端点所对应的刻度，问这两条线段会不会在钟面上相交。如果会，则输出 YES，不会则输出 NO。
题目描述
There is a clock labeled with the numbers $ 1 $ through $ 12 $ in clockwise order, as shown below.
In this example, $ (a,b,c,d)=(2,9,10,6) $ , and the strings intersect.
Alice and Bob have four distinct integers $ a $ , $ b $ , $ c $ , $ d $ not more than $ 12 $ . Alice ties a red string connecting $ a $ and $ b $ , and Bob ties a blue string connecting $ c $ and $ d $ . Do the strings intersect? (The strings are straight line segments.)
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 5940 $ ) — the number of test cases.
The only line of each test case contains four distinct integers $ a $ , $ b $ , $ c $ , $ d $ ( $ 1 \leq a, b, c, d \leq 12 $ ).
输出格式
For each test case, output “YES” (without quotes) if the strings intersect, and “NO” (without quotes) otherwise.
You can output “YES” and “NO” in any case (for example, strings “yEs”, “yes”, and “Yes” will be recognized as a positive response).
样例 #1
样例输入 #1
15
2 9 10 6
3 8 9 1
1 2 3 4
5 3 4 12
1 8 2 10
3 12 11 8
9 10 12 1
12 1 10 2
3 12 6 9
1 9 8 4
6 7 9 12
7 12 9 6
10 12 11 1
3 9 6 12
1 4 3 5
样例输出 #1
YES
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
提示
The first test case is pictured in the statement.
In the second test case, the strings do not intersect, as shown below.
题意：一个圆里面化12分，两两相连看是否有交点，有输出yes，没有输出no思路：固定两个点的区间，判断另外两个点是否在这个区间里，只要一个在另一个不在就输出yes，其余输出no（注意端点相交）
python">t=int(input())
for i in range(t):a,b,c,d=map(int,input().split())n=0if a>b:a,b=b,aif a<=c<=b:n+=1if a<=d<=b:n+=1if n%2==1:print('YES')else:print('NO')
4.Binary Cut
题面翻译
题目描述
给定一个二进制字符串 $ ^{\dagger} $ 。请找到您需要将其切割成的最小片段数，将生成的片段重新排列成有序的二进制字符串。
请注意：
- 每个字符必须恰好位于其中一个片段中；
- 这些片段必须是原始字符串的连续子字符串；
- 你必须在重排中使用所有的片段。
† ^{\dagger} †二进制字符串是由字符 $ \texttt{0}$ 和 1 \texttt{1} 1 组成的字符串。排序后的二进制字符串是一个二进制字符串，使得所有字符 0 \texttt{0} 0 位于所有字符 1 \texttt{1} 1 之前。
输入格式
第一行包含一个整数 t t t（ 1 ≤ t ≤ 500 1\leq t\leq 500 1≤t≤500）——测试用例的数量。
每个测试用例的唯一一行包含一个由 0 \texttt{0} 0 和 1 \texttt1 1 组成的字符串 s s s （ 1 ≤ ∣ s ∣ ≤ 500 1 \leq |s| \leq 500 1≤∣s∣≤500），其中 ∣ s ∣ |s| ∣s∣ 表示字符串 s s s 的长度。
输出格式
对于每个测试用例，输出将字符串重新排列为有序二进制字符串所需的最小分割数量。
题目描述
You are given a binary string $ ^{\dagger} $ . Please find the minimum number of pieces you need to cut it into, so that the resulting pieces can be rearranged into a sorted binary string.
Note that:
- each character must lie in exactly one of the pieces;
- the pieces must be contiguous substrings of the original string;
- you must use all the pieces in the rearrangement.
$ ^{\dagger} $ A binary string is a string consisting of characters $ \texttt{0} $ and $ \texttt{1} $ . A sorted binary string is a binary string such that all characters $ \texttt{0} $ come before all characters $ \texttt{1} $ .
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 500 $ ) — the number of test cases.
The only line of each test case contains a single string $ s $ ( $ 1 \leq |s| \leq 500 $ ) consisting of characters $ \texttt{0} $ and $ \texttt{1} $ , where $ |s| $ denotes the length of the string $ s $ .
输出格式
For each test case, output a single integer — the minimum number of pieces needed to be able to rearrange the string into a sorted binary string.
样例 #1
样例输入 #1
6
11010
00000000
1
10
0001111
0110
样例输出 #1
3
1
1
2
1
2
提示
The first test case is pictured in the statement. It can be proven that you can’t use fewer than $ 3 $ pieces.
In the second and third test cases, the binary string is already sorted, so only $ 1 $ piece is needed.
In the fourth test case, you need to make a single cut between the two characters and rearrange them to make the string $ \texttt{01} $ .
题意：切割二进制字符串，达到0和1分开（0在1前面）的最小分割次数。思路:三种情况：- 当我们遇到一段全是 `0` 或全是 `1` 的字符串，就不需要分开；
- 当我们遇到 `01` 这个子串时，我们只能保留一个 `01` 子串；
- 当我们遇到 `10` 就一定得分段。最后要记住加 1，因为本来就有一段。
python">t=int(input())
for i in range(t):s=input()x=0y=0for i in range(len(s)-1):if s[i]=='1' and s[i+1]=='0':x+=1elif s[i]=='0' and s[i+1]=='1':if y==0:y=1else:x+=1print(x+1)
5.Find the Car
题面翻译
一条笔直的公路上有 k k k 个标志，已知这条公路的长度 n n n，第 i i i 个标志位于 a i a_{i} ai 点，一辆大巴车从 0 0 0 点出发，从一个站点到另一个站点匀速行驶，并在 b i b_{i} bi 分钟经过第 i i i 个标志。现给出 q q q 个询问，求大巴车经过 d d d 点的时间（向下取整）。
输入有 t t t 组，对于每组数据的 q q q 个询问，输出一行，用空格间隔。
对于 100 % 100\% 100% 的数据， 1 ≤ t ≤ 1 0 4 1\le t\le 10^4 1≤t≤104， k ≤ n ≤ 1 0 9 k\le n\le 10^9 k≤n≤109， 1 ≤ k , q ≤ 1 0 5 1\le k,q\le 10^5 1≤k,q≤105， 1 ≤ a 1 < a 2 < … < a k = n 1\le a_1<a_2<\ldots<a_k=n 1≤a1<a2<…<ak=n， 1 ≤ b 1 < b 2 < … < b k ≤ 1 0 9 1\le b_1<b_2<\ldots<b_k\le 10^9 1≤b1<b2<…<bk≤109。
题目描述
Timur is in a car traveling on the number line from point $ 0 $ to point $ n $ . The car starts moving from point $ 0 $ at minute $ 0 $ .
There are $ k+1 $ signs on the line at points $ 0, a_1, a_2, \dots, a_k $ , and Timur knows that the car will arrive there at minutes $ 0, b_1, b_2, \dots, b_k $ , respectively. The sequences $ a $ and $ b $ are strictly increasing with $ a_k = n $ .
Between any two adjacent signs, the car travels with a constant speed. Timur has $ q $ queries: each query will be an integer $ d $ , and Timur wants you to output how many minutes it takes the car to reach point $ d $ , rounded down to the nearest integer.
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.
The first line of each test case contains three integers $ n $ , $ k $ , and $ q $ , ( $ k \leq n \leq 10^9 $ ; $ 1 \leq k, q \leq 10^5 $ ) — the final destination, the number of points Timur knows the time for, and the number of queries respectively.
The second line of each test case contains $ k $ integers $ a_i $ ( $ 1 \leq a_i \leq n $ ; $ a_i < a_{i+1} $ for every $ 1 \leq i \leq k-1 $ ; $ a_k = n $ ).
The third line of each test case contains $ k $ integers $ b_i $ ( $ 1 \leq b_i \leq 10^9 $ ; $ b_i < b_{i+1} $ for every $ 1 \leq i \leq k-1 $ ).
Each of the following $ q $ lines contains a single integer $ d $ ( $ 0 \leq d \leq n $ ) — the distance that Timur asks the minutes passed for.
The sum of $ k $ over all test cases doesn’t exceed $ 10^5 $ , and the sum of $ q $ over all test cases doesn’t exceed $ 10^5 $ .
输出格式
For each query, output a single integer — the number of minutes passed until the car reaches the point $ d $ , rounded down.
样例 #1
样例输入 #1
4
10 1 3
10
10
0
6
7
10 2 4
4 10
4 7
6
4
2
7
1000000000 1 1
1000000000
1000000000
99999999
6 1 3
6
5
2
6
5
样例输出 #1
0 6 7
5 4 2 5
99999999
1 5 4
提示
For the first test case, the car goes from point $ 0 $ to point $ 10 $ in $ 10 $ minutes, so the speed is $ 1 $ unit per minute and:
- At point $ 0 $ , the time will be $ 0 $ minutes.
- At point $ 6 $ , the time will be $ 6 $ minutes.
- At point $ 7 $ , the time will be $ 7 $ minutes.
For the second test case, between points $ 0 $ and $ 4 $ , the car travels at a speed of $ 1 $ unit per minute and between $ 4 $ and $ 10 $ with a speed of $ 2 $ units per minute and:
- At point $ 6 $ , the time will be $ 5 $ minutes.
- At point $ 4 $ , the time will be $ 4 $ minutes.
- At point $ 2 $ , the time will be $ 2 $ minutes.
- At point $ 7 $ , the time will be $ 5.5 $ minutes, so the answer is $ 5 $ .
For the fourth test case, the car travels with $ 1.2 $ units per minute, so the answers to the queries are:
- At point $ 2 $ , the time will be $ 1.66\dots $ minutes, so the answer is $ 1 $ .
- At point $ 6 $ , the time will be $ 5 $ minutes.
- At point $ 5 $ , the time will be $ 4.16\dots $ minutes, so the answer is $ 4 $ .
题意：一动点到定点，随时间变化的求离到点的时间
思路：二分查找
对路段数组 a 进行排序，确保路段按照起点的顺序排列。
对于每个查询的指定点 d使用二分查找找到第一个大于等于d 的元素的位置，即找到指定点所在的路段。
有数学上的线性插值的思想求间隔的时间在加上在t中查询m的时间
python">import bisect
t=int(input())
for i in range(t):n,k,q=list(map(int,input().split()))p=[0]+list(map(int,input().split()))t=[0]+list(map(int,input().split()))c=[]for j in range(q):m=int(input())idx=bisect.bisect_left(p,m)temp=t[idx-1]rem=(m-p[idx-1])*(t[idx]-t[idx-1])//(p[idx]-p[idx-1])temp+=remc.append(temp)print(*c)
