首页 > 其他分享 >10 - 2 ~ 10 - 3 模拟赛报告

10 - 2 ~ 10 - 3 模拟赛报告

时间：2024-10-02 17:22:45浏览次数：1  
标签：10 const 报告 int LL cin kMaxN using 模拟

启动新赛季！

10.2

题目一览：

题目名称 躲避技能 奶茶兑换券 帮助 神奇的变换
题目类型 传统 传统 传统 传统
文件名 skill tea help change
时空限制 \(2s256M\) \(1s256M\) \(2s256M\) \(5s256M\)
测试点数量 \(25\) \(10\) \(20\) \(25\)

请观看 VCR，并回答作者表达的情感。

  • \(\texttt{『S』}\) 今天我们充分发扬 PTY 告诉我们的策略！

那我们直接把暴力分拿满！

T1

题面：有一棵树，一些节点上有若干个箱子，要把所有箱子推到若干节点的坑中（坑中可能可以填一个或者多个），经过每一条边都有相应代价，求完成任务最小的代价。

思路：

直接建树爆搜，然后全排列，复杂度 \(O(m !)\)。

// Darkworldmystery 2023 ~ 2024
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;
using LL = long long;

const LL kMaxN = 1e5 + 5;

struct Edge
{
    LL to, w;
} ;

LL n, m, s[kMaxN], imp[kMaxN], dis[15][kMaxN], id[kMaxN], ret = 1e18;
vector<Edge> nbr[kMaxN];

LL refc(string x)
{
    int ret = 0;
    for(int i = x.size() - 1; i >= 0; i--)
        ret = ret * 10 + (x[i] - '0');
    return ret;
}

void dfs(LL x, LL father, LL root = 1)
{
    for(LL i = 0; i < nbr[x].size(); i++)
    {
        LL y = nbr[x][i].to, w = nbr[x][i].w;
        if(y == father)
            continue;
        dis[root][y] = dis[root][x] + w;
        dfs(y, x, root);
    }
    return ;
}


int main()
{
    freopen("skill.in", "r", stdin);
    freopen("skill.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(LL i = 1; i <= m; i++)
        cin >> s[i], id[i] = i;
    for(LL i = 1; i <= m; i++)
        cin >> imp[i];
    for(LL i = 1, x, y, w; i < n; i++)
    {
        string ww;
        cin >> x >> y;
        cin >> ww;
        w = refc(ww);
        // cerr << w << "\n";
        nbr[x].push_back({y, w});
        nbr[y].push_back({x, w});
    }
    dfs(1, 0);
    for(LL i = 1; i <= m; i++)
        dfs(s[i], 0, s[i]);
    do 
    {
        LL B = 0;
        for(int i = 1; i <= m; i++)
            B += dis[s[i]][imp[i]];
        ret = min(ret, B);
    } while(next_permutation(s + 1, s + 1 + m));
    cout << ret << "\n";
    return 0;
}

如愿以偿地拿到了暴力 \(\color{red} 20 pt\)。

T2

题面：玥玥有无限张价值 \(m\) 的奶茶代金券，每次玥玥会使用代金券购买两杯奶茶。只有当代金券的总价值大于等于奶茶的总价值才可以购买，但是奶茶店是不找零的。

假设每张代金券价值 \(10\) 元，然后买了一杯 \(11\) 元和一杯 \(4\) 元的奶茶。则需要两张代金券才能购买，但是两张代金券价值 \(20\)，奶茶总价值 \(15\)，即我们可以认为玥玥这样做浪费了 \(5\) 元。

现在已知玥玥总共购买了 \(n\) 种价值的奶茶，第 \(i\) 种奶茶购买的数量为 \(a_i\)，价格为 \(b_i\)。请问玥玥最少浪费多少钱？

思路：直接枚举所有搭配，然后和这个搭配浪费的钱用 vector 存起来，然后贪浪费的钱少的，然后枚到没了为止。

也是非常好写。

// Darkworldmystery 2023 ~ 2024
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;
using LL = long long;

const LL kMaxN = 1e5 + 5;

struct Milktea
{
    LL x, price;
    friend bool operator < (const Milktea &x, const Milktea &y)
    {
        return x.price < y.price;
    }
} a[kMaxN];
struct E
{
    LL a, b, D;
    friend bool operator < (const E &x, const E &y)
    {
        return x.D < y.D;
    }
} ;

vector<E> vt;
LL n, m, ret;


int main()
{
    freopen("tea.in", "r", stdin);
    freopen("tea.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(LL i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].price;
    sort(a + 1, a + 1 + n);
    if(n <= 1000)
    {
        for(LL i = 1; i <= n; i++)
            for(LL j = i; j <= n; j++)
                vt.push_back({i, j, (m - (a[i].price + a[j].price) % m == m ? 0 : m - (a[i].price + a[j].price) % m)});
        sort(vt.begin(), vt.end());
        for(auto i : vt)   
        {
            LL x = i.a, y = i.b, w = i.D, T = min(a[x].x, a[y].x);
            if(x == y)
                T /= 2;
            if(a[x].x <= 0 || a[y].x <= 0)
                continue;
            a[x].x -= T, a[y].x -= T;
            ret += w * T;
        }
        cout << ret << "\n";
        return 0;
    }
    cout << "1145141919810" << "\n";
    return 0;
}

顺利的拿到了 \(\color{orange} 30 pt\)。

另 \(30 \%\) 的性质听了感觉非常无语，不过因为数据出锅没有这个性质的数据。

T3

题面：有 \(n\) 个人，第 \(i\) 个人的 EQ \(x_i\) 和 IQ \(y_i\)，每个人的 EQ 都不一样。

第 \(i\) 个人可以分享自己的 IQ 给 EQ 在 \([c_i, d_i]\) 的人，也愿意接受 EQ 在 \([a_i, b_i]\) 的人，不属于自己的 IQ 不可以再分享给别人。

在他们尽可能分享自己的脑子 IQ 的情况下，每个人的 IQ。

思路：好啊这波更简单，直接按题意模拟。

// Darkworldmystery 2023 ~ 2024
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;
using LL = long long;

const LL kMaxN = 1e5 + 5;

struct Point
{
    LL num, score, ans = 1, mine;
    pair<LL, LL> allow, help;
} a[kMaxN];

LL n;

bool check(Point x, Point y)
{
    return x.score >= y.allow.first && 
           x.score <= y.allow.second &&
           y.score >= x.help.first &&
           y.score <= x.help.second;
}

int main()
{
    freopen("help.in", "r", stdin);
    freopen("help.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(LL i = 1; i <= n; i++)
        cin >> a[i].num, a[i].ans = a[i].num;
    for(LL i = 1; i <= n; i++)
        cin >> a[i].score;
    for(LL i = 1; i <= n; i++)
        cin >> a[i].allow.first >> a[i].allow.second >> a[i].help.first >> a[i].help.second;
    if(n <= 1000)
    {
        for(LL i = 1; i <= n; i++)
            for(LL j = i + 1; j <= n; j++)
            {
                if(check(a[i], a[j]))
                    a[j].ans += a[i].num;
                if(check(a[j], a[i]))
                    a[i].ans += a[j].num;
            }
        for(LL i = 1; i <= n; i++)
            cout << a[i].ans << " ";
    }
    return 0;
}

成功拿到了 \(\color{orange} 30 pt\)。

T4

题面：有一天，玥玥在电视上，看到了一种神奇的数字变换。

这种变换首先需要我们拿到一个正整数，然后对它分别进行以下分解：

  1. 分解它的质因数，数一数其质因数的指数，如果有一个质因数的指数 \(\ge 2\)，写下 \(0\)；否则，若有奇数个质因数，写下 \(−1\)，否则写下 \(1\)。
  2. 分解其所有正约数，写下其约数个数以及约数总和。

显然，对于每一个数 \(x\)，经过变换后将得到 \(3\) 个整数。

玥玥试了试，发现他算出了正确的答案，他太开心了！

然而，很不幸，这一切被玥玥的老师看见了。老师总算是找到了给玥玥出题的机会，于是在第二天，老师给玥玥留了一道《好》题。

老师给玥玥了 \(n\) 个正整数，排成一排。老师让玥玥仔细看看这个序列（名字叫 \(a\)），然后告诉了玥玥他会问 \(q\) 个问题。每一个问题中，老师给出两个数 \(l, r\)，让玥玥算出数字 \(x\) 的答案，其中 \(x = \displaystyle\prod_{i = l} ^ {r} a_i\)

玥玥：老师，这个数（指 \(x\)）太大了怎么办？

老师：没关系，你只需要告诉我答案对 \(10 ^ 9 + 7\) 取模的结果就行了（完全理解成了答案太大）。实在不行的话，可以请别人帮忙哦。

这下可把玥玥难住了。她请班上 OI 最强的你来帮他解决这个问题，毕竟，这可能会给她加不少德育分啊！

老师比较善良，所以每一次回答问题时，只需要回答答案中的第 \(type\) 问就可以。注意，这里的输出 \(x\) 的答案指的是输出 \(y\) 经过上述变换得到的 \(3\) 个整数中的第 \(type\) 个。

由于老师的问题是一个一个问的，所以本题强制在线。

思路：依然暴力（不过有一个 \(type = 3\) 的没时间写了）

// Darkworldmystery 2023 ~ 2024
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e5 + 5, kMod = 1e9 + 7;

int n, q, a[kMaxN], opt, T;

int main()
{
    freopen("change.in", "r", stdin);
    freopen("change.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q >> opt;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int l, r; q; q--)
    {
        cin >> l >> r;
        l ^= T, r ^= T;
        LL x = 1;
        for(int i = l; i <= r; i++)
            x *= a[i];
        if(opt == 1)
        {
            LL sum = 0, cnt = 0;
            bool f = 0;   
            for(int i = 2; i <= x; i++)
            {
                if(x % i == 0)
                {
                    sum++;
                    x /= i;
                }
                while(x % i == 0)
                    f = 1, x /= i;
            }
            if(f == 1)
                cout << "0\n", T = 0;
            else if(sum & 1 == 1)
                cout << kMod - 1 << "\n", T = kMod - 1;
            else
                cout << "1\n", T = 1;
        }
        else if(opt == 2)
        {
            LL ret = 0;
            for(int i = 1; i * i <= x; i++)
            {
                if(x % i == 0)
                {
                    LL j = n / i;
                    (ret += 2) %= kMod;
                }
            }
            cout << (ret + kMod) % kMod << "\n";
            T = (ret + kMod) % kMod;
        }
        // else if(opt == 3)
        // {
        //     LL ret = 0;
        //     for(int i = 1; i <= sqrt(x); i++)
        //     {
        //         if(x % i == 0)
        //         {
        //             LL j = n / i;
        //             (ret += i + j) %= kMod;
        //         }
        //     }
        //     cout << (ret + kMod) % kMod << "\n";
        //     T = (ret + kMod) % kMod;
        // }
    }
    return 0;
}

预估的是 \(\color{red} 24 pt\)，但是折了半，只有 \(\color{red} 12 pt\)，不过赛后 mmt 的一句话，让我感觉很离谱了。

你怎么没有判完全平方数啊？

标签：10,const,报告,int,LL,cin,kMaxN,using,模拟
From： https://www.cnblogs.com/DarksBlog/p/18444874

相关文章

  • win11,vc22源码编译opencv410
    1.安装cmake 2.配代理，否则无法下载依赖包3.自行编译OpenCV源码步骤4.注意配置系统变量，重启机器https://blog.csdn.net/weixin_50648158/article/details/139742826亲测可用OpenCV4.10.0在Windows10，64位，vs2022下的编译及配置方法https://blog.csdn.net/yxfamyself/article......
  • LoongArch@微处理器体系结构专利技术研究方法@20241002
    微处理器体系结构专利技术研究方法第一辑：X86指令集总述 微处理器体系结构专利技术研究方法第二辑：x86多媒体指令集 微处理器体系结构专利技术研究方法第三辑：X86指令实现专利技术 ......
  • 10月做题记录
    10月做题记录✩trick✯会大部分，要\(tj\)提示✬会小部分/完全没想到，看了\(tj\)才会◈脑电波✡有某一算法的神秘通用性质⊗待补目录10月做题记录CF2018FSpeedbreakerCounting✬✩CF2018FSpeedbreakerCounting✬✩非常牛题目，就是学\(whk\)学傻了，乘法过后的取......
  • 模拟赛总结(二)
    2024.8.1T1集合(mex.cpp)枚举每个数，求他是\(mex\)的概率，就是取完比他小的，比他大的随便取的方案数比上总方案数codeT2取模(mod.cpp)有点套路定义：\(odd\)为奇数，\(even\)为偶数，\(num_{odd}\)或者\(t\)为奇数个数那个下取整可以变为：\[\begin{cases}&\text{odd+even:......
  • 2024.10 - 做题记录与方法总结
    赏赐的是CCF，收回的也是CCF-《CCF圣经》2024/10/01国庆快乐！P10856【MX-X2-T5】「CfzRound4」Xor-Forces题面：题目描述给定一个长度为\(n=2^k\)的数组\(a\)，下标从\(0\)开始，维护\(m\)次操作：操作一：给定\(x\)，设数列\(a'\)满足\(a'_i=a_{i\oplusx}\)，将\(a\)......
  • 补题报告
    背景2024-10-1上午打的比赛（CSP-J模拟），作赛后总结报告。交替出场(Alter)赛时AC。思路１.先将结果数设为长度(默认每个长度为1的子串符合要求)２.遍历每个子串，判断是否满足01交替串，是+1３.输出我的代码#include<iostream>#include<string>#include<cstring>#i......
  • 10.2 总结
    T1躲避技能赛时拿的是暴力的\(40\)分，没开long。40pts用LCA乱搞，枚举每一个人去哪里，复杂度\(\mathcalO(m!\logn)\)。AC给每一个躲避点打上\(-1\)标记，当前点打上\(1\)标记，每一次向上转移边长乘子树标记和即可。T2奶茶兑换券暴力不会。T3帮助40pts枚举每......
  • 痞子衡嵌入式半月刊： 第 108 期
    痞子衡嵌入式半月刊：第108期这里分享嵌入式领域有用有趣的项目/工具以及一些热点新闻，农历年分二十四节气，希望在每个交节之日准时发布一期。本期刊是开源项目（GitHub:JayHeng/pzh-mcu-bi-weekly），欢迎提交issue，投稿或推荐你知道的嵌入式那些事儿。上期回顾：《痞子衡嵌入式半月......
  • P1020 [NOIP1999 提高组] 导弹拦截
    P1020[NOIP1999提高组]导弹拦截参考材料需要抽象一下，第一问就可以抽象为最长不上升子序列，第二问可以抽象为最长上升子序列长度。就如下图的情况：然后可以先\(n^2\)做法做，因为\(n\ge100000\)所以要滚动数组，求最长不上升子序列可以反向从n开始递推。我是n^2我不好......
  • 2024.9.24 模拟赛 CSP4
    模拟赛暴力场。出题人学政治的？T1商品值域线段树直接看值域上，每两个相邻的点的差提供的贡献，相当于值域上某一区间每一个位置都有\(1\)的贡献再减一。所以直接值域线段树，查询区间和。贪心发现左右端点一定挂在某个点上时最优。注意左右端点挂住的情况分别跑一遍。边界处理......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99