Xunyoyo

租用游艇题目描述长江游艇俱乐部在长江上设置了 $n$ 个游艇出租站 $1,2,\cdots,n$。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 $i$ 到游艇出租站 $j$ 之间的租金为 $r(i,j)$（$1\le i\lt j\le n$）。试设计一个算法，计算出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。 输入格式第一行中有一个正整数 $n$，表示有 $n$ 个游艇出租站。接下来的 $n-1$ 行是一个半矩阵 $r(i,j)$（$1\le i<j\le n$）。 输出格式输出计算出的从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。 样例 #1样例输入 #112335 157 样例输出 #1112 提示$n\le 200$，保证计算过程中任何时刻数值都不超过 $10^6$。 题解题目解析题目给的数据是这个意思: 中转站1 中转站2 中转站3 中转站1 0 5 15 中转站2 0 0 7 中转站3 0 0 0 用二维数组存下来就是: 1a[i][j] := 从中转站i到中转站j需要 ...

LCS题面翻译题目描述： 给定一个字符串 $s$ 和一个字符串 $t$ ，输出 $s$ 和 $t$ 的最长公共子序列。 输入格式： 两行，第一行输入 $s$ ，第二行输入 $t$ 。 输出格式： 输出 $s$ 和 $t$ 的最长公共子序列。如果有多种答案，输出任何一个都可以。 说明/提示： 数据保证 $s$ 和 $t$ 仅含英文小写字母，并且 $s$ 和 $t$ 的长度小于等于3000。 题目描述文字列 $ s $ および $ t $ が与えられます。 $ s $ の部分列かつ $ t $ の部分列であるような文字列のうち、最長のものをひとつ求めてください。 输入格式入力は以下の形式で標準入力から与えられる。 $ s $ $ t $ 输出格式$ s $ の部分列かつ $ t $ の部分列であるような文字列のうち、最長のものをひとつ出力せよ。 答えが複数ある場合、どれを出力してもよい。 样例 #1样例输入 #112axybabyxb 样例输出 #11axb 样例 #2样例输入 #212aaxayaz 样例输出 #21aa 样例 #3样例输入 #312az 样例输出 #31 样例 #4 ...

Knapsack 2题面翻译$n$ 个物品，选取其中若干个物品，使得对选取的这些物品 $\sum w_i\leq W$ 的前提下最大化 $\sum v_i$。 其实就是背包问题。 注意数据范围与上一题不同。 题目描述$ N $ 個の品物があります。 品物には $ 1,\ 2,\ \ldots,\ N $ と番号が振られています。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N $) について、品物 $ i $ の重さは $ w_i $ で、価値は $ v_i $ です。 太郎君は、$ N $ 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は $ W $ であり、持ち帰る品物の重さの総和は $ W $ 以下でなければなりません。 太郎君が持ち帰る品物の価値の総和の最大値を求めてください。 输入格式入力は以下の形式で標準入力から与えられる。 $ N $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ $ : $ $ w_N $ $ v_N $ 输出格式太郎君が持ち帰る品物の価値の総和の最大 ...

补题 Codeforces Round 881 (Div. 3)D. Apple TreeTimofey has an apple tree growing in his garden; it is a rooted tree of $n$ vertices with the root in vertex $1$ (the vertices are numbered from $1$ to $n$). A tree is a connected graph without loops and multiple edges. This tree is very unusual — it grows with its root upwards. However, it’s quite normal for programmer’s trees. The apple tree is quite young, so only two apples will grow on it. Apples will grow in certain vertices (these vertices may ...

补题 [2023牛客寒假算法基础集训营1] 本题主要考察了DFS123时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld 题目描述shino是一名喜欢拼图的女高中生，他最喜欢玩的拼图是黄金拼图（指把爱丽丝和九条可怜拼在一起），不过这和本题并没有什么关系。 点我看原番 点我看名场面 某天，shino发现了一款叫做《拼图啊》（PTA）的全新拼图游戏，shino希望你能编写程序帮她开发这个游戏的外挂。 PTA的拼图由 $n\times n$ 个大小为 $1\times1$ 的拼图块组成，每个拼图块都是在正方形的 $1\times1$ 拼图块基础上生成的，生成方法为：对于每一条边，可以选择不变、向里削出一个半圆形的缺口、向外补上一个半圆形的凸出三种操作之一。因此，一个拼图块可以由一个长度为 $4$ 的字符串描述，四个字符分别表示上、右、下、左四条边进行的操作，上述三种操作依次记为 $0,1,2$ 。 例如，下图的左图为一个 $2\times2$ 的拼图。而右图为左图中左上角的一块 $1\t ...

补题 [2023牛客寒假算法基础集训营1] 现在是，学术时间 (I)123时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld 题目描述北京IT大学（BIT）计算机学院为了在下一轮学科评估中让计算机学科获得$A+$的评定结果，进行了如引进强大的老师、加强课程之类、提高授课质量等多方面的努力。而为了提高学科评估中，学术成果一项的得分，计算机学院的院长打算通过重新分配论文的方式使得学院里所有教授的H指数值之和尽可能大。 具体来说，H指数用于粗略的评估一位教授的学术水平。一位教授可以发表多篇论文，每篇论文有一个引用量。定义一位教授的H指数为使得”该教授发表的所有论文中，有至少 $H$ 篇论文的引用量大于等于 $H$ “这一命题成立的最大的 $H$ 。 现在，院长发现学院里的每位老师当前的发表文章数都为 $0$ ，且恰好每人都有一篇写好的论文未发表，由于院长很懂学术界，他也可以准确的预知到每篇文章发表后的引用量。院长决定以最优的方式重新分配这些论文，他可以任意指定一篇论文由哪位教授发表。规定每篇论文只能 ...

补题 [NC252735] 修改后的和123时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld 题目描述牛牛面前有一个由 $n$ 个整数组成的数组 $A_1,A_2,…,A_n$。 牛牛打算对这个数组进行若干次操作。 每次操作牛牛可以选择 $A_1,A_2,…,A_n$ 中的任意一个非负整数，记所选数的下标为 $k$。然后牛牛会把 $A_k,A_{k+1},…,A_n$ 都减少 $A_k$。 牛牛想知道他对这个数组进行恰好 $m$ 次操作后，数组中所有数的和最少是多少。 输入描述 本题采用多组案例输入，第一行一个整数 $T$ 代表案例组数。 每组案例中，第一行输入两个空格分隔的整数 $n\ m$。 接下来一行输入 $n$ 个由空格分隔的整数代表：$A_1,A_2,…,A_n$。 保证： $0 < n,m \leq 10^5$ $-10^6 \le A_i \le 10^6$ 单个测试点中所有案例 $n$ 的和不超过 $2\times 10^5$ 单组案例的 $ ...

补题 [CF1840C] Ski Resort题目描述Dima Vatrushin 是一所学校的数学教师。由于他的出色工作，他被派去度假 $n$ 天。Dima长期以来一直梦想去滑雪胜地，因此他想安排几天连续的时间去滑雪。由于度假需要仔细准备，他至少要去 $k$ 天。 给定一个包含度假胜地天气预报的数组 $a$。换句话说，在第 $i$ 天，气温将为 $a_i$ 度。 Dima出生在西伯利亚，因此只有整个假期都不超过 $q$ 度的情况下，他才能度假。 不幸的是，Dima学数学学的，以至于他忘记了如何计算。他请求你帮助他计算在胜地选择度假日的方法数。 输入格式输入的第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) — 表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $ n $ , $ k $ , $ q $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \le k \le n $ , $ -10^9 \le q \le 10^9 $ )— 数组 $ a $ 的长度，Dima 在度假村最少需 ...

补题 [CF1840B] Binary Cafe题目描述从前，Toma 来到了一家二进制咖啡厅，这是一个非常受欢迎且不同寻常的地方。 咖啡厅提供了$ k$ 种不同的美味甜点，这些甜点从 $0$ 到 $k−1$ 进行编号。第 $i$ 个甜点的成本为 $i^2$ 枚硬币，因为这是一家二进制咖啡厅！Toma 愿意花费不超过 $n$ 枚硬币来品尝甜点。同时，他对于购买任何一种甜点超过一次都不感兴趣，因为品尝一次足以评价口感。 他有多少种不同的方式可以购买多种（可能为零）甜点来品尝？ 输入格式输入的第一行包含一个整数 $t$ $(1≤t≤1000)$——测试用例的数量。 接下来是 $t$ 行，每行描述一个测试用例。 每个测试用例都在单独的一行上给出，由两个整数 $n$ 和 $ k$ $(1≤n,k≤10^9)$ 组成——Toma愿意花费的硬币数量以及二进制咖啡馆中的甜点数。 输出格式输出 $t$ 个整数，其中第 $i$ 个整数应该等于第 $i$ 个测试用例的答案——购买甜点品尝的方法数。 样例 #1样例输入 #112345651 22 12 210 2179 100 样例输出 #11234522 ...

补题 [ABC304C] Virus题目描述二维平面上有编号为 $1, 2, \ldots, N$ 的 $N$ 个人，第 $i$ 个人位于坐标为 $(X_i,Y_i)$ 的点。 第 $1$ 个人感染了病毒。病毒会从感染者传播给距离感染者 $D$ 以内的人。 这里，距离定义为欧几里得距离，即对于两个点 $(a_1,a_2)$ 和 $(b_1,b_2)$，这两个点之间的距离为 $\sqrt{(a_1-b_1)^2 + (a_2-b_2)^2}$。 经过足够长的时间后，即当第 $i$ 个人感染病毒时，与第 $i$ 个人距离在 $D$ 以内的所有人都感染了病毒，请确定每个 $i$ 是否感染了病毒。 输入格式输入按以下格式从标准输入中给出： $N$ $D$$X_1$ $Y_1$$X_2$ $Y_2$$\vdots$$X_N$ $Y_N$ 输出格式输出 $N$ 行。第 $i$ 行，如果第 $i$ 个人感染了病毒，则输出 Yes；否则输出 No。 样例 #1输入样例 #1123454 52 -13 18 80 5 输出样例 #11234YesYesNoYes 样例 #2输入样例 #212343 ...