• 22/11/24

    1，单调队列；

    (76条消息) 单调队列专题_Dull丶的博客-CSDN博客

    2，kmp算法；

    先是自己和自己匹配，求出ne数组，然后和另一串匹配，进行求解；

    循环里三步：while，if，记录ne数组/挪串匹配；

    1. #pragma GCC optimize(3)
    2. #include
    3. #define rep1(i,a,n) for( int i=(a);i<(n);++i)
    4. #define rep2(i,a,n) for( int i=(a);i<=(n);++i)
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--)
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define endl "\n"
    11. #define lowbit(m) ((-m)&(m))
    12. #define dbug(y) cout<<(y)<<"\n"
    13. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    14. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    15. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    16. #define tulun int e[N],ne[N],h[N],w[N],idx
    17. #define T_solve() int T;cin>>T;while(T--)solve()
    18. #define pi 3.14159265358979323846
    19. using namespace std;
    20. typedef long long LL;
    21. typedef unsigned long long ULL;
    22. typedef pair<int,int> PII;
    23. typedef pair<long long,long long> PLL;
    24. typedef double dob;
    25. const int N=1e6+10,mod=1e6+3,base=131;
    26. char s[N],p[N];
    27. int ne[N];
    28. int n,m;
    29. signed main()
    30. {
    31.     quick_cin();
    32.     cin>>n>>p+1>>m>>s+1;
    33.     for(int i=2,j=0;i<=n;i++)
    34.     {
    35.         while(j&&p[i]!=p[j+1])j=ne[j];
    36.         if(p[i]==p[j+1])j++;
    37.         ne[i]=j;
    38.     }
    39.     for(int i=1,j=0;i<=m;i++)
    40.     {
    41.         while(j&&s[i]!=p[j+1])j=ne[j];
    42.         if(s[i]==p[j+1])j++;
    43.         if(j==n)
    44.         {
    45.             cout<" ";
    46.             j=ne[j];
    47.         }
    48.     }
    49.     return 0;
    50. }

    3，trie树，最大异或和；

    1. #pragma GCC optimize(3)
    2. #include
    3. #define rep1(i,a,n) for( int i=(a);i<(n);++i)
    4. #define rep2(i,a,n) for( int i=(a);i<=(n);++i)
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--)
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define endl "\n"
    11. #define lowbit(m) ((-m)&(m))
    12. #define dbug(y) cout<<(y)<<"\n"
    13. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    14. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    15. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    16. #define tulun int e[N],ne[N],h[N],w[N],idx
    17. #define T_solve() int T;cin>>T;while(T--)solve()
    18. #define pi 3.14159265358979323846
    19. using namespace std;
    20. typedef long long LL;
    21. typedef unsigned long long ULL;
    22. typedef pair<int,int> PII;
    23. typedef pair<long long,long long> PLL;
    24. typedef double dob;
    25. const int N=1e6+10,mod=1e6+3,base=131;
    26. int a[N],son[N<<2][2],idx;
    27. int n;
    28. void insert(int x)
    29. {
    30.     int p=0;
    31.     per2(i,30,0)
    32.     {
    33.         int s=x>>i&1;
    34.         if(!son[p][s])son[p][s]=++idx;
    35.         p=son[p][s];
    36.     }
    37. }
    38. int search(int x)
    39. {
    40.     int p=0,res=0;
    41.     per2(i,30,0)
    42.     {
    43.         int s=x>>i&1;
    44.         if(son[p][!s])
    45.         {
    46.             res+=1<
    47.             p=son[p][!s];
    48.         }
    49.         else p=son[p][s];
    50.     }
    51.     return res;
    52. }
    53. signed main()
    54. {
    55.     quick_cin();
    56.     cin>>n;
    57.     rep2(i,1,n)
    58.     {
    59.         cin>>a[i];
    60.         insert(a[i]);
    61.     }
    62.     int ans=0;
    63.     rep2(i,1,n)
    64.     {
    65.         ans=max(ans,search(a[i]));
    66.     }
    67.     dbug(ans);
    68.     return 0;
    69. }

     4，n-皇后问题

    对角线及反对角线的状态表示；

    正对角线就是y+x，该线上y+x都一样

    反对角线y-x都一样，但是数组下标不能为0，故统一加n；

    1. #pragma GCC optimize(3)
    2. #include
    3. #define rep1(i,a,n) for( int i=(a);i<(n);++i)
    4. #define rep2(i,a,n) for( int i=(a);i<=(n);++i)
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--)
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define endl "\n"
    11. #define lowbit(m) ((-m)&(m))
    12. #define dbug(y) cout<<(y)<<"\n"
    13. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    14. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    15. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    16. #define tulun int e[N],ne[N],h[N],w[N],idx
    17. #define T_solve() int T;cin>>T;while(T--)solve()
    18. #define pi 3.14159265358979323846
    19. using namespace std;
    20. typedef long long LL;
    21. typedef unsigned long long ULL;
    22. typedef pair<int,int> PII;
    23. typedef pair<long long,long long> PLL;
    24. typedef double dob;
    25. const int N=1e2+10,mod=1e6+3,base=131;
    26. int n;
    27. char g[N][N];
    28. int col[N],dg[N],udg[N];
    29. void dfs(int u)
    30. {
    31.     if(u==n)
    32.     {
    33.         rep1(i,0,n)dbug(g[i]);
    34.         cout<
    35.         return;
    36.     }
    37.     int x=u;
    38.     rep1(y,0,n)
    39.     {
    40.         if(col[y]||dg[y+x]||udg[y-x+n])continue;
    41.         col[y]=dg[y+x]=udg[y-x+n]=1;
    42.         g[x][y]='Q';
    43.         dfs(x+1);
    44.         g[x][y]='.';
    45.         
    46.         col[y]=dg[y+x]=udg[y-x+n]=0;
    47.     }
    48. }
    49. signed main()
    50. {
    51.     quick_cin();
    52.     cin>>n;
    53.     rep1(i,0,n)
    54.     rep1(j,0,n)g[i][j]='.';
    55.     dfs(0);
    56.     return 0;
    57. }

    5，走迷宫；

    走到终点的最短路径，第一次走到的一定是最短的！因为是层向拓展，所以第一次走到的一定是最短的！；

    1. #pragma GCC optimize(3)
    2. #include
    3. #define rep1(i,a,n) for( int i=(a);i<(n);++i)
    4. #define rep2(i,a,n) for( int i=(a);i<=(n);++i)
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--)
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define endl "\n"
    11. #define lowbit(m) ((-m)&(m))
    12. #define dbug(y) cout<<(y)<<"\n"
    13. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    14. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    15. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    16. #define tulun int e[N],ne[N],h[N],w[N],idx
    17. #define T_solve() int T;cin>>T;while(T--)solve()
    18. #define pi 3.14159265358979323846
    19. using namespace std;
    20. typedef long long LL;
    21. typedef unsigned long long ULL;
    22. typedef pair<int,int> PII;
    23. typedef pair<long long,long long> PLL;
    24. typedef double dob;
    25. const int N=1e2+10,mod=1e6+3,base=131;
    26. int n,m;
    27. int a[N][N];
    28. int d[N][N];
    29. int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    30. void bfs()
    31. {
    32.     queueq;
    33.     q.push({1,1});
    34.     d[1][1]=1;
    35.     while(q.size())
    36.     {
    37.         auto t=q.front();
    38.         q.pop();
    39.         int x=t.first,y=t.second;
    40.         rep1(i,0,4)
    41.         {
    42.             int xx=x+dx[i];
    43.             int yy=y+dy[i];
    44.             if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!a[xx][yy]&&!d[xx][yy])
    45.             {
    46.                 d[xx][yy]=d[x][y]+1;
    47.                 q.push({xx,yy});
    48.             }
    49.         }
    50.     }
    51.     dbug(d[n][m]-1);
    52. }
    53. signed main()
    54. {
    55.     quick_cin();
    56.     cin>>n>>m;
    57.     rep2(i,1,n)
    58.     rep2(j,1,m)cin>>a[i][j];
    59.     bfs();
    60.     return 0;
    61. }

    6，dijkstra算法；

    注意continue的使用；

    1. #pragma GCC optimize(3)
    2. #include
    3. #define rep1(i,a,n) for( int i=(a);i<(n);++i)
    4. #define rep2(i,a,n) for( int i=(a);i<=(n);++i)
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--)
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define endl "\n"
    11. #define lowbit(m) ((-m)&(m))
    12. #define dbug(y) cout<<(y)<<"\n"
    13. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    14. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    15. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    16. #define tulun int e[N],ne[N],h[N],w[N],idx
    17. #define T_solve() int T;cin>>T;while(T--)solve()
    18. #define pi 3.14159265358979323846
    19. using namespace std;
    20. typedef long long LL;
    21. typedef unsigned long long ULL;
    22. typedef pair<int,int> PII;
    23. typedef pair<long long,long long> PLL;
    24. typedef double dob;
    25. const int N=1e5+10,mod=1e6+3,base=131;
    26. tulun;
    27. void add(int a,int b,int c)
    28. {
    29.     w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    30. }
    31. int n,m;
    32. int dist[N];
    33. int st[N];
    34. void dijkstra()
    35. {
    36.     memset(dist,0x3f,dist);
    37.     priority_queue,greater>q;
    38.     q.push({0,1});
    39.     dist[1]=0;
    40.     while(q.size())
    41.     {
    42.         auto t=q.top();
    43.         q.pop();
    44.         int jl=t.first,ver=t.second;
    45.         if(st[ver])continue;
    46.         st[ver]=1;
    47.         for(int i=h[ver];~i;i=ne[i])
    48.         {
    49.             int j=e[i];
    50.             if(dist[j]>w[i]+jl)
    51.             {
    52.                 dist[j]=w[i]+jl;
    53.                 q.push({dist[j],j});
    54.             }
    55.         }
    56.     }
    57.     if(dist[n]==0x3f3f3f3f)dbug(-1);
    58.     else dbug(dist[n]);
    59. }
    60. signed main()
    61. {
    62.     quick_cin();
    63.     memset(h,-1,h);
    64.     cin>>n>>m;
    65.     rep2(i,1,m)
    66.     {
    67.         int a,b,c;
    68.         cin>>a>>b>>c;
    69.         add(a,b,c);
    70.     }
    71.     dijkstra();
    72.     return 0;
    73. }

    7，floyed算法；

    适用数据范围小的最短路，可以求负权边；

    注意初始化的方法，和dp类似，注意含义；

    1. #pragma GCC optimize(3)
    2. #include
    3. #define rep1(i,a,n) for( int i=(a);i<(n);++i)
    4. #define rep2(i,a,n) for( int i=(a);i<=(n);++i)
    5. #define per1(i,n,a) for( int i=(n);i>(a);i--)
    6. #define per2(i,n,a) for( int i=(n);i>=(a);i--)
    7. #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
    8. #define memset(a,i,b) memset((a),(i),sizeof (b))
    9. #define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
    10. #define endl "\n"
    11. #define lowbit(m) ((-m)&(m))
    12. #define dbug(y) cout<<(y)<<"\n"
    13. #define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
    14. #define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
    15. #define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
    16. #define tulun int e[N],ne[N],h[N],w[N],idx
    17. #define T_solve() int T;cin>>T;while(T--)solve()
    18. #define pi 3.14159265358979323846
    19. using namespace std;
    20. typedef long long LL;
    21. typedef unsigned long long ULL;
    22. typedef pair<int,int> PII;
    23. typedef pair<long long,long long> PLL;
    24. typedef double dob;
    25. const int N=1e3+10,mod=1e6+3,base=131;
    26. int d[N][N];
    27. int n,m,k;
    28. #define inf 0x3f3f3f3f
    29. void floyed()
    30. {
    31.     rep2(k,1,n)
    32.     rep2(i,1,n)
    33.     rep2(j,1,n)
    34.     d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    35. }
    36. signed main()
    37. {
    38.     quick_cin();
    39.     cin>>n>>m>>k;
    40.     rep2(i,1,n)
    41.     rep2(j,1,m)
    42.     {
    43.         if(i==j)d[i][j]=0;
    44.         else d[i][j]=inf;
    45.     }
    46.     rep2(i,1,m)
    47.     {
    48.         int a,b,c;
    49.         cin>>a>>b>>c;
    50.         d[a][b]=min(d[a][b],c);
    51.     }
    52.     floyed();
    53.     rep2(i,1,k)
    54.     {
    55.         int a,b;
    56.         cin>>a>>b;
    57.         if(d[a][b]>inf/2)dbug("impossible");
    58.         else dbug(d[a][b]);
    59.     }
    60.     return 0;
    61. }

  • 相关阅读:
    1.django简介及安装
    所有字母异位词
    js分割字符串
    【无人机通信优化】基于粒子群算法的多跳无线网络部署优化附matlab代码
    （亲测完全可行）charles抓包夜神模拟器保姆级教程
    Java: Java中接口和抽象类的区别以及应用场景
    72道Java线程面试题，一题一答案，不搞花里胡哨
    [吴恩达机器学习课程笔记] week four强化学习
    ubuntu下yolov5 tensorrt模型部署
    力扣 轮转数组三段逆置法和三段拷贝法（C语言）
  • 原文地址：https://blog.csdn.net/aidaqiudeaichao/article/details/128017715