USACO07MAR Face The Right Way G 差分
- 2020 年 4 月 6 日
- 筆記
題目鏈接 https://www.luogu.com.cn/problem/P2882
分析
這個題來看的話好像有點難下手，不如再去讀一遍題 N遍，發現一句話很重要Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line，就是說只能翻轉固定的長度區間，那這樣是不是就可以枚舉區間了？枚舉一層區間,再枚舉每次起點，最後加上區間修改，時間複雜度(O(N^3))，肯定會T掉，接下來就考慮優化了。
優化怎麼入手呢？時間主要就是出在這三層循環上，只要省掉一層循環，時間複雜度就能到(O(N^2))，這樣就可以過，第一層循環，顯然不能省略，第二層同樣，只有在區間修改這一層循環上可以做點手腳，回憶區間修改，有幾種做法，線段樹，樹狀數組，還有差分，前兩者用在這都有點大材小用或是說不是很合適，因為判斷是否區間修改完成不好判斷，而差分用在這個區間上就很合適了。那我們大概思路也就有了，首先讀入數組，將B標記成1，F標記成0，這裡怎麼標記都無所謂，然後利用枚舉區間，差分修改，最後輸出答案，下面考慮一下細節。
我們枚舉區間完，要從左到右一次反轉區間，為什麼呢？題目中要求的是最小次數，就是要先保證次數最小，再考慮區間長度，而我們如果先修改後面的，把後面改好了，再去改前邊的，結果一定不會比先改前邊的好（有可能相等，如00100），所以我們為保證最小次數，一定從最左端開始依次枚舉，如果這個點不符合，就把他後面的整個區間翻轉，這裡就要用到差分了，肯定直接修改會T掉，我們可以考慮，如果這個區間要修改，那麼原來的1會變成2，0會變成1，好像沒什麼規律，但再看就發現所有的奇數都需要改變，偶數就不用，每次修改給整個區間加一，判斷奇偶數就行，然後這就變成了一個區間加一個數的操作，相信大家應該都會。這樣修改就完成了，那麼怎麼判斷能不能完成題目的任務呢？由題意可以知道如果當前區間長度小於修改的區間長度，是不能修改的，也就是從n往前的長度為len的區間總是無法被修改的，所以判斷這一段區間內有無不滿足條件的點即可。
最後找答案的時候也有一個地方，就是當操作修改次數不同時，直接用操作修改次數最小的那個答案就行，但如果當前操作次數和原來答案相同，是不是要考慮一下區間長度改成最小值？答案顯然是不是，…………，因為我們是從小到大枚舉的區間長度，所以在遇到相等的時候，已經得到的答案的區間長一定是小的，所以只在次數不同時修改答案，但判斷上也不會錯。
其他優化
當然以下優化不加也沒問題，畢竟演算法時間複雜度足夠過掉這道題。
我做完之後看了看時間大概700ms左右，好像有點高，看別人的時間好像沒有特別大，所以我加了加小優化。
為方便說，由上到下一次標號(1-4),1,2跑的時間還是挺快的但沒啥用，(NOIp)不可能給你開O2也不可能給你c++17，所以還是看一下3和4，這倆時間大概有一倍的關係，看一下程式碼吧
3
#include<cstdio> #include<cstring> using namespace std; const int N=5e3+10; char s[3]; int cf[N],a[N]; int min(int a,int b){ if(a<b)return a; else return b; } int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s); if(s[0]=='B')a[i]=1; else a[i]=0; } int res=0x3f3f3f3f,ans=0x3f3f3f3f; for(int len=1;len<=n;len++){ int cnt=1,k=0;memset(cf,0,sizeof(cf)); for(int i=1;i<=n;i++){ cf[i]+=cf[i-1]; if(i+len-1<=n){ if(a[i]+cf[i]&1){ cf[i]++;cf[i+len]--;k++; } }else if(cf[i]+a[i]&1){cnt=0;break;} } if(cnt) if(k<ans){ ans=k;res=len; } else if(k==ans)res=min(res,len); } printf("%d %d",res,ans); return 0; } 4
#include<cstdio> #include<cstring> using namespace std; const int N=5e3+10; char s[3]; int cf[N],a[N]; int min(int a,int b){ if(a<b)return a; else return b; } int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s); if(s[0]=='B')a[i]=1; else a[i]=0; } int res=0x3f3f3f3f,ans=0x3f3f3f3f; for(int len=1;len<=n;len++){ int cnt=1,k=0;memset(cf,0,sizeof(cf)); for(int i=1;i<=n;i++){ cf[i]+=cf[i-1]; if(i+len-1<=n){ if(a[i]+cf[i]&1){ cf[i]++;cf[i+len]--;k++; } }else if(cf[i]+a[i]&1)cnt=0; } if(cnt) if(k<ans){ ans=k;res=len; } else if(k==ans)res=min(res,len); } printf("%d %d",res,ans); return 0; } 其實就是少一個break，感覺這個加上還是很有必要的，因為可能極限數據的時候，CCF那評測機狀態不好，再卡一下，可能會出問題。
