acwing week2 基礎演算法3總結 總結點1：雙指針演算法 //常用模版框架 for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; } 常見問題分類： (1) 對於一個序列，用兩個指針維護一段區間 ( ...
acwing week2 基礎演算法3總結
總結點1：雙指針演算法
//常用模版框架
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
}
常見問題分類：
(1) 對於一個序列，用兩個指針維護一段區間
(2) 對於兩個序列，維護某種次序，比如歸併排序中合併兩個有序序列的操作
題1：最長連續不重覆子序列
我們用指針i指向子序列的終點，j指向子序列的起點。
每次指針i後移時，這個序列中重覆的那個數只可能是s[i],所以我們判斷一下s[i]出現的次數是否大於1，
如果大於1，說明子序列中s[i]這個數重覆了，那麼就更新答案和起點，繼續迴圈。
判斷出現的次數，我們用數組a做標記。
代碼：
#include <iostream>
using namespace std;
int n;
const int N = 100010;
int s[N], a[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
int ans = 0;
for (int i = 0, j = 0; i < n; i++)//i指向終點，j指向起點
{
a[s[i]]++;//新加值的次數+1；
while (j < i && a[s[i]]>1)//如果重覆(a[s[i]]>1) 就更新起點，直到a[s[i]] == 1;
{
a[s[j]]--;//刪除數的次數--
j++;//起點指針後移
}
ans = max(ans, i - j + 1);//更新答案
}
cout << ans << endl;
return 0;
}
題2,3都是雙指針演算法，不做講解，直接看代碼
題2：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int n, m, x;
const int N = 100010;
int a[N], b[N];
int main()
{
cin >> n >> m >> x;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < m; i++)
{
cin >> b[i];
}
for (int i = 0, j = m - 1; i < n; i++)
{
while (a[i] + b[j] > x)
{
j--;
}
if (a[i] + b[j] == x)
{
cout << i << ' ' << j << endl;
break;
}
}
return 0;
}
題3:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int n, m;
const int N = 100010;
int a[N], b[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < m; i++)
{
cin >> b[i];
}
int ans = 0;
for (int i = 0, j = 0; i < n&&j<m; i++)
{
while (a[i] != b[j])
{
j++;
if (j == m)
{
j--;
break;
}
}
if(a[i] ==b[j])ans++,j++;
}
if (ans == n) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
總結點2：離散化
離散化的題乍一看感覺和首碼和和差分很像，但是在數據的範圍上有很大的區別。
一般離散化數據的跨度非常大，但是真正使用的數據點的個數比較少，而首碼和和差分，一般數據的跨度是多少，使用的數據點的個數就是多少。
題1：區間和
這道題原本是首碼和和差分的例題，但是修改了l,r的範圍，這時繼續使用首碼和就會超時，那麼我們就需要使用離散化。
首先我們將所有用到的點輸入到alls數組中，然後對alls數組進行排序，然後去重。
這時我們可以將alls數組看作是一個數軸，左右使用的坐標，都按次序排好了。
這時我們將alls數組中坐標的對應的下標作為他的這個坐標對應的新坐標，然後將每個坐標下的數字，按照新坐標的次序輸入到a[]數組中。
這時我們想求原坐標下A-B的區間和，可以轉換為新坐標下As-Bs的和；
因為新坐標的範圍比較小，此時就可以用首碼和和差分左進一步處理。
代碼：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 300010;
int n, m;
vector<int> alls;
vector<pair<int, int >> add, query;//儲存每一次操作的兩個數
int a[N], s[N];
int find(int x)
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
int x, c;
cin >> x >> c;
add.push_back({ x, c });
//x是需要用到的坐標
alls.push_back(x);
}
for (int i = 0; i < m; i++)
{
int x, c;
cin >> x >> c;
query.push_back({ x,c });
alls.push_back(x);
alls.push_back(c);
}
//對alls數組進行排序並去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//將原坐標對應的數據，儲存到新坐標中
for (int i = 0; i < n; i++)
{
int x = find(add[i].first);
a[x] += add[i].second;
}
//首碼和模版
for (int i = 1; i <= alls.size(); i++)
{
s[i] = s[i - 1] + a[i];
}
for (int i = 0; i < m; i++)
{
int l = find(query[i].first), r = find(query[i].second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
總結點3：區間合併
題1：區間合併
情況1：
對於這種情況，兩個區間不需要合併。
情況2：
這種情況下，合併後的區間就是長的區間。
情況3：
這種情況合併後，區間是上面區間的左端點，和下麵區間的右端點。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
int n;
vector<pair<int, int>> segs;//用segs去儲存初始時的各個區間
void merge(vector<pair<int, int>> &segs)//註意對segs加&,因為需要修改segs的值
{
vector<pair<int, int>> res;//創建數組，儲存新區間
sort(segs.begin(), segs.end());//先將原區間按照左端點排序
int l = -2e9, r = -2e9;//分別控制新區間的左右端點
for (auto seg : segs)
{
if (seg.first > r)//第一種情況
{
if (l != -2e9) res.push_back({l,r});//如果不是初始值，就將區間放入新數組
l = seg.first, r = seg.second;//更新左右端點
}
else//第二三種情況
{
r = max(r, seg.second);
}
}
if (l != -2e9) res.push_back({ l,r });//放入最後一個區間
segs = res;//將新數組的值賦值給原數組
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
segs.push_back({ l,r });
}
merge(segs);
cout << segs.size() << endl;
return 0;
}
