2015年4月28日 星期二

[CF 533E] Correcting Mistakes

作法:

假設原字串為 X ,並且遺漏掉的兩個位子分別是 X[ a ] 和 X[ b ] ,其中 a < b ,那麼可以得到:S[ i ] = T[ i ] ,對於所有的 i < a 或 i >= b ,並且對於 a ~ b 之間的區間,會變成兩個字串位移一個,也就是如果設 S 是漏掉 X[ a ] 的字串, T 是漏掉 X[ b ] 的字串,那麼 S[ i ] = T[ i + 1 ] ,其中 a <= i < b - 1 。因此只要先找到兩個字串從左邊開始比對的第一個不一樣的點,還有從右邊開始比對的第一個不一樣的點,把中間的部份切下來,看把 S 往左移一格或往右移一格會不會和 T 一模一樣就好了。

這題我在賽中 hack 到了3個人,用的測資是: 3 aba bab ,答案是 2 ,不少人都以為如果兩個字串不一樣的位置太多,那麼答案一定 <= 1 。

code :



#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
char s[maxn],t[maxn] ;
main()
{
    int n ; scanf("%d%s%s",&n,s+1,t+1) ;
    int x=-1 , y=-1 ;
    for(int i=1;i<=n;i++) if(s[i]!=t[i])
        {x=i ; break ;}
    for(int i=n;i>=1;i--) if(s[i]!=t[i])
        {y=i ; break ;}
 
    int ans=0 , i ;
    for(i=x;i<y;i++) if(s[i]!=t[i+1]) break ;
    if(i==y) ans++ ;
    for(i=x;i<y;i++) if(t[i]!=s[i+1]) break ;
    if(i==y) ans++ ;
 
    printf("%d\n",ans) ;
}
 

沒有留言:

張貼留言