YZOJ P2319 宇宙图书馆

YZOJ P2319 宇宙图书馆

时间限制：1000MS      内存限制：131072KB

难度： \(3.4\)

  • 题目描述

宇宙图书馆（Universal Library）是一个规模巨大的图书馆，该图书馆收集各个星球出版的大量系列图书。为了统一时间，宇宙图书馆的每本书的出版年份以 “宇宙年” 为单位来记录。当然，尽管图书馆可以存非常多的书，但书不能无休止地增加，因此管理员会定期剔除出版年份小于某个数的所有书。

由于书的数量多，无法手工统计，你需要编写一个图书管理系统，来管理宇宙图书馆的图书记录。

  • 输入格式

第一行为一个正整数 \(N\)，为该系统设定的出版年份上限（单位：宇宙年，之后涉及的所有出版年份均为 \(1\) 到 \(N\) 之间的正整数。

之后，每行一个合法的命令，命令有以下五种：

Add t x：添加一套共 \(x\) 本书（\(x\) 为正整数），这一套书的出版年份均为 \(t\)（单位：宇宙年）；

Remove t：删除所有出版年份小于 \(t\) （单位：宇宙年）的书，并输出被删除的书的数量；

Count a b：统计出版年份（单位：宇宙年）在 \(a, b\) 之间（含 \(a, b\)，保证 \(a \leq b\) ）的书的数量，并输出；

List x：将所有书按出版年份从大到小（也就是从新到旧）顺序列出，但由于输出可能较多，这里只要求输出列表中给定的第 \(x\) 本书的出版年份（如果不存在，输出 No）；

Quit：退出系统，结束程序。

  • 输出格式

对每个 Remove、Count、List 命令，输出一行答案。…

YZOJ P3669 [USACO2008 Mar]土地购买

YZOJ P3669 [USACO2008 Mar]土地购买

时间限制：1000MS 内存限制：262144KB

难度：\(6.0\) （自评）

  • 题目描述

农夫 John 准备扩大他的农场，他正在考虑 \(N\) （\(1 \leq N \leq 1,000,000\)） 块长方形的土地。

每块土地的长宽满足 (\(1 \leq\) 宽 \(\leq 1,000,000\)， \(1 \leq\) 长 \(\leq 1,000,000\)）。每块土地的价格是它的面积，但 FJ 可以同时购买多块土地。

这些土地的价格是它们最大的长乘以它们最大的宽，但是土地的长宽不能交换。如果 FJ 买一块 \(3 \times 5\) 的地和一块 \(5 \times 3\) 的地，则他需要付 \(5 \times 5=25\)。

FJ 希望买下所有的土地，但是他发现分组来买这些土地可以节省经费。他需要你帮助他求出最小的经费。

  • 输入格式

输入文件的第 \(1\) 行一个数 \(N\)， 表示土地块数。第 \(2\) 行至第 \(N+1\) 行，每行包含两个数，表示第 \(i\) 块土地的长和宽。

  • 输出格式

最小的可行费用。

  • 样例输入

  • 样例输出

 

 

 …

YZOJ P3129 [校内训练20170627]跳格子

YZOJ P3129 [校内训练20170627]跳格子

时间限制：1000MS 内存限制：524288KB

难度：\(7.0\)

  • 题目描述

在一个花园里有一排 \(n\) 个格子，这些格子编号为 \(1\) 到 \(n\) 。袋鼠喜欢在花园的格子上跳跃。

袋鼠的跳跃方式是这样的：一开始，袋鼠位于 \(s\) 号格子上，接着它会选择一个尚未经过的格子上跳跃，经过 \(n-1\) 次跳跃后，所有格子都被经过了一次，袋鼠的跳跃将结束。袋鼠总是会在 \(t\) 号格子结束跳跃。

由于袋鼠中了病毒，所以如果上一步往前跳，那么这一步必须往后跳；反之，若上一步往后跳，那么这一步往前跳。

请问袋鼠有多少种跳跃的方案呢？

形式化地，你需要求出有多少个 \(1\) 到 \(n\) 的排列 \(p_1, p_2, \cdots, p_n\)，满足：

1， \(p_1=s ，p_n=t\)；

2， 对任意 \(2 \leq i \leq n-1\)，或者 \((p_i-1<p_i) \land (p_i+1<p_i)\) ，或者 \((p_i-1>p_i) \land (p_i+1>p_i)\) 。

  • 输入格式

输入共一行，包含三个正整数 \(n, s, t\) 。

  • 输出格式

输出共一行，包含一个整数，表示跳跃的方案数对 \(1,000,000,007\) 取模的结果。

  • 样例输入【包含两组样例】

  • 样例输出

  • 样例 1 说明

从 \(2\) 号格子到 \(3\) 号格子的跳跃方案有两种，一种是 \(2,1,4,3\)，一种是 \(2,4,1,3\) 。

  • 数据规模与约定

 

 

 …

[CF868-F] Yet Another Minimization Problem

[CF868-F] Yet Another Minimization Problem

时间限制：1000MS 内存限制：262144KB

难度：\(6.0\)

  • 题目描述

有 \(n\) 个正整数构成序列 \(a\) ，定义一个区间 \([l, r]\) 的代价为 满足 \(l \leq i, j \leq r\) 并使得 \(a_i=a_j\) 的无序对 \([i, j]\) 的数量。

现要把 \(a\) 分成 \(k\) 个互不相交且不为空的连续的区间，求出在所有分法中，分出区间的最小代价和是多少。

  • 输入格式

第一行，两个正整数 \(n, k\) 。

第二行，序列 \(a\) ，共 \(n\) 个元素，用一个空格隔开。

  • 输出格式

一个整数，表示在所有分法中，分出区间的最小代价和。

  • 样例输入

  • 样例输出

  • 样例说明

一种可能的分法为 \([1], [1, 3], [3, 3, 2, 1]\) 。

第一个区间的代价为 \(0\) ，第二个区间的代价为 \(0\) ，第三个区间的代价为 \(1\) ，最小代价和为 \(1\) 。

（其他样例见原题

  • 数据范围

对于 \(10\%\) 的数据，\(2 \leq n \leq 20\) 。

对于 \(40\%\) 的数据，\(2 \leq n \leq 1000\) 。

对于 \(100\%\) 的数据，\(2 \leq n \leq 10^5\) ，\(2 \leq k \leq min\{20,n\}\) 。

保证 \(1 \leq a_i \leq n\) 。

 

 

 

\(Source\): CF868-F …

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries

时间限制：2000MS 内存限制：262144KB

难度：\(5.2\)

  • 题目描述

给定一个长度为 \(n\) 的非负整数序列 \(a\) 和一个正整数 \(m\) 。

现在有 \(q\) 组询问，每组询问给定两个正整数 \(l, r\) ，每次可以选择满足 \(l \leq i \leq r\) 的若干个 \(a_i\) （也可以一个都不选），使得这些 \(a_i\) 的和是 \(m\) 的非负整数倍，并输出满足条件的选择方案数对 \(10^9+7\) 取模后的余数。

  • 输入格式

第一行为两个正整数 \(n\) 和 \(m\) 。

第二行为序列 \(a\) ，共 \(n\) 个元素，用一个空格隔开。

第三行为询问数 \(q\) 。

接下来的 \(q\) 行，每一行都有两个正整数，分别为 \(l\) 和 \(r\) 。

  • 输出格式

共 \(q\) 行。

第 \(i\) 行为第 \(i\) 组询问的答案。

  • 样例输入

  • 样例输出

  • 样例说明

对于第一组询问 \(l=1, r=2\) ，有 不选、选择 \(5, 1\) ，共 \(2\) 种情况。

对于第二组询问 \(l=1, r=3\) ，有 不选、选择 \(5, 1\) 、选择 \(5, …

YZOJ P2202 Legend VII – Ornament

YZOJ P2202 Legend VII – Ornament

时间限制：1000MS 内存限制：131072KB

难度：\(5.0\)

  • 题目描述

  • 输入格式

第一行有两个整数 \(N\) 和 \(Q\)，表示商店有 \(N\) 个装饰品，一共有 \(Q\) 个询问。

第二行有 \(N\) 对整数，每 \(i\) 对整数 \(p_i, b_i\) 表示第 \(i\) 个装饰品的价格和好看度。

接下来 \(Q\) 行，每行两个整数 \(a, c\)，分别描述 \(Q\) 个询问。

  • 输出格式

对于每个询问输出一行，一个整数表示最大好看度。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据，\(N \leq 100, Q \leq 1000\) 。

对于 \(100\%\) 的数据，\(N \leq 1000, Q \leq 100000, 1 \leq a \leq N, c \leq 1000\) 。

 

 

 …

YZOJ P2384 Naive – DP II

YZOJ P2384 Naive – DP II

时间限制：2000MS 内存限制：768KB

难度：\(5.0\) 出题人：lightning

  • 题目描述

请注意不寻常的空间限制。

由于空间的限制，无法直接给出每个位置的金币数量，所以需要用一种新的方法来得到金币的数量——定义长度为 \(P\) 的数组 \(P\) 和长度为 \(T\) 的数组 \(T\)，棋盘 \((i,j)\) 上的金币数量为 \((P_i+T_j) \bmod Mod\) 。

  • 输入格式

第一行输入三个整数，\(P\)、\(T\)、\(Mod\) 。

第二行输入 \(P\) 个整数，表示数组 \(P\) 。

第三行输入 \(T\) 个整数，表示数组 \(T\) 。

  • 输出格式

输出包括两行——

第一行输出一个整数表示获得的最多的金币数。

第二行输出方案，方案用一个只包含 \(P\) 和 \(T\) 的字符串表示，\(P\) 表示向下、\(T\) 表示向右。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据，\(P, T \leq 100\) 。

对于 \(100\%\) 的数据，\(P, T \leq 5000，Mod \leq 100000\) 。

 

 

 …

YZOJ P3782 [校内训练20180619]组合数问题

YZOJ P3782 [校内训练20180619]组合数问题

时间限制：1000MS 内存限制：524288KB

难度：\(6.5\) 出题人：zzx

  • 题目描述

  • 输入格式

第一行一个正整数 \(n\) 表示数对个数。

接下来 \(n\) 行，第 \(i\) 行两个正整数 \(a_i, b_i\)，表示一个数对 \((a_i, b_i)\) 。

  • 输出格式

一行一个整数，表示所求式子的值。

  • 样例输入

  • 样例输出

  • 样例说明

  • 数据规模与约定

保证 \(2 \leq n \leq 200,000\) ， \(1 \leq b_i \leq a_i \leq 2000\) 。

 

 

 …

MCPE去除Xbox登录验证，愉快的玩耍服务器

前几天又把Minecraft PE下载下来了，更新的还真的很快，我最后一次玩好像是在0.10版本左右，现在已经更新到了1.6了。

成功的利用PocketMine搭了个服务器，但是我发现不知道从什么时候开始MCPE连服务器的时候竟然需要登录Xbox账号！！！

这个可以算是非常烦人。虽然我的手机上有Google全家桶，但是要和别人联机这就不好玩了。如果把Google Play Service的依赖弄掉，那么Xbox的验证就无法成功。如果要成功登录Xbox，手机里就必须装有Google Play Service。这个真的是非常烦人。

所以我决定把Xbox验证的功能手动弄掉。（注：直接用幸运破解器弄掉Google Play Service的验证）

 

首先把整个APK解包出来，来到./com.mojang.minecraftpe/lib/armeabi-v7a，底下有两文件。

其中那个50多MB的libminecraftpe.so就是我们的目标文件。

用IDA6.8打开它（IDA7.0我只有x64的）（IDA6.8下载地址：Click Here）

然后就是长达3个多小时的分析过程。。。。。。。。。。。（强烈吐槽IDA的单线程）

（PS：是真的三个多小时）

首先快速定位到字符串xbox.externalServer.title

详细的字符串信息可在./assets/resource_packs/vanilla/texts/zh_CN.lang找到

然后一个F5下去，寻找一下代码，立马就发现一个登录验证函数

isSignedIn()的返回值给v14，然后在底下判断是否成功

来到汇编代码，BLX就是ARM中的执行函数指令，且返回值保存在R0寄存器

（Intel汇编call为执行函数指令，返回值保存在eax）

因为IDA不支持ARM的汇编直接修改，所以必须转换为Hex才可以修改。

观察到相同的部位，所以直接修改。

4F F0 01 04 = MOV R0, #1

00 BF = NOP

修改过后就变成这样，这就很开心了

但是还不能开心的太早，这里还有一句验证登陆的语句。

跟刚才一样弄掉。

这样所有的验证就都弄掉了，应用这个Patch，然后重新打包APK，就可以得到一个很开心的最新版本的MCPE Stable 1.6.0.14

只要在设置里更改名字就好了，再也不需要Xbox和GooglePlayService的登录验证了。

.idb下载：libminecraftpe.idb

详情见：https://mc.mnihyc.com/

 

 

Thanks to https://bbs.pediy.com/thread-230034.htm，帮我节省了很多寻找验证的时间。

 …