首页 > 其他分享 >1.3 CW 模拟赛 赛时记录

1.3 CW 模拟赛 赛时记录

时间：2025-01-03 11:45:18浏览次数：1  
标签：赛时 1.3 int pos else rm lld CW dis

前言

还是传统手法, 冲冲冲

看题

\(\rm{T1}\)

好吧, 不会高精度, 寄了

\(\rm{T2}\)

博弈

\(\rm{T3}\)

我不到啊

\(\rm{T4}\)

看不懂思密达

首先这套题肯定不是能拿大分的题, 所以今天尽量多分析, 给每个题留足思考时间, 然后多打暴力, 最后拼高分 / 正解

以后也尽量做到看题的时候奠定策略基础

\(\rm{T1}\)

思路

目标是拿到 \(50 \%\) , 后面的都需要高精度, 先不管他

首先你肯定是要观察性质的, 你容易发现, 当两个数的数字分配完成时, 那么数字就随之确定, 一定是从大到小排序

所以 \(50 \%\) 好像直接爆搜就能过?
不过一般不会是这样的, 分析一下复杂度, 你发现总共的分配可能是 \(2^{A + B}\) 级别的
好吧就是爆搜能过

实现

框架

首先枚举每个数分配方式, 判断是否合法之后统计答案

代码

好像时间给的很长

考场上忘了快写怎么打是真的绷不住, 现造了一个

#include <bits/stdc++.h>
// #define test_case
#define int long long
const int MAXVAL = 10;
const int MAXN = 21;

void write(__int128 x) {
    if (x / 10 == 0) { std::cout << (char)('0' + x); return; }
    write(x / 10);
    std::cout << (char)('0' + x - ((x / 10) * 10));
}

int T;
int a, b;
int num[MAXVAL];
int ret[MAXN];

bool cmp(int a, int b) { return a > b; }

__int128 ans = 0;
__int128 calc(int s) {
    std::vector<int> A, B; int pos = 0; A.clear(), B.clear();
    while (s) {
        if (s & 1) A.push_back(ret[pos]); else B.push_back(ret[pos]);
        s >>= 1, pos++;
    }

    std::sort(A.begin(), A.end(), cmp) , std::sort(B.begin(), B.end(), cmp);
    __int128 Anum = 0, Bnum = 0;
    for (int i = 0; i < A.size(); i++) Anum = Anum * 10 + A[i]; for (int i = 0; i < B.size(); i++) Bnum = Bnum * 10 + B[i];
    return Anum * Bnum;
}

signed main()
{
    #ifdef test_case
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    scanf("%lld", &T);
    while (T--) {
        ans = 0;
        scanf("%lld %lld", &a, &b);
        for (int i = 1; i <= 9; i++) scanf("%lld", &num[i]);
        for (int i = 0, j = 1; i < a + b; i++) {
            if (num[j]) ret[i] = j, num[j]--;
            else { j++; ret[i] = j, num[j]--; }
        }

        for (int s = 0; s < (1 << (a + b)); s++) { // 枚举状态 , 1 为分给 a , 2 为分给 b
            if (__builtin_popcount(s) != a) continue;
            ans = std::max(ans, calc(s));
        }
        write(ans); puts("");
    }

    return 0;
}

极限数据 \(780 \ \rm{ms}\) , 应该能过

捣鼓了一下正确性浪费了一点时间, 但是应该没问题了

\(\rm{T2}\)

目前得分 \(50 \ \rm{pts}\)

思路

还是继续拼暴力分, 最后再去搞正解
还是神秘博弈论, 先猜一个贪心(

手模一下, 看下有没有好的性质
考虑确定两个人起手的点之后, 能不能 \(\mathcal{O} (n)\) 的计算出最大答案?
容易发现的是, 两个人选择的范围相当于包含起始点的一段圆弧, 然后拼起来组成一个圆, 其中, 距离起始点更近的点, 更容易被选到, 这个是感性理解

具体怎么写还是考虑动态规划?
一个很好的性质是确定了一方的选点, 另一方的也就随之确定, 所以我们可以把博弈过程看做是确定一个分配方案

你发现确定两个人的起始点, 其实是可以确定 \(\rm{Alice}\) 的选点可能的, 考虑写个代码验证一下
具体的, 就是分成两个弧, \(\rm{Alice}\) 可以选择一个弧的优势(过半), 然后其他的劣势

感觉现在是猜结论, 全靠感性, 我也不知道怎么解释这个问题

那么这样枚举两个起始点, 好像是 \(\mathcal{O} (n^2)\) 的?

具体的

  • 两边都是奇数个 : 可以选择两种方式, 选取一边的超过一半和另外一边的少于一半
  • 两边都是偶数个 : 唯一情况分一半
  • 一奇一偶 : 唯一情况多吃一点

所以这样子打下来, 可以知道 \(\rm{Alice}\) 确定唯一占领时, \(\rm{Bob}\) 怎么选才能最大化自己, 然后就知道答案了

做到 \(\mathcal{O} (n^2)\) 唯一需要的是考虑环上的和怎么快速计算

实现

目前得分 \(95 \ \rm{pts}\) , 剩下全部冲 \(\rm{T2}\)

框架

首先是枚举两个分割点
如何把两边分开 : 断环为链拷两遍
如何计算和 : 前缀和
如何快速计算分一半 : 计算编号之差

我们细致一点方便写代码:
首先读入这个环的时候就将其断开复制两遍
枚举 \(\rm{Alice}\) 的起手点 ( \(\rm{subtask} \ 3\) 直接钦定为 \(1\) ), 对于这个点我们枚举 \(\rm{Bob}\) 的所有起手点, 然后我们可以找到这个起手点的两个位置, 显然的根据上面的分类讨论

  • 两边都是奇数个 : 可以选择两种方式, 选取一边的超过一半和另外一边的少于一半
  • 两边都是偶数个 : 唯一情况分一半
  • 一奇一偶 : 唯一情况多吃一点

还有一个问题 : 如何在链上找到两个起手点
其实很简单, 假设两个起手点 \(u < v\) , 直接找到 \(v\) 第二遍复制的位置即可

然后检查答案即可

注意同 \(\rm{Alice}\) 起手点之间取 \(\min\) , 不同之间取 \(\max\)

代码

#include <bits/stdc++.h>
// #define test_case
#define int long long
const int MAXN = 5e5 + 20;

int n;
int cir[MAXN << 1], dis[MAXN << 1];
bool sub3 = false; // 是否满足 sub3 的性质

signed main()
{
#ifdef test_case
    freopen("ex_game4.in", "r", stdin);
    freopen("myout.out", "w", stdout);
#endif

    scanf("%lld", &n); sub3 = (n > 5000);
    for (int i = 1; i <= n; i++) scanf("%lld", &cir[i]);
    for (int i = 1; i <= n; i++) cir[n + i] = cir[i]; // 断环为链
    for (int i = 1; i <= 2 * n; i++) dis[i] = dis[i - 1] + cir[i];

    if (sub3) {
        int u = 1;
            int res = 0x3f3f3f3f3f3f3f3f; // Alice 起手相同的答案
            for (int v = 1; v <= n; v++) { // Bob 起手点
                if (u == v) continue;

                /*预处理链上的位置*/
                int pos, i, j;
                if (u > v) pos = u, i = v, j = v + n; else pos = n + u, i = v, j = v + n;

                int now = 0; // 当前答案
                if ((pos - i - 1) % 2 && (j - pos - 1) % 2) {
                    int l = i + (pos - i - 1) / 2;
                    int r = pos + (j - pos) / 2;
                    now = std::max(dis[pos] - dis[l] + dis[r - 1] - dis[pos], dis[r] - dis[pos] + dis[pos] - dis[l + 1]);
                } else if ((pos - i - 1) % 2 == 0 && (j - pos - 1) % 2 == 0) {
                    int l = i + (pos - i - 1) / 2;
                    int r = pos + (j - pos - 1) / 2;
                    now = dis[pos] - dis[l] + dis[r] - dis[pos];
                } else {
                    int l, r;
                    if ((pos - i - 1) % 2) l = i + (pos - i - 1) / 2, r = pos + (j - pos - 1) / 2;
                    else r = pos + (j - pos) / 2, l = i + (pos - i - 1) / 2;
                    now = dis[pos] - dis[l] + dis[r] - dis[pos];
                }
                res = std::min(res, now);
            }
        printf("%lld", res);
    } else {
        int ans = 0;
        for (int u = 1; u <= n; u++) { // Alice 起手点
            int res = 0x3f3f3f3f3f3f3f3f; // Alice 起手相同的答案
            for (int v = 1; v <= n; v++) { // Bob 起手点
                if (u == v) continue;

                /*预处理链上的位置*/
                int pos, i, j;
                if (u > v) pos = u, i = v, j = v + n; else pos = n + u, i = v, j = v + n;

                int now = 0; // 当前答案
                if ((pos - i - 1) % 2 && (j - pos - 1) % 2) {
                    int l = i + (pos - i - 1) / 2;
                    int r = pos + (j - pos) / 2;
                    now = std::max(dis[pos] - dis[l] + dis[r - 1] - dis[pos], dis[r] - dis[pos] + dis[pos] - dis[l + 1]);
                } else if ((pos - i - 1) % 2 == 0 && (j - pos - 1) % 2 == 0) {
                    int l = i + (pos - i - 1) / 2;
                    int r = pos + (j - pos - 1) / 2;
                    now = dis[pos] - dis[l] + dis[r] - dis[pos];
                } else {
                    int l, r;
                    if ((pos - i - 1) % 2) l = i + (pos - i - 1) / 2, r = pos + (j - pos - 1) / 2;
                    else r = pos + (j - pos) / 2, l = i + (pos - i - 1) / 2;
                    now = dis[pos] - dis[l] + dis[r] - dis[pos];
                }
                res = std::min(res, now);
            }
            ans = std::max(ans, res);
        }
        printf("%lld", ans);
    }

    return 0;
}

\(\rm{T3}\)

从这里开始都是纯暴力, 给 \(\rm{T2}\) 留 \(1 \ \rm{h}\) 左右打的时间, 主要问题是 \(\rm{T2}\) 思路是否正确, 看起来很对啊

\(\rm{T2}\) 优化的时间应该是没有了, 但是拿 \(60 \ \rm{pts}\) 是可观的

思路

打个 \(20 \ \rm{pts}\) , 直接跑路

框架

首先读入
然后暴力

代码

#include <bits/stdc++.h>
#define int long long
const int MAXN = 120;

int n, m, k;
bool mp[MAXN][MAXN];
int cnt = 0;

struct posters { int w, h; } posts[2];

signed main()
{
    scanf("%lld %lld %lld", &n, &m, &k);
    if (k == 1) {
        scanf("%lld %lld", &posts[1].w, &posts[1].h);
        printf("%lld", posts[1].w * posts[1].h);
    } else if (k == 2) {
        scanf("%lld %lld", &posts[1].w, &posts[2].w); scanf("%lld %lld", &posts[1].h, &posts[2].h);
        for (int i = 1; i <= posts[1].w; i++) for (int j = 1; j <= posts[1].h; j++) mp[i][j] = true;
        for (int i = n - posts[2].w + 1; i <= n; i++) for (int j = m - posts[2].h + 1; j <= m; j++) mp[i][j] = true;
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (mp[i][j]) cnt++;

        printf("%lld", cnt);
    } else {
        printf("520641");
    }

    return 0;
}

\(\rm{T4}\)

还是纯暴力

目前得分 \(70 \ \rm{pts}\)

思路

你注意到 \(\mathcal{O} (nq)\) 很好做啊, 拼上一个 \(m = 1\) 不是无敌了

考虑 \(m = 1\) 怎么做, \(\mathcal{O} (nq)\) 是模拟算法
我们标记当前的前后缀分割点, 然后每次旋转相当于把分割点往后调了一位

于是处理就简单了

实现

框架

对于 \(\mathcal{O} (nq)\) 是模拟算法
对于 \(m = 1\) 按照上面的做就可以了

\(20 \ \rm{min}\) 极速通关

哦哦, 看反了, \(m = 1\) 的操作是把最后一个丢到前面去, 但是代码也是同理的

代码

#include <bits/stdc++.h>
#define int long long
const int MAXN = 1.5e5 + 20;

int n, m, q;
struct node { int c, a; } ret[MAXN];

/*暴力模拟*/
class subtask1
{
private:
    std::vector<int> pos;

public:
    void solve() {
        while (q--) {
            int op; scanf("%lld", &op);
            if (op == 1) {
                int l, r; scanf("%lld %lld", &l, &r);
                int ans = 0;
                for (int i = l; i <= r; i++) ans += ret[i].a;
                printf("%lld\n", ans);
            } else {
                int x; scanf("%lld", &x);
                pos.clear();
                for (int i = 1; i <= n; i++) if (ret[i].c == x) pos.push_back(i);
                for (int i = pos.size() - 1; i > 0; i--) std::swap(ret[pos[i]], ret[pos[i - 1]]);
            }
        }
    }
} sub1;

class subtask2
{
private:
    int pre[MAXN], suf[MAXN];
    /*预处理前后缀和*/
    void init() {
        pre[0] = suf[0] = 0;
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + ret[i].a;
        for (int i = n; i >= 1; i--) suf[n - i + 1] = suf[n - i] + ret[i].a;
    }

public:
    void solve() {
        init();
        int x = 1; // 分割点位置
        while (q--) {
            int op; scanf("%lld", &op);
            if (op == 1) {
                int l, r; scanf("%lld %lld", &l, &r);
                int ans = 0;
                if (r < x) ans = suf[x - l] - suf[x - r - 1];
                else if (l < x && r >= x) ans = suf[x - l] + pre[r - x + 1];
                else ans = pre[r - x + 1] - pre[l - x];
                printf("%lld\n", ans);
            } else {
                int bin; scanf("%lld", &bin);
                x++;
                x = x > n ? 1 : x;
            }
        }
    }
} sub2;

signed main()
{
    scanf("%lld %lld %lld", &n, &m, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &ret[i].c); for (int i = 1; i <= n; i++) scanf("%lld", &ret[i].a);

    if (n <= 1000 && q <= 1000) sub1.solve();
    else if (m == 1) sub2.solve();

    return 0;
}

先这样, 去做 \(\rm{T2}\)

总结

以后的策略都这样了, 加油

我有绝对不能输的理由!

标签：赛时,1.3,int,pos,else,rm,lld,CW,dis
From： https://www.cnblogs.com/YzaCsp/p/18649797

相关文章

  • SNH Titan 1.3 for Windows - 社交网络自动化数据收集和分析
    SNHTitan1.3forWindows-社交网络自动化数据收集和分析SocialNetworkHarvester请访问原文链接：https://sysin.org/blog/snh-titan/查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgSNHTitan-SocialNetworkHarvester为调查人员和分析人员提供来自社交网......
  • 星球助手发布更新v1.3.0
    星球助手发布更新v1.3.0，重要的更新内容有"导出"模块可以按照天或者月进行合并导出到一个文件."搜索"模块的搜索输入框旁边展示搜出的帖子数量.添加文档，请阅读官网的”星球助手/常见问题“页面如何备份数据如何判断某个星球的帖子下载完全如何按日期下载星球的帖子下载的......
  • Royal Elementor Addons Pro v1.3.987 + v1.5.0 elementor网页设计元素组件插件下载
    RoyalElementorAddonsProelementor网页设计元素组件插件破解版简介&下载RoyalElementorAddonsProNulledElementor小部件、模板套件和扩展。从零到英雄构建网站所需的唯一Elementor插件！动态网站生成器建立任何类型的网站：使用Elementor动态标签创建自定义帖子类型创......
  • 鸿蒙1.3：资源文件的使用
    一、资源文件介绍应用开发中使用的各类自定义资源文件统一存放于应用的resources目录下resources目录①base目录与限定词目录②rawfile目录基础目录结构resources|—base//默认存在的目录||—element|||—string.json||—media|||—icon.png|—en_GB-ve......
  • AcWing 791：高精度加法 ← string+数组
    【题目来源】https://www.luogu.com.cn/problem/P1601https://www.acwing.com/problem/content/793/【题目描述】高精度加法，相当于a+bproblem，不用考虑负数。输入不含前导0。【输入格式】分两行输入。a,b≤10^500。【输出格式】输出只有一行，代表a+b的值。【输入样例】1......
  • 11.30
    importpandasaspdimportnumpyasnpfromsklearn.model_selectionimporttrain_test_splitfromsklearn.ensembleimportRandomForestClassifierfromsklearn.metricsimportaccuracy_score,precision_score,recall_score,f1_score,classification_reportfromskle......
  • 12.28 CW 模拟赛 赛时记录
    前言还是只管考试的策略,别想其他的每个题控制用时,根据时间选择策略,冷静看题完蛋了是\(\rm{NOIP}\),我们没救了\(\rm{T1}\)怎么办,像是很典的题但是我多半做不出来别人做过容斥的肯定会,但是我就不一样了\(\rm{T2}\)好像也不会做\(\rm{T3}\)基环树上的\(\rm......
  • Kubernetes快速部署(v1.31.4)
    文章目录1、初始化2、安装kubeadm3、单节点初始化4、集群网络环境搭建5、安装和配置calicoctl6、集群工作节点添加7、补充1、初始化将系统升级到最新，可以使用阿里源镜像站，本教程使用CentOS7系统(考虑大量用户使用的版本)yum-yupdate关闭selinux和防火墙system......
  • 梦中代码审计赚取1.3W赏金之旅
    公众号:白日梦安全免责声明 本文仅供学习与参考，严禁使用本文中提供的技术信息或代码工具进行任何非法测试或违法行为。若使用者因此造成任何直接或间接损失，后果由使用者自行承担。本文内容仅限学习用途，任何不良后果与文章作者无关。使用者应遵守相关法律法规，尊重他人合法权......
  • 11.30
    详细讲述了在实际编码过程中的各种要点和最佳实践，对我们日常的编程活动有着直接的指导意义。“靠巧合编程”是我们要避免的。很多时候，我们可能会因为某些巧合让程序暂时运行起来，但这种代码往往是脆弱的。比如，在没有完全理解算法原理的情况下，通过一些试错和猜测编写代码，可能在某些......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99