• 2022/7/20

            思维练了三道，然后又看了lca的课，为了学重构树先去刷了最小生成树的一些基础题 

    1547E - Air Conditioners

            其实一开始就都错题目了，初始的那些温度也是可以被改变的，所以我们可以想一下如果左边的空调温度加上距离后比当前位置的空调温度还要低，那当前空调的温度就要更新，同理右边也是如此，所以可以分别从左从右遍历一遍求出t[i]的最小值就可以

    Codeforces Round #731 (Div. 3) E. Air Conditioners （思维）_半碗无糖蓝莓冻的博客-CSDN博客

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. ll q,n,k,a[300005],t[300005];
    6. int main(){
    7.     scanf("%lld",&q);
    8.     while(q--){
    9.         scanf("%lld%lld",&n,&k);
    10.         for(int i=1;i<=k;i++) scanf("%lld",&a[i]);
    11.         for(int i=0;i<=n+1;i++) t[i]=1e18;
    12.         for(int i=1;i<=k;i++) scanf("%lld",&t[a[i]]);
    13.         for(int i=1;i<=n;i++) t[i]=min(t[i],t[i-1]+1);
    14.         for(int i=n;i>=1;i--) t[i]=min(t[i],t[i+1]+1);
    15.         for(int i=1;i<=n;i++) printf("%lld ",t[i]);
    16.         printf("\n");
    17.     }
    18.     system("pause");
    19.     return 0;
    20. } 
    21.

    Pipes

    s=" "+s才可以，s=""+s是不可以的！！！

    分清楚情况传递关系搞清楚就可以，难的是在实现上

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. ll t,n;
    6. bool dp[3][200005][7];
    7. string s[3];
    8. int main(){
    9.     scanf("%lld",&t);
    10.     while(t--){
    11.         scanf("%lld",&n);
    12.         cin>>s[1]>>s[2];s[2]=" "+s[2];s[1]=" "+s[1];
    13.         for(int i=0;i<=n+1;i++)
    14.         for(int j=0;j<=6;j++) dp[0][i][j]=dp[1][i][j]=dp[2][i][j]=0;
    15.         for(int p=1;p<=2;p++){
    16.             for(int j=1;j<=n;j++){
    17.             for(int i=1;i<=2;i++){
    18.                 if(s[i][j]=='1'||s[i][j]=='2'){
    19.                     s[i][j]='1';
    20.                     if(i==1&&j==1){dp[i][j][2]=1;}
    21.                     if(i==1&&s[i][j+1]>'2') dp[i][j+1][4]=dp[i][j][2];
    22.                     else if(s[i][j+1]>'2') dp[i][j+1][5]=dp[i][j][2];
    23.                     if(s[i][j+1]<'3') dp[i][j+1][2]=dp[i][j][2];
    24.                 }
    25.                 else{
    26.                     s[i][j]='3';
    27.                     if(i==1&&j==1){dp[i][j][4]=1;}
    28.                     if(i==1){
    29.                         dp[i][j][3]=dp[i+1][j][5];
    30.                         if(s[i][j+1]>'2') dp[i][j+1][4]=dp[i][j][3];
    31.                         if(s[i][j+1]<'3') dp[i][j+1][2]=dp[i][j][3];
    32.                     }
    33.                     else{
    34.                         dp[i][j][6]=dp[i-1][j][4];
    35.                         if(s[i][j+1]<'3') dp[i][j+1][2]=dp[i][j][6];
    36.                         if(s[i][j+1]>'2') dp[i][j+1][5]=dp[i][j][6];
    37.                     }
    38.                 }
    39.             }
    40.         }
    41.         }
    42.        // cout<
    43.         if(dp[2][n][2]&&s[2][n]=='1'||dp[2][n][6]&&s[2][n]=='3') printf("YES\n");
    44.         else printf("NO\n");
    45.     }
    46.     system("pause");
    47.     return 0;
    48. } 
    49.

    1389B - Array Walk

    dp[i][j][0]表示走到了第j个位置，往左走了i步，这次是往右走所能获得的最大价值，dp[i][j][1]就是往左走能获得的最大价值，一共走了多少步也很容易能算出来即j-1+2*i,然后根据题目来列方程就可以，要注意第一层循环要循环z，不然dp[i-1][j+1][0]可能会没有更新

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. ll t,n,k,z,a[100005],dp[6][100005][2];
    6. int main(){
    7.     scanf("%lld",&t);
    8.     while(t--){
    9.         scanf("%lld%lld%lld",&n,&k,&z);
    10.         for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    11.         for(int i=0;i<=5;i++) 
    12.         for(int j=0;j<=n;j++) dp[i][j][0]=dp[i][j][1]=0;
    13.         ll ans=0;
    14.         for(int i=0;i<=z;i++){
    15.             for(int j=1;j<=n;j++){
    16.                 if(i==0&&j==1){
    17.                     dp[0][j][0]=a[j];continue;
    18.                 }
    19.                 if(j-1+2*i<=k){
    20.                     if(i>0) dp[i][j][1]=max(dp[i][j][1],dp[i-1][j+1][0]+a[j]);
    21.                     dp[i][j][0]=max({dp[i][j][0],dp[i][j-1][0]+a[j],dp[i][j-1][1]+a[j]});
    22.                 }
    23.                 else break;
    24.                 ans=max({ans,dp[i][j][0],dp[i][j][1]});
    25.             }
    26.         }
    27.         printf("%lld\n", ans);
    28.     }
    29.     system("pause");
    30.     return 0;
    31. } 
    32.

    P3379 【模板】最近公共祖先（LCA） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

    lca树剖做法的模板

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. ll n,m,s,siz[500005],d[500005],son[500005],f[500005],top[500005];
    6. ll cnt,head[500005];
    7. struct Edge{
    8.     ll from,to,next;
    9. }edge[10000006];
    10. void addedge(ll from, ll to){
    11.     edge[++cnt].from = from;
    12.     edge[cnt].to = to;
    13.     edge[cnt].next =head[from];
    14.     head[from] = cnt;
    15. }
    16. void dfs1(ll x,ll fa){
    17.     siz[x]=1;d[x]=d[fa]+1;
    18.     son[x]=0;f[x]=fa;
    19.     for(int i=head[x];i;i=edge[i].next){
    20.         ll j=edge[i].to;
    21.         if(j==fa) continue;
    22.         dfs1(j,x);
    23.         siz[x]+=siz[j];
    24.         if(siz[son[x]]
    25.     }
    26. }
    27. void dfs2(ll x,ll topx){
    28.     top[x]=topx;
    29.     if(son[x]) dfs2(son[x],topx);
    30.     for(int i=head[x];i;i=edge[i].next){
    31.         if(edge[i].to!=f[x]&&edge[i].to!=son[x])
    32.             dfs2(edge[i].to,edge[i].to);
    33.     }
    34. }
    35. ll lca(ll x,ll y){
    36.     while(top[x]!=top[y]){
    37.         if(d[top[x]]
    38.             swap(x,y);
    39.             x=f[top[x]];
    40.     }
    41.     return d[x]
    42. }
    43. int main(){
    44.     scanf("%lld%lld%lld",&n,&m,&s);
    45.     for(int i=1;i
    46.         ll u,v;
    47.         scanf("%lld%lld",&u,&v);
    48.         addedge(u,v);
    49.         addedge(v,u);
    50.     }
    51.     dfs1(s,0);
    52.     dfs2(s,s);
    53.     while(m--){
    54.         ll u,v;
    55.         scanf("%lld%lld",&u,&v);
    56.         printf("%lld\n",lca(u,v));
    57.     }
    58.     system("pause");
    59.     return 0;
    60. } 
    61.

     P1194 买礼物 - 最小生成树模板

     这个也算是最小生成树的模板了，需要注意的是优惠可能比原价还贵，，，

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. ll n,m,s[500005],cost[500005];
    6. ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
    7. struct node{
    8.     ll u,v,w;
    9.     bool operator<(const node& a)const{
    10.         return w
    11.     }
    12. }edge[500005];
    13. ll kruskal(){
    14.     ll ans=0;
    15.     for(int i=1;i<=m;i++) s[i]=i;
    16.     sort(edge+1,edge+m*m+1);
    17.     ll cnt=0;
    18.     for(int i=1;i<=m*m;i++){ 
    19.         ll x=findd(edge[i].u);
    20.         ll y=findd(edge[i].v);
    21.         if(x==y) continue;
    22.         s[x]=y;
    23.         ans+=edge[i].w;
    24.         cnt++;
    25.         if(cnt>=m-1) break;
    26.     }
    27.     return ans;
    28. }
    29. int main(){
    30.     scanf("%lld%lld",&n,&m);
    31.     for(int i=1;i<=m;i++)
    32.     for(int j=1;j<=m;j++){
    33.         ll x;
    34.         scanf("%lld",&x);
    35.         edge[(i-1)*m+j].w=x==0?n:min(x,n);
    36.         edge[(i-1)*m+j].u=i;
    37.         edge[(i-1)*m+j].v=j;
    38.     }
    39.     printf("%lld\n",kruskal()+n);
    40.     system("pause");
    41.     return 0;
    42. } 
    43.

    P1195 口袋的天空 - 最小生成树​​​

    一直没看懂题意，最后还是在讨论区里知道的题意，要把n个点连成k个连通分量，也就是要剩下k个分量，剩下一个分量时需要n-1条边，剩下k个分量时就是需要n-k条边，需要注意的就是这一点

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. ll n,m,k,s[1005],vis[1005];
    6. ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
    7. struct node{
    8.     ll x,y,w;
    9.     bool operator<(const node& a)const{
    10.         return w
    11.     }
    12. }ed[10005];
    13. ll kruscal(){
    14.     ll ans=0,cnt=0,flag=0;
    15.     for(int i=1;i<=n;i++) s[i]=i,vis[i]=0;
    16.     sort(ed+1,ed+m+1);
    17.     for(int i=1;i<=m;i++){
    18.         ll x=findd(ed[i].x),y=findd(ed[i].y);
    19.         if(x==y) continue;
    20.         s[x]=y;
    21.         cnt++;
    22.         ans+=ed[i].w;
    23.         if(cnt>=n-k){flag=1;break;}
    24.     }
    25.     if(!flag) return -1;
    26.     return ans;
    27. }
    28. int main(){
    29.     scanf("%lld%lld%lld",&n,&m,&k);
    30.     for(int i=1;i<=m;i++){
    31.         scanf("%lld%lld%lld",&ed[i].x,&ed[i].y,&ed[i].w);
    32.     }
    33.     ll ans=kruscal();
    34.     if(ans==-1) printf("No Answer");
    35.     else printf("%lld\n",ans);
    36.     system("pause");
    37.     return 0;
    38. } 
    39.

    P1536 村村通 - 并查集​​​​​​

    有连通分量的思想，用并查集合并能合并的点，最后看看还剩下几个连通分量，答案就是剩下的连通分量个数-1；

    1. #include 
    2. #define ll long long
    3. #define lowbit(x) ((x)&(-x))
    4. using namespace std;
    5. ll n,m,s[1005],vis[1005];
    6. ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
    7. void uni(ll x,ll y){
    8.     ll xx=findd(x),yy=findd(y);
    9.     if(xx!=yy){
    10.         s[xx]=yy;
    11.     }
    12. }
    13. int main(){
    14.     while(scanf("%lld", &n)!=EOF){
    15.         if(n==0) break;
    16.         scanf("%lld", &m);
    17.         for(int i=1;i<=n;i++) s[i]=i,vis[i]=0;
    18.         for(int i=1;i<=m;i++){
    19.             ll u,v;
    20.             scanf("%lld%lld", &u, &v);
    21.             uni(u,v);
    22.         }
    23.         ll ans=0;
    24.         for(int i=1;i<=n;i++){
    25.             if(!vis[findd(i)]) vis[findd(i)]=1,ans++;
    26.         }
    27.         printf("%lld\n",ans-1);
    28.     }
    29.     system("pause");
    30.     return 0;
    31. } 
    32.

  • 相关阅读:
    【HCSD大咖直播】亲授大厂面试秘诀【云驻共创】
    Windows安装docker
    Redis-02
    运算符与表达式
    Python入门指南：探索无限可能的编程世界
    java 单元测试Junit
    pytorch中gather函数详解【包你看懂，我敢说在CSDN上没人解释的比我清楚】
    @vue/cli创建项目遇到ERROR Failed to get response from /vue-cli-version-marker 解决方法
    Mysql允许远程访问
    Vatee万腾的数字化掌舵：Vatee科技引领未来的新高度
  • 原文地址：https://blog.csdn.net/weixin_52621204/article/details/125886730