清北學(xué)堂五一集訓(xùn)Day-1
清北學(xué)堂五一集訓(xùn)Day-1
上午
1.在比賽時盡量使用'\n'，不要用endl
2.隊列(FIFO)
stl隊列：
#include<queue>
//#include<bits/stdc++.h>
using namespace std;
queue<int> q;
//queue<隊列里面的元素類型> 變量名;
int main()
{
q.push(233);
q.push(2233);//向隊列里面加入一個元素
q.pop();//從隊列中刪除一個元素 刪除是隊列頭的元素 233 void類型沒有返回值
int x = q.front();//獲取隊列頭元素 2233
cout << q.size() << endl;//獲取隊列剩余的元素個數(shù) 1
}
手寫隊列：
#include<bits/stdc++.h>
using namespace std;
struct queue
{
int a[1000];
int head=1;//隊列頭在哪里
int tail=0;//隊列尾巴在哪里
void push(int x)
{
tail ++;
a[tail] = x;
}
void pop()
{
head++;
}
int size()
{
return tail-head+1;
}
int front()
{
return a[head];
}
}q;
int main()
{
q.push(233);
q.push(2233);//向隊列里面加入一個元素
q.pop();//從隊列中刪除一個元素 刪除是隊列頭的元素 233 void類型沒有返回值
int x = q.front();//獲取隊列頭元素 2233
cout << q.size() << endl;//獲取隊列剩余的元素個數(shù) 1
}
3.棧(FILO)
stl隊列：
#include<stack>
//#include<bits/stdc++.h>
using namespace std;
stack<int> q;
//stack<隊列里面的元素類型> 變量名;
int main()
{
q.push(233);
q.push(2233);//向棧里面加入一個元素
q.pop();//從棧中刪除一個元素 刪除是隊列頭的元素 2233 void類型沒有返回值
int x = q.top();//獲取棧頂部元素 233
cout << q.size() << endl;//獲取棧剩余的元素個數(shù) 1
}
4.雙指針
1個從前開始，1個自后向前
int main()
{
cin >> n;
for (int i=1;i<=n;i++)
cin >> a[i];
cin >> m;
int sum=0;
for (int l=1,r=1;l<=n;sum-=a[l],l++)
{
while (sum<=m && r<=n)
{
sum += a[r];
r++;
}
if (sum>m)
{
r--;
sum -= a[r];
}
ans = max(ans,r-l);//a[l] ~ a[r-1]
}
}
5.雙端隊列(deque)
#include<deque>
using namespace std;
deque<int> q;//雙端隊列
//q.push_front() 從前面加入
//q.pop_front() 從前面刪除
//q.front() 詢問前面的數(shù)是多少
//q.push_back() 從后面加入
//q.pop_back() 從后面刪除
//q.back() 詢問后面的數(shù)是多少
int a[maxn];
void push(int i)//單調(diào)隊列的插入 插入下標(biāo)為i的元素 要保證隊列單調(diào)遞增
{
while (q.size() > 0 && a[q.back()] >= a[i])
q.pop_back();
q.push_back(i);
}
int main()
{
cin >> n;
for (int i=1;i<=n;i++)
cin >> a[i];
cin >> m;//所有長度為m的區(qū)間的最小值
for (int i=1;i<=n;i++)
{
push(i);//向單調(diào)隊列里面加入a[i]這個元素
if (i-m == q.front()) q.pop_front();//把a(bǔ)[i-m]這個數(shù)刪掉
if (i>=m)//區(qū)間長度已經(jīng)超過m了 需要取出最小值
cout << a[q.front()] << "\n";
}
}
6.堆:
1.大根堆
#include<queue>
//#include<bits/stdc++.h>
using namespace std;
priority_queue<int> q;
//大根堆
struct rec
{
int a,b;
};
//如果要把結(jié)構(gòu)體 放入 stl比大小 只能重載小于號
bool operator<(const rec &x,const rec &y)
{
return x.a + x.b > y.a + y.b;
}
priority_queue<rec> qq;//取出a+b最小的結(jié)構(gòu)體
int main()
{
q.push(233);
q.push(2233);//向堆里面加入一個元素
q.pop();//從堆中刪除一個元素 刪除是堆中最大的元素 2233 void類型沒有返回值
int x = q.top();//獲取堆中最大元素 233
cout << q.size() << endl;//獲取堆剩余的元素個數(shù) 1
}
2.小根堆:
①stl小根堆:
#include<queue>
#include<bits/stdc++.h>
using namespace std;
priority_queue< int , vector<int> , less<int> > q;
struct rec
{
int a,b;
};
//如果要把結(jié)構(gòu)體 放入 stl比大小 只能重載小于號
bool operator<(const rec &x,const rec &y)
{
return x.a + x.b > y.a + y.b;
}
priority_queue<rec> qq;//取出a+b最小的結(jié)構(gòu)體
int main()
{
q.push(-233);
q.push(-2233);//向堆里面加入一個元素
q.pop();//從堆中刪除一個元素 刪除是堆中最大的元素 2233 void類型沒有返回值
int x = q.top();//獲取堆中最大元素 233
cout << q.size() << endl;//獲取堆剩余的元素個數(shù) 1
}
②通過對大根堆取負(fù)號實現(xiàn):
#include<queue>
//#include<bits/stdc++.h>
using namespace std;
priority_queue<int> q;
//大根堆
//小根堆最簡單的方法：取負(fù)號
struct rec
{
int a,b;
};
//如果要把結(jié)構(gòu)體 放入 stl比大小 只能重載小于號
bool operator<(const rec &x,const rec &y)
{
return x.a + x.b > y.a + y.b;
}
priority_queue<rec> qq;//取出a+b最小的結(jié)構(gòu)體
int main()
{
q.push(-233);
q.push(-2233);//向堆里面加入一個元素
q.pop();//從堆中刪除一個元素 刪除是堆中最大的元素 2233 void類型沒有返回值
int x = q.top();//獲取堆中最大元素 233
cout << q.size() << endl;//獲取堆剩余的元素個數(shù) 1
}
7.heapa:
struct heap{
int a[1010];//堆的每一個元素
int n=0;
int top()//詢問最大值
{
return a[1];
}
void push(int x)//插入一個數(shù)
{//O(logn)
n++;a[n] = x;
int p=n;
while (p!=1)
{
if (a[p] > a[p>>1])
{
swap(a[p],a[p>>1]);
p = p>>1;
}
else
{
break;
}
}
}
void pop()//刪除最大值
{
swap(a[1],a[n]);n--;
int p=1;
while ((p<<1) <= n)
{
int l=p<<1;
int r=l|1;//p*2+1
int pp=l;
if (r<=n && a[r] > a[l]) pp=r;//pp一定是兩個兒子中較大的那個
if (a[pp] > a[p])
{
swap(a[pp],a[p]);
p=pp;
}
else
{
break;
}
}
}
int size()//詢問還有幾個數(shù)
{
return n;
}
};
8.并查集:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e8;
int to[maxn],n,p1,p2;//to[i] 代表i的箭頭指向誰
int go(int p)//從p點出發(fā) 看最后會走到哪里
{
if (p == to[p]) return p;
else
{
to[p] = go(to[p]);
return to[p];
}
}
int main()
{
cin >> n;
for (int i=1;i<=n;i++)
to[i] = i;
//合并
to[go(p1)] = go(p2);
//查詢
go(p1) == go(p2);
}
下午
9.trie（本質(zhì)是樹）:
下一個節(jié)點是上面所有節(jié)點的和
如1-0-1-0 1010(10) -表示一條邊
struct node
{
int nxt[2];//nxt[0] nxt[1] 代表從當(dāng)前點走0和1會走到哪里 走到0的話代表這個節(jié)點不存在
node()
{
nxt[0] = nxt[1] = 0;
}
}z[23333];
void insert(int x)
{
int p=root;
for (int i=30;i>=0;i--)
{
int y=(x>>i)&1;//取出x二進(jìn)制的第i位
if (z[p].nxt[y] == 0) {;
cnt++;
z[p].nxt[y] = cnt;
}
p = z[p].nxt[y];
}
}
int query(int x)//從trie中找一個數(shù) 使得他和x異或之后最大
{
int p=root,ans=0;
for (int i=30;i>=0;i--)
{
int y=(x>>i)&1;
if (z[p].nxt[y^1] != 0) ans=ans|(1<<i),p=z[p].nxt[y^1];
else p=z[p].nxt[y];
}
return ans;
}
int main()
{
root = 1;
}
10.莫隊(≈暴力):
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int belong[maxn],cnt,ans;
struct query
{
int l,r,id,ans;
}q[maxn];
bool cmp1(const query &q1, const query &q2)
{
if (belong[q1.l] != belong[q2.l]) return belong[q1.l] < belong[q2.l];
else return q1.r < q2.r;
}
bool cmp2(const query &q1, const query &q2)
{
return q1.id < q2.id;
}
void ins(int x)
{
cnt [x] ++;
if (cnt [x] % 2 == 0) ans++;
else if (cnt [x] != 1) ans--;
}
void del(int x)
{
cnt [x] --;
if (cnt[x] != 0)
{
if (cnt[x] % 2 == 0) ans++;
else ans--;
}
}
int main()
{
cin >> n >> m;
for (int i=1;i<=n;i++)
cin >> a[i];
for (int i=1;i<=m;i++)
{
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
int s = sqrt(n);
for (int i=1;i<=n;i++)
belong[i] = i/s+1;
sort(q+1,q+m+1,cmp1);
for (int i=q[1].l;i<=q[1].r;i++)
ins(a[i]);
q[1].ans = ans;
for (int i=2;i<=m;i++)//O(Nsqrt(N))
{
int l1=q[i-1].l,r1=q[i-1].r;
int l2=q[i].l,r2=q[i].r;
if (l1 < l2)
for (int i=l1;i<l2;i++)
del(a[i]);
else
for (int i=l2;i<l1;i++)
ins(a[i]);
if (r1 < r2)
for (int i=r1+1;i<=r2;i++)
ins(a[i]);
else
for (int i=r2+1;i<=r1;i++)
del(a[i]);
q[i].ans = ans;
}
sort(q+1,q+m+1,cmp2);
for (int i=1;i<=m;i++)
cout << q[i].ans << "\n";
return 0;
}
11.分塊(≈分治)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int n,m;
int belong[maxn],a[maxn];//belong[i] 代表第i個數(shù)屬于第幾塊
int sum[maxn];//sum[i] 代表第i塊的和是多少
int daxiao[maxn];//daxiao[i] 代表第i塊的大小是多少
int col[maxn];//col[i] 代表第i塊被整體加了col[i]
int main()
{
cin >> n >> m;
for (int i=1;i<=n;i++)
cin >> a[i];
int s = sqrt(n);//每塊的大小
for (int i=1;i<=n;i++)
belong[i] = i/s+1;
for (int i=1;i<=n;i++)
{
sum[belong[i]] += a[i];
daxiao[belong[i]] ++;
}
for (int x=1;x<=m;x++)
{
int opt;
cin >> opt;
if (opt == 1)//詢問操作
{
int l,r;
cin >> l >> r;
int ans=0;
if (belong[l] == belong[r])
for (int i=l;i<=r;i++)
ans += a[i] + col[belong[i]];
else
{
for (int i=l;belong[i] == belong[l]; i++)
ans += a[i] + col[belong[i]];
for (int i=r;belong[i] == belong[r]; i--)
ans += a[i] + col[belong[i]];
for (int i=belong[l] + 1; i < belong[r]; i++)
ans += sum[i];
}
cout << ans << "\n";
}
else
{
int l,r,v;
cin >> l >> r >> v;
if (belong[l] == belong[r])
for (int i=l;i<=r;i++)
a[i] += v;
else
{
for (int i=l;belong[i] == belong[l]; i++)
a[i] += v,sum[belong[i]] += v;
for (int i=r;belong[i] == belong[r]; i--)
a[i] += v,sum[belong[i]] += v;
for (int i=belong[l] + 1; i < belong[r]; i++)
{
sum[i] += v * daxiao[i];
col[i] += v;
}
}
}
}
return 0;
}
12.merge
void merge(int l,int r)//要計算l~r這個區(qū)間有多少個逆序?qū)?{
if (l==r) return;
int m=(l+r) >> 1;//(l+r)/2
merge(l,m);//遞歸去算l~m的答案 a[l]~a[m] 排好序了
merge(m+1,r);//遞歸去算m+1~r的答案 a[m+1]~a[r] 排好序了
//i在左邊 j在右邊的答案
int p1 = l, p2 = m+1;
for (int i=l;i<=r;i++)
{
if (p1 > m) b[i] = a[p2],p2++;
else if (p2 > r) b[i] = a[p1],p1++;
else if (a[p1] <= a[p2]) b[i] = a[p1],p1++;
else b[i] = a[p2],p2++,ans+=m-p1+1;
}
for (int i=l;i<=r;i++)
a[i] = b[i];
}
13.染色的暴力做法
int main()
{
cin >> n;
for (int i=1;i<=n;i++)
to[i] = i;
for (int i=m;i>=1;i--)//倒著讀 自己實現(xiàn)
{
int l,r,x;
//go(i) 從i向右 第一個沒被染色的位置
cin >> l >> r >> x;//第i個操作
int p = go(l);
while (p<=r)//當(dāng)前位置還在區(qū)間內(nèi)
{
a[p] = x;//染色
int np = go(p+1);
to[p] = go(r+1);
p = np;
}
}
}
查看18道真題和解析