e975 - 3. 情書解密 (Love)
題目描述
題目要求找出最小的位移量 k，使得加密的情書解密後包含 "Love" 或 "love"。輸入為加密過的情書內容，輸出為最小位移量 k。
解題思路
這題採用暴力解法。由於位移量 k 的範圍是 0 到 25，因此可以迭代所有可能的位移量，並對每個位移量解密字串。解密後，檢查字串是否包含 "Love" 或 "love"。如果找到包含 "Love" 或 "love" 的字串，則返回對應的位移量。由於題目要求最小位移量，因此在找到第一個匹配的位移量後，立即返回。
程式碼中，getchar_unlocked() 用於快速讀取字元，putchar_unlocked() 用於快速輸出字元。迴圈中，將每個字元解密，如果字元超出字母範圍，則迴繞到字母的開頭。
複雜度分析
- 時間複雜度: O(26 * N)，其中 N 是字串的長度。因為需要迭代 26 種可能的位移量，並且對於每個位移量，需要遍歷整個字串。
- 空間複雜度: O(N)，因為需要儲存輸入字串。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int al=0;
char a[1001];
int main(){
while(a[al]=getchar_unlocked()){
if(a[al]==-1)break;++al;
}
for(int ans=0;;++ans){
for(int i=0;i<al;++i){
if((a[i]=='l'||a[i]=='L')&&a[i+1]=='o'&&a[i+2]=='v'&&a[i+3]=='e'){
if(ans<10)putchar_unlocked('0'+ans);
else{
putchar_unlocked('0'+ans/10);
putchar_unlocked('0'+ans%10);
}
return 0;
}
++a[i];
(a[i]>'z'||(a[i]>'Z'&&a[i]<'a'))?a[i]-=26:0;
}
}
}