• ACW 最长上升子序列模型 && 数字三角形模型 P1967 [NOIP2013 提高组] 货车运输 day34

    哦 今天一时兴起想刷提高课 不知道是提高课的题太水了 还是讲的很细

    大概两个多小时就能刷十多道吧

    P1967 [NOIP2013 提高组] 货车运输

    这道题思路挺简单的吧 不过我好像是dfs 那里写错了一点调了蛮久的

    这个大概可以一眼看出最大生成树 

    可是我最开始想的就是dfs来找最大载重 时间复杂度大概是O（q*n）1e8感觉可以通过的啊

    可是题解里面都是lca 那没办法 那我们就用倍增lca吧 时间复杂度是O（qlogn+nlog）

    这里fa就是lca里的fa

    W和fa的定义差不多 该点距2^j的点的最大限重

    注意我们更新时就因该把k放在外层 因为是倍增嘛

    dfs的时候记得把根节点初始成inf 其实不初始也能ac

    最后还要注意的就是dfs时不要和我一样

    fa[j][0]的爹是x;

    depth[j]=depth[x]+1;

    1. #include 
    2. using namespace std;
    3. const int N = 5e4+10;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int n,m,p[N],h[N],e[M],ne[M],w[M],idx,W[N][21],fa[N][21],depth[N];
    15. bool vis[N];
    16. struct Edge{
    17.     int a,b,w;
    18.     bool operator < (const Edge&W)const{
    19.         return w>W.w;
    20.     }
    21. }edge[M];
    22. void add(int a,int b,int c){
    23.     e[idx]=b;
    24.     w[idx]=c;
    25.     ne[idx]=h[a];
    26.     h[a]=idx++;
    27. }
    28. int find(int x){
    29.     if(p[x]!=x)p[x]=find(p[x]);
    30.     return p[x];
    31. }
    32. void kruskal(){
    33.     sort(edge,edge+m);
    34.     for(int i=1;i<=n;i++)p[i]=i;
    35.     for(int i=0;i
    36.         int a=edge[i].a,b=edge[i].b,w=edge[i].w;
    37.         if(find(a)!=find(b)) {
    38.             p[find(a)]=find(b);
    39.             add(a,b,w),add(b,a,w);
    40.         }
    41.     }
    42. }
    43. void dfs(int x){
    44.     vis[x]=1;
    45.     for(int i=h[x];~i;i=ne[i]){
    46.         int j=e[i];
    47.         if(!vis[j]){
    48.             fa[j][0]=x;
    49.             depth[j]=depth[x]+1;
    50.             W[j][0]=w[i];
    51.             for(int k=1;k<=20;k++)fa[j][k]=fa[fa[j][k-1]][k-1];
    52.             dfs(j);
    53.         }
    54.     }
    55. }
    56. int lca(int a,int b){
    57.     if(depth[a]swap(a,b);
    58.     int ans=inf;
    59.     for(int k=20;k>=0;k--){
    60.         if(depth[fa[a][k]]>=depth[b]){
    61.             ans=min(W[a][k],ans);//
    62.             a=fa[a][k];
    63.         }
    64.     }
    65.     if(a==b)return ans;
    66.     for(int k=20;k>=0;k--){
    67.         if(fa[a][k]!=fa[b][k]){
    68.             ans=min(ans,min(W[a][k],W[b][k]));
    69.             a=fa[a][k];
    70.             b=fa[b][k];
    71.         }
    72.     }
    73.     ans=min(ans,min(W[a][0],W[b][0]));//
    74.     return ans;
    75. }
    76. signed main(){
    77.     cin>>n>>m;
    78.     memset(h,-1,sizeof h);
    79.     for(int i=0;i
    80.         int a,b,c;cin>>a>>b>>c;
    81.         edge[i]={a,b,c};
    82.     }
    83.     kruskal();
    84.     for(int i=1;i<=n;i++){
    85.         if(!vis[i]){
    86.             depth[i]=1;
    87.             dfs(i);
    88.             W[i][0]=inf;
    89.         }
    90.     }
    91.     for(int k=1;k<=20;k++){
    92.         for(int i=n;i>=1;i--){
    93.             W[i][k]=min(W[i][k-1],W[fa[i][k-1]][k-1]);
    94.         }
    95.     }
    96.     int q;cin>>q;
    97.     while(q--){
    98.         int a,b;cin>>a>>b;
    99.         if(find(a)!=find(b))cout<<-1<
    100.         else cout<<lca(a,b)<
    101.     }
    102.     return ~~(0^_^0);
    103. }

    下面基本都很简单就随便贴一贴把

    AcWing 1015. 摘花生

    1. #include 
    2. using namespace std;
    3. const int N = 110;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int f[N][N],a[N][N];
    15. signed main(){
    16.     int t;cin>>t;
    17.     while(t--){
    18.         int n,m;cin>>n>>m;
    19.         for(int i=1;i<=n;i++)
    20.             for(int j=1;j<=m;j++)
    21.                 cin>>a[i][j];
    22.         for(int i=1;i<=n;i++)
    23.             for(int j=1;j<=m;j++)
    24.                 f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
    25.         cout<
    26.     }
    27.     return ~~(0^_^0);
    28. }

    AcWing 1018. 最低通行费

    1. #include 
    2. using namespace std;
    3. const int N = 110;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int f[N][N],a[N][N];
    15. signed main(){
    16.     int n;cin>>n;
    17.     for(int i=1;i<=n;i++)
    18.         for(int j=1;j<=n;j++)
    19.             cin>>a[i][j];
    20.     memset(f,0x3f3f,sizeof f);
    21.     f[1][0]=f[0][1]=0;
    22.     for(int i=1;i<=n;i++)
    23.         for(int j=1;j<=n;j++)
    24.             f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
    25.     cout<
    26.     return ~~(0^_^0);
    27. }

    AcWing 1027. 方格取数

    这道题还有点难度 但也不是特别难

    主要是以前没见过 就是一个四维的吧 然后他简化成了三维

    1. #include 
    2. using namespace std;
    3. const int N = 15;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int f[N<<1][N][N],a[N][N];
    15. signed main(){
    16.     fast
    17.     int n;cin>>n;
    18.     int x,y,w;
    19.     while(cin>>x>>y>>w,x||y||w)a[x][y]=w;
    20.     for(int k=2;k<=n*2;k++){
    21.         for(int i1=1;i1<=n;i1++){
    22.             for(int i2=1;i2<=n;i2++){
    23.                 int j1=k-i1,j2=k-i2;
    24.                 if(j1<1||j1>n||j2<1||j2>n)continue;
    25.                 if(i1==i2){
    26.                     f[k][i1][i2]=max(max(max(f[k-1][i1][i2],f[k-1][i1-1][i2]),f[k-1][i1][i2-1]),f[k-1][i1-1][i2-1])+a[i1][k-i1];
    27.                 }else{
    28.                     f[k][i1][i2]=max(max(max(f[k-1][i1][i2],f[k-1][i1-1][i2]),f[k-1][i1][i2-1]),f[k-1][i1-1][i2-1])+a[i1][k-i1]+a[i2][k-i2];
    29.                 }
    30.             }
    31.         }
    32.     }
    33.     cout<2*n][n][n]<
    34.     return ~~(0^_^0);
    35. }

    AcWing 275. 传纸条

    和上面一题一模一样虽然这个多了不能相交的条件

    这个随便想一下就知道吧

    相交肯定不是最优解

    1. #include 
    2. using namespace std;
    3. const int N = 55;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int f[N<<1][N][N],a[N][N];
    15. signed main(){
    16.     fast
    17.     int n,m;cin>>n>>m;
    18.     for(int i=1;i<=n;i++)
    19.         for(int j=1;j<=m;j++)
    20.             cin>>a[i][j];
    21.     for(int k=2;k<=n+m;k++){
    22.         for(int i1=1;i1<=n;i1++){
    23.             for(int i2=1;i2<=n;i2++){
    24.                 int j1=k-i1,j2=k-i2;
    25.                 if(j1<1||j1>m||j2<1||j2>m)continue;
    26.                 if(i1==i2)f[k][i1][i2]=max(max(max(f[k-1][i1][i2],f[k-1][i1-1][i2]),f[k-1][i1][i2-1]),f[k-1][i1-1][i2-1])+a[i1][k-i1];
    27.                 else f[k][i1][i2]=max(max(max(f[k-1][i1][i2],f[k-1][i1-1][i2]),f[k-1][i1][i2-1]),f[k-1][i1-1][i2-1])+a[i1][k-i1]+a[i2][k-i2];
    28.             }
    29.         }
    30.     }
    31.     cout<
    32.     return ~~(0^_^0);
    33. }

    AcWing 1017. 怪盗基德的滑翔翼

    1. #include 
    2. using namespace std;
    3. const int N = 110;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int f[N];
    15. signed main(){
    16.     fast
    17.     int t;cin>>t;
    18.     while(t--){
    19.         int n;cin>>n;
    20.         int a[N];
    21.         for(int i=1;i<=n;i++)cin>>a[i];
    22.         for(int i=1;i<=n;i++)f[i]=1;
    23.         int ans=-2e9;
    24.         for(int i=1;i<=n;i++){
    25.             for(int j=1;j
    26.                 if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
    27.                 ans=max(ans,f[i]);
    28.             }
    29.         }
    30.         for(int i=1;i<=n;i++)f[i]=1;
    31.         for(int i=n;i>=1;i--){
    32.             for(int j=i+1;j<=n;j++){
    33.                 if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
    34.                 ans=max(ans,f[i]);
    35.             }
    36.         }
    37.         cout<
    38.     }
    39.     return ~~(0^_^0);
    40. }

    AcWing 1014. 登山

    1. #include 
    2. using namespace std;
    3. const int N = 1010;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int n,f1[N],f[N];
    15. signed main(){
    16.     fast
    17.     int n;cin>>n;
    18.     int a[N];
    19.     for(int i=1;i<=n;i++)cin>>a[i];
    20.     for(int i=1;i<=n;i++)f[i]=f1[i]=1;
    21.     for(int i=1;i<=n;i++)
    22.         for(int j=1;j
    23.             if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
    24.     for(int i=n;i>=1;i--)
    25.         for(int j=i+1;j<=n;j++)
    26.             if(a[i]>a[j])f1[i]=max(f1[i],f1[j]+1);
    27.     int ans=-2e9;
    28.     for(int i=1;i<=n;i++)ans=max(ans,f[i]+f1[i]);
    29.     cout<-1<
    30.     return ~~(0^_^0);
    31. }

    AcWing 482. 合唱队形

    1. #include 
    2. using namespace std;
    3. const int N = 1010;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int n,f1[N],f[N];
    15. signed main(){
    16.     fast
    17.     int n;cin>>n;
    18.     int a[N];
    19.     for(int i=1;i<=n;i++)cin>>a[i];
    20.     for(int i=1;i<=n;i++)f[i]=f1[i]=1;
    21.     for(int i=1;i<=n;i++)
    22.         for(int j=1;j
    23.             if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
    24.     for(int i=n;i>=1;i--)
    25.         for(int j=i+1;j<=n;j++)
    26.             if(a[i]>a[j])f1[i]=max(f1[i],f1[j]+1);
    27.     int ans=-2e9;
    28.     for(int i=1;i<=n;i++)ans=max(ans,f[i]+f1[i]);
    29.     cout<1<
    30.     return ~~(0^_^0);
    31. }

    AcWing 1012. 友好城市

    1. #include 
    2. using namespace std;
    3. const int N = 5010;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. pair<int,int>p[N];
    15. int f[N];
    16. signed main(){
    17.     fast
    18.     int n;cin>>n;
    19.     for(int i=1;i<=n;i++)cin>>p[i].first>>p[i].second;
    20.     sort(p+1,p+n+1);
    21.     int a[N];
    22.     for(int i=1;i<=n;i++)a[i]=p[i].second,f[i]=1;
    23.     int ans=0;
    24.     for(int i=1;i<=n;i++){
    25.         for(int j=1;j
    26.             if(a[i]>a[j]){
    27.                 f[i]=max(f[i],f[j]+1);
    28.                 ans=max(ans,f[i]);
    29.             }
    30.         }
    31.     }
    32.     cout<
    33.     return ~~(0^_^0);
    34. }

    AcWing 1016. 最大上升子序列和

    1. #include 
    2. using namespace std;
    3. const int N = 1010;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int f[N];
    15. signed main(){
    16.     fast
    17.     int n;cin>>n;
    18.     int a[N];
    19.     int ans=-2e9;
    20.     for(int i=1;i<=n;i++)cin>>a[i],f[i]=a[i],ans=max(ans,a[i]);
    21.     for(int i=1;i<=n;i++){
    22.         for(int j=1;j
    23.             if(a[i]>a[j]){
    24.                 f[i]=max(f[i],f[j]+a[i]);
    25.                 ans=max(ans,f[i]);
    26.             }
    27.         }
    28.     }
    29.     cout<
    30.     return ~~(0^_^0);
    31. }

    AcWing 1010. 拦截导弹

    这个以前我做的时候还是绿题来着 刚刚去看了变黄了

    确实该变变了 不过这种时候确实发现自己成长挺多的

    1. #include 
    2. using namespace std;
    3. const int N = 1010;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int a[N],f[N],f1[N];
    15. signed main(){
    16.     fast
    17.     int n=1;
    18.     while(cin>>a[n])n++;
    19.     n--;
    20.     int ans=-2e9;
    21.     for(int i=1;i<=n;i++)f1[i]=f[i]=1;
    22.     for(int i=1;i<=n;i++){
    23.         for(int j=1;j
    24.             if(a[j]>=a[i]){
    25.                 f[i]=max(f[i],f[j]+1);
    26.                 ans=max(ans,f[i]);
    27.             }
    28.         }
    29.     }
    30.     if(ans!=-2e9)cout<
    31.     else cout<<1<
    32.     ans=-2e9;
    33.     for(int i=1;i<=n;i++){
    34.         for(int j=1;j
    35.             if(a[i]>a[j]){
    36.                 f1[i]=max(f1[i],f1[j]+1);
    37.                 ans=max(ans,f1[i]);
    38.             }
    39.         }
    40.     }
    41.     if(ans!=-2e9)cout<
    42.     else cout<<1<
    43.     return ~~(0^_^0);
    44. }

    AcWing 187. 导弹防御系统

    这道题可以爆搜 可以迭代加深 因为答案很浅

    然后我们用了个 类似以前的log级别的LIS模型

    f[i]表示第i个数的最小值？

    差不多吧50范围加个基础剪枝就过了

    1. #include 
    2. using namespace std;
    3. const int N = 55;
    4. const int M = 5e4+10;
    5. const int mod = 998244353;
    6. #define int long long
    7. #define endl '\n'
    8. #define Endl '\n'
    9. #define _ 0
    10. #define inf 0x3f3f3f3f3f3f3f3f
    11. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    12. int max(int x,int y){return x>y?x:y;}
    13. int min(int x,int y){return x
    14. int ans,down[N],up[N],n,a[N];
    15. void dfs(int u,int s,int d){
    16.     if(s+d>=ans)return;
    17.     if(u==n+1){
    18.         ans=s+d;
    19.         return;
    20.     }
    21.     int k=0;
    22.     while(k=a[u])k++;
    23.     int t=up[k];
    24.     up[k]=a[u];
    25.     if(k==s)dfs(u+1,s+1,d);
    26.     else dfs(u+1,s,d);
    27.     up[k]=t;
    28.  
    29.     k=0;
    30.     while(k
    31.     t=down[k];
    32.     down[k]=a[u];
    33.     if(k==d)dfs(u+1,s,d+1);
    34.     else dfs(u+1,s,d);
    35.     down[k]=t;
    36. }
    37. signed main(){
    38.     fast
    39.     while(cin>>n,n){
    40.         for(int i=1;i<=n;i++)cin>>a[i];
    41.         ans=2e9;
    42.         dfs(1,0,0);
    43.         cout<
    44.     }
    45.     return ~~(0^_^0);
    46. }

  • 相关阅读:
    用户体验 | 如何度量用户体验？
    双十二电容笔哪个品牌好？十大电容笔知名品牌
    存档＆改造【03】Apex-Fancy-Tree-Select花式树的导入及学习
    深入理解 pytest.main()：Python 测试框架的核心功能解析
    栈与队列经典题目——用队列实现栈
    spring基础知识详解
    vue 样式加scoped不起作用 局部更改element-ui的默认样式
    lambda表达式
    OpenCV自学笔记八：几何变换
    《Linux》day3--shell语法（上）
  • 原文地址：https://blog.csdn.net/qq_23852555/article/details/125884137