DAY16共3題：
-
奇♂妙拆分（簡單數學）
-
區區區間間間（單調堆疊）
-
小AA的數列（位運算dp）
?? 作者：Eriktse
?? 簡介：19歲，211計算機在讀，現役ACM銀牌選手??力爭以通俗易懂的方式講解演算法！??歡迎關注我，一起交流C++/Python演算法，（優質好文持續更新中……）??
?? 閱讀原文獲得更好閱讀體驗：https://www.eriktse.com/algorithm/1119.html
奇♂妙拆分（簡單數學）
根據貪心的想法，若要使得因子盡可能多，那么因子應當盡可能小，大于根號n的因子至多一個，從小到大列舉[1, sqrt(n)]的所有整數，如果i能夠整除n就作為一個因子，
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
int n;cin >> n;
set<int> st;
for(int i = 1;i <= n / i; ++ i)
if(n % i == 0)st.insert(i), n /= i;
st.insert(n);
cout << st.size() << '\n';
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _;cin >> _;
while(_ --)solve();
return 0;
}
區區區間間間（單調堆疊）
題意：給定一個陣列，求所有子區間的最大值與最小值的差的和，
如果暴力列舉肯定不行，單單是子區間個數就有n ^ 2個，所以我們應該考慮每一個元素對答案的貢獻，也就是說我們需要知道某個元素a[i]它會在多少個區間里作為最大值，在多少個區間里作為最小值，
我們預處理出四個陣列，分別是lmax[], rmax[], lmin[], rmin[]表示點i作為最大值的左右最遠位置，和作為最小值的左右最遠位置（lmax[i] = j，表示在區間[j, i]中的最大值都是a[i]，其他的三個陣列類似定義），
用單調堆疊可以處理出這四個陣列，一下以求lmax[]舉例，維護一個單調不增堆疊，堆疊記憶體放的是下標，
初始時堆疊內僅有一個a[0] = inf，
當我們遇到一個a[i]時，不斷地判斷堆疊頂元素，如果堆疊頂元素比a[i]小，說明這個堆疊頂應當彈出，
當更新完畢后，此時的堆疊頂的右邊相鄰位置就是a[i]往左的最遠的位置了，因為此時堆疊頂是a[i]往左的第一個大于等于a[i]的位置，那么這中間的元素都會小于a[i]，
其他的三個陣列類似，注意，如果我們處理lmax用的是單調不增堆疊，那么處理rmax就應當用單調遞增堆疊，而不是單調不減堆疊，否則可能出現區間重復表示或沒有歸屬的問題（自己思考），
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9, inf =8e18;
int a[N], stk[N], top, lmax[N], rmax[N], lmin[N], rmin[N];
void solve()
{
int n;cin >> n;
for(int i = 1;i <= n; ++ i)cin >> a[i];
a[0] = a[n + 1] = inf;
top = 0;
stk[++ top] = 0;
for(int i = 1;i <= n; ++ i)
{
while(top && a[i] > a[stk[top]])top --;
lmax[i] = stk[top] + 1;
stk[++ top] = i;
}
top = 0;
stk[++ top] = n + 1;
for(int i = n;i >= 1; -- i)
{
while(top && a[i] >= a[stk[top]])top --;
rmax[i] = stk[top] - 1;
stk[++ top] = i;
}
a[0] = a[n + 1] = -inf;
top = 0;
stk[++ top] = 0;
for(int i = 1;i <= n; ++ i)
{
while(top && a[i] < a[stk[top]])top --;
lmin[i] = stk[top] + 1;
stk[++ top] = i;
}
top = 0;
stk[++ top] = n + 1;
for(int i = n;i >= 1; -- i)
{
while(top && a[i] <= a[stk[top]])top --;
rmin[i] = stk[top] - 1;
stk[++ top] = i;
}
int ans = 0;
for(int i = 1;i <= n; ++ i)
{
ans += a[i] * (rmax[i] - i + 1) * (i - lmax[i] + 1);
ans -= a[i] * (rmin[i] - i + 1) * (i - lmin[i] + 1);
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _;cin >> _;
while(_ --)solve();
return 0;
}
小AA的數列（位運算 | 前綴和）
這道題一看有點懵，感覺不是很好處理，但依然是套路題，
看到異或，我們應該想把每一個二進制位拆分開，實際上這里約32位二進制位可以先認為是相互獨立的，對于每一位都計算出貢獻，然后按照位權重加和即可，
異或題的套路基本都是拆分二進制，整體考慮起來比較復雜，拆分后會簡單很多，
先不管L, R，
假如我們考慮陣列1 2 3 4 5的第0位：
獲取第0位后得到b陣列：1 0 1 0 1，
因為我們要得到區間內1的個數，所以處理一個異或前綴和p[]是自然而然的，然后我們列舉每一位作為左端點，看看會得到一個怎樣的式子：
我們知道異或其實就是% 2的加法，也是% 2減法，所以我們將異或前綴和改為普通前綴和p[]，以上的柿子可以轉化為：
那么我們就可以對p再做一個前綴和p2，但是p2的步長應為2，
然后上面的柿子就等價于（其中l, r為j的上下限，需要保證與i - 1奇偶性相同，j的個數為(r - l + 2) / 2）:
因為這個p2存在p2[-1]的情況，所以我們做個小小的便宜，方便代碼的撰寫（其實你想要特判也行，只是不太方便，也容易出錯），
注意一下其他細節即可，
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 109, p = 1e9 + 7, T = 100;
int a[N], b[N], p1[N], p2[N];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, l, r;cin >> n >> l >> r;
for(int i = 1;i <= n; ++ i)cin >> a[i];
int ans = 0;
for(int w = 0;w <= 32; ++ w)
{
for(int i = 1;i <= n; ++ i)b[i] = a[i] >> w & 1;
for(int i = 1;i <= n; ++ i)p1[T + i] = (b[i] + p1[T + i - 1]) % 2;
for(int i = 1;i <= n; ++ i)p2[T + i] = p1[T + i] + p2[T + i - 2];
int sum = 0;
for(int i = 1;i <= n; ++ i)
{
int j1 = max(i + 1, l + i - 1), j2 = min(n, r + i - 1);
if((j1 - i) % 2 == 0)j1 ++;
if((j2 - i) % 2 == 0)j2 --;
if(j2 < j1)continue;
sum += abs(p2[T + j2] - p2[T + j1 - 2] -
p1[T + i - 1] * ((j2 - j1) / 2 + 1));
}
ans = (ans + (1ll << w) * sum % p) % p;
}
cout << ans << '\n';
return 0;
}
?? 本文由eriktse原創，創作不易，如果對您有幫助，歡迎小伙伴們點贊??、收藏?、留言??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550666.html
標籤：其他
下一篇：返回列表