????????CF 811D? Color with Occurrences

問：給一個string s，和 n個substring ai，求最少數量的substring覆蓋s

轉換字符串覆蓋問題 -> 區間覆蓋問題

區間覆蓋：

????????1. 按左邊界升序排

????????2. 在 左邊界 小于/等于/等于+1 當前右邊界里，選右邊界最遠的

當s的長度短，可以使用 數組 做區間覆蓋：

? ? ? ? ri 代表從 si開始可以覆蓋到的最遠右邊界

規定左右邊界協議 和 下標：

? ? ? ? 左閉右開 or 左閉右閉，0-index or 1-index

‘學習：

? ? ? ? 1.? s.substr(開始， substr長度）

? ? ? ? 2. s.length() 要 cast 到 int，不然會 RE

? ? ? ? 3. max_element()? 左閉右開? ? ? ? ? ? ? ? ? ? ? ??

總結：

????????? 1.?轉換字符串覆蓋問題 -> 區間覆蓋問題

? ? ? ? ? 2.? pair區間覆蓋 和 數組區間覆蓋? ?

? ? ? ? ? 3.? 規定左右邊界 和 下標協議

#include <iostream> #include <algorithm> #include <cstring> #include <map> #include <vector> #include <utility> using namespace std;/* 1 bababa 2 ba aba */ void solve(){string s; cin>>s;int n; cin>>n;//0 index, 左閉右開int r[105]; int id[105];memset(r, 0, sizeof(r));for(int i=0;i<n;i++){string sb; cin>>sb;//應該是 小于等于for(int j=0;j<=(int)s.length()-(int)sb.length();j++){//substr(開始， substr的長度)if(s.substr(j, sb.length())==sb){//開始 + 長度 超 1//r[j] in//左閉右閉 [l, r]if(j+sb.length() > r[j]){r[j]=j+sb.length();id[j]=i;}}}}// for(int i=0;i<s.length();i++){// cout<<r[i]<<" ";// }int end=0;vector<pair<int, int> > ans;while(end<s.length()) {//max_element 左閉右開 [r, l)int next_end=max_element(r, r+end+1)-r;if(r[next_end] <= end){ cout<<-1<<endl;return;}ans.push_back({id[next_end], next_end});end=r[next_end];} cout<<ans.size()<<endl;for(int i=0;i<ans.size();i++){cout<<ans[i].first+1<<" "<<ans[i].second+1<<endl;} } int main(){int t; cin>>t;while(t--){solve();} }

---------------------------------------------------------------------------------------------------------------------------------

CF1637D Yet Another Minimization Problem

給兩個數組a和b，定義一個數組的cost為? ? ? ?

??????????????????????????????????????????????????????????????????????

每次操作可以選一個下標 k，交換 ak 和 bk

求兩個數組的最小cost和

遇到一個公式，嘗試分解到線性:

? ? ? ? ? ? ? ? 1. 展開式子

????????????????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???2. 分離常數（constant）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

? ? ? ? ? ? ? ? 這里把sigma 分配，發現第一項和第三項是常數? （不論怎么換，a和b的都會計算）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? 3. 轉換成線性

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ?

? ? ? ? ? ? ? ? ? ? ? ?！！！這里注意 j 可以 轉成 i

? ? ? ? ? ? ? ? ? 4. 找到不能被分解的式子，要優化（設有多個未知數）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? 5. 分類合并，簡化式子

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 線性合并一起，平方合并一起

????????????????????????????????????????

? ? ? ? ? ? ? ? ? ? 以下為完整公式：

?????????????????????????????????????????????????????? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? 找一個值對cost的貢獻? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 對于aj, 它會與 ?a1 .. aj-1 的結合 并產生貢獻, (a1 * aj) + (a2 * aj) +....(aj-1 *aj)

目前的決策（01, 換或不換）依賴于過去的線性和 與 結果 -->? dp

? ? ? ? 由于ai 和 bi 最大100，n最大100，于是 和 最大 20000

不論怎么換ai和bi，前i個a和b的線性和都是常數

跑 01背包-恰好裝滿j的最小值，

讓S[i] 等于a和b的前i個值的和，

讓 dp[i][j] 等于 a的前i個值和為j 的最小cost：

? ? ? ? if (j >= a[i]) :?

??????????????????????????????? ? ? ? ? ??

? ? ? ? if (j >= b[i]) :

????????????????

總結：

? ? ? ? 1.?遇到一個公式，嘗試分解到線性:

? ? ? ? ? ? ? ? 1. 展開式子

????????????????2. 分離常數（constant）

? ? ? ? ? ? ? ? 3. 分類合并，簡化式子

? ? ? ? ? ? ? ? 4. 找到不能被分解的式子，要優化（設有多個未知數）

? ? ? ? ?

? ? ? ? 2.?一個下標的貢獻？

? ? ? ??動態規劃？-> 決策

? ? ? ? ? ? ? ??? ? ? ?

#include <iostream> #include <cstring> #include <algorithm> using namespace std;int MAX=0x7f7f7f7f; /* 1 4 3 6 6 6 2 7 4 1 */ int dp[105][20005]; void solve(){int n, a[105], b[105];cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];int fConst=0, S[105];S[0]=0;for(int i=1;i<=n;i++){fConst += a[i]*a[i]+b[i]*b[i];S[i]=S[i-1]+a[i]+b[i];}fConst *= (n-1);//memset(arr, (int)#, size)memset(dp, MAX, sizeof(dp));dp[0][0]=0;for(int i=1;i<=n;i++){// j 不能！！！從 a[i] 開始for(int j=0;j<=S[n];j++){if(j>=a[i]){dp[i][j]=min(dp[i][j], dp[i-1][j-a[i]]+(j-a[i])*a[i]+(S[i]-j-b[i])*b[i]);}if(j>=b[i]){dp[i][j]=min(dp[i][j], dp[i-1][j-b[i]]+(j-b[i])*b[i]+(S[i]-j-a[i])*a[i]);}}}int ans=1e9;for(int j=0;j<=S[n];j++){ans=min(ans, dp[n][j]);}cout<<2*ans + fConst<<endl; }int main(){int t; cin>>t;while(t--){solve();} }

--------------------------------------------------------------------------------------------------------------------------------

CF 811E Add Modulo 10:?

? ? ? ? 給一個數組a，每次操作可以選 i，把a[i] 變成 a[i] + (a[i] mod 10)， 求能否把 所有 ai 變成一樣。

????????????????

? ? ? ? 通過舉例觀察到規律 （性質）：

? ? ? ? ? ? ? ? 個位會一直在2， 4， 6， 8 循環，之后證明了有于odd+odd=even，even+even=even（除了5），于是每個同階數的個位都是獨特的，比如說 96，十位是9的只有96

? ? ? ??

? ? ? ? 一開始的想法：把所有的數的個位變成2，然后打擂臺，每次輪回+20 （+4+8+6+2)

? ? ? ? 正確做法：直接每個數 % 20 就行，會等于 2 or 12，如果 有 2 和 12 則 不可能變一樣

? ? ? ? ? ? ? ? ? ? ? ? 打擂臺 -> 比較數的性質不同 -> 每個數的性質不同

? ? ? ? 總結：

? ? ? ? ? ? ? ? ps：已經非常接近答案了，需更耐心的舉例 和 細致的觀察性質

????????????????通過舉例觀察到規律 （性質）

????????????????打擂臺 -> 比較數的性質不同 -> 每個數的性質不同? ? ? ? ? ? ? ??

#include <iostream> #include <algorithm> using namespace std;/* 1 3 2 18 22 */ void solve(){int n; cin>>n;int ar[n+5];for(int i=0;i<n;i++) cin>>ar[i];for(int i=0;i<n;i++){while(ar[i]%10!=0 && ar[i]%10!=2) ar[i]+=ar[i]%10;} sort(ar, ar+n);if(ar[n-1]%10==0){for(int i=0;i<n-1;i++){if(ar[i]!=ar[n-1]){cout<<"NO"<<endl;return;}}cout<<"YES"<<endl;return;}for(int i=1;i<n;i++){if(ar[i]%20!=ar[i-1]%20){cout<<"NO"<<endl; return;}}cout<<"YES"<<endl; }int main(){int t; cin>>t;while(t--){solve();} }

????????????????????????? ? ? ? ? ??

????????

? ? ??

總結

以上是生活随笔為你收集整理的2022 Aug 18 刷题log的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。