1. 首頁 > 生活百科 > >

C.差分維護，D.容斥原理 CodeTON Round 3

生活百科

C. Complementary XOR題目大意：給你兩個01串ab，問你是否可以通過一下兩種操作在不超過n+5次的前提下將兩個串都變為0，同時需要輸出可以的操作方案

  1. 選擇一個區間[l,r]
  2. 將串a的[l,r]翻轉(0 \(\rightarrow\) 1,1 $\rightarrow$0)， 同時將b的[1,l)和（r,n]區間翻轉
解題思路：通過寫兩組樣例，我們可以嘗試這種思路 ， 因為我們需要輸出可以的操作方案，我們很難去考慮同時操作a,b兩個串的操作，所以我們嘗試只考慮a串 。將a串的全部0變成1，觀察b串經過這種操作后的結果 。我們可以發現，如果a串全為1，那b串此時有三種可能：
  1. 全為0
  2. 全為1
  3. 即含1，又含0
我們發現狀況1可以通過對a進行一次[1,n]操作使a，b都為0狀況2可以通過對a進行一次[1,1],[2,n]操作使a,b都為0（觀察最后一個樣例）但是狀況3我們沒有任何辦法使得a，b都為0
自此整個題目分析完畢，我們只需要記錄讓a全部為1的操作對b的影響，最后看b串是否屬于情況1,2即可
我們觀察操作對b的影響是對[1,l)和（r,n]整個的影響，所以可以理解為對[1,l)和（r,n]操作次數都+1，因為翻轉2次等于沒翻轉，（只有翻轉奇數次才會真的翻轉），因為是對整個區間+1，所以就可以考慮用差分維護（O(1)）
操作影響如下，假如選擇的區間為[i,i],對b的影響就是b[1] += 1;b[i]-=1;b[i+1] += 1;
代碼實現：
# include<iostream># include<bits/stdc++.h>using namespace std;# define int long long# define endl "\n"const int N = 2e5 + 10, inf = 1e9 + 7;int b[N];int a[N];void solve() { int n; cin>>n; for(int i = 1;i <= n+1;++i) b[i] = a[i] = 0; string s1,s2; cin>>s1>>s2; s1 = "?"+s1; s2 = "?"+s2; bool ok = true; vector<pair<int,int>> ans; for(int i = 1;i <= n;++i)//看看兩個串是不是本身就為全0{if(s1[i]!= '0'||s2[i] != '0') {ok = false;break;} } if(ok){cout<<"YES"<<endl;cout<<0<<endl;return; } for(int i = 1;i <= n;++i){if(s1[i] == '0'){ans.push_back({i,i});b[1] += 1;//差分維護對b的影響b[i]-=1;b[i+1] += 1;} } for(int i = 1;i <= n;++i){a[i] = a[i-1]+b[i];//前綴和計算對每個位置的影響 } for(int i = 1;i <= n;++i){if(a[i]&1){//如果操作次數為奇數則進行變化if(s2[i] == '0') s2[i] = '1';else s2[i] = '0';} } for(int i = 1;i <= n;++i){if(s2[i] != s2[1])//非（全0或者全1）{cout<<"NO"<<endl;return;} } if(s2[1] == '0'){ans.push_back({1,n}); } else{ans.push_back({1,1});ans.push_back({2,n}); } cout<<"YES"<<endl; cout<<ans.size()<<endl; for(auto [x,y]:ans){cout<<x<<" "<<y<<endl; }}int tt;signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); tt = 1; cin >> tt; while (tt--)solve(); return 0;}
D. Count GCD題目大意：對于給定n,m，給你一個含n個數的數組，數組中每個數的取值范圍在[1,m]
問能構造多少組數組b滿足一下條件：
  1. b[i] \(\in\)[1,m]
  2. gcd(b[1],b[2],...,b[i]) = a[i]
解題思路：基本看到構造多少組b滿足以上條件的就可以考慮原數組每一位的貢獻了，類似于組合數學是每一位的貢獻的積為總的組數所以總的框架就是
int ans = 1; for(int i = 2;i <= n;++i){if(a[i] == a[i-1]){int t = m/a[i];//當前這一位的貢獻ans = ans*t%mod;//總貢獻}else{int t = cal(a[i-1]/a[i],m/a[i]);//當前這一位的貢獻ans = ans*t%mod;} } cout<<ans<<endl;【C.差分維護，D.容斥原理 CodeTON Round 3】然后考慮每一位的貢獻是怎么樣的形式我們寫兩組數據大概可以的到一下的思路：因為是前綴gcd，所以明顯每個數的質因子是不斷變小的，然后我們如果要求解b[i]就有如下思路：gcd(a[i-1],b[i]) = a[i]那我們要求的其實就是a[i]的倍數，比如a[i-1] = 6,a[i] = 3,那能夠滿足g(6,b[i]) = 3的只有3的倍數（3,6,9,12,15.....k*3<= m）,但是我們很容易就發現6,12是不能選的gcd(6,6||12) = 6 ， 同理如果m/a[i] (所有的倍數)包含a[i-1]/a[i]的質因子的時候就都不能選
所以，問題可以轉化為：從[1，m/a[i]]中選與（a[i-1]/a[i])互質的數有多少個
于是引入容斥原理：
C.差分維護，D.容斥原理 CodeTON Round 3

文章插圖
Tot = C\(_n\)\(^1\) - C\(_n\)\(^2\) + C\(_n\)\(^3\).....
用韋恩圖表示如下：
C.差分維護，D.容斥原理 CodeTON Round 3

文章插圖
C.差分維護，D.容斥原理 CodeTON Round 3

文章插圖
所以我們就考慮用總的（m/a[i])-res（所有與a[i-1]/a[i]不互質的數的并集）
之所以取與a[i-1]/a[i]不互質的數的并集是因為它比較好表示，用（m/a[i])/（選中的因子的積)就是不互質數的數量比如從1,2,3,4,5,6中求與2,3不互質的數實際上就是6-（2的倍數（{2,4,6} $\rightarrow$6/2 = 3）+3的倍數（{3,6} $\rightarrow$6/3 = 2）-（2*3）的倍數（{6} $\rightarrow$6/6 = 1）） = 6-3-2+1 = 2{1,5}

推薦閱讀