首页 > 其他分享 >3.25-3.31

3.25-3.31

时间：2024-03-31 15:55:42浏览次数：16  
标签：10 int long while 3.25 3.31 push define

天梯赛2：

7-12 这是二叉搜索树吗？

在满足题意的前提下从前后分别往中间走模拟二叉树的建立即可。

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e5+10 , M = 1e6+10 ;

int k[N];
int n,st=0;
vector<int> ans;

void build(int l,int r) {
    if(l>r) return ;
    int i = l+1 , j=r;
    if(st) {
        while(i<=r && k[i]>=k[l]) i++;
        while(j>l && k[j]<k[l]) j--;
        i-- , j++;
    }
    else {
        while(i<=r && k[i]<k[l]) i++;
        while(j>l && k[j]>=k[l]) j--;
        i-- , j++;
    }
    if(j-i!=1) return ;
    build(l+1,i);
    build(j,r);
    ans.push_back(k[l]);
}

void solve() {
    cin >> n;
    for(int i=1;i<=n;i++) cin >> k[i];
    build(1,n);
    if(ans.size()==n) {
        cout << "YES" << endl;
        for(int i=1;i<=n;i++) cout << ans[i-1] << " \n"[i==n];
        return ;
    }
    ans.clear();
    st^=1;
    build(1,n);
    if(ans.size()==n) {
        cout << "YES" << endl;
        for(int i=1;i<=n;i++) cout << ans[i-1] << " \n"[i==n];
        return ;
    }
    cout << "NO" << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

7-13 肿瘤诊断

三维bfs即可。（赛时写的dfs爆栈空间导致re，好似了这下）

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e5+10 , M = 1e6+10 ;

int n,m,l,t;
int k[70][1310][130];
bool vis[70][1310][130];

struct node {
    int l,x,y;
};

int dx[7]={0,1,-1,0,0,0,0};
int dy[7]={0,0,0,1,-1,0,0};
int dz[7]={0,0,0,0,0,1,-1};

int bfs(int a,int b,int c) {
    int cnt=1;
    queue<node> q;
    q.push({a,b,c});
    vis[a][b][c]=1;
    while(q.size()) {
        auto [z,x,y] = q.front();
        q.pop();
        for(int i=1;i<=6;i++) {
            int xt = dx[i]+x , yt = dy[i]+y , zt = dz[i]+z;
            if(xt>=1 && xt<=n && yt>=1 && yt<=m && zt>=1 && zt<=l && !vis[zt][xt][yt] && k[zt][xt][yt]==1) {
                cnt++;
                vis[zt][xt][yt]=1;
                q.push({zt,xt,yt});
            }
        }
    }
    return cnt;
}

void solve() {
    cin >> n >> m >> l >> t;
    for(int x=1;x<=l;x++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) cin >> k[x][i][j];
        }
    }
    int ans=0;
    for(int x=1;x<=l;x++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(k[x][i][j]==1 && !vis[x][i][j]) {
                    int cnt = bfs(x,i,j);
                    if(cnt>=t) ans+=cnt;
                    cnt=0;
                }
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

7-15 特殊堆栈

 multiset（自定义排序）维护对顶堆。也可以权值树状数组加二分。 这里用的二分维护vector的增加和删除操作。 
//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e5+10 , M = 1e6+10 ;

int k[N];

void solve() {
    int n;
    cin >> n;
    int idx=0;
    vector<int> ans;
    while(n--) {
        string s;
        cin >> s;
        if(s=="Pop") {
            if(idx==0) {
                cout << "Invalid" << endl;
            }
            else {
                int x = k[idx--];
                ans.erase(lower_bound(ans.begin() , ans.end() , x));
                cout << x << endl;
            }
        }
        else if(s=="PeekMedian") {
            if(idx==0) {
                cout << "Invalid" << endl;
            }
            else {
                int x = (idx+1)/2-1;
                cout << ans[x] << endl;
            }
        }
        else {
            int x;
            cin >> x;
            k[++idx]=x;
            ans.insert(lower_bound(ans.begin() , ans.end() , x) , x);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

div4：

D：完全背包板子改一下

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e5+10 , M = 1e6+10 ;

int f[N];

vector<int> v;

void init() {
    for(int i=0;i<(1<<5);i++) {
        int x=0;
        for(int j=4;j>=0;j--) {
            if((i>>j)&1) x = x*10+1;
            else x=x*10;
        }
        f[x]=1;
        if(x) v.push_back(x);
    }
    f[100000]=1;
    for(auto & t : v) {
        for(int j=t;j<=100000;j++) {
            if(j%t==0) {
                int w = j/t;
                if(f[w]) f[j]=1;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    cout << (f[n] ? "YES" : "NO") << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
    init();
    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

E：枚举字符串长度检查即可

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e5+10 , M = 1e6+10 ;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;
    for(int k=n;k>=1;k--) {
        if(n%k) continue;
        int cnt=0 , len=n/k;
        for(int i=1,j=1;i<=n;i++) {
            if(s[j]!=s[i]) cnt++;
            if(j==len) j=1;
            else j++;
        }
        string d = s + ' ';
        reverse(d.begin() , d.end());
        int res=0;
        for(int i=1,j=1;i<=n;i++) {
            if(d[j]!=d[i]) res++;
            if(j==len) j=1;
            else j++;
        }
        if(cnt<2 || res<2) {
            cout << len << endl;
            return ;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

F：两种写法：

一：分类讨论，并且必须满足a+1 == c。

二：bfs维护层数，先a在b最后c，这种更好写。

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e5+10 , M = 1e6+10 ;

void solve() {
    int a,b,c;
    cin >> a >> b >> c;
    if(!a && !b) {
        if(c==1) cout << 0 << endl;
        else cout << -1 << endl;
    }
    else if(!a && !c) cout << -1 << endl;
    else if(!b && !c) cout << -1 << endl;
    else if(!c) cout << -1 << endl;
    else if(!a) {
        if(c==1) cout << b << endl;
        else cout << -1 << endl;
    }
    else if(!b) {
        if(a+1!=c) cout << -1 << endl;
        else {
            int cnt=0;
            for(int i=0;;i++) {
                int x = (1<<i);
                if(cnt+x>=a) {
                    cout << i+1 << endl;
                    return ;
                }
                else cnt+=x;
            }
        }
    }
    else {
        if(a+1!=c) {
            cout << -1 << endl;
            return ;
        }
        int ans=0;
        int cnt=0 , w;
        for(int i=0;;i++) {
            int x = (1<<i);
            if(cnt+x>a) {
                ans=i;
                a-=cnt;
                w=x;
                break;
            }
            else cnt+=x;
        }
        if(a+b<=w) {
            cout << ans+1 << endl;
            return ;
        }
        b-=w-a;
        int d = (w-a)+a*2;
        int res=b/d;
        if(b%d) res++;
        cout << ans+res+1 << endl;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

 G：很经典的状压DP

初始化每个点作为起点的情况。

然后二进制枚举每一种状态，若当前状态被标记，记录一下答案，更新当前状态可以到达的其他的状态。

比如当前状态f[i][j]，现在枚举到一个点k，若j可以到k并且k这个点当前状态没有标记k点，就考虑更新k点。

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e5+10 , M = 1e6+10 ;

void solve() {
    int n;
    cin >> n;
    vector<pair<string , string>> s(n+10);
    vector<vector<int>> d(n+10,vector<int>(n+10));
    for(int i=0;i<n;i++) cin >> s[i].first >> s[i].second;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(i==j) continue;
            if(s[i].first==s[j].first || s[i].second==s[j].second) d[i][j]=d[j][i]=1;
        }
    }
    vector<vector<int>> f((1<<n)+10,vector<int>(n+10));
    for(int i=0;i<n;i++) f[1<<i][i]=1;
    int ans=0;
    for(int i=1;i<(1<<n);i++) {
        for(int j=0;j<n;j++) {
            if(f[i][j]) {
                int res=0;
                for(int k=0;k<n;k++) {
                    if((i>>k)&1) res++;
                }
                ans=max(ans,res);
                for(int k=0;k<n;k++) {
                    if(((i>>k)&1)==0 && d[j][k]) {
                        f[i|(1<<k)][k]=1;
                    }
                }
            }
        }
    }
    cout << n-ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

天梯赛3：

7-14 天梯地图

Dijkstra维护两个键值即可。

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 510 , M = 1e6+10 ;

struct node {
    int x,y,z;
    bool operator < (const node & a) const {
        return x > a.x;
    }
};

int n,m,st,en;
int fl[N],ft[N];
int disl[N],dist[N];
int L[N],T[N];
bool visl[N],vist[N];
vector<int> ansl,anst;
vector<node> vl[N],vt[N];

void bfsl(int x) {
    priority_queue<node> q;
    memset(disl , 0x3f , sizeof disl);
    memset(T , 0x3f , sizeof T);
    q.push({0,0,x});
    disl[x]=0 , T[x]=0;
    while(q.size()) {
        int t = q.top().z;
        q.pop();
        if(visl[t]) continue;
        visl[t]=1;
        for(auto & [u,w,d] : vl[t]) {
            if(disl[u] > disl[t] + w) {
                disl[u] = disl[t] + w;
                T[u]=T[t]+1;
                fl[u]=t;
                q.push({disl[u],T[u],u});
            }
            else if(disl[u] == disl[t] + w) {
                if(T[u]>T[t]+1) {
                    T[u] = T[t]+1 , fl[u]=t;
                    q.push({disl[u],T[u],u});
                }
            }
        }
    }
}

void bfst(int x) {
    priority_queue<node> q;
    memset(dist , 0x3f , sizeof dist);
    memset(L , 0x3f , sizeof L);
    q.push({0,0,x});
    dist[x]=0 , L[x]=0;
    while(q.size()) {
        int t = q.top().z;
        q.pop();
        if(vist[t]) continue;
        vist[t]=1;
        for(auto & [u,w,d] : vt[t]) {
            if(dist[u] > dist[t] + w) {
                dist[u] = dist[t] + w;
                L[u]=L[t]+d;
                ft[u]=t;
                q.push({dist[u],L[u],u});
            }
            else if(dist[u] == dist[t] + w) {
                if(L[u]>L[t]+d) {
                    L[u] = L[t]+d , ft[u]=t;
                    q.push({dist[u],L[u],u});
                }
            }
        }
    }
}

void solve() {
    cin >> n>> m;
    for(int i=1;i<=m;i++) {
        int v1,v2,way,l,t;
        cin >> v1 >> v2 >> way >> l >> t;
        vl[v1].push_back({v2,l,t});
        vt[v1].push_back({v2,t,l});
        if(way==0) {
            vl[v2].push_back({v1,l,t});
            vt[v2].push_back({v1,t,l});
        }
    }
    cin >> st >> en;
    fl[st]=-1 , ft[st]=-1;
    bfsl(st);
    bfst(st);

    int d = en;
    while(fl[d]!=-1) ansl.push_back(d) , d = fl[d];
    ansl.push_back(st);

    d = en;
    while(ft[d]!=-1) anst.push_back(d) , d = ft[d];
    anst.push_back(st);

    reverse(ansl.begin() , ansl.end());
    reverse(anst.begin() , anst.end());

//    cout << "ansl: " << endl;
//    for(auto & t : ansl) cout << t << ' ';
//    cout << endl;
//
//    cout << "anst: " << endl;
//    for(auto & t : anst) cout << t << ' ';
//    cout << endl;
//
//    cout << "dist: " << endl;
//    for(int i=0;i<n;i++) cout << dist[i] << " \n"[i==n-1];

    if(ansl==anst) {
        cout << "Time = " << dist[en] << "; Distance = " << disl[en] << ": ";
        for(int i=0;i<ansl.size();i++) {
            cout << ansl[i];
            if(i==ansl.size()-1) cout << endl;
            else cout << " => ";
        }
    }
    else {
        cout << "Time = " << dist[en] << ": ";
        for(int i=0;i<anst.size();i++) {
            cout << anst[i];
            if(i==anst.size()-1) cout << endl;
            else cout << " => ";
        }
        cout << "Distance = " << disl[en] << ": ";
        for(int i=0;i<ansl.size();i++) {
            cout << ansl[i];
            if(i==ansl.size()-1) cout << endl;
            else cout << " => ";
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}
View Code

 

标签：10,int,long,while,3.25,3.31,push,define
From： https://www.cnblogs.com/lzywakaka/p/18106603

相关文章

  • SMU Winter 2024 div2 ptlks的周报Week 7（3.25-3.31）
    哈夫曼编码对出现频率大的字符赋予较短的编码，对出现频率小的字符赋予较长的编码。哈夫曼树的建树过程为，每次选取最小和次小的根节点，将它们之和作为它们的根节点，左子节点为小点，右子节点为次小点，直至仅剩一棵树。一棵哈夫曼树，左子树为0，右子树为1，以根节点到叶子结点的路径作为每个叶......
  • 3.25-3.31周报
    天梯赛27-10红色警报这道题的题意要注意是删去一个城市后增加了多少个区域，而不是有多少个城市变成了单独的点，赛时理解错了题意，用set做会有点有问题。其实很简单，就是bfs搜一下有多少个联通块，每次删除把被删的点打个标记，每次联通块的个数和上一次的比较一下，只要增加就是改变了连......
  • 3.25~3.28
    另：？咋写这玩意的时候突然耳鸣了几秒我不会要趋势了吧（我发现和5k聊题总会出点问题倒不是说听不懂他的思路而是出在一些奇奇怪怪的地方......
  • 就业班 第二阶段 2401--3.25 day5 mycat读写分离
    @[TOC] 启动并更改临时密码[root@mysql1~]#systemctlstartmysqld&&passwd=`greppassword/var/log/mysqld.log|awk'END{print$NF}'`&&mysqladmin-p"$passwd"password'Qwer123..';MyCAT读写分离Mycat是一个开源的数据库系统，但是由......
  • 2024.03.25【补】【版面编排】排版四大原则！！
    排版最重要也是最基础的四大原则：1.对齐：我们的大脑总是会去寻找一条看不见的横线或者竖线，利用网格系统，将元素适当对齐就能创作出舒适好看的版面把杂乱的内容根据线条对齐，混乱感也会随之消失，取而代之的是秩序感和舒适感，这样还能创造出让读者舒适的视觉动线2.对比：当所有的信息......
  • 云原生周刊：Kubernetes v1.30 一瞥 ｜ 2024.3.25
    开源项目推荐RetinaRetina是一个与云无关的开源Kubernetes网络可观测平台，它提供了一个用于监控应用程序运行状况、网络运行状况和安全性的集中中心。它为集群网络管理员、集群安全管理员和DevOps工程师提供可操作的见解，帮助他们了解DevOps、SecOps和合规性用例。Retina......
  • 2024.3.25
    IstartedtoreadChinaDailyinthemorning,it'sprettygood.ItakealookatthenewsofMarathoninWuxi,andshareitwithmyfriendwhosaidthisappwaslikeFacebook.SchoolinformationSectioncalledmetoday,theythoughtmyMAChadbee......
  • 3.25
    javaweb实现数据查询分页首先我们需要一个用于分页的工具类packagecom.lgh.app.page;/***@authorlgh**此类是用于分页的工具类*可以重复利用**/importjava.util.List;publicclassPage<T>{//当前是第几页privateintpageNo;//当前页......
  • 3.25
    <!DOCTYPEhtml><html><head><title>艾鑫个人主页</title><metahttp-equiv="content-type"content="text/html;charset=UTF-8"><styletype="text/css">/*设置超链接样式*/table{  border-collapse......
  • 3.25毕设
    封装后端返回的数据首先建一个Result类，用于封装返回的数据，我这里包含了四个参数，参数含义分别如下这里测试一下。 返回了预期的数据 ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99