重庆市赛

summary: 第十一届重庆市大学生程序设计竟赛西南大学, 2023 年 12 月 17 日

A Yesterday Once More

2 seconds

256 megabytes

历经四年, 终于再次迎来重庆市大学生程序设计竟赛。在第十届重庆市大学生程序设计竟赛中, 狂小 P 想解锁快乐 C 的 iPhone, 但是他只知道解锁密码由四位阿拉伯数字' $0$ ' ~' $9$ '组成。

现在给你一个长度为 10 的数组 $D [0 . .9]$ , 保证对于 $i \in [0, 9] \cap Z$ , 都有 $D_{i} \in {0, 1} \circ D_{i} = 0$ 表示数字 $i$ 没有在解锁密码中出现, $D_{i} = 1$ 表示数字 $i$ 在解锁密码中出现至少一次。

四年前狂小 P 按照可能的密码从小到大逐一进行尝试, 在四年后的今天, 狂小 P 已经尝试到了 $a b c d$ , 现在他想知道下一个需要尝试的可能的密码是多少。

Input

第一行包含 10 个整数, 表示 $D [0 . .9]$
第二行包含一个长度为 4 的字符电, 表示 $a b c d$ 。
(保证在给出的输入下, $D [a], D [b], D [c], D [d]$ 都是 1 )。

Output

输出一个长度为 $4$ 的字符电, 表示下一个需要尝试的可能的密码是多少, 若不存在下一个可能的密码了, 输出 $- 1$ 。

Examples

input 1

0 0 0 0 1 1 0 0 0 0 
4445

ouput 1

input 2

0 0 0 0 0 0 1 0 0 0 
6666

ouput 2

-1

input 3

1 1 0 0 0 0 0 0 0 0
0001

output 3

Code

比赛时，使用的是进制的做法，但是我需要 dfs 的写法.
gpt 4 dfs 写法

#include <bits/stdc++.h>
using namespace std;
int d[10], code[4];
int inc()
{
    int i = 3;
    while (i >= 0 && code[i] == 9)
        code[i] = 0,i--;
    if (i >= 0)
        code[i]++;
    return i;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    for (int i = 0; i < 10; i++)
        cin >> d[i];
    for (int i = 0; i < 4; i++)
    {
        char c;
        cin >> c;
        code[i] = c - '0';
    }
    while (1)
    {
        int i = inc();
        if (i < 0)
        {
            cout << -1 << '\n';
            break;
        }
        for (i = 0; i < 4; i++)
            if (d[code[i]] == 0)
                break;
        if (i == 4)
        {
            for (i = 0; i < 4; i++)
                cout << code[i];
            cout << '\n';
            break;
        }
    }
}

在这段代码中，首先输入 $d [0. . . 9]$ 和当前密码 $a b c d$ 。然后通过不断增加 $a b c d$ 的值直到找到下一个符合要求的密码。inc () 函数是用来增加密码的，如果找不到符合要求的密码，那么返回 -1。对于每个增加的密码，检查它的每一位是否都出现在 $d [0. . . 9]$ 中，如果都出现了，那么输出这个密码并结束程序。

B 典

16109 和 B 题很像。

Time limit: 2 seconds

Memory limit: 256 megabytes

原题

cxvdzxhb 喜欢平方数, 比如 $0, 1, 4, 9, 16, \dots$ 。但是发现有些数可以表示成两个平方数的和, 他觉得这样的数典。比如 $1 = 0^{2} + 1^{2}, 2 = 1^{2} + 1^{2}, 10 = 1^{2} + 3^{2}, 25 = 3^{2} + 4^{2}$ .
cxvdzxhbx 现在得到了一个长度为 $n$ 的序列 $a_{i}$ 和 $q$ 次询问。
每次问 $(l, r)$ 表示问区间 $[l, r]$ 中的数所构成的集合, 有多少个非空子集, 满足子集中的所有元素的乘积所表示的数典。

Input

第一行 2 个整数 $n, q (1 ⩽ n, q ⩽ 10^{5})$ 表示序列的元素数和询问个数。
第二行有 $n$ 个整数 $a_{i} (1 ⩽ a_{i} ⩽ 10^{7})$ 。
接下来 $q$ 行, 其中第 $i$ 行有两个整数 $l_{i}, r_{i} (1 ⩽ l_{i} ⩽ r_{i} ⩽ n)$ 表示询问的区间。

Output

对于每个询问, 输出一行一个整数, 表示答案, 由于答案可能非常大, 你需要对 $998244353$ 取模

Example

input

output

3
0
3

C 电路

2 seconds

256 megabytes

原题

有一个电路, 由 $n$ 个元件和 $m$ 个导线构成。对于 $i$ 号元器件, 我们需要为该元件选择一个 $1 \sim L_{i}$ 的正整数电压, 记为 $a_{i}$ , 为了让该元器件在该电压下正常工作, 我们需要 $c_{i, a i}$ 的成本。（并不是选择的电压越高成本越大)。对于导线 $i$ , 它连接了两个元器件 $u, v$ , 其电压分别为 $a_{u}, a_{v}$ , 则这个导线需要维护成本 $b_{i} \times | a_{u} - a_{v} |$ , 请你为每个元器件选择合适的电压, 让整个电路的成本最小。

Input

第一行包含两个正整数 $n (1 \leq n \leq 30)$ 和 $m (1 \leq m \leq 100)$ 。
接下来 $n$ 行,其中第 $i$ 行开头有一个整数 $L_{i} (1 \leq L_{i} \leq 10)$ , 接下来 $L_{i}$ 个整数 $c_{i, 1}, c_{i, 1}, \dots, c_{i, L_{i}}$ $(1 \leq c_{i, j} \leq 10^{9})$ 表示对于第 $i$ 个器件, 其电压为 $j$ 时的维护成本为 $c_{i, j}$ 。

接下来 $m$ 行, 其中第 $i$ 行包含三个整数 $u, v (1 \leq u, v \leq n)$ 表示第 $i$ 根导线连接了 $u$ 和 $v$ 两个元件, $b_{i}$ $(1 \leq b_{i} \leq 10^{9})$ 表示这两个元件的电压的单位差值下需要花费的成本。

Output

输出仅一个整数, 表示最小成本。

Example

input

5 4
4 1 100 100 100
2 100 1
3 100 100 1
5 100 100 100 1 1
2 100 1
1 2 5
1 3 5
1 4 10
1 5 5

output

D 搬空商店

Time limit: 2 seconds

Memory limit: 256 megabytes

原题

某手游有 $ABCD$ 四个副本, 为了完美毕业, 你需要铜材料 $a$ 个, 银材料 $b$ 个, 金材料 $c$ 个, 特殊材料 $d$ 个。

刷一次 $A$ 副本, 你可以得到 $A a$ 个铜材料, $A d$ 个特殊材料。
刷一次 B 副本, 你可以得到 $B b$ 个银材料, $B d$ 个特殊材料。
刷一次 $C$ 副本, 你可以得到 $C c$ 个金材料, $C d$ 个特殊材料。
刷一次 D 副本, 你可以得到 $D a$ 个铜材料, $D b$ 个银材料, $D c$ 个金材料, $D d$ 个特殊材料。

另外 5 个铜材料可以转换为 1 个银材料, 5 个银材料可以转换为 1 个金材料。
问最少刷多少次副本, 才能完美商店毕业, 同时你还想知道 ABCD 副本分别要刷多少次。如果有多个答案满足条件, 你想尽可能的少刷 $A$ 副本。如果这时候还有多个答案满足条件, 就尽可能的少刷 $B$ 副本。如果还有, 就尽可能的少刷 C 副本。

Input

第一行 4 个整数 $a, b, c, d (1000 ⩽ a, b, c, d ⩽ 2000) 。$
第二行 2 个整数 $A a, A d (10 ⩽ A a, A d ⩽ 100)$ 。
第三行 2 个整数 $B b, B d (10 ⩽ B b, B d ⩽ 100)$ 。
第四行 2 个整数 $C c, C d (10 ⩽ C c, C d ⩽ 100)$ 。
第五行 4 个整数 $D a, D b, D c, D d (10 ⩽ D a, D b, D c, D d ⩽ 100) 。$

Output

输出一行, 包含五个整数, 第一个整数表示总刷本次数, 后面四个整数分别表示 $ABCD$ 本的刷本次数

Example

input

100 200 300 400
100 10
90 10
80 10
10 11 12 70

output

11 1 2 3 5

E Misreading

Time limit: 2 seconds

Memory limit: 256 megabytes

原题

Given is a positive integer $n$ . Consider repeatedly applying the operation below on $n$ : First, choose a positive integer $z$ satisfying all of the conditions below:

$z$ can be represented as $z = p^{e}$ , where $p$ is a prime number and $e$ is a positive integer;
$z$ divides $n$ ;
$z$ is different from all integers chosen in previous operations.

Then, replace $n$ with $\frac{n}{z}$ .
Find the maximum number of times the operation can be applied.
The above problem is from D - Div Game

When lajiniunai first faced this problem, he read it wrong, changed the third condition to " $e$ is different from all integers chosen in previous operations". Then the three condition is changed to the following

$z$ can be represented as $z = p^{e}$ , where $p$ is a prime number and $e$ is a positive integer;
$z$ divides $n$ ;
$e$ is different from all integers chosen in previous operations.

Now with others unchanging, find the maximum number of times the operation can be applied.

Input

The first line contains a positive integer $T (1 ⩽ T ⩽ 1000)$ showing the number of test cases. Then $T$ cases follow, for each of the $T$ lines containing a positive integer $z (1 ⩽ z ⩽ 10^{18})$ .

Output

For each test case, print one line containing a number showing the answer.

翻译版

对于给定的正整数 $n$ ，考虑反复对 $n$ 应用以下操作：首先，选择一个满足以下所有条件的正整数 $z$ ：

$z$ 可表示为 $z = p^{e}$ ，其中 $p$ 是一个质数， $e$ 是一个正整数；
$z$ 整除 $n$ ；
$e$ 与先前操作中选择的所有整数不同。

然后，用 $\frac{n}{z}$ 替换 $n$ 。

找出可以执行此操作的最大次数。

当 lajiniunai 第一次面对这个问题时，他读错了题目，将第三个条件改成了“ $e$ 与先前操作中选择的所有整数不同”。

现在在其他条件不变的情况下，找出可以执行此操作的最大次数。

输入

第一行包含一个正整数 $T (1 ⩽ T ⩽ 1000)$ ，表示测试用例的数量。然后是 $T$ 个测试用例，每个测试用例包含一个正整数 $z (1 ⩽ z ⩽ 10^{18})$ 。

输出

对于每个测试用例，打印一行包含一个数字，表示答案。

Example

input

output

F 交换

Time limit: 1 seconds

Memory limit: 256 megabytes

原题

endereye 得到了一个只包含数字 $0 - 9$ 字符串 $s$ , 他发现有时候交换相邻两个位置的字符，可以得到一
个全新的字符串 $t$ 。然后他不断重复这样的交换操作，得到了所有可能得到的字符串。他注意到，这其
中有些字符串只用至少 $1$ 次交换操作就可以得到，有些需要至少 $2$ 次交换操作， $\dots$ 有些至少需要 $k$ 次
交换操作。他想知道这个 $k$ 最大能是多少。
他不知道怎么计算这个答案，所以把问题交给了你。

Input

第一行一个整数 $T (1 \leq T \leq 10)$ 。
接下来 $T$ 组数据：
每组数据第一行，包含一个整数 $n (1 \leq n \leq 10^{5})$ ，表示字符串的长度。
第二行包含一个由数字 $0 - 9$ 构成的长度为 $n$ 字符串 $s$ 。

Output

每组数据输出仅包含一行，输出答案

Example

input

output

G word 文档

Time limit: 1 seconds

Memory limit: 256 megabytes

原题

在 word 文档中, 有一个字符 $a$ , 现在你可以进行以下几种操作任意次:

全选: 选中文档中所有字符。
复制: 复制当前选中的字符到粘贴板。
粘贴: 将粘贴板的内容粘贴, 如果当前没有选中任意字符, 则内容会追加在原内容的后面。如果当前选中了一些字符, 那么这些字符会被当前粘贴的内容替换, 并且会取消选中状态。

你需要用最少的次数, 将文档中的字符数量变为恰好 $n$ 个。

Input

第一行包含一个正整数 $T (1 \leq T \leq 10^{3})$ 一表示数据组数。
接下来 $T$ 行, 每一行表示一组数据, 每组数据仅一个正整数 $n (1 \leq n \leq 10^{9})$ 一意义如题。

Output

$T$ 行, 每行包含一个非负整数, 表示该组数据的答案。

Example

input

output

0
10
998244355

Note

对于样例中的第二组数据, 变化过程如下:
$a \overset{select}{⟶} a \overset{copy}{⟶} a \overset{paste \times 3}{⟶}$ $a a a$ $\overset{select}{⟶} a a a \overset{copy}{⟶} a a a \overset{paste \times 3}{⟶}$ $a a a a a a a a a$
字符外的方框表示被选中状态。总共 $10$ 次操作。

Code

群友的代码 (记忆化搜索)

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> dp;
void dfs(int n)
{
    dp[n] = n + 2;
    for (int i = 2, m = sqrt(n); i <= m; i++)
    {
        if (n % i == 0)
        {
            if (dp.find(n / i) == dp.end())
                dfs(n / i);
            dp[n] = min(dp[n], dp[n / i] + 2 + i);
        }
    }
}
void solve()
{
    int n;
    cin >> n;
    if (dp.find(n) != dp.end())
    {
        cout << dp[n] << '\n';
        return;
    }
    if (n == 1)
    {
        cout << '0' << '\n';
        return;
    }    
    dfs(n);
    cout << dp[n] << '\n';
}
int main()
{
    ios::sync_with_stdio (false),cin.tie (nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}

H Hotpot

Time limit: 2 seconds

Memory limit: 256 megabytes

原题

Chongqing hotpot is one of the most famous dishes around the world. People love its spicy taste.
There are $n$ types of ingredients (say Maodu, Yachang, Yageng, Neiroupian, Sanxianrou,...) for the hotpot in total, the number of each type is infinity. For $i$ -th ingredient, it needs to be cooked for $a_{i}$ minutes.

Every minute, HeartBlack will add one ingredient to hotpot or take out all well-cooked (ready-to-eat) ingredients in the hotpot (If there are no cooked ingredients, she will do nothing).

Given what HeartBlack does at the start of every minute.
For each time she takes out ingredient, you need to print the types of ingredients she takes out in increasing order (If she takes out nothing, print -1) in a line. Attention, if there are more than one ingredients of the same type, the output needs to be repeated. For example, if there are 3 ingredients of type 2 taken out, you should print "2 2 2 ".

Input

The first line contains two positive integers, $n$ and $t (1 \leq n \leq 2 \times 10^{5}, 1 \leq t \leq 2 \times 10^{5})$ , denoting the number of types of ingredient and the total time eating hotpot (minute).

The second line contains $n$ positive integers, $a_{1}, a_{2}, \dots, a_{n} (1 \leq a_{i} < t)$ , denoting the time each ingredient needs to be cooked.

The next $t$ lines consist of one or two integers each. The first integer of $i$ -th line is $b_{i} (b_{i} \in {0, 1})$ , denoting what HeartBlack does in $i$ -th minute.

If $b_{i}$ is 0 , there is one more integer $c_{i} (1 \leq c_{i} \leq n)$ , denoting HeartBlack adds a $c_{i}$ -th type of ingredient to hotpot.

If $b_{i}$ is 1 , denoting HeartBlack takes out all the cooked ingredient.

Output

For each minute HeartBlack takes out, print the types of ingredients she takes out in increasing order in a line or print -1 when there are no cooked ingredients.

Example

input

output

-1
1 2 2 3

Note

Attention, if there are more than one ingredients of the same type, the output needs to be repeated. For
example, if there are $3$ ingredients of type $2$ taken out, you should print" $2 2 2$ ".

Code

用 set 解决，还并不知道是否正确。

#include <bits/stdc++.h>
using namespace std;
set<pair<int, int>> b,cooked;//b代表等等待成熟的食物，cooked代表已经成熟的食物
int n, t, a[200010];
int main()
{
    int k = 0;
    cin >> n >> t;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int time = 1; time <= t; time++)
    {
        int op;
        cin >> op;
        if (!op)
        {
            int x;
            cin >> x;
            b.insert({x, time + a[x]});
        }
        else
        {
            for (auto it = b.begin(); it != b.end();)
            {
                if (time >= it->second)
                {
                    cooked.insert({it->first,k++});
                    it = b.erase(it);
                }
                else
                    break;
            }
            if (cooked.empty())
            {
                cout << -1;
            }
            else
            {
                for (auto v : cooked)
                    cout << v.first << " ";
            }
            cout << '\n';
            cooked.clear();
        }
    }
}

I 井盖

Time limit: 3 seconds

Memory limit: 256 megabytes

原题

在路面上, 有 $n$ 个井盖, 井盖可以视作一个点, 其面积忽略不计, 第 $i$ 个井盖在坐标 $(x_{i}, y_{i})$ 。每个井盖都有 $p_{i}$ 的概率坏掉, 为了防止行人掉进去, 工作人员决定用警戒线将所有坏掉的井盖围住, 同时警戒线的长度最短。围住后, 在警戒线内部的区域都无法进入了。现在工作人员想知道, 被警戒线围住的区域的面积的期望是多少。请你帮他计算一下，并告诉他对 $10^{9} + 7$ 取模后的答案。

如果答案能表示为有理数的形式 $\frac{a}{b}$ , 则对质数 $M$ 取模后的答案为 $a \times b^{M - 2} mod M$ 。

Input

第一行包含一个整数 $n (1 ⩽ n ⩽ 2000)$ 。
接下来 $n$ 行中, 第 $i$ 行包含 4 个整数 $x_{i}, y_{i}, a_{i}, b_{i} (- 10^{9} \leq x_{i}, y_{i} \leq 10^{9}, 1 \leq a_{i} < b_{i} \leq 10^{9})$ , 表示第 $i$ 个点的坐标 $(x_{i}, y_{i})$ , 和出现的概率 $p_{i} = \frac{a_{i}}{b_{i}}$ 。

Output

输出一行一个整数, 表示答案。

Examples

input 1

output 1

41666667

input 2

output 2

750000006

Note

在第一个样例中, 坏掉一个或两个井盖被围住的面积都是 0 , 当坏掉了三个井盖的时候, 围住的面积是 $1$ , 概率为 $\frac{1}{2} \times \frac{1}{3} \times \frac{1}{4} = \frac{1}{24}$ , 取模后为 $1 \times 24^{10^{9} + 7} mod (10^{9} + 7) = 41666667$ 。