首页 > 其他分享 >「解题报告」2023-10-17 模拟赛

「解题报告」2023-10-17 模拟赛

时间:2023-10-17 10:23:05浏览次数:36  
标签:10 ch 17 int ll write le 2023

1、取石子游戏

(nim.pas/c/cpp)

【题目描述】

小林和亮亮正在玩一个取石子的游戏。

石子一共有 \(n\) 堆,其中第 \(i\) 堆恰好有 \(i\) 粒石子。小林先取,亮亮后取,并且两人依次轮流取石。每一次取石子的人可以选择任意一堆还未被取完的石子,并取走这一堆中任意多粒石子(注意,不能一粒石子也不取,也不能同时在多堆石
子中取石)。最终,无石可取的人为败。

小林和亮亮都十分聪明,他们的每次取石都会采取最优策略。在经过多次游戏后,小林发现了先手必胜的条件,但他不满足于此,他想知道,在知道石子的堆数 \(n\) 后,他第一次取石有多少种方式可以获胜。

【输入格式】

第一行一个整数 \(T\),表示数据组数。

接下来 \(T\) 行每行一个整数 \(n\),表示石子的堆数。

【输出格式】

每组数据输出一个整数,表示在两个人都采用最佳策略的情况下,小林第一次取石能够获胜的方式数,如小林必败,则输出 \(0\)。

【样例输入】

2
2
3

【样例输出】

1
0

【样例解释】

\(n=2\) 时小林只有一种取胜方式,即取在第二堆石子中取一粒。

\(n=3\) 时小林必败,因此输出 \(0\)。

【数据规模】

对于 \(20\%\) 的数据,\(n \le 10\);

对于 \(50\%\) 的数据,\(n \le 1000\);

对于 \(90\%\) 的数据\(n \le 10^{15}\);

对于 \(100\%\) 的数据,\(1 \le n \le 10^{1000}\),\(1 \le T \le 10\)。

\(50\) 分暴力

先判断是否必输,如果必输的话直接输出 \(0\) 即可。

否则,\(n^2\) 枚举第一次在哪个堆里拿走多少个石子,查看剩下的石子异或和是否为 \(0\)。

// The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

template<typename T>
void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

template<typename T>
void print(T x, char c) {
   write(x);
   putchar(c);
}

const int N = 1010;

int T;
ll n;
ll a[N];

void solve() {
    n = read<ll>();
    int cnt = 0;
    ll sum = 0;
    for (ll i = 1; i <= n; ++ i) {
        a[i] = a[i - 1] ^ i;
        sum ^= i;
    }
    if (sum == 0) {
        puts("0");
        return ;
    }
    rep (i, 1, n, 1) {
        rep (j, 1, i, 1) {
            ll k = sum;
            k ^= i;
            k ^= (i - j);
            if (k == 0) {
                ++ cnt;
            }
        }
    }
    print(cnt, '\n');
}

int main() {
    // freopen("nim.in", "r", stdin);
    // freopen("nim.out", "w", stdout);
    T = read<int>();
    while (T --) {
        solve();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

\(90\) 分做法

如果 \(x\) 为偶数时,\(x \operatorname{xor} (x + 1) = 1\),可以发现 \(1 \sim n\) 的异或和 \(S\) 有以下规律:

\[S = \begin{cases} 1, \quad n \bmod 4 = 1\\ n + 1, \quad n \bmod 4 = 2\\ 0, \quad n \bmod 4 = 3\\ n, \quad n \bmod 4 = 0 \end{cases} \]

\(n \bmod 4 = 3\) 时,先手必败,答案为 \(0\)。\(n \bmod 4 = 1\) 时,在任意编号为奇数的石子堆中取 \(1\) 可以使异或和为 \(0\),且只有这些方案,于是答案为 \(\dfrac{(n + 1)}{2}\)。\(n \bmod 4 = 0 或 2\) 时,\(S\) 与 \(n\) 位数相同,设它们的最高位为 \(t\),\(S\) 的第 \(t\) 位为 \(1\),为使 \(S\) 变为 \(0\),必须修改一个第 \(t\) 位为 \(1\) 的数。显然修改任意第 \(t\) 位为 \(1\) 的数都可以使 \(S\) 变为 \(0\)。答案即为 \(n\) 去掉最高位再加 \(1\)。

// The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

template<typename T>
void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

template<typename T>
void print(T x, char c) {
   write(x);
   putchar(c);
}

const int N = 1010;

int T;
ll n;
ll a[N];

void solve1() {
    n = read<ll>();
    int cnt = 0;
    ll sum = 0;
    for (ll i = 1; i <= n; ++ i) {
        a[i] = a[i - 1] ^ i;
        sum ^= i;
    }
    if (sum == 0) {
        puts("0");
        return ;
    }
    rep (i, 1, n, 1) {
        rep (j, 1, i, 1) {
            ll k = sum;
            k ^= i;
            k ^= (i - j);
            if (k == 0) {
                ++ cnt;
            }
        }
    }
    print(cnt, '\n');
}

ll get(ll x) {
    int cnt = 0;
    while (x) {
        x >>= 1;
        ++ cnt;
    }
    return (1ll << (cnt - 1));
}

void solve2() {
    n = read<ll>();
    if (n % 4 == 3) {
        puts("0");
        return ;
    }
    if (n % 4 == 1) {
        print((n + 1) / 2, '\n');
        return ;
    }
    if (n % 4 == 2 || n % 4 == 0) {
        ll g = get(n);
        print(n - g + 1, '\n');
    }
}

int main() {
    // freopen("nim.in", "r", stdin);
    // freopen("nim.out", "w", stdout);
    T = read<int>();
    while (T --) {
        solve2();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

2、魔数

(number.pas/c/cpp)

【题目描述】

小林和亮亮是好朋友。小林有一个幸运数字 \(a\),亮亮有一个幸运数字 \(b\)。一
个数字称之为“幸运数”当且仅当它只由 \(a\) 和 \(b\) 组成。小林称一个数为“魔数”,当且仅当这个数各数位之和为“幸运数”,且这个数字本身也是“幸运数”。

举个例子:小林的幸运数字为 \(2\),亮亮的幸运数字为 \(6\),那么 \(23\) 不是“幸运数”,而 \(26、222\) 是“幸运数”。进一步,\(222\) 是“魔数”(因为 \(2+2+2=6\)),而 \(26\) 不是“魔数”(因为 \(2+6=8\) )。

亮亮想要知道,有多少个 \(n\) 位的“魔数”(一个 \(n\) 位数不包含前导 \(0\)),由于这个数字会很大,所以亮亮只关心这个数模 \(1000000007\)(\(10^9+7\),是一个质数)的结果。

【输入格式】

只有一行,包含三个整数:\(a、b、n\)。意义见题目描述。

【输出格式】

只有一个整数,表示 \(n\) 位的“魔数”的个数模\(1000000007\) 的结果。

【样例输入】

2 6 3

【样例输出】

1

【样例解释】

两个幸运数字分别为 \(2\) 和 \(6\),则位数为 \(3\) 的“魔数”只有 \(222\) 一个。

【数据规模】

对于 \(30\%\) 的数据: \(1 \le n \le 5\);

对于 \(60\%\) 的数据:\(1 \le n \le 100\);

对于 \(100\%\) 的数据:\(1 \le a < b \le 9, 1 \le n \le 10^6\)。

只需枚举这 \(n\) 位数中有多少位是 \(a\),设有 \(i\) 位,则各个位上的数字的和为 \(i \times a + (n - i) \times b\),再进行判断即可,复杂度 \(O(6n)\)。(大概)唯一会的题

// The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

template<typename T>
void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

template<typename T>
void print(T x, char c) {
   write(x);
   putchar(c);
}

const int N = 1e6 + 5;
const int mod = 1e9 + 7;

int a, b, n;
ll sum, ans;
int dig[N];
ll fac[N], inv[N];

ll qpow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) {
            res = res * x % mod;
        }
        y >>= 1;
        x = x * x % mod;
    }
    return res;
}

ll C(ll n, ll m) {
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

bool check(ll res) {
    while (res) {
        if (res % 10 != a && res % 10 != b) return false;
        res /= 10;
    }
    return true;
}

void dfs(int u) {
    if (u > n) {
        if (check(sum)) {
            ++ ans;
            ans %= mod;
        }
        return ;
    }
    dig[u] = a;
    sum += a;
    dfs(u + 1);
    sum -= a;
    dig[u] = b;
    sum += b;
    dfs(u + 1);
    sum -= b;
}

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
    a = read<int>(), b = read<int>(), n = read<int>();
    if (n <= 5) {
        dfs(1);
        print(ans % mod, '\n');
        return 0;
    }
    fac[0] = inv[0] = 1;
    rep (i, 1, n, 1) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[n] = qpow(fac[n], mod - 2);
    per (i, n - 1, 1, 1) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
    ll ans = 0;
    rep (i, 0, n, 1) {
        sum = 1ll * a * i + 1ll * (n - i) * b;
        if (check(sum)) {
            ans = (ans + C(n, i)) % mod;
        }
    }
    print(ans % mod, '\n');
    fclose(stdin);
    fclose(stdout);
    return 0;
}

3、军训站队

(queue.pas/c/cpp)

【题目描述】

小林和亮亮刚入高中,首先就迎来了军训。这一天,他们班的同学正在教官的指导下进行队列练习。

班上总共有 \(n\) 位同学,他们站成一排,然而,本该站成一条直线的他们却排成了“一字长蛇阵”。用数学的语言来描述,如果把训练场看成一个平面直角坐标系,第 \(i\) 名同学所在位置的横坐标是 \(i\),而所有同学的纵坐标本该是 \(0\)(或者任意一个相等的常量),这样就排成了一条直线。当然,由于同学们排的歪歪扭扭,所以第 \(i\) 位同学的横坐标依然是 \(i\),而纵坐标却成了 \(Y_i\) (为了简化问题,我们假设所有的坐标都是整数)。

对此,教官当然十分生气,因此他决定下命令调整队伍,使得所有人能够站
成一条直线(也即让所有的 \(Y_i\) 相同)。教官的命令总共有三种:

  1. 除了某一个同学外,其余所有同学向前走一步(向前走一步可理解为 \(Y_i\) 的
    值加 \(1\),下同);

  2. 除了某一个同学外,其余所有同学向前走两步;

  3. 除了某一个同学外,其余所有同学向前走五步。

教官希望他能以最少的命令次数使得所有同学站成一条直线,但是他不会算,于是就让亮亮帮他来计算。亮亮虽然聪明,可是由于班上同学人数众多,他一下子也解决不了这个问题,只能来寻求会编程的你的帮助,你能告诉亮亮答案吗?

【输入格式】

第一行有一个整数 \(n\),表示班上共有 \(n\) 位同学。

第二行有 \(n\) 个整数,第 \(i\) 个整数 \(Y_i\) 表示第 \(i\) 位同学初始位置的纵坐标。

【输出格式】

一个整数,表示最少的下达命令次数。

【样例输入】

4
1 1 2 6

【样例输出】

2

【样例解释】

一种方案是:\(1\ 1\ 2\ 6 \rightarrow 2\ 2\ 2\ 7 \rightarrow 7\ 7\ 7\ 7\)

【数据规模】

对于 \(40\%\) 的数据,\(n \le 10, Y_i \le 10\);

对于 \(100\%\) 的数据,\(1 \le n \le 100000,0 \le Y_i \le 10^9。\)

除了这个同学,其他人都往前走 \(1\) 步、\(2\) 步、\(5\) 步,用物理上的相对运动,可以将其看作其他人都不动,这个同学往后走 \(1\) 步、\(2\) 步、\(5\) 步,将 \(Y\) 从小到大排序,则他们最后会落在 \(Y_{\min}, Y_{\min} - 1, Y_{\min} - 2, Y_{\min} - 3, Y_{\min} - 4\) 这 \(5\) 个位置上,枚举这 \(5\) 个位置,找到最小的步数,最有方案肯定是先走 \(5\),走不动后再走 \(2\),走不动后再走 \(1\),这样可以使步数最小。

// The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

template<typename T>
void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

template<typename T>
void print(T x, char c) {
   write(x);
   putchar(c);
}

const int N = 1e5 + 5;

int n;
ll ans, minn;
ll y[N], x[N];

int main() {
    // freopen("queue.in", "r", stdin);
    // freopen("queue.out", "w", stdout);
    n = read<int>();
    rep (i, 1, n, 1) {
        y[i] = read<int>();
    }
    sort(y + 1, y + n + 1);
    per (i, n, 1, 1) {
        y[i] -= y[1];
    }
    memcpy(x, y, sizeof x);
    rep (j, 0, 4, 1) {
        ans = 0;
        memcpy(x, y, sizeof y);
        rep (i, 1, n, 1) {
            x[i] += j;
        }
        rep (i, 1, n, 1) {
            if (x[i] >= 5) {
                ans += (1ll * x[i] / 5);
                x[i] %= 5;
            }
            if (x[i] >= 2) {
                ans += (1ll * x[i] / 2);
                x[i] %= 2;
            }
            if (x[i] > 0) {
                ans += (1ll * x[i]);
                x[i] = 0;
            }
        }
        if (j == 0) {
            minn = ans;
        } else {
            minn = min(minn, ans);
        }
    }
    print(minn, '\n');
    return 0;
}

标签:10,ch,17,int,ll,write,le,2023
From: https://www.cnblogs.com/yifan0305/p/17769095.html

相关文章

  • 《流畅的Python》 读书笔记 第三章字典和集合 20231017
    第3章字典和集合dict类型是Python语言的基石模块的命名空间、实例的属性和函数的关键字参数中都可以看到字典的身影跟它有关的内置函数都在__builtins__.__dict__模块中模块的命名空间:我的理解是sys.modules实例的属性:我的理解是实例.__dict__classA:def_......
  • MBR10200CT-ASEMI肖特基MBR10200CT参数、规格、尺寸
    编辑:llMBR10200CT-ASEMI肖特基MBR10200CT参数、规格、尺寸型号:MBR10200CT品牌:ASEMI封装:TO-220恢复时间:>50ns正向电流:10A反向耐压:200V芯片个数:2引脚数量:3类型:肖特基、插件肖特基二极管特性:低耐压、高效率浪涌电流:200A正向压降:1.05V封装尺寸:如图工作温度:-65°C~175°C......
  • 珍惜免费升级Win11机会!微软宣布放弃Windows 10时间:还有2年
    对于微软来说,不升级Windows11的用户,就是最大的阻碍,如果你还坚守Windows10,那么不好意思了。Windows10支持将于2025年10月14日结束,用户正好有两年时间升级硬件并安装Windows11。整整两年后(距今730天),微软将发布Windows10家庭版和专业版的最后一次安全更新。这意味着Windows......
  • 【一句日历】2023年10月
    【2023年10月1日·星期日】国家是大家的,爱国是每个人的本分。                                                 ——陶行知【2023年10月2日·星期一】兰生幽谷,不为莫......
  • 【2023-10-29】连岳摘抄
    23:59中庭地白树栖鸦,冷露无声湿桂花。今夜月明人尽望,不知秋思在谁家。                                                 ——唐·王建《十五夜望月寄杜郎中》孩子多......
  • 10月14日例会总结
    目录例会总结代码以及知识点例会总结代码以及知识点"""类和对象在程序中先有类,再有对象"""#类classlei:#定义一个类需要用class关键字#类属性school='fuyang'#对象的绑定方法def__init__(self,name,age):#初始化方法self.n......
  • KaOS Linux 2023.09 新增 KDE Gear 23.08,将焦点转向 KDE Plasma 6 ISO
    导读这个新的ISO快照还包括了最新的KDEPlasma5.27.8和KDEFrameworks5.110更新。受Arch Linux 启发,面向KDE的独立开发的 KaOSLinux 发行版的开发团队今天 宣布 KaOS2023.09 正式发布,提供了一张全新的、与最新GNU/Linux技术和开源软件一致的安装镜......
  • 日常记录--2023-10月16日--周一
    日程:今天只有上午有课,7点起床,吃了个早饭去上课,早上第一节数据结构,学习了队列,还讲了相关应用。中午午休一个小时,下午起来干了点别的,完善了之前的代码,晚上7-9点听了下代码随想路,学了会javaweb。学了什么:可恶的Javaweb,复习了数据结构。PS:不想学习,想要成为月饼盒;......
  • 20231026
    (1)通过查阅资料,写出一个或多个MapReduce的具体应用,并谈谈自己对MapReduce的认识。(满分10分)(2)词频统计任务编程实践,任务要求:在Linux系统本地创建两个文件,即文件wordfile1.txt和wordfile2.txt,文件wordfile1.txt的内容格式如下,需要将zhangsan换成自己名字的英文全拼:zhangsanlovesSp......
  • 20231016
    早上上了工程实训课,玩了高铁和火车模拟器和沙盘下午Java课,发现布置的作业是我几周前自己试着做过的最近在看代码大全,学到了自定义数据结构的一些妙用,组织顺序结构的代码,条件和循环中常见的错误排查以及避免,好多好多。......