济南CSPS储备营DAY-2

ZMS114514 · 2025-01-23 09:01:02 · 个人记录

• 快速幂

  为了计算2^k可以用快速幂在0(log n)完成

代码呈现：

int ksm(int a,int b,int p)
{
    int ret=1;
    for(;b;b>>=1,a=(long long)a*a%p);
    {
        if(b&1)ret=(long long)ret*a%p;
    }
    return ret;
}//for循环 

int ksm2(int a,int b,int p)
{
    if(b==0)return 1%p;
    if(b==1)return a%p;
    long long men=ksm2(a,b>>1,p);
    if(b&1)return men*men%p*a%p;
    return men*men%p;
}//递归 

• 矩阵快速幂

  两个矩阵为nm和mp，通过乘法结合律计算式子得结果

• 倍增

  可替换为二分but更优秀

• ST表

  维护一个数据结构，支持查询任意区间的最大值。 在每一个位置i维护区间[i,i+2^k)的最大值。

• 单调队列

  可以看作两个栈模拟的队列 如题P1886(板子题)

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

int n, k;
int a[N];

int q[N], head, tail;

int mx[N], mn[N];

signed main() {
    n = read(), k = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    head = 1, tail = 0;
    for(int i = 1; i <= n; ++ i) {
        while(head <= tail && a[q[tail]] <= a[i]) --tail;
        q[++ tail] = i;
        while(head <= tail && q[head] <= i - k) ++ head;
        if(i >= k) mx[i] = a[q[head]];
    }
    head = 1, tail = 0;
    for(int i = 1; i <= n; ++ i) {
        while(head <= tail && a[q[tail]] >= a[i]) --tail;
        q[++ tail] = i;
        while(head <= tail && q[head] <= i - k) ++ head;
        if(i >= k) mn[i] = a[q[head]];
    }
    for (int i = k; i <= n; ++ i)
        cout << mn[i] << " ";
    puts("");
    for (int i = k; i <= n; ++ i)
        cout << mx[i] << " ";
    puts("");
    return 0;
}

• 单调栈 如同站队，从左侧插入新人，将新人看不到的人（即被挡住的人）踢掉，得到一个单调递增的栈

• 堆

  大根堆 or 小根堆 O(long n) ——优先队列(priority_queue)

  对顶堆(bushi 有点恶心)

  合并堆

• 并查集

  少有的码量少但好用的算法，有名字可知作用为合并两个集合，可看作树，建立公共祖先，由此便可称之为找爸爸算法，其精华在于getfather函数中的递归 常用为路径压缩和按秩合并

  经典例题：P1892团伙

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int dr[1145],fa[1145];
bool flag[1010];
int getf(int x){
    if(fa[x]==x) return x;
    return fa[x]=getf(fa[x]);
}
int main(){
    cin>>n>>m;
    char c;
    int x,y;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>c>>x>>y;
        if(c=='F')
            fa[getf(x)]=getf(y);
        else {
            if(!dr[x]) dr[x]=y;
            else fa[getf(y)]=getf(dr[x]);
            if(!dr[y]) dr[y]=x;
            else fa[getf(x)]=getf(dr[y]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        flag[getf(i)]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(flag[i])
        {   
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

P1551 亲戚 代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,p,a,b,f[5555];
int getf(int x)
{
    if(f[x]!=x)
    {
        return getf(f[x]);
    }
    else return x;
}
void merge(int a,int b)
{
    int fa=getf(a);
    int fb=getf(b);
    if(fa!=fb)
    {
        f[fb]=fa;
    }
}
int main()
{
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }   
    for(int i=1;i<=m;i++)
    {

        cin>>a>>b;
        merge(a,b);
    }
    while(p--)
    {
        cin>>a>>b;
        if(getf(a)==getf(b))
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0;
 } 

• 线段树

• 分治结构发挥神力，下放sum和懒标记

本章结