思维题 9 道 题面

A 数字天平

题目描述

有 $n$ 个数字。他可以选择一个参数 $k$，当 $k$ 的值选择以后，就不能更改了。然后，可以执行无限次操作，每次从 $n$ 个数字中选择位置不同的 $k$ 个数字，并使这 $k$ 个数字减去 $1$。他想使所有的数字都相等。现在他想知道，他可以选择的最大的 $k$ 值是多少。

输入格式

第一行一个整数 $n$，表示数字个数。第二行 $n$ 个整数，表示这 $n$ 个数字。

输出格式

输出一行一个整数，表示符合条件的最大 $k$ 值。

B 简单题

题目描述

有一个整数 $S$，现在他想知道，是否存在一组整数 $a,b,c$ 满足 $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{1}{S}$。如果存在，请给出一组任意解。

输入格式

一个整数 $S$。

输出格式

如果有解，输出一行三个整数 $a,b,c$，表示一组合法的解。要求 $a\le b\le c$。

C 纸牌游戏

题目描述

A 和 B 正在玩一种纸牌游戏。游戏有 $2N$ 张牌，牌上的数字是 1 到 $2N$。他们把牌分成了两份，A 有 $N$ 张，B 有另外 $N$ 张。接下来他们进行 $N$ 轮出牌，每次各出一张牌。一开始，谁出的牌上的数字大，谁就获得这一轮的胜利。A 有一个特殊权利，他可以在任意一个时刻把原本数字大的获胜的规则改成数字小的获胜，这个改变将会一直持续到游戏结束。特别的，A 可以从第一轮开始就使用小牌获胜的规则，也可以直到最后一轮都还使用大牌获胜的规则。现在，A 已经知道了 B 的出牌顺序，他想知道他最多能赢多少轮。

输入格式

第一行一个正整数 $N$，表示卡牌游戏的总回合数。接下来 $2N$ 行，每行一个整数，表示 B 依次出的牌。

输出格式

输出一行一个正整数，表示 A 能赢的最多轮次。

D 巡视王国

题目描述

一个国有 $n$ 座城市，按照 1 到 $n$ 编号，城市之间用 $m$ 条双向道路相连。保证任意两座城市都能通过若干条道路相互到达，即认为这 $n$ 座城市形成了有 $n$ 个点的简单无向图。国的国防部长会对全国进行巡视。他的巡视方式非常特殊：对于 $n$ 个点形成的简单无向图，他会每次挑选两个具有相同度数的点进行巡视，然后删掉这两个点及其所有的连边，直到巡视完所有的城市或者无法进行下一轮巡视为止。现在他想知道，是否存在方法能够使自己完成巡视。

输入格式

第一行输入两个整数 $n,m$，表示城市的个数与道路的条数。接下来 $m$ 行，每行两个整数 $u,v$，表示 $u$ 与 $v$ 之间存在一条双向道路。保证图连通，无重边和自环。

输出格式

如果存在方法使得他能完成巡视，则输出 "YES"，否则输出 "NO"。

E 数学考试

题目描述

小明被一道数学题目难住了，你能帮他解决吗？对于 $1-n$ 的排列，有 $m$ 个限制条件，第 $i$ 个限制条件 $a_i$ 表示前 $a_i$ 个数不能是 $1,2,\dots ,a_i$ 的一个排列，求符合要求的排列的个数。答案对 $998244353$ 取模。

输入格式

第一行两个正整数 $n,m$。第二行 $m$ 个正整数 $a_1,a_2,\dots ,a_m$。

输出格式

一个整数，表示符合要求的排列个数对 $10^9+7$ 取模的结果。

F 区间

题目描述

给定一个长度为 $n$ 的数列 $a_1,a_2,\dots ,a_n$，现在你需要支持以下两个操作：

1. $1lr$ 表示给下标从 $l$ 到 $r$ 的每个数 $a_i$ 开平方（下取整）。
2. $2lr$ 表示询问下标从 $l$ 到 $r$ 的数的和。

输入格式

第一行一个整数 $n$，表示数列长度。第二行 $n$ 个整数，表示初始数列中的数字。第三行一个整数 $q$，表示操作的次数。接下来 $q$ 行，每行为 $1lr$ 或 $2lr$，分别表示两种操作。

输出格式

对于每个 $2lr$ 的操作，输出一行，包含一个整数，表示答案。

G 图计算

题目描述

有一个 $n$ 个点 $m$ 条边的无向图，在这个图上小明能很轻易地计算有多少个点对相互联通。有一天，小明将这张图复制了 $k$ 次，也就是说总共有 $k$ 张图，每张图初始都和原来的图相同。为了难倒小明，敌人偷偷往这些图里加了 $q$ 条边。每次加边操作会给定三个整数 $x,u,v$ 表示在第 $x$ 张图的 $u$ 和 $v$ 之间加一条无向边。每次操作后小明会问有多少个无序点对 $(a,b)$ 满足在所有 $k$ 张图上都连通。小明被难倒了。你能帮帮他吗？

输入格式

第一行四个整数 $n,m,k,q$，表示图的点数、边数、图被复制的次数和加边的次数。接下来 $m$ 行，每行两个整数 $u,v$ 表示原始图中有一条无向边连接 $u$ 和 $v$。接下来 $q$ 行，每行三个整数 $x,u,v$ 表示在第 $x$ 张图的 $u$ 和 $v$ 之间加一条无向边。

输出格式

输出 $q$ 行，每行一个整数，表示加入这条无向边后有多少个无序点对 $(a,b)$ 满足 $a$ 和 $b$ 在所有 $k$ 张图上都连通。

H 纸盒糖果

题目描述

小明准备了 $n$ 个箱子横排成一列，第 $i$ 个箱子里装着 $a_i$ 个糖果。为了让糖果数尽可能公平，小明可以多次执行以下操作： 选择一个里面不少于 $x$ 个糖果的箱子，从这个箱子里取出一个糖果。他的目标是：任何两个相邻的箱子之和都不多于 $x$ 个糖果。请确定实现他的目标所需的最小操作次数。

输入格式

第一行两个整数 $n$ 和 $x$。第二行 $n$ 个整数 $a_1,a_2,\dots ,a_n$。

输出格式

输出一行一个整数，表示达到目标所需的最小操作次数。

I 幸运数

题目描述

对于给定的正整数 $a$，数位包含 1~9 全部数字，且至少两个数位是 $d(1\le d\le 9)$ 的数被称为幸运数。现在给定一个正整数 $n$，请找到正整数 $k(1\le k\le 2\times 10^{10})$ 使得 $n\times k$ 是幸运数。

输入格式

一行两个正整数 $n$ 和 $d$。

输出格式

输出一个正整数，表示正整数 $k(1\le k\le 2\times 10^{10})$。