这道题把两个拼在一起,不能翻转,我们可以固定一的位置,把二放到一下面,但是不要忘记,第二个的最左端可以在第一个最左端的左边,所以遍历二的左边的可能性实际上(假设一最左边位置为b1,长度n1,二类推)从b1-n2到b1+n1,如果我们把n2取最大100,那不妨假定b1位置就为100,当n2实际没有100时,假设为50,那我们从0到50的位置实际上第一个和第二个并不会接触,这些情况答案大于n1+n2,但是最终答案并不会改变,因为继续遍历必定会遍历到n1+n2,而n1+n2小于之前这些从0到50的这些不存在的情况的答案,所以无所谓。
#include <bits/stdc++.h> using namespace std; char first[105], second[105]; int fir[305],sec[105];//注意因为第一段的左100,右100和自己的100都是合法的位置,因为第二段可以放到第一段的最右,当两段均为100时,第一段的起始位置为100,末尾200,加上第二段就300 int main() { while(scanf("%s", first) != EOF) { memset(fir, 0, sizeof(fir)); memset(sec, 0, sizeof(sec)); int ans = 0x3f3f3f3f; scanf("%s", second); int fir_cnt = strlen(first); int sec_cnt = strlen(second); for(int i = 0; i < fir_cnt; i++) { fir[100 + i] = first[i] - '0';//第一段最左边从100开始,因为从0~99这100个位置可能放置第二段的 } for(int i = 0; i < sec_cnt; i++) { sec[i] = second[i] - '0'; } for(int i = 0; i < fir_cnt + 100; i++)//第二段的起始位置 { bool flag = true; for(int j = 0; j < sec_cnt; j++) { if(fir[i + j] + sec[j] > 3) { flag = false; break; } } if(flag) { ans = min(ans, max(fir_cnt + 100, i + sec_cnt) - min(i, 100));//取两段最右减去两段最左即得到两段合起来的两端长度 } } printf("%d\n", ans); } return 0; }