寒假第一周（图论复习+补DP)

whatdo / 2024-01-28 / 原文

组合数+快速幂

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+7,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
int kmp(int a,int k,int p)
{
    int ans=1;
    while (k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a%p;
    }
    return ans;
}  // 快速幂 
int fac[N];

int C(int n,int m){
    if( n<m )    return 0;
    return fac[n]*kmp( fac[m]*fac[n-m]%mod,mod-2,mod )%mod;
} // 组合数

void solve()
{
    fac[0] = 1;
    for(int i=1;i<=1000;i++)    fac[i] = fac[i-1]*i%mod;  // 初始化
    int x=C(c的下标,c的上标);
    cout<<x<<endl;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

欧拉筛

bool isprime[MAXN]; // isprime[i]表示i是不是素数
int prime[MAXN]; // 现在已经筛出的素数列表
int n; // 上限，即筛出<=n的素数
int cnt; // 已经筛出的素数个数

void euler()
{
    memset(isprime, true, sizeof(isprime)); // 先全部标记为素数
    isprime[1] = false; // 1不是素数
    for(int i = 2; i <= n; ++i) // i从2循环到n（外层循环）
    {
        if(isprime[i]) prime[++cnt] = i;
        // 如果i没有被前面的数筛掉，则i是素数
        for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
        // 筛掉i的素数倍，即i的prime[j]倍
        // j循环枚举现在已经筛出的素数（内层循环）
        {
            isprime[i * prime[j]] = false;
            // 倍数标记为合数，也就是i用prime[j]把i * prime[j]筛掉了
            if(i % prime[j] == 0) break;
            // 最神奇的一句话，如果i整除prime[j]，退出循环
            // 这样可以保证线性的时间复杂度
        }
    }
}

二分（整数+浮点数）

整数：
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数：
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

 二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

 二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

离散化

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n';
using namespace std;
const int N=3e6+7,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=100003;
typedef pair<int,int> PII;


vector<PII> a;
vector<PII> b;
vector<int> all;
int ans[N];
int s[N];
int n,m;
int find(int  x)
{
    int l,r;
    l=0,r=all.size()-1;
    while (l<r)
    {
        int mid=(l+r)/2;
        if(all[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1;
}

void solve()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int c,x;
        cin>>x>>c;
        a.push_back({x,c});

        all.push_back(x);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        b.push_back({l,r});

        all.push_back(l);
        all.push_back(r);
    }
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());

    for(auto i:a)
    {
        int x= find(i.first);
        ans[x]+=i.second;
    }

    for(int i=1;i<=all.size();i++)
    {
        s[i]=s[i-1]+ans[i];
    }

    for(auto i:b)
    {
        cout<<s[find(i.second)]-s[find(i.first)-1]<<endl;
    }
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

 

 树状数组（动态前缀和求解）

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=5e4+9,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
int lowbit(int x)   // 用于加减找到目标区间进行修改
{
    return ((x) & (-x));
}
int tree[N];
void add(int i,int x)  // 对区间进行加减
{
    for(int pos=i;pos<N;pos+=lowbit(pos))
    {
        tree[pos]+=x;
    }
}
int Query(int n) // 求1到n的前缀和
{
    int ans=0;
    for(int pos=n;pos;pos-= lowbit(pos))
    {
        ans+=tree[pos];
    }
    return ans;
}

int Query(int a,int b) // 求b-a的前缀和
{
    return Query(b)- Query(a-1);
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        add(i,x);
    }
  
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();

    }
    return 0;
}

 线段树（功能和树状树状差不多，但是树状数组改异或同或比较好改）

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=5e4+9,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
// node 这个是线段树的节点，用于递归
void build_tree(int arr[],int tree[],int node,int start,int end) {   // 建立树

    if (start == end) {
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;

        build_tree(arr, tree, left_node, start, mid);
        build_tree(arr, tree, right_node, mid + 1, end);
        tree[node] = tree[left_node] + tree[right_node];
    }

}
// idx和val 意是是把idx改成val    就是idx是小标
void update_tree(int arr[],int tree[],int node,int start,int end,int idx,int val)   //改区间值
{
    if (start == end) {
        arr[idx] = val;
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
        if (idx >= start && idx <= mid) {
            update_tree(arr, tree, left_node, start, mid, idx, val);
        } else {
            update_tree(arr, tree, right_node, mid + 1, end, idx, val);
        }
        tree[node] = tree[left_node] + tree[right_node];
    }
}

int query_tree(int arr[],int tree[],int node,int start,int end,int L,int R) {   // 得出L到R的区间和
    if (R < start || L > end) {
        return 0;
    } else if (L <= start && end <= R) {
        return tree[node];
    } else if (start == end) {
        return tree[node];
    } else {
        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;

        int sum_left = query_tree(arr, tree, left_node, start, mid, L, R);
        int sum_right = query_tree(arr, tree, right_node, mid + 1, end, L, R);

        return sum_left + sum_right;
    }

}

int arr[N];
int tree[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) //注意下标要是0开始
    {
        cin>>arr[i];
    }
    build_tree(arr,tree,0,0,n-1);
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();

    }
    return 0;
}

 朴素最短路djstla

#include<algorithm>
#include<cstring>
using namespace std;

const int N=510;

int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定

int n,m;

int Dijkstra()
{
    memset(dist, 0x3f,sizeof dist);     //初始化距离  0x3f代表无限大

    dist[1]=0;  //第一个点到自身的距离为0

    for(int i=0;i<n;i++)      //有n个点所以要进行n次 迭代
    {
        int t=-1;       //t存储当前访问的点

        for(int j=1;j<=n;j++)   //这里的j代表的是从1号点开始
            if(!st[j]&&(t==-1||dist[t]>dist[j]))     
                t=j;

        st[t]=true;   

        for(int j=1;j<=n;j++)           //依次更新每个点所到相邻的点路径值
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }

    if(dist[n]==0x3f3f3f3f) return -1;  //如果第n个点路径为无穷大即不存在最低路径
    return dist[n];
}
int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);    //初始化图 因为是求最短路径
                                //所以每个点初始为无限大

    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);     //如果发生重边的情况则保留最短的一条边
    }

    cout<<Dijkstra()<<endl;
    return 0;
}

 log堆优化dijstla复杂度更低

 

#include <bits/stdc++.h>
//#define double long double
//#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+9,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;

int n,m;
int h[N],e[N],ne[N],w[N];
int idx;
bool st[N];
int dist[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int dis()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    priority_queue<PII,vector<PII>,greater<PII>> heap;

    heap.push({0,1});//第一个值存距离，第二个值存点

    while (heap.size())
    {
        auto t=heap.top();
        heap.pop();

        int v=t.second,dis=t.first;
        if(st[v]) continue;
        st[v]= true;

        for(int i=h[v];i!=-1;i=ne[i])//遍历每一个节点，找到每一节点取节点之间最小距离，不断更新
        {
            int j=e[i];
            if(dist[j] > dis+w[i])
            {
                dist[j]=dis+w[i];
                heap.push({dist[j],j});
            }
        }
    }

    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}


void solve()
{
    memset(h,-1,sizeof h);

    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }

    int x=dis();
    cout<<x<<endl;
}

signed main(){
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

 求多源最短路（就是每一个节点之间的最短路）

#include <bits/stdc++.h>
//#define double long double
//#define int long long
#define endl '\n'
using namespace std;
const int N=210,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;

int n,m,q;
int d[N][N];

void floyd()//一个贪心去找每一个节点的中间最优节点
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}

void solve()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;
        }
    }
    while (m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        d[a][b]=min(d[a][b],w);
    }
    floyd();

    while (q--)
    {
        int a,b;
        cin>>a>>b;
        if(d[a][b] > INF/2) puts("impossible");
       else  cout<<d[a][b]<<endl;
    }
}

signed main(){
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

求最小生成树（kruskal，用并查集加贪心实现）就是把每一个节点的联通的最小代价

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+9,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
int kmp(int a,int k,int p)
{
    int ans=1;
    while (k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a;
    }
    return ans;
}


struct G
{
    int u,v,val;
}a[N];

int fu[N];

int find(int x)
{
    if(fu[x]==x) return x;
    else return fu[x]=find(fu[x]);
}
bool cmp(G x,G y)
{
    return x.val<y.val;
}
int n,m;
int ans=0;
int djs()
{

    int sum=0;
    for(int i=1;i<=m;i++)
    {
        int dx=find(a[i].u);
        int dy=find(a[i].v);
        if(dx!=dy)
        {
            fu[dx]=dy;
            sum+=a[i].val;
            ans++;
        }
    }
    return sum;
}


void solve()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fu[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].u>>a[i].v>>a[i].val;
    }

    sort(a+1,a+1+m,cmp);

    int x=djs();

    if(ans<n-1)
    {
        cout<<"impossible";
    }
    else
    {
        cout<<x;
    }

}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

最小生成树2（类似像djstla，去求一个点到一个集合的距离，每次求完就把点加进集合即可，这样可以出全部点到集合的最小代价）区别就是这个是点到集合而djstala是起点到每一个点

#include <bits/stdc++.h>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=510+9,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;

int n,m;
int dist[N];
bool st[N];
int g[N][N];

int prim()
{
    memset(dist,0x3f,sizeof dist);

    int ans=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j] && (t==-1 || dist[t]>dist[j]))
            {
                t=j;
            }
        }
        if(i && dist[t]==INF)
        {
            return INF;
        }
        if(i)
        {
            ans+=dist[t];
        }

        st[t]= true;
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
    }
    return ans;
}

void solve()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);

    for(int i=1;i<=m;i++)
    {
          int a,b,c;
          cin>>a>>b>>c;
          g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int x=prim();

    if(x==INF) cout<<"impossible"<<endl;
    else cout<<x<<endl;
}

signed main(){
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

 题解：

P8638 [蓝桥杯 2016 省 A] 密码脱落 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 

题解：题目是可以变为求最长回文串，然后可以运用区间DP来求解最优的步数掉到指定的串

这里区间状态是由中间向两端转换

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=1005+7,M=1e1;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;

int f[N][N];

void solve()
{
    string s;
    cin>>s;
    int n=s.size();
    s=' '+s;
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++) f[i][i]=0;

    for(int i=2;i<=n;i++)
    {
        for(int l=1;l+1<=n;l++)
        {
            int r=l+i-1;
            if(s[l]==s[r])
            {
                if(i!=2) f[l][r]=f[l+1][r-1];
                else f[l][r]=0;
            }
            else f[l][r]=min(1+f[l+1][r],1+f[l][r-1]);
        }
    }
    cout<<f[1][n];
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//     cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

P8625 [蓝桥杯 2015 省 B] 生命之树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：一道数状DP的模板题，dfs跑一边然后每一个节点取一个最优值，要这个节点或者不要然后取一个最值就行了

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+7,M=1e1;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;

int a[N];
vector<int> tu[N];
int dp[N][2];
int vis[N];
void dfs(int x)
{
    vis[x]=1;
    dp[x][1]=a[x];
    dp[x][0]=0;
    for(int i=0;i<tu[x].size();i++)
    {
        int t=tu[x][i];
        if(!vis[t])
        {
            dfs(t);
            dp[x][1]+=max(dp[t][1],dp[t][0]);
        }
        else
        {
            dp[x][1]=max(dp[x][1],a[x]);
        }
    }
}
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        tu[x].push_back(y);
        tu[y].push_back(x);
    }

    dfs(1);
    int ans=-INF;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,dp[i][1]);
        ans=max(ans,dp[i][0]);
    }
    cout<<ans<<endl;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//     cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

 

总结：这一周主要是复习一下图论的知识点，最短路等等，感觉自己基础还是差了点，dp自己不是很擅长，这个寒假需要加强，然后就是赛后补题，后面计划写完就补，手感热一点，下个星期开始专注比赛

图论完结，还有蓝桥杯的备赛多刷吧

 

寒假第一周（图论复习+补DP)更多相关文章

今日报告-66

设置Windows10暂停更新3000天

AQS公平锁的流程

AMD锐龙7 7800X3D网游专项测试：竟比i9-13900KS强了15%

常用总线技术基本参数对比

探索图像数据中的隐藏信息：语义实体识别和关系抽取的奇妙之旅

设置Chrome浏览器自动升级

JavaScript – 小技巧 Tips

Winform无边框窗体实现拖动

STM32基础（一）

技术人的修炼---九五小庞

vue自定义事件用法及$emit

ODOO 科目配置4

sqlite 触发器 c#

postgresql在插入数据后怎么获取自增id

EF Core 的基本使用

error: failed to push some refs to 'https://github.com/*******/********.github.io.git'

欧拉降幂

编程语言能力对比

基于机器视觉的小车轨迹控制软件界面展示

随机推荐

AJAX & AXIOS-2024/11/1

验证码处理在自动化测试中的应用

一些学科笑话

NOIP2024模拟赛20 & 11.1 小记

20241101 数据结构与算法期中机试收获

Java，启动！

什么是IT技术

即将到来！

2024/11/1日 日志 关于JavaScript简介&引入方式 以及基础语法的学习

舍得-时间-工作是人的一生最重要的事情-自己要有私房钱-人的一生最重要的事情是书写自己的人生

2.TiUP 部署 DM 集群

原型模式的C++实现

python bytecode解析

09-XSS键盘监听、cookie窃取&文件上传绕过

ubuntu 24.04 部署 mysql 8.4.3 LTS

国标GB28181公网平台LiteGBS国标GB28181视频平台建筑工地无线视频联网监控系统方案

imes完工下线

android 13 更改手机信号调整

BFS(Breath First Search 广度优先搜索)

Visual Studio Code（VSCode）中设置中文界面

热门话题

Ethernaut Level 11: Elevator Attack and Blockchain Interaction

快速部署开源spug运维平台的Docker安装指南

驱动调试之printk的原理与使用

计算机思维模型及其应用

华为云发布代码大模型PanGu-Coder2，实现高效代码生成

Linux多硬盘数据存储和分区操作

构建高可用架构: 分层冗余与自动故障转移

LoRA：高效调参的大语言模型适应方法

《分布式系统的基本原理及互联网分层架构的本质》

Hadoop写流程解析

Java架构师的系统架构设计方法论中的规范要点

使用observeDOM解决BetterScroll插件在移动端无法滑动的问题

互联网一致性架构设计实践

高并发系统架构与水平扩展

混合应用的崛起：跨平台开发取代原生应用

  穗舟网 （www.seizhou.com）

本站除标明"本站原创"外所有文章版权归创作人所有，本站不承担任何法律责任和连带责任，如有冒犯请直接联系，我们将立即予以纠正并致歉。

Powered by WordPress  ·  v1.0.0-alpha