Q779’s Blog

洛谷P5982 [PA2019] Trzy kule 题解 题目链接：P5982 [PA2019] Trzy kule 题意： 对于两个长度为 \(n\) 的 \(01\) 串 \(a_{1..n},b_{1..n}\)，定义它们的距离 \(d(a,b)=|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\)。 给定三个长度为 \(n\)的 \(01\) 串 \(s_1,s_2,s_3\)以及三个非负整数 \(r_1,r_2,r_3(0\le r_i\le n)\)，问有多少个长度为 \(n\) 的 \(01\) 串 \(S\)满足\(d(S,s_1)\le r_1,d(S,s_2)\le r_2,d(S,s_3)\le r_3\) 这三个不等式中至少有一个成立。 输入格式： 第一行一个正整数 \(n\)。 第二行一个非负整数 \(r_1\)，然后一个长度为 \(n\) 的 \(01\) 串 \(s_1\)。 第三行一个非负整数 \(r_2\)，然后一个长度为 \(n\) 的 \(01\) 串 \(s_2\)。 第四行一个非负整数 \(r_3\)，然后一个长度为...

AT_birthday0410_x - この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇を 题解 题目链接：AT_birthday0410_x 因为此题是道非常残忍的题，可以的话我认为你应该先开心地做其他题，如果其他题做完了还有时间的话，就以此题为消遣吧（以上为题目名称） 题目背景 如果你想AK这场比赛（お誕生日コンテスト），你可以尝试挑战这道题。从准备比赛的阶段开始，我就很担心我是否可以出这样的题目，但我还是决定冒一次险，因为这是一场具有挑战性的比赛。 题目描述 给出一个式子，由一位数整数，括弧，四则运算符号(加减乘除)组成，请输出计算结果。 （译者注：请不要忙着打，先把后面看完。） 输入格式 \(\begin{array}{ll} t & \\ W \quad H \\ B_1 & \\ B_2 & \\ \cdots & \\B_H &\end{array}\) 其中， \(t\) 是非负整数，表示此为第 \(t\) 组数据...

C++语法 stringstream 类的用法 转载并修改自 https://blog.csdn.net/hanjing_csdn/article/details/79922660 一、数字 \(\rightarrow\) 字符串 C++ 中 stringstream 类是一种十分有用的类，特别是当我们需要在程序中使用字符串和数字数据互相转换时。 要想在程序中使用 stringstream 类，我们需要引入头文件 <sstream> 。 stringstream 对象的使用方法与其他 stream 系列对象的使用方法非常相似。 当我们需要按预订的格式将程序中的数据保存在一个 string 中的时候，可以先创建一个 stringstream 对象 并通过运算符 << 将数据传递给 stringstream 对象，这与 cout 对象的方法类似。 接着，我们可以通过调用 stringstream 类的函数 str() 建对象所包含的内容赋值给一个 string 对象。 在下面的程序中，我们先将数据传递给一个 stringstream 对象，然后通过该对象将数...

洛谷P1175 表达式的转换 题解 题目链接：P1175 表达式的转换 题意： 平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。 后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。 例如：8-(3+2*6)/5+4 可以写为：8 3 2 6 * + 5 / - 4 + 其计算步骤为： 8 3 2 6 * + 5 / - 4 + 8 3 12 + 5 / - 4 + 8 15 5 / - 4 + 8 3 - 4 + 5 4 + 9 编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。 输入格式： 就一行，是一个中缀表达式。输入的符号中只有这些基本符号 0123456789+-*/^()，并且不会出现形如 2*-3 的格式。 表达式中的基本数字也都是一位的，不会出现形如 12 形式的数字。 所输入的字符串不要判错。 输出格式： 若干个后缀表达式，...

[ARC061F] Card Game for Three 题解 题目链接：[ARC061F] Card Game for Three 题意： 有三堆牌, 分别有 \(n_1, n_2, n_3\) 张。牌上写着数字 \(1,2,3\) 中的一个。 先从牌堆 \(1\) 中抽一张，接下来，牌上写着几就从几号牌堆抽取。 求在所有可能的 \(3^{n_1+n_2+n_3}\) 种方案中，先把牌堆 \(1\) 抽空的方案数。 答案对 \(10^9+7\) 取模。 \(n_1, n_2, n_3 \leq 3 \times 10^5\)，时限 \(3 \mathrm{~s}\) 。 计数好题，是我怎么看都不可能做出来的题。不过至少我现在会了。 条件计数的题目有两种解决办法：要么容斥，要么寻找更简洁的充要条件。 这道题看上去就不像容斥，因此考虑寻找充要条件，将原题的计数转化为更简单的题目的计数。 把抽出来的牌排成一个序列，显然每种放置方式都恰好对应一个序列。【构造映射】 注意到牌可能拿不完，因此一个序列可能对应多种方案。 具体地，一个长度为 \(m\) 的序列对应 \(3^{n_1 +...

洛谷P3609 [USACO17JAN] Hoof, Paper, Scissor G 题解 题目链接：P3609 [USACO17JAN] Hoof, Paper, Scissor G 题意： 你可能玩过“石头，剪刀，布”，这个游戏在奶牛中同样流行，不过它的名字变成了“蹄子，剪刀，布”。 “蹄子，剪刀，布”和“石头，剪刀，布”的规则十分类似，两只奶牛数到三，然后出一个代表蹄子，剪刀或布的手势。蹄子胜过剪刀，剪刀胜过布，布胜过蹄子。特别地，如果两只奶牛的手势相同，则视为平局。 现在 FJ 和 Bassie 要进行 \(N\) 轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒，她最多只想变换 \(K\) 次手势。 现在请你帮 Bassie 求出她最多能赢多少轮。 本题与 银组同名题目 在题意上一致，唯一的差别在于对变手势次数的限制。 输入格式： 第一行输入两个整数 \(N,K\)（\(1 \leq N \leq 10^5\)，\(0 \leq K \leq 20\)）。 接下来 \(N\) 行，每行一个字母，代表 FJ 这一轮出的手势。H 代表蹄...

洛谷P8968 觅光 | Searching for Hope (hard version) 题解 题目链接：洛谷P8968 觅光 | Searching for Hope (hard version) 题意： 现在有一棵 \(n\) 个节点的有根二叉树。 凡人与神明在这棵树上进行一个游戏。凡人需要从根投下若干个球，每个球带 \(1\) 单位正电荷或带 \(1\) 单位负电荷。 树上每一个点有容量，第 \(i\) 个点可以容纳 \(c_i\) 个球。初始每一个点容纳的球数为 \(0\)。我们称一个点被充满当且仅当它容纳的球的个数等于它的容量。 每一次一个球下落到一个点时： 如果该点没有孩子节点或者所有孩子节点上都已经充满球，则停止，该点容纳的球的个数 \(+1\)； 如果该点恰有一个孩子节点未充满，则向那个孩子下落； 如果有 \(2\) 个孩子节点均未充满： 如果左侧子树中所有球的电荷代数和大于右侧子树所有球的电荷代数和，则如果当前球带正电则向右下落，否则向左下落； 如果左侧子树中所有球的电荷代数和小于右侧子树所有球的电荷代数和，则如果当前球带正电则向左下落，否则向右下落；...

洛谷P9149 串串题 题解 题目链接：P9149 串串题 题意： 给定长度分别为 \(n,m\) 的整数序列 \(A,B\) 和常数 \(W,d\)，序列从 \(1\) 开始标号，保证 \(A_i,B_i \in [1,W]\)。 容易发现，我们有 \(\binom{W}{d}\) 种方案选择 \([1,W]\) 中的 \(d\) 个互不相同的整数。 对于每一种选择的方案，我们删去 \(A\) 中出现的对应的 \(d\) 种整数，令此时序列 \(B\) 在序列 \(A\) 中的出现次数为这次选择方案的权值。 你需要求所有的选择方案的权值和，对 \({10}^9+7\) 取模。 若对题意有疑问，请阅读样例及样例解释。 注：\(\binom{a}{b}\) 表示组合数，含义为在 \(a\) 个物品中无序地选择出 \(b\) 个物品的方案数。 请注意：我们并不会删除序列 \(\mathbf{B}\) 中出现的对应整数。 输入格式： 本题有多组数据。 第一行，一个正整数 \(T\)，表示数据组数。对于每组数据： 第一行，四个正整数 \(n, m, W, d\)，保证 \(d \le ...

洛谷P5515 [MtOI2019] 灵梦的计算器 题解 题目链接：P5515 [MtOI2019] 灵梦的计算器 题意： 灵梦得到了 \(3\) 个实数 \(n,a,b\) ( \(4\le n\le 5,5 \le a,b \le 10\) ) ，她成功地计算了 \(n^a+n^b\)，得到了一个只显示整数部分的结果。 灵梦想知道，若存在一个实数 \(n'(n' \geq 0)\)，使得 \({n'}^a+{n'}^b\) 的结果在计算器上与 \(n^a+n^b\) 的结果显示出来完全一致时，\(n'\) 的变化范围，即 \(n'\) 的最大值与最小值之差。 如果你不知道如何计算 \(n^k\)，请使用cmath库的pow()函数，pow(n,k)的结果即为 \(n^k\) 的结果。 为了提高本题的难度，灵梦给你设置了 \(T\) 组询问。而为了在某种程度上减少你的输入和输出量，我们采用以下的代码来生成询问(代码来自河童重工)： namespace Mker { // Powered By Kawashiro_N...

[ABC190E] Magical Ornament 题解 题目链接：[ABC190E] Magical Ornament 题意： AtCoder 王国流通着 \(N\) 种魔法石，编号为 \(1,2,\dots,N\)。高桥想要把魔法石排成一列做成装饰品。 有的魔法石能够相邻放在一起，有的魔法石却不行。有 \(M\) 组魔法石是可以相邻的，分别是 \((\)魔法石 \(A_1,\) 魔法石 \(B_1),\ (\) 魔法石 \(A_2,\) 魔法石 \(B_2),\ \dots,\ (\) 魔法石 \(A_M,\) 魔法石 \(B_M)\)。除此之外的任何两个魔法石都不能相邻摆放。（可以相邻的魔法石摆放前后顺序不限。） 请判断是否存在这样一种排列方式，使得其中包含 \(C_1,C_2,\dots,C_K\) 中的每一种魔法石。如果存在，求形成这样一个序列所需的最小宝石数量。如果不存在，输出 -1。 \(1 \le N,M \le 10^5,1\le K\le 17,1\le C_i < C_{i+1} \le N\) 把 \(m\) 组条件看作 \(A_i\) 向 \...

[ARC061E]Snuke’s Subway Trip 题解 题目链接：[ARC061E]Snuke’s Subway Trip 题意： Snuke的城镇有地铁行驶，地铁线路图包括 \(N\) 个站点和 \(M\) 个地铁线。站点被从 \(1\) 到 \(N\) 的整数所标记，每条线路被一个公司所拥有，并且每个公司用彼此不同的整数来表示。 第 \(i\) 条线路( \(1≤i≤M\) )是直接连接 \(p_i\) 与 \(q_i\) 的双向铁路，中间不存在其他站点，且这条铁路由 \(c_i\) 公司所拥有。 如果乘客只乘坐同一公司的铁路，他只需要花费一元，但如果更换其他公司的铁路需要再花一元。当然，如果你要再换回原来的公司，你还是要花一元。 Snuke在 \(1\) 号站的位置出发，他想通过地铁去第 \(N\) 站，请求出最小钱数。如果无法到达第 \(N\) 站，输出 \(-1\)。 输入格式： 第一行，输入 \(N,M\) 接下来的 \(M\) 行，输入 \(p_i\) \(q_i\) \(c_i\) ，代表 \(p_i\) 与 \(q_i\) 中间有直接连接的双向边，且这...

UOJ26 【IOI2014】Game 题解 题目链接：UOJ26 【IOI2014】Game 题意： 健佳是一个喜欢做游戏的小男生。当有人问问题时，他更喜欢通过玩游戏的方式作答，而不是直接回答。健佳碰到了他的朋友梅玉，跟她讲了台湾的航空网。在台湾有 \(n\) 个城市（编号为 \(0,\ldots,n-1)\) ，其中有些城市之间有航线。每个航线连接两个城市，并且是双向的。 梅玉问健佳，是否任意两个城市之间都可以坐飞机互达（直接或间接），健佳不想直接回答，而是要通过做游戏的方式来告诉她。梅玉可以问”城市 \(u\) 和 \(v\) 之间有直接航线吗? “，健佳会立刻直接回答该问题。梅玉会询问每对城市恰好一次，因此总计会有 \(r=n(n-1) / 2\) 个问题。如果由前 \(i(i<r)\) 个问题的答案可以推断出整个航空网是否连通，也就是说，是否任意一对城市之间都可以坐飞机互达（直接或间接），梅玉就获胜。否则意味着她需要知道全部 \(r\) 个回答，此时健佳获胜。 为了让游戏更好玩，他们俩同意，健佳可以不要管台湾的真实航空网，而是可以随着游戏的进展而编造航空网，也就...