作者expiate (弯曲屎壳郎)
看板Math
标题[其他] 怎麽证明这样的排序和输入一定可行？
时间Thu Sep 17 06:06:33 2020
我在做一道题如下：
https://nus.kattis.com/problems/longswaps
这道题我的作法是先排序然後在跟原来的输入一个字元一个字元比较
如果不同，就检查在限制k下能否跟其它字元做交换。
虽然通过测试的case，但我想是否有严谨的数学能证明呢？
谢谢了
下面是我的code，希望有帮助
int main(){
string str;
int k;
cin >> str >> k;
string sorted = str;
sort(sorted.begin(),sorted.end());
for(int i=0;i<str.size();++i){
if(str[i]!=sorted[i] && i-k<0 && i+k>=str.size()){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
--
与怪物战斗的人，应当小心自己不要成为怪物。
当你远远凝视深渊时，深渊也在凝视你。
弗里德里希·威廉·尼采
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 98.207.101.195 (美国)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1600294001.A.8D5.html
1F：→ hwanger : 看不懂原PO的算法 冏 提供一个 若|s|>=2k 则任意相 09/17 09:41
2F：→ hwanger : 邻两个都可以在其他不动的情况下互换 如考虑 09/17 09:44
3F：→ hwanger : (a1,a2,a3,a4, ,2)要换a3,a4 则a1,a3互换 a1,a4互 09/17 09:46
4F：→ hwanger : 换 a1,a3再互换 09/17 09:47
5F：→ hwanger : 但当|s|<2k时 a_{n-k},...,a_k是不能动的 但a1,..., 09/17 09:53
6F：→ hwanger : a_{n-k-1},a_k,a_{k+1},...,an是可以排序的(先把比 09/17 09:55
7F：→ hwanger : 较小的都丢到头 比较大都丢到尾 再用泡泡) 09/17 09:57
8F：→ hwanger : 所以只要检查排序前後的子字串a_{n-k},...,a_k是否 09/17 09:58
9F：→ hwanger : 一样即可 09/17 09:59
10F：→ hwanger : 上面|s|<2k的情况打错了 比较a_{n-k+1},...,a_k才对 09/17 10:12
※ 编辑: expiate (98.207.101.195 美国), 09/17/2020 11:08:35
11F：→ hwanger : 如果code就是原PO原本的算法 那上面就是证明的大纲 09/17 11:24
12F：→ hwanger : (任意相邻两个都可以在其他不动的情况下互换保证了 09/17 11:25
13F：→ hwanger : 泡泡) 09/17 11:25
14F：→ expiate : 请问你|s|是指string长度吗？s的起始状态都不会影响 09/17 11:32
15F：→ expiate : 最後的结果吗？还是你认为|s|>=2k保证可以排序? 09/17 11:34
16F：→ hwanger : |s|是string长度 不是我的符号 是你的网页里的符号 09/17 12:31
17F：→ hwanger : |s|>=2k 不论s是何 都可以排序 重点在这个情况 我 09/17 12:36
18F：→ hwanger : 们可以做到任意两个相邻位置的字符可以互换而不变 09/17 12:36
19F：→ hwanger : 动其他字符的位置 如此再依Bubble sort即可 09/17 12:36
20F：→ hwanger : 在你的code中 但当|s|>2k时 你for回圈里的if条件是 09/17 12:41
21F：→ hwanger : 永不满足的唷 09/17 12:41
22F：推 hwanger : typo: |s|>=2k 09/17 12:48
23F：→ expiate : 我想我可以理解，那数学上的证明就这样解释即可吗？ 09/17 13:07
24F：→ hwanger : Lemma: Assume |s|>=2k. Then we can exchange the 09/17 13:08
25F：→ hwanger : characters at i-th and (i+1)th positions without 09/17 13:09
26F：→ hwanger : change the positions of other characters. 09/17 13:09
27F：→ hwanger : Proof: Assume the string is "(a1)(a2)...(an)". 09/17 13:09
28F：→ hwanger : Case 1: If i<k, then consider 09/17 13:10
29F：→ hwanger : swap(ai,an)→swap(a{i+1},an)→swap(ai,an) 09/17 13:11
30F：→ hwanger : Case 2: If i>k, then consider 09/17 13:11
31F：→ hwanger : swap(ai,a1)→swap(a{i+1},a1)→swap(ai,a1) 09/17 13:11
32F：→ hwanger : Case 3: If i=k, then consider 09/17 13:12
33F：→ hwanger : swap(a{k+1},a1)→swap(a1,an)→swap(ak,an) 09/17 13:13
34F：→ hwanger : →swap(a1,an)→swap(a{k+1},a1) 09/17 13:13
35F：→ hwanger : 这样有一点程式基础的人都可以理解 对数学而言稍微 09/17 13:14
36F：→ hwanger : 可以接受 如果要全部转成数学语言的也是可以 09/17 13:15
37F：→ hwanger : 让(a1,a2,...,an)为一个1到26的有限序列 考虑所有的 09/17 13:17
38F：→ hwanger : permutation σ使得(a_σ(1),...,a_σ(n))为递增 09/17 13:19
39F：→ hwanger : 收集所有这样的σ的集合称作S 并令G为symmetric 09/17 13:22
40F：→ hwanger : group S_n的子群 G:=< (i,j) : |i-j|>=k > 则问题变 09/17 13:24
41F：→ hwanger : 成问S和G的交集是否非空 而证明这个问题的想法基本 09/17 13:25
42F：→ hwanger : 上就和一开始提到的想法一样 此时swap的角色就是 09/17 13:26
43F：→ hwanger : symmetric group里的transposition 09/17 13:27
44F：→ hwanger : 而上面的Lemma基本上就是说G包含(1,2),(2,3),..., 09/17 13:30
45F：→ hwanger : (n-1,n) 所以G就是S_n 自然而然S交G非空 09/17 13:32
46F：→ hwanger : 而对於n<2k 也是一样转换过来即可 09/17 13:34
47F：→ hwanger : 实际上在些情形下 G是由(1,2),(2,3),..,(n-k-1,n-k) 09/17 13:36
48F：→ hwanger : (k+1,k+2),...,(n-1,n)和(1,n)所生成的 也就是G是 09/17 13:37
49F：→ hwanger : {1,2,...,n-k,k+1,k+2,...,n}的permuation group 09/17 13:39
50F：→ hwanger : 此时S交G非空意味着存在一个σ在S中 使得σ(i)=i 对 09/17 13:42
51F：→ hwanger : 於所有i = n-k+1,...,k 09/17 13:43
52F：→ hwanger : 最後这些讨论只是为了严谨而存在 没有给出任何新知 09/17 13:55
53F：→ hwanger : 识唷 冏 09/17 13:56
54F：→ expiate : 非常感谢大大详细的解说，您总是这麽热心回答大家 09/18 01:30
55F：→ expiate : 的问题。再次感恩 09/18 01:30
56F：推 wohtp : 补充一下，s < 2k 就一定存在做不到的case。这样加 09/18 03:42
57F：→ wohtp : 起来才算完整解答原po的问题。 09/18 03:42
58F：→ expiate : 也感谢上面大大，真的谢谢你们拨冗回答问题 09/18 04:15