首页 > 编程语言 >2022年中国大学生程序设计竞赛女生专场 ACEGHIL

2022年中国大学生程序设计竞赛女生专场 ACEGHIL

时间：2023-09-18 22:22:05浏览次数：37  
标签：ACEGHIL 专场 int void cin t1 ++ 2022 ll

2022年中国大学生程序设计竞赛女生专场

目录

概况

因为女生赛，要给女队找找题，我又试了下2022女生赛，题目很多小细节需要注意，不然会wa很多发，前 \(3\) 题都要注意下小细节。I 的写法假了，但好在扣了常数扣过去了
image

A - 减肥计划

  1. 若 \(k \leq n\)，模拟即可
  2. 输出第 \(n + 1\) 轮后的队首

我忘记开 1e6 的数组了，而 TLE 两发

const int N = 1e6 + 10;
 
int n, k, a[N];
void solve()
{       
    cin>>n>>k;
 
    deque<pair<int, int>> q;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        q.push_back({i, a[i]});
    }
    int who = 1, win = 0;
    while(win <= 2000000)
    {
        auto t1 = q.front(); q.pop_front();
        auto t2 = q.front(); q.pop_front();
        if(t1.second >= t2.second)
        {
            who = t1.first;
            win++;
            q.push_front(t1);
            q.push_back(t2);
        }
        else
        {   
            win = 0;
            who = t2.first;
            win++;
            q.push_front(t2);
            q.push_back(t1);
        }   
        if(win >= k)
        {
            cout<<who<<'\n';
            return;
        }
    }
    cout<<q.front().first<<'\n';
    return;
}

C - 测量学

注意题目可以顺时针或逆时针走，注意这个，我忽略而 WA 了两发

其他就是高中数学，唯一的难点就是将弧度转化成角度

double pi = acos(-1);
int n;
double R, a;
void solve()
{       
    // cin>>n>>r>>a;
    scanf("%d%lf%lf", &n, &R, &a);
    double c = a * 180.0 / pi / 360.0;
    a = 2 * pi - a;
    double c1 = a * 180.0 / pi / 360.0;
    double res = 2.0 * R * pi * c;
    res = min(2.0 * R * pi * c1, res);
 
    for(int i = 1; i <= n; i++)
    {
        double r;  scanf("%lf", &r);
        double ans = 2.0 * (R - r) + 2.0 * r * pi * c;
        res = min(ans, res);
        ans = 2.0 * (R - r) + 2.0 * r * pi * c1;
        res = min(ans, res);
    }
 
    printf("%.9lf\n", res);
 
    return;
}

E - 睡觉

  1. 如果听完一整首歌的疲惫值是下降的，在无限长的时间内，答案是YES
  2. 一首歌内可以入睡，答案是YES
  3. 入睡的时刻可能出现两首歌之间，或多首歌，看3首歌的清醒度\(\leq k\) 的最长时间是否大于 $ > 2 n$，我们开倍长数组，模拟判断即可
  4. NO

第一次交没有判断2的情况

const int N = 1e6 + 10;
 
int x, t, k, n, d, a[N];
void solve()
{       
    int s = 0;
    cin>>x>>t>>k>>n>>d;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        a[i + n] = a[i];
        a[i + 2 * n] = a[i];
        a[i + 3 * n] = a[i];
        a[i + 4 * n] = a[i];
        a[i + 5 * n] = a[i];
        a[i + 6 * n] = a[i];
        a[i + 7 * n] = a[i];
        a[i + 8 * n] = a[i];
        a[i + 9 * n] = a[i];
 
        if(a[i] <= d)
            s++;
        else s--;
    }
    if(s >= 1)
    {
        cout<<"YES\n";
        return;
    }
    s = x;
    int last = 0;
    for(int i = 1; i <= 10 * n; i++)
    {
        if(a[i] <= d)
            s--;
        else s++;
        if(s <= k)
            last++;
        else last = 0;
        if(last >= t)
        {
            cout<<"YES\n";
            return;
        }
    }
    if(last >= 3 * n)
    {
        cout<<"YES\n";
        return;
    }
    else
        cout<<"NO\n";
 
    return;
}

G - 排队打卡

直接模拟这个过程即可

ll t, m;
ll n, k;
pair<ll, ll> a[N];
void solve()
{       
    cin>>t>>m;
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
        cin>>a[i].first>>a[i].second;
    n++;
    a[n] = {t, 0};
    sort(a + 1, a + 1 + n);
 
    ll people = 0, s = 0;
    ll r1 = 2e18, r2 = 2e18;
    for(int i = 1; i <= n; i++)
    {
        ll gap = a[i].first - s - 1;
        s = a[i].first;
        people = people - gap * k;;
        people = max(people, 0ll);
        people = people + a[i].second;
        if(a[i].second == 0 && people != m)
        {
            cout<<"Wrong Record\n";
            return;
        }
        if(a[i].second != 0 && a[i].first >= t)
        {
            ll t = (people + 1) / k + ((people + 1) % k != 0);
            if(t <= r2)
                r1 = a[i].first, r2 = t;
        }
        people = max(people - k, 0ll);
    }
    cout<<r1<<" "<<r2<<'\n';
    return;
}

H - 提瓦特之旅

当时一看用 \(k\) 条边到 \(t\) 号结点，这不是bellman-ford吗？直接往这方面想，发现复杂度是 \(O(NM)\) 是可以预处理出来的，查询的时候预处理\(w_1, w_2, \dots,w_{n-1}\)的前缀和，那么查询的时间复杂度是 \(O(QN)\)

const int N = 5e2 + 10;
const int M = 2e5 + 10;
 
 
ll f[N][N], g[N][N], cnt;
ll n, m, k, dist[N], backup[N];
struct EDGES
{
    ll a, b, w;
}edge[M];
void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    memset(f, 0x3f, sizeof f);
    dist[1] = 0;
    for(int i = 1; i < n; i++)
    {
        memcpy(backup, dist, sizeof dist);
        // cout<<backup[0]<<'\n';
        for(int j = 0; j < 2 * m; j++)
        {
            auto e = edge[j];
            if(backup[e.a] <= 1e10)
                dist[e.b] = min(dist[e.b], backup[e.a] + e.w);
        }
        for(int j = 1; j <= n; j++)
            f[i][j] = min(dist[j], f[i - 1][j]);
        // for(int j = 1; j <= n; j++)
        //     cout<<"round : "<<i<<"  v : "<<j<<"  "<<f[i][j]<<'\n';
 
    }
}
void solve()
{       
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        ll u, v, w;
        cin >> u >> v >> w;
        edge[cnt++] = {u, v, w};
        edge[cnt++] = {v, u, w};
    }
    bellman_ford();
    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 1; j <= n; j++)
    //         cout<<f[i][j]<<" ";
    //     cout<<'\n';
    // }
    int q;  cin>>q;
    for(int i = 1; i <= q; i++)
    {
        int t;  cin>>t;
        vector<ll> s(n + 1);
 
        for(int i = 1; i <= n - 1; i++)
        {
            cin>>s[i];
            s[i] += s[i - 1];
        }
        ll res = 1e18;
        for(int i = 1; i <= n - 1; i++)
            if(f[i][t] != 0)
                res = min(f[i][t] + s[i], res);
        cout<<res<<'\n';
    }
    return;
}

I - 宠物对战

很神奇，是一个简单dp，最开始TLE，怎么也过不去，扣了下常数就过了

\(f_{i,0/1}\) 代表第 \(i\) 位字符，最后一个字符串属于A类或B类

我的做法时间复杂度 \(O(\sum|a_i| + \sum|b_i| + N|S| + M|S|)\)

但看别人代码发现，存一下预处理的哈希值，每次转移看有没有哈希值等于\(S_{l, \dots, r}\) 的哈希值就可以了

这样是 \(O(\sum|a_i| + \sum|b_i| + |S|^2\log N)\)

\[f_{i,0} = \min f_{i - |a_i|} + 1 \\ f_{i,1} = \min f_{i - |b_i|} + 1 \]

const int N = 1e5 + 10;
 
 
typedef pair<long long, long long> pll;
struct DoubleStringHash
{
    vector<long long> h1, h2, w1, w2;
    long long base1 = 131, base2 = 13331;
    long long p1 = 1e9 + 7, p2 = 1e9 + 9;
    void init(string s) {
        int len = s.size();
        s = " " + s;
        h1.resize(len + 1), w1.resize(len + 1);
        h2.resize(len + 1), w2.resize(len + 1);
        h1[0] = 0, w1[0] = 1;
        h2[0] = 0, w2[0] = 1;
        for(int i = 1; i <= len; i++) {
            h1[i] = (h1[i - 1] * base1 + s[i]) % p1, w1[i] = w1[i - 1] * base1 % p1;
            h2[i] = (h2[i - 1] * base2 + s[i]) % p2, w2[i] = w2[i - 1] * base2 % p2;
        }
    }
    inline pll get(int l, int r) {
        return {(h1[r] - h1[l - 1] * w1[r - l + 1] % p1 + p1) % p1, (h2[r] - h2[l - 1] * w2[r - l + 1] % p2 + p2) % p2};
    }
}ha[N], hb[N], hs;
int n, m, f[N][2], len1[N], len2[N];
string s[N], ss[N];
pll sa[N], sb[N];
bool cmp(string a, string b)
{
    return a.size() < b.size();
}
void solve()
{       
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>s[i];
    cin>>m;
    for(int i = 1; i <= m; i++)
        cin>>ss[i];
    sort(s + 1, s + 1 + n, cmp);
    sort(ss + 1, ss + 1 + m, cmp);
 
    for(int i = 1; i <= n; i++)
    {
        len1[i] = s[i].size();
        ha[i].init(s[i]);
        sa[i] = ha[i].get(1, len1[i]);
    }
    for(int i = 1; i <= m; i++)
    {
        len2[i] = ss[i].size();
        hb[i].init(ss[i]);
        sb[i] = hb[i].get(1, len2[i]);
    }    
    memset(f, 0x3f, sizeof f);
    f[0][0] = f[0][1] = 0;
    string op; cin>>op; int len = op.size();
    hs.init(op);
    for(int i = 1; i <= len; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i - len1[j] < 0) 
                break;
            if(f[i - len1[j]][0] + 1 >= f[i][1]) continue;
            auto t1 = hs.get(i - len1[j] + 1, i);
            if(sa[j].first == t1.first && sa[j].second == t1.second)
                f[i][1] = min(f[i - len1[j]][0] + 1, f[i][1]);
        }
        for(int j = 1; j <= m; j++)
        {
            if(i - len2[j] < 0) 
                break;
            if(f[i - len2[j]][1] + 1 >= f[i][0]) continue;
            auto t1 = hs.get(i - len2[j] + 1, i);
            if(sb[j].first == t1.first && sb[j].second == t1.second)
                f[i][0] = min(f[i - len2[j]][1] + 1, f[i][0]);
        }
    }
    if(f[len][0]  > 5000 && f[len][1] > 5000)
        cout<<-1<<'\n';
    else    
        cout<<min(f[len][0], f[len][1])<<'\n';
    return;
}

L - 彩色的树

很典的树上启发式合并，改一改add，query，del函数就没了

const int N = 1e5 + 10;
int n, k;
vector<int> e[N];
int l[N], r[N], id[N], sz[N], hs[N], dep[N], tot;
int col[N], c[N], now;
vector<int> del_c[N * 2];
 
int res[N];
 
inline void add(int u)
{
    if(c[col[u]] == 0)  now++;
    c[col[u]]++;
    del_c[dep[u]].push_back(col[u]);
}
 
inline void del(int depth)
{
    for(auto it : del_c[depth])
    {
        c[it]--;
        if(c[it] == 0)  now--;
    }
    del_c[depth].clear();
}
 
inline void query(int u)
{
    res[u] = now;
}
 
void dfs_init(int u,int f) {
    dep[u] = dep[f] + 1;
    l[u] = ++tot;
    id[tot] = u;
    sz[u] = 1;
    hs[u] = -1;
    for (auto v : e[u]) {
        if (v == f) continue;
        dfs_init(v, u);
        sz[u] += sz[v];
        if (hs[u] == -1 || sz[v] > sz[hs[u]])
            hs[u] = v;
    }
    r[u] = tot;
}
 
void dfs_solve(int u, int f, bool keep) {
    // cout<<u<<" "<<f<<" "<<keep<<'\n';
    for (auto v : e[u]) {
        if (v != f && v != hs[u]) {
            dfs_solve(v, u, false);
        }
    }
    if (hs[u] != -1) {
        dfs_solve(hs[u], u, true);
    }
 
    for (auto v : e[u]) {
        if (v != f && v != hs[u]) {
            // for (int x = l[v]; x <= r[v]; x++)
            //     query(id[x]);
            for (int x = l[v]; x <= r[v]; x++)
                if(dep[u] + k >= dep[id[x]])
                    add(id[x]);
        }
    }
    add(u);
    del(dep[u] + k + 1);
    query(u); 
    if (!keep) {
        for(int x = l[u]; x <= r[u]; x++)
                del(dep[id[x]]);
    }
}
 
void solve()
{       
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
        cin>>col[i];
    for (int i = 1; i < n; i++) {
        int u, v;   cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs_init(1, 0);
    dfs_solve(1, 0, false);
 
    int q;  cin>>q;
    for(int i = 1; i <= q; i++)
    {
        int u;  cin>>u;
        cout<<res[u]<<'\n';
    }
}

标签：ACEGHIL,专场,int,void,cin,t1,++,2022,ll
From： https://www.cnblogs.com/magicat/p/17713269.html

相关文章

  • [HUBUCTF 2022 新生赛]ezPython
    附件链接：https://wwvc.lanzouj.com/iIqq218z5x0d给了一个pyc文件利用命令将pyc转换为py文件uncompyle6ezPython.pyc>ezPython.py打开py文件#uncompyle6version3.9.0#Pythonbytecodeversionbase3.7.0(3394)#Decompiledfrom:Python3.8.2(tags/v3.8.2:7b3ab......
  • 2022年07月 python界面可视化 VS2022配置PyQt5环境
    文章目录 一、VS2022配置PyQt5环境1.安装anaconda及opencv-python1.1安装对应的anaconda包1.2安装opencv-python2.安装PyQt53.安装PyQt常用工具4.配置系统环境变量5.配置VS2022中的外部工具6.第一个VS2022下的pyqt5程序一、VS2022配置PyQt5环境本机环境：......
  • [Writeup]2022 NewstarCTF_Week5(Web部分)
    一只网络安全菜鸟--(˙<>˙)/--写博客主要是想记录一下自己的学习过程，过两年毕业了也能回头看看自己都学了些啥东西。由于本人水平有限内容难免有错误、疏漏、逻辑不清、让人看不懂等各种问题，恳请大家批评指正如果我写的东西能对你有一点点帮助，那真是再好不过了。2023Newsta......
  • M1版本MacBook使用PD配置kali2022.1虚拟机
    经过了两天的努力终于成功了，在这里把过程记录一下。主机：M1芯片MACBOOK_PRO14寸软件：paralleldesktop18.1.1镜像：kali-linux-2022.1-installer-arm64前前后后安装了好几个版本，2021.4、2022.1、2022.2、2022.4、2023.1、2023.3，都是在安装pdtools的时候卡住，然后解决不了问题从......
  • Sketchup 2015、2016、2017、2018、2019、2020、2021、2022、2023（草图大师）下载
    SketchUp是一套直接面向设计方案创作过程的设计工具，其创作过程不仅能够充分表达设计师的思想而且完全满足与客户即时交流的需要，它使得设计师可以直接在电脑上进行十分直观的构思，是三维建筑设计方案创作的优秀工具。草图大师也就是SketchUp，是一个建筑景观专业的3D建模软件，由于运行......
  • 草图大师下载-草图大师2022官网版 各个版本下载
    sketchup草图大师是一款应用于建筑领域的全新三维建模软件。sketchup草图大师的功能是非常强大的，成为全球千万设计师选择的设计工具，模型很多质量很好。sketchup草图大师是必不可少的一款建模软件，有需要的朋友们不妨下载试试看。软件地址：看置顶贴sketchup草图大师安装步骤：1、在本站......
  • origin软件下载 origin2022最新中文版下载 各个版本下载
    Origin制图功能增强数据和管理导入功能大为增强;对原有的图形类型进行了重整，使之更加合理;数据处理方面，参数设置的功能大大增强，在各个方面可以细调;数据分析和处理：回归，拟合，统计，图象处理，信号处理，光谱处理等功能都比以前强大;软件地址：看置顶贴Origin8.0软件特色1.为了获得更高效的数......
  • ACL2022 paper1 CAKE: A Scalable Commonsense-Aware Framework for Multi-View Knowl
    CAKE:用于多视域知识图谱补全的可扩展常识感知框架ACL2022Abstract  知识图谱存储大规模事实三元组，然而不可避免的是图谱仍然具有不完整性。（问题）以往的只是图谱补全模型仅仅依赖于事实域数据进行实体之间缺失关系的预测，忽略了宝贵的常识知识。以往的知识图嵌入技术存在无效负......
  • 【专题】2022年中国跨境电商行业研究报告PDF合集分享（附原数据表）
    报告链接：http://tecdat.cn/?p=32044近年来，我国的跨境电子商务发展迅速，在过去五年中，其贸易额增长率达到了16.2%，已经成为稳定对外贸易的一支重要力量。阅读原文，获取专题报告合集全文，解锁文末52份跨境电商行业相关报告。一方面，随着跨境电子商务的发展，跨境电子商务的监管政策得到了......
  • 2021年中国大学生程序设计竞赛女生专场 AKDGIBC
    2021年中国大学生程序设计竞赛女生专场目录2021年中国大学生程序设计竞赛女生专场概况C-连锁商店B-攻防演练I-驾驶卡丁车G-3G网络D-修建道路K-音乐游戏A-公交线路概况前五题去年的这个时候VP的，今年学校要去打女生赛，我先帮她们看看C-连锁商店一眼状压，但发现......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99