首页 > 其他分享 >Day13 备战CCF-CSP练习

Day13 备战CCF-CSP练习

时间:2024-11-10 14:07:55浏览次数:4  
标签:res string int auto heap Day13 push CCF CSP

Day 13

题目描述

题目分析

大模拟,用栈储存每一个多项式,最后根据导数的加法原则依次求导相加,注意取模。

C++代码

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 100010, MOD = 1e9 + 7;
string oper;
int n, m;
stack<vector<pair<map<string, int>, int>>> heap;
map<string, int> num;
map<string, int> p;

bool is_num(string x)
{
    for (auto s : x)
        if (!isdigit(s) && s != '-')
            return false;
    return true;
}

int qmi(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res % MOD;
}

int to_num(string x)
{
    int res = 0, flag = 1;
    for (auto s : x)
    {
        if (s == '-')
            flag = -1;
        else
            res = res * 10 + s - '0';
    }
    return res * flag;
}

void calc(string op)
{
    auto a = heap.top();
    heap.pop();
    auto b = heap.top();
    heap.pop();

    if (op == "+")
    {
        for (auto it : b)
            a.push_back(it);
        heap.push(a);
    }
    else if (op == "-")
    {
        for (auto it : a)
            b.push_back({it.first, -1ll * it.second});
        heap.push(b);
    }
    else
    {
        vector<pair<map<string, int>, int>> t;
        for (auto itb : b)
        {
            for (auto ita : a)
            {
                pair<map<string, int>, int> tmp;
                for (auto [k, v] : itb.first)
                {
                    tmp.first[k] = itb.first[k] + ita.first[k];
                }
                tmp.second = ita.second * itb.second % MOD;
                t.push_back(tmp);
            }
        }
        heap.push(t);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        string s = "x" + to_string(i);
        p[s] = 0;
    }

    getline(cin, oper);
    getline(cin, oper);

    for (int i = 0; i < oper.size(); i++)
    {
        string x = "";
        while (oper[i] != ' ' && i < oper.size())
            x += oper[i++];

        if (x == "+" || x == "-" || x == "*")
            calc(x);
        else if (is_num(x))
        {
            vector<pair<map<string, int>, int>> c;
            c.push_back({p, to_num(x)});
            heap.push(c);
        }
        else
        {
            auto t = p;
            t[x]++;
            vector<pair<map<string, int>, int>> c;
            c.push_back({t, 1});
            heap.push(c);
        }
    }

    // auto t = heap.top();
    // for (auto [y, c] : t)
    // {
    //     for (auto [k, v] : y)
    //         cerr << k << ' ' << v << endl;
    //     cerr << "c " << c << '\n';
    // }

    while (m--)
    {
        int id;
        cin >> id;
        string x = "x" + to_string(id);
        for (int i = 1; i <= n; i++)
        {
            string x2 = "x" + to_string(i);
            int number;
            cin >> number;
            num[x2] = number;
        }

        // for (auto [y, c] : num)
        // {
        //     cerr << y << ' ' << c << '\n';
        // }

        int res = 0;

        for (auto t : heap.top())
        {
            auto it = t.first;
            int c = t.second;
            if (c == 0)
                continue;
            int k = c;
            for (auto y : it)
            {
                string w = y.first;
                int mi = y.second;
                // cout << w << ' ' << num[w] << ' ' << mi << '\n';
                if (x == w)
                {
                    if (mi == 0)
                    {
                        k = 0ll;
                        break;
                    }
                    else
                    {
                        k = k * qmi(num[w], mi - 1) % MOD;
                        k = k * mi % MOD;
                    }
                }
                else
                {
                    k = k * qmi(num[w], mi) % MOD;
                }
                // cout << k << '\n';
            }
            res = (res + k) % MOD;
        }
        cout << (res % MOD + MOD) % MOD << '\n';
    }

    return 0;
}

标签:res,string,int,auto,heap,Day13,push,CCF,CSP
From: https://www.cnblogs.com/mathblog/p/18537909

相关文章

  • 2024 CSP-J/S 游记
    前言暑假和开学后一直在考模拟赛,前前后后考了有四十多场,这应该比我以前三年考过的模拟赛数量加起来还多了,所以这个赛季还是希望能考好一点的(虽然模拟赛考的很烂)。印象最清晰的是一场S组模拟赛把CDQ分治加斜率优化dp放在了T1。很多大数据结构T4也是之前没有见过的码量(......
  • 2024CSP_S2游记
    markdown和Latex就不修了,太麻烦了,将就看吧从S1到S2今年NFLSHC初三10个复赛,于是还给了初一和六年级8个,去年初三只有4个,进步了由于去年J组320应该够了,所以今年没考J,不去浪费J组国一名额,攒功德2024.9.23上午做操排队时被人踩了,由于自带的脆皮属性导致骨折,悲剧,带伤集训+出战CSP-S......
  • 2024 CSP 游记
    游记逆转时空的公式就是珍惜当下。DAY-38初赛,不会的我都蒙了A和B。DAY-0.4白天在学校十分有干劲,晚上九点半下课到家十点半,收拾物件到十一点多倒头就睡。DAY0火车上正在酣睡中,@Kenma@lichenxi111俩人在旁边大力敲击键盘开卷,本人只能强制开机跟他们一起开打。和@......
  • CSP 2024-S 游记 黑暗的枷锁
    09-21今天考完了初赛,明显感觉数学门槛变高了一些,有高中数学知识才能保证看得懂题意,只是苦了小学和初中同学,看数据参加人数还涨了50%,权当拉低分数线了吧。用小图灵估分70。应该是稳过。09-28出分了,刚好70,稳过。竟然和小图灵估的一分不差。10-25复赛前一天晚上,停课的竞赛生们都......
  • CSP-S2024 游记
    Day0到武汉了。酒店环境不错,但隔音效果不太好。看了会板子,十一点半就睡了。Day16:05时醒了,生物钟作祟。倒头睡,然后直接就睡到了8:30,起床随便吃了点早饭。学弟来我房间问题,好吧,看半天他的搜索剪枝不够。然后日常水谷,又看了会板子,写了一下基本不会考的后缀数组。12:00的......
  • CSP2024游记
    CSP2024游记现在才写好像有点晚了,不过没有关系(\(Part1\)日记\(Day0\)上午一点也不想做题,看了一上午,但不知道看了什么教练给整了场\(IOI\)赛制模拟赛,但发现T1一眼不会就没打上大巴了,感觉挺高级的(没团体出游过导致的),在大巴上遇见了gzx&Merlin第一次用耳机,挺好,就是听歌......
  • CSP2023邮寄
    前言事实上这篇游记很早以前就应该出现了,但是由于一些原因始终没有把它写出来。已经过去很久了,所以有些地方记忆比较模糊,望见谅!游记部分那时的我,还在一个机构和@chenzhaoxu2027等巨佬学习一些高端的知识。但是老师讲得不太清楚导致我也听不太懂,可能还是太菜了。@chenzhaoxu......
  • CSP 2024 游记
    Day-1回到家光速打准考证,考试前一天才打印(逆天忘了不是第一轮,把文具全拿上了,尺子、圆规、铅笔……查了查考场路线,锐评一波SZ的考场,怎么选在了坪山区,离学校都要一个半小时,地铁只能坐到双龙,虽然有车接驳,但有来无回(发了个朋友圈,睡前调了个6点的闹钟,怕睡过头,然而还是睡过头了......
  • CSP-JS总结(修订版)
    CSP-J/S2024游记初赛CSP-J开头的int确实挺搞心态的,组合排列也放得挺前,不过顺利做出来了做完颓了。结果错挺多的,赛后感觉还是不够细致,下午的比赛要更细心一点小图灵:89.5怎么了呢?连90都上不了了CSP-S看题然后发现一堆不会做有点懵,感觉阅读程序不是很能读得懂然后完......
  • CSP-S 2024 游记
    Day0出发。在车上随便写了几题。到了酒店之后本来想调出来正在写的那道题就睡觉的,结果调到0:10都没调出来/fn,直接睡了。Day1早上起来吃完早餐回房间接着写题。然后睡了\(30\)min,然后吃午饭。然后去考场。然后开考了。开考前还是一如既往的不许动鼠标键盘什么的。没事......