当前位置: 首页 > article >正文

AtCoder Beginner Contest 397(ABCDE)

目录

A - Thermometer

翻译:

思路:

实现:

B - Ticket Gate Log

翻译:

思路:

实现:

C - Variety Split Easy

翻译:

思路:

实现:

D - Cubes

翻译:

思路:

实现:


A - Thermometer

翻译:

        高桥测量了自己的体温,发现它是 X^0C

        体温分为以下几种:

  • 高于或等于 38.0^0C:"高烧"
  • 高于或等于 37.5^0C 和低于 38.0^0C:"发烧"
  • 低于 37.5^0C:"正常"

高桥的体温属于哪种分类?请根据输出部分以整数形式给出答案。

思路:

        先判断>=38.0再判断<37.5,都不对输出发烧。可以写快点。

实现:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;

void solve(){
    double n;cin>>n;
    if (n>=38){
        cout<<"1\n";
    }else if (n<37.5){
        cout<<"3\n";
    }else{
        cout<<"2\n";
    }
}

int main(){
    // 关闭输入输出流同步
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数,不填默认
    // cout.precision();
    solve();
    return 0;
}



B - Ticket Gate Log

翻译:

        高桥汇总了检票口的使用记录。但是,他不小心删除了一些进出站记录。他正试图恢复被删除的记录。

        给你一个由 i 和 o 组成的字符串 S。我们想在 S 的任意位置插入 0 个或多个字符,这样得到的字符串就能满足以下条件:

  • 它的长度是偶数,每个奇数(第 1、第 3......个)字符都是 i,而每个偶数(第 2、第 4......个)字符都是 o。

        求需要插入的最少字符数。在此问题的约束条件下,可以证明通过插入适当数量的字符、 S 就能满足条件。

思路:

        字符串 io 是没问题,无需改变的。那么删除这些没问题的后剩下都是要在前后插入的字符了,统计一下剩下字符串长度即可。

实现:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;

void solve(){
    string s;cin>>s;
    int cnt = 0;
    for (int i=1;i<s.size();i++){
        if (s[i]=='o' && s[i-1]=='i') cnt++;
    }
    int n = s.size();
    cout<<n-2*cnt<<"\n";
}

int main(){
    // 关闭输入输出流同步
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数,不填默认
    // cout.precision();
    solve();
    return 0;
}



C - Variety Split Easy

翻译:

        给你一个长度为 N 的整数序列:A=(A_1,A_2,...,A_N)

        当把 A 在一个位置分割成两个非空(连续)子数组时,求这两个子数组中不同整数的计数之和的最大值。

        更具体地说,对于整数 i,求以下两个值的最大和,使得 1≤i≤N-1:(A_1,A_2,...,A_i) 中不同整数的数量,和(A_{i+1},A_{i+2},...,A_N)中不同整数的数量。 

思路:

        前后缀分解,倒序遍历设立一个数组suffix,suffix[i]为[ i : n ]中A的不同整数数量。之后正序遍历求出以每个为分割点得到的和,比较下。

实现:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 3e5+10;
int vis[MX];
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    for (int i=1;i<=n;++i) cin>>a[i];
    vector<int> suffix(n+1);
    memset(vis,0,sizeof(vis));
    for (int cnt=0,i=n;i>=1;--i){
        vis[a[i]]++;
        if (vis[a[i]]==1) cnt++;
        suffix[i] = cnt;
    }
    int maxx = 0;
    memset(vis,0,sizeof(vis));
    for (int cnt=0,i=1;i<n;i++){
        vis[a[i]]++;
        if (vis[a[i]]==1) cnt++;
        maxx = max(maxx,cnt+suffix[i+1]);
    }
    cout<<maxx<<"\n";
}

int main(){
    // 关闭输入输出流同步
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数,不填默认
    // cout.precision();
    solve();
    return 0;
}

D - Cubes

翻译:

        你被给予一个正整数N。决定是否存在一个正整数对(x,y)使得X^3-y^3=N。如果这个整数对,输出这样一个整数对(x,y)。

思路:

       N=x^3-y^3 \leq (y+1)^3-y^3=3y^2+3y+1如果y存在,可得y至少都为y<\sqrt\frac{N}{3}。而直接遍历明显不行。

        令d=x-y, 由N=x^3-y^3=(x-y)(x^2+xy+y^2)\geq (x-y)(x-y)^2=d^3可得d\leq \sqrt[3]N。那么如果(x,y)存在,则满足(d+y)^3-y^3=N=>d^3+3d^2y+3dy^2=N=>d^2+3dy+3y^2=\frac{N}{d}。(注意求幂使用pow返回的是浮点型存在精度问题)。且在d确定的情况下上式单调递增,可用二分判断在d确定下y是否存在。

        结论:先遍历d区间[1,\sqrt\frac{N}{3}),在内部二分搜索y是否有y满足d^2+3dy+3y^2=\frac{N}{d}。即可。时间复杂度为O(\sqrt[3]NlogN)。注意在此题中要注意整型越界问题。(纯纯数学题)

实现:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){
    ll n;cin>>n;
    for (ll d=1;d*d*d<=n;d++){
        if (n%d!=0) continue;
        ll l = 0,r = 900000010;
        while (l+1!=r){
            ll mid = (l+r)/2;
            if (d*d+3*d*mid+3*mid*mid>=n/d){
                r = mid;
            }else{
                l = mid;
            }
        }
        if (d*d+3*d*r+3*r*r==n/d){
            cout<<r+d<<" "<<r<<"\n";
            return;
        }
    }
    cout<<-1<<"\n";
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
}

E - Path Decomposition of a Tree

翻译:

        给你一颗有NK个点的树。点的编号为1,2,...,NK,并且第 i 条边(i=1,2,...,NK-1)连接点u_iv_i

        确定这棵树是否可以分解成 N 条路径,每条路径的长度为 K。更确切地说,确定是否存在满足以下条件的 N×K 矩阵 P:

  •  P_{1,1},...,P_{1,K},P_{2,1},...,P_{N,K}是一个由1,2,...,NK组成的排列。
  • 对于每个i=1,2,...,N和j=1,2,...,K-1它们间有边连接着点P_{i,j},P_{i,j+1}

思路:

        对于一个有NK个节点的树(以1为根节点),要求得到N个互不干扰大小为K的子树。

        如果一个子树的大小为k(当前树的根节点也算上)且子节点数量 <= 2。那么这颗子树为可用路径,删除它。

        如果子树大小 >k 或 子节点数量 >=3 或 子树大小 <k 且 子节点数量 >=2。那么答案就只能为No。对于上面子树的情况可以画图辅助思考下。  

实现:

#include<bits/stdc++.h>
using namespace std;
const int MX = 2e5+10;
int n,k;
vector<vector<int>> tree(MX);
int f = 1;
// 属于当前点的子树大小
int dfs(int now,int fa){
    int res = 1,cnt = 0;
    for (int& i:tree[now]){
        if (i==fa) continue;
        int tree_size = dfs(i,now);
        res += tree_size;
        if (tree_size) cnt++;
    }
    if (res>k || cnt>=3 || res<k && cnt>=2){
        f = 0;
    }
    if (res==k && cnt<=2){
        res = 0;
    }
    return res;
}
void solve(){
    cin>>n>>k;
    for (int x,y,i=1;i<n*k;i++){
        cin>>x>>y;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    dfs(1,1);
    if (f){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
}

  有建议可以评论,我会积极改进qwq。


http://www.kler.cn/a/590080.html

相关文章:

  • 六十天前端强化训练之第二十二天之React 框架 15天深度学习总结(大师版)
  • Matlab 四分之一车辆被动悬架和模糊pid控制对比
  • Visual Studio 2022和C++实现带多组标签的Snowflake SQL查询批量数据导出程序
  • hubilder打包ios app, 并上传TestFlight
  • 分而治之:用于 RGB-T 显著目标检测的 Confluent Triple-Flow 网络(问题)
  • 扩散模型的具体应用——音乐生成(主页有源码)
  • 攻克 3D 模型网站建设难题,看迪威系统优势
  • 【day14】画流程图
  • NFS网络文件共享服务
  • Git 的使用上传下载和更新
  • 算法——图论——交通枢纽
  • 【Maven-plugin】有多少官方插件?
  • 在MacOS 10.15上安装Node.js
  • c++如何利用线程池和epool设计高并发服务器
  • 高效手机检测:视觉分析技术的优势
  • 【css酷炫效果】纯CSS实现3D翻转卡片动画
  • Java 大视界 -- Java 大数据在智能教育虚拟实验室建设与实验数据分析中的应用(132)
  • LeRobot源码剖析——对机器人各个动作策略的统一封装:包含ALOHA ACT、Diffusion Policy、VLA模型π0
  • 【binlog2sql实践】MySQL数据库binlog日志ROW格式转换标准SQL
  • Linux 蓝牙音频软件栈实现分析