🚀歡迎來到本文🚀
🍉個人簡介：陳童學哦，彩筆ACMer一枚。
🏀所屬專欄：杭電多校集訓
本文用于記錄回顧總結(jié)解題思路便于加深理解。

A - 循環(huán)位移

ProblemDescription

Input

Output

解題思路

題目要我們求字符串B中有多少個子串屬于字符串A的循環(huán)位移串。
一般對于這種循環(huán)位移的東西，我們都可以去倍增一下會比較好寫。
在這里我們可以將字符串A倍增一倍然后去字符串B中找有多少個長度為字符串A長度的字串然后通過字符串哈希統(tǒng)計答案。
首先我們可以計算一下倍增后的字符串A的每個字符的的哈希值，然后再將每個區(qū)間長度為原字符串A長度的字串的哈希值標記為1，最后再類似的處理字符串B的每個字符的哈希值，然后再判斷字符串B中長度為原字符串A長度的哈希值是否被標記，如果被標記那么答案就++。
還需要注意的就是在此之前我們需要預處理一個數(shù)組f用于計算哈希值，以及區(qū)間哈希值如何計算。

AC代碼

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 5e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
//h1代表字符串A中字符的哈希值
//h2代表字符串B中字符的哈希值
i64 h1[N],h2[N];
//預處理的數(shù)組
i64 f[N];
//字符串A中區(qū)間哈希值的計算
i64 get1(int l,int r){return h1[r] - h1[l - 1] * f[r - l + 1];
}
//字符串B中哈希值的計算
i64 get2(int l,int r){return h2[r] - h2[l - 1] * f[r - l + 1];
}
void solve(){string s1,s2;cin >> s1 >> s2;int n1 = s1.size();int n2 = s2.size();s1 = '?' + s1 + s1;s2 = '?' + s2;//計算字符串A的每個字符的哈希值for(int i = 1;i < s1.size();i ++){h1[i] = h1[i - 1] * 11 + s1[i];}map<i64,int> mp;//標記A的每個循環(huán)位移串for(int i = 1;i < s1.size();i ++){if(i + n1 - 1 < s1.size()){mp[get1(i,i + n1 - 1)] = 1;}}//計算字符串B的每個字符的哈希值for(int i = 1;i < s2.size();i ++){h2[i] = h2[i - 1] * 11 + s2[i];}i64 ans = 0;//統(tǒng)計答案，被標記了就是答案，加1for(int i = 1;i < s2.size();i ++){if(i + n1 - 1 < s2.size()){ans += mp[get2(i,i + n1 - 1)];}}cout << ans << "\n";
}int main(){	ios::sync_with_stdio(false);cin.tie(nullptr);f[0] = 1;//預處理的數(shù)組ffor(int i = 1;i <= N;i ++){f[i] = f[i - 1] * 11;}int t = 1;cin >> t;while(t --){solve();}return 0;
}

B - 星星

ProblemDescription

$?ai的代價獲得1顆星星。$


$?di的代價獲得4顆星星。$

$他想要獲得恰好k顆星星，但是并不知道最小代價是多少，請你幫他計算這個最小值。$

Input

$本題有多組數(shù)據(jù)$


$1\le n\le 1000,0\le k\le n\times 4.$
$滿足\sum n\le 100000$

Output

解題思路

n次獲得星星中恰好獲得k顆星星的最小代價，是不是有點和01背包的n件物品中背包容量恰好為v的最大價值有點類似。
對的，那么這題肯定大概率應(yīng)該就是個變形版的01背包了。
那么就直接考慮dp，$dp[N]$代表的是獲得星星為$N$時所付出的最小代價。

AC代碼

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
//獲得1、2、3、4顆星星時所需要付出的代價
int a[1010],b[1010],c[1010],d[1010];
//獲得星星數(shù)為x時所需付出的最小代價
i64 dp[4040];
void solve(){//初始化為無窮大memset(dp,0x3f,sizeof(dp));//獲得0顆星星時不需要付出代價dp[0] = 0;int n,k;cin >> n >> k;for(int i = 1;i <= n;i ++){cin >> a[i] >> b[i] >> c[i] >> d[i];}//第i次獲得星星的機會for(int i = 1;i <= n;i ++){//目前獲得的星星數(shù)for(int j = k;j >= 0;j --){//在獲得1、2、3、4顆星星時依次轉(zhuǎn)移for(int t = 1;t <= 4;t ++){if(j >= t){if(t == 1){dp[j] = min(dp[j],dp[j - t] + a[i]);}else if(t == 2){dp[j] = min(dp[j],dp[j - t] + b[i]);}else if(t == 3){dp[j] = min(dp[j],dp[j - t] + c[i]);}else if(t == 4){dp[j] = min(dp[j],dp[j - t] + d[i]);}}}}}//輸出恰好獲得k顆星星時的最小代價cout << dp[k] << "\n";
}int main(){	ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}return 0;
}

H - 位運算

ProblemDescription

$按位異或\oplus ：二進制下每一位做異或，即0\oplus 0=0,0\oplus 1=1,1\oplus 0=1,1\oplus 1=0。$
$按位或?：二進制下每一位做或，即0?0=0,0?1=1,1?0=1,1?1=1。$
$現(xiàn)在，對于一個在[0,2^k)中的整數(shù)n，小丁想要知道，有多少組也在[0,2^k)中的整數(shù)a,b,c,d，滿足：$

$a?b\oplus c?d=n$
$注意，運算符是從左往右依次順序結(jié)合的，即可以認為原表達式為：$
$(((a?b)\oplus c)?d)=n$

Input

Output

解題思路

對于這種位運算的題，絕大部分情況下直接枚舉十進制下的數(shù)肯定會TLE的，一般都是找二進制下每位的規(guī)律。
要使得$(((a?b)\oplus c)?d)=n$，那么二進制的這位數(shù)字要么為1要么為0，如果它們當前位通過運算后的結(jié)果1，那么n的二進制下的當前位也應(yīng)該位1，反之則為0。
那么我們便可以通過預處理四個數(shù)取1或0的所有情況，然后通過判斷n的二進制下每位是1還是0累加答案即可。
或者我們可以通過分類討論。
一、n的當前位在二進制下位1時
??1、當d的當前位為1時，$((a?b)\oplus c)$中的a、b、c無論如何取值都不會影響結(jié)果，所有共有$2^3$即8。
??2、當d的當前位為0時，再分類討論下$((a?b)\oplus c)$為1還是0。
????①、當c為1時，$(a?b)$共有3種情況使得$(((a?b)\oplus c)?d)$為1
????②、當c為0時，$(a?b)$共有1種情況使得$(((a?b)\oplus c)?d)$為1
綜上所述共有12種情況使得進制位為1。

二、n的當前位在二進制下位0時
??1、當d的當前位為1時，$((a?b)\oplus c)$中的a、b、c無論如何取值無法使得$((a?b)\oplus c)$滿足條件，即0種情況。
??2、當d的當前位為0時，再分類討論下$((a?b)\oplus c)$為1還是0。
????①、當c為1時，$(a?b)$共有1種情況使得$(((a?b)\oplus c)?d)$為0
????②、當c為0時，$(a?b)$共有3種情況使得$(((a?b)\oplus c)?d)$為0
綜上所述共有12種情況使得進制位為4。

最后總結(jié)也就能看出來如果n二進制下的當前位為1的話就$?12$，否則$?4$

AC代碼

#include<bits/stdc++.h>
#define look(x) cout << #x << " ==  " << x << "\n"
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){int n,k;cin >> n >> k;i64 ans = 1;for(int i = 0;i < k;i ++){if((n >> i) & 1){ans *= 12;}else{ans *= 4;}}cout << ans << "\n";
}int main(){	ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}return 0;
}