SMU Summer 2024 Contest Round 5

🕗 发布于 2024-07-20 20:46 笔记

A.Robot Takahashi - SMUOJ

对于f(X)最大的那个X，它要满足的是让尽量多的小孩的重量小于它，让尽量多的成人的重量大于等于它。那么这个重量要么是某个成人的重量，要么是某个小孩的重量+1，暴力枚举即可

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int n,m,k;
string s;



void sovle(){
    vector<int>x,y;
    int maxx=0,maxy=0,ansx=0;
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        cin>>k;
        if(s[i]=='0') x.push_back(k);
        else y.push_back(k);
    }
    sort(x.begin(),x.end());sort(y.begin(),y.end());
    for(auto ed:x){
        int l=0,l1=0,r=x.size()-1,r1=y.size()-1,ans=0,ans1=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(x[mid]<=ed){
                ans=mid+1;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }while(l1<=r1){
            int mid1=(l1+r1)>>1;
            if(y[mid1]<=ed){
                ans1=mid1+1;
                l1=mid1+1;
            }else r1=mid1-1;
        }
        int qum=ans+y.size()-ans1;
        ansx=max(ansx,qum);
    }
    for(auto ed:y){
        int l=0,l1=0,r=x.size()-1,r1=y.size()-1,ans=0,ans1=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(x[mid]<ed){
                ans=mid+1;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }while(l1<=r1){
            int mid1=(l1+r1)>>1;
            if(y[mid1]<ed){
                ans1=mid1+1;
                l1=mid1+1;
            }else r1=mid1-1;
        }
        int qum=ans+y.size()-ans1;
        ansx=max(ansx,qum);
    }
    cout<<ansx<<endl;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1;
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

B.Connect 6 - SMUOJ

也是很暴力......

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5+10;
const int mod = 998244353;
int n,m,k;


void sovle(){
    cin>>n;
    string s[n];
    for(int i=0;i<n;i++) cin>>s[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int num1=0,num=0,sum1=0,sum=0,qum1=0,qum=0;
            if(j+5<n){
                for(int w=j;w<=j+5;w++){
                    if(s[i][w]=='#') num1++;
                }
                if(num1+2>=6){
                    cout<<"Yes"<<endl;
                    return;
                }
            }
            if(i+5<n){
                for(int w=i;w<=i+5;w++){
                    if(s[w][j]=='#') sum1++;
                }
                if(sum1+2>=6){
                    cout<<"Yes"<<endl;
                    return;
                }
            }if(j+5<n&&i+5<n){
                for(int w=0;w<6;w++){
                    if(s[i+w][j+w]=='#') qum1++;
                }
                if(qum1+2>=6){
                    cout<<"Yes"<<endl;
                    return;
                }
            }if(j-5>=0&&i+5<n){
                for(int w=0;w<6;w++){
                    if(s[i+w][j-w]=='#'){
                        qum++;
                    }
                }
                if(qum+2>=6){
                    cout<<"Yes"<<endl;
                    return;
                }
            }
        }
    }
    cout<<"No"<<endl;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1; 
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

C.Strange Balls - SMUOJ

当k个值为k的数连在一起就会爆炸。数是一个一个放的，所以一定不会发生第二次爆炸。这个很像一个栈的模型，但是栈不知道有几个数是连在一起的，那么我们再开一个栈记录栈顶这个数连在一起的个数就行了

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5+10;
const int mod = 998244353;
int n,m,k;

void sovle(){
    cin>>n;
    stack<int>v,x;
    int num=0,sum=0;
    for(int i=0;i<n;i++){
        cin>>m;
        v.push(m);
        if(!x.size()){
            x.push(1);
            num=m;
            cout<<1<<endl;
            continue;
        }
        if(num==m){
            int u=x.top();
            x.pop();
            if(u+1==m){
                u++;
                while(u--){
                    v.pop();
                }
                if(v.size()) num=v.top();
            }
            else x.push(u+1);
        }else{
            num=m;
            sum=1;
            x.push(1);
        }
        cout<<v.size()<<endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1; 
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

想要找到第一个为-1的节点，如果暴力枚举必然超时，怎么样更快地找呢？我们可以想象一下当前位置下去不为-1的，像是一个连起来的块块，这个块块的后面就是第一个为-1的位置，然后发挥一下想象力，是不是对于块块中的每个点，第一个为-1的位置都是那里，就好像那个位置是他们的父亲，对，就是并查集。一开始每个位置都是-1，父亲都是自己，被修改后，他的父亲就变成了下一个位置的父亲（！重要，不是下一个，而是下一个的父亲，因为下一个位置可能被修改过，父亲可能不是自己），这样我们就可以实现O1的查询了。

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1048576;
int n,m,k;
int a[N];
int f[N];
set<int>v;

int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}

void sovle(){
    cin>>n;
    for(int i=0;i<N;i++){
        a[i]=-1;
        f[i]=i;
    }
    while(n--){
        int x,y;cin>>x>>y;
        if(x==1){
            int id=find(y%N);
            a[id]=y;
            f[id]=find((id+1)%N);
        }else{
            cout<<a[y%N]<<endl;
        }
    }    
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1;
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

E.Red Polyomino - SMUOJ

在一个最大8*8的字符型矩阵中，让你用k个.连通起来，问有多少种方案。染色模型？（不会）

最大也就8*8，直接剪枝暴搜。枚举每个.作为起点开始搜，并用一个set<vector<string>>v来记录矩阵的状态，每一个状态只能出现一次，当.的周围有@时接着进入一层dfs，注意标记和回溯

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int n,m,k,ans;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
vector<string>s;
set<vector<string> >v;

void dfs(int x){
    if(v.count(s)) return;
    v.insert(s);
    if(!x) {ans++;return;}
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(s[i][j]=='.'){
                for(int h=0;h<4;h++){
                    int xx=dx[h]+i,yy=dy[h]+j;
                    if(xx<0||xx>=n||yy<0||yy>=n||s[xx][yy]!='@') continue;
                    s[i][j]='@';
                    dfs(x-1);
                    s[i][j]='.';
                }
            }
        }
    }
}

void sovle(){
    cin>>n>>k;
    s.resize(n);
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(s[i][j]=='.'){
                s[i][j]='@';
                dfs(k-1);
                s[i][j]='.';
            }
        }
    }
    cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); 
    int t = 1;
    //cin>>t;
    while (t--){
        sovle();
    }

    return 0;
}

F.Stronger Takahashi - SMUOJ

01BFS，待我学了之后回来补

原文地址：https://blog.csdn.net/2301_80353190/article/details/140573690

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【颜色分类】python刷题记录
下一篇：牛客周赛51：小红走矩阵（二分+bfs）

目标检测(object detection)
目标检测广泛应用在多个领域：无人驾驶，机器人…那么如何去定位一个目标的位置呢？
阅读更多2024-11-15
目标检测评估指标详解
特别是IoU，它在目标检测中用于评估预测框的定位准确性，是其他指标（如TP、FP、FN等）的基础。1.正样本（Positive Sample）：在目标检测任务中，指的是那些确实包含目标物体的图像区域。
阅读更多2024-11-15
《目标检测》R-CNN网络基础（RCNN，Fast-RCNN）
训练阶段多，训练耗时：微调CNN⽹络+训练SVM+训练边框回归器。预测速度慢: 使⽤GPU, VGG16模型处理⼀张图像需要47s。占⽤磁盘空间⼤：5000张图像产⽣⼏百G的特征⽂件。数据的形状变化
阅读更多2024-11-15
第5章: 图像变换与仿射操作
在 Pillow 中，我们将此矩阵简化为六个参数。# 创建自定义仿射变换案例：生成透视效果通过调整仿射变换矩阵的参数，可以创建透视效果，使图像看起来像从不同角度拍摄。# 创建透视效果。
阅读更多2024-11-15
itss认证的作用
认证的作用
阅读更多2024-11-15
什么是HTTP，什么是HTTPS？HTTP和HTTPS都有哪些区别？
什么是HTTP，什么是HTTPS？HTTP和HTTPS都有哪些区别？
阅读更多2024-11-15
kafka中topic的数据抽取不到hdfs上问题解决
将json文件抽取到kafka的消息队列（topic）中，再从topic中将数据抽取到hdfs。我们在从kafka中topic的数据抽到hdfs上的时候会出现 flume不报错，但也不抽取的情况。其实
阅读更多2024-11-15
聊天服务器(5)数据库环境搭建和编程
设置中文。
阅读更多2024-11-15
Ubuntu 22.04.4 LTS + certbot 做自动续签SSL证书(2024-11-14亲测)
在运行上述命令时，Certbot 可能会提示您选择一个或多个域名，并询问您是否希望将所有流量重定向到 HTTPS。Certbot 是一个易于使用的客户端，它可以自动获取和安装 SSL/TLS 证书，以
阅读更多2024-11-15
探秘 RPC：揭开远程过程调用的实现原理
概念理解RPC 旨在让开发人员在构建分布式系统时，无需过多关注底层网络通信的细节，就能够像在本地调用函数那样去调用远程服务器上的服务或方法。例如，在一个电商系统中，订单服务可能部署在一台服务器上，而库
阅读更多2024-11-15