首页 > 其他分享 >IAI 12月月赛

IAI 12月月赛

时间:2023-01-01 21:47:32浏览次数:67  
标签:cnt 12 IAI int sum son ans id

T1 拼接单词

我这里是暴力做法,30tps,set内存爆了

#include <bits/stdc++.h>
using namespace std;
vector<string> ve;
int main()
{
    string a, b;
    cin >> a >> b;
    auto n = a.size(), m = b.size();
    string temp, temp1;
    for (unsigned int i = 0; i < n; i++)
    {
        temp1 += a[i], temp = "";
        for (int j = m - 1; j >= 0; j--)
        {
            temp = b[j] + temp;
            ve.push_back(temp1 + temp);
        }
    }
    set<string> s(ve.begin(), ve.end());
    cout << s.size();
    return 0;
}

T2 八进制小数

正解应该是秦九韶+高精度+快速幂,我这里还没订正,只采用秦九韶(30tps)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    char eight[600];
    double sum;
    int i;
    scanf("%s", eight);
    sum = 0.0;
    for (int i = 0; eight[i] != '\0'; i++)
        sum += (eight[i] - '0') * pow(0.125, i + 1);
    while (sum > 0)
    {
        sum *= 10;
        cout << (int)sum;
        sum -= (int)sum;
    }
    return 0;
}

T3 最长路

正解参照树的直径两次dfs,算次大和最大的路径长度

我这里瞎写的dfs(0tps)

#include <bits/stdc++.h>
using namespace std;
const int N = 201000;
vector<int> son[N], father[N];
bool vis[N];
int ans = 0, cnt = 0, n;
void dfs(int s, int sum)
{
    vis[s] = 1, cnt++;
    if (cnt == n)
    {
        ans = max(ans, sum);
        return;
    }
    if (father[s].size())
    {
        for (auto v : father[s])
            if (!vis[v])
            {
                dfs(v, sum + 1);
                cnt--;
            }
    }
    if (son[s].size())
    {
        for (auto v : son[s])
            if (!vis[v])
            {
                dfs(v, sum + 1);
                cnt--;
            }
    }
}

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        int u;
        cin >> u; 
        son[u].push_back(i);
        son[i].push_back(u);
    }
    for (int i = n; i <= n; i++)
    {
        ans = 0;
        memset(vis, 0, sizeof(vis));
        dfs(i, 0);
        cout << ans << ' ';
    }
    return 0;
}

T4 最大频率

我们先算出每一个区间的起始位置和结束位置,离散化一下,然后询问时参照下图

image-20230101212010441

然后用三个if语句判断一下即可。

(样例已过)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
struct node
{
    int num, id;
} a[N];
pair<int, int> x[N];
int main()
{
    int cnt = 1;
    cin >> n >> m;
    a[1].id = 1;
    x[1].first = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].num;
        if (a[i].num != a[i - 1].num && i > 1)
        {
            a[i].id = ++cnt;
            x[(cnt - 1)].second = i - 1;
            x[cnt].first = i;
        }
        else
            a[i].id = cnt;
    }
    x[cnt].second = n;
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        int ans = 0, y = 0;
        for (int i = l; i <= r; i++)
        {
            if (x[a[i].id].first >= l && x[a[i].id].second <= r)
                ans = max(ans, x[a[i].id].second - x[a[i].id].first + 1);
            else if (x[a[i].id].first >= l && x[a[i].id].second > r)
                ans = max(ans, r - x[a[i].id].first + 1);
            else if (x[a[i].id].first < l && x[a[i].id].second <= r)
                ans = max(ans, x[a[i].id].second - l + 1);
        }
        cout << ans << endl;
    }
    return 0;
}

时间复杂度 \(O(nm)\) 预测60tps

标签:cnt,12,IAI,int,sum,son,ans,id
From: https://www.cnblogs.com/ljfyyds/p/17018640.html

相关文章

  • 【LeetCode】122. 买卖股票的最佳时机Ⅱ
    官方介绍文档LeetCode说明连接:122.买卖股票的最佳时机II-力扣(LeetCode)贪心算法参考解题思路:买卖股票的最佳时机II(贪心,清晰图解)-买卖股票的最佳时机II-力扣(Le......
  • 12、网关SpringCloud-Gateway
    网关作为流量的入口,常用功能包括路由转发、权限校验、限流控制等。而springcloudgateway作为SpringCloud官方推出的第二代网关框架,取代了Zuul网关。网关提供API......
  • OneStack:Ubuntu 12.04 (或11.10) 一键安装部署OpenStack云计算平台
     OneStack:在Ubuntu12.04(precise)上一键安装部署OpentackEssex提醒:如果你喜欢折腾,喜欢自己一步一步安装各个功能组件和配置conf文件,你可以略过此文。本文工具可以在裸机和虚......
  • RNN详解(12)
    本文部分参考和摘录了以下文章,在此由衷感谢以下作者的分享!​​​https://zhuanlan.zhihu.com/p/28054589​​​​​​https://zhuanlan.zhihu.com/p/28687529​​​​​......
  • 好题分享、心路历程(力扣1225)
    【题目介绍】该题为力扣1225,名为报告系统状态的连续日期。【题型分类】属于连续专题。官网标为困难题。【思路分享】这里的连续属于时间连续,采用row_number()、subd......
  • 力扣---1262. 可被三整除的最大和
    给你一个整数数组 nums,请你找出并返回能被三整除的元素最大和。示例1:输入:nums=[3,6,5,1,8]输出:18解释:选出数字3,6,1和8,它们的和是18(可被3整除的最大和)。示例2......
  • fix协议介绍12-取消订单被拒(OrderCacelReject)
    FIX.5.0SP2MessageOrderCancelReject [type'9']<OrdCxlRej>Theordercancelrejectmessageisissuedbythebrokeruponreceiptofacancelrequestorcancel......
  • 122FPS、51.8mAP 超轻量关键点检测算法PP-TinyPose来啦!
    精准的人机交互任务,如手势控制、智能健身、体感游戏等,背后的核心技术是什么?那必须是关键点检测!还有智慧城市、智慧安防等领域的打架斗殴、司机/工人违规操作等异常行为识别,......
  • sql server 2012 导出SQL文件
    一.工具1.1sqlserver2012二.方法2.1打开sqlserver2012,连接成功后,选择需要导出表的数据库--任务---生成脚本2.2显示:生成和发布脚......
  • 2022/12/31
    今天在整第三个elf...还没弄完,进度好慢啊我的进度感觉是最慢的吧QAQ师傅说以后要讲讲IDA的更牛逼一点用法,今天找到几篇博客,自己打算先看看看看小甲鱼,学学汇编,不能一直......