BearChild · Blog

灵魂宝石 Time Limit: 5 Sec Memory Limit: 128 MB Description “作为你们本体的灵魂，为了能够更好的运用魔法，被赋予了既小巧又安全的外形” 　　我们知道，魔法少女的生命被存放于一个称为灵魂宝石（Soul Gem）的装置内。 　　而有时，当灵魂宝石与躯体的距离较远时，魔法少女就无法控制自己的躯体了。 　　在传说中，魔法少女 Abel仅通过推理就得到了这个现象的一般法则，被称为Abel定理： 　　存在宇宙常量 R（是一个非负实数，或正无穷） ，被称为灵魂宝石常量，量纲为空间度量（即：长度）。 　　如果某个魔法少女的灵魂宝石与她的躯体的距离严格超过 R，则她一定无法控制自己的躯体；如果这个距离严格小于 R，则她一定可以控制自己的躯体。 （这里的距离指平面的 Euclid距离。） 　　注意：该定理不能预言距离刚好为 R 的情形。 　　可能存在魔法少女 A 和 B，她们离自己的灵魂宝石的距离都恰好为 R，但是 A可以控制自己的躯体，而 B 不可以。 　　现在这个世界上再也没有魔法少女了，但是我们却对这个宇宙常量感兴趣。 　　我们只能通过之前的世界遗 ...

Shik and Travel Time Limit: 50 Sec Memory Limit: 512 MB Description 给定一棵n个点的树，保证一个点出度为2/0。 遍历一遍，要求每条边被经过两次，第一次从根出发，最后一次到根结束，在叶子节点之间移动。 移动一次的费用为路径上的边权之和，第一次和最后一次免费，移动的最大费用 最小可以是多少。 Input 第一行一个n，表示点数。 之后两个数x, y，若在第 i 行，表示 i+1 -> x 有一条权值为 y 的边。 Output 输出一个数表示答案。 Sample Input 7 　　1 1 　　1 1 　　2 1 　　2 1 　　3 1 　　3 1 Sample Output 4 HINT 2 < n < 131,072 　　0 ≤ y ≤ 131,072 Solution 问题的本质就是：求一个叶子节点排列，按照排列顺序走，使得两两距离<=K。 　　因为第一天和最后一天不花费，可以第一天从根走到一个叶子，最后一天从某一叶子走回根。 　　我们首先二分答案。 对于子树u维护二元组(a, b)，表示存 ...

Norma Time Limit: 20 Sec Memory Limit: 64 MB Description Input 第1行，一个整数N； 第2~n+1行，每行一个整数表示序列a。 Output 输出答案对10^9取模后的结果。 Sample Input 4 　2 　4 　1 　4 Sample Output 109 HINT N <= 500000 　1 <= a_i <= 10^8 Solution Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118#include<bits/stdc++.h>u ...

弹飞绵羊 Time Limit: 10 Sec Memory Limit: 259 MB Description 某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。 Input 第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1， 接下来一行有n个正整数，依次为那n个装置的初始弹力系数。 第三行有一个正整数m， 接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。 Output 对于每个i=1的情况，你都要输出一个需要的步数，占一行。 Sample Input 4 　1 2 1 ...

动态规划 Time Limit: 50 Sec Memory Limit: 128 MB Description 一开始有n个数，一段区间的价值为这段区间相同的数的对数。 　　我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。 　　我们想让最终这n个数的价值和尽可能少。 　　例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。 Input 第一行两个数n,k。 　　接下来一行n个数ai表示这n个数。 Output 一个数表示答案。 Sample Input 10 2 　　1 2 1 2 1 2 1 2 1 2 Sample Output 8 HINT 对于100%的数据1<=n<=100000,1<=k<=min(n,20),1<=ai<=n。 Solution 首先，暴力DP非常显然，f[i][j] 表示分了 i 段，当前做到第 j 个元素的最小值。 那么 f[i][j] = f[i - 1][k] + sum(k + 1, j ...

减法 Time Limit: 10 Sec Memory Limit: 256 MB Description 给你一个n个数的序列A，并且给出m次操作B。 操作的含义是：每次从A中选出不同的B_i个数，把它们减去1。一个数>0被看作是可以选择的。 问最多执行完第几个操作。 Input 第一行给出两个整数，序列长度n与操作数m。 第二行n个数，表示序列A。 第三行m个数，表示操作序列B。 Output 输出一个整数，表示最多执行完第几个操作。 Sample Input 3 4 　　2 1 3 　　3 1 2 1 Sample Output 3 HINT 1 <= n, m <=100000 Solution 考虑贪心，显然是每次减去大的数。 我们二分答案做到第几次，然后构造一组不上升序列times，表示每个数最多可以被减几次，每次把区间**[1, B[i]]**加一。 如果每个数都足够大的话，这显然是一组合法解。但是每个数不一定都够减。 我们可以基于这个序列来做调整，考虑什么情况下是合法的呢？ 　　显然，前面不够减的可以是分摊到后面去，而若A从大到小排序，贪心尽量多减， ...

稻草人 Time Limit: 40 Sec Memory Limit: 256 MB Description JOI村有一片荒地，上面竖着N个稻草人，村民们每年多次在稻草人们的周围举行祭典。 有一次，JOI村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件： 田地的形状是边平行于坐标轴的长方形； 左下角和右上角各有一个稻草人； 田地的内部(不包括边界)没有稻草人。 给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数 Input 第一行一个正整数N，代表稻草人的个数 接下来N行，第i行(1<=i<=N)包含2个由空格分隔的整数Xi和Yi，表示第i个稻草人的坐标 Output 输出一行一个正整数，代表遵从启示的田地的个数 Sample Input 4 　0 0 　2 2 　3 4 　4 3 Sample Output 3 HINT 1<=N<=2*10^5 0<=Xi<=10^9(1<=i<=N), Xi(1<=i<=N)互不相同。 0<=Yi<=10^9(1<= ...

简单题 Time Limit: 50 Sec Memory Limit: 128 MB Description 你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作： 命令 参数限制 内容 1 x y A 1<=x,y<=N，A是正整数 将格子x,y里的数字加上A 2 x1 y1 x2 y2 1<=x1<= x2<=N 1<=y1<= y2<=N 输出x1 y1 x2 y2这个矩形内的数字和 3 无 终止程序 Input 输入文件第一行一个正整数N。 接下来每行一个操作。 Output 对于每个2操作，输出一个对应的答案。 Sample Input 4 　1 2 3 3 　2 1 1 3 3 　1 2 2 2 　2 2 2 3 4 　3 Sample Output 3 　5 HINT 1<=N<=500000,操作数不超过200000个，内存限制20M。 对于100%的数据，操作1中的A不超过2000。 Solution 首先把询问拆成4个，那么我们就只要维护一个点 ...

捉迷藏 Time Limit: 40 Sec Memory Limit: 256 MB Description 捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。 　　他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。 　　游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。 　　在起初的时候，所有的灯都没有被打开。 　　每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。 　　为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。 　　我们将以如下形式定义每一种操作： 　　C(hange) i 改变第i房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 　　G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。 Input 第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的 ...

Game Time Limit: 20 Sec Memory Limit: 512 MB Description 从前有个游戏。游戏分为 k 轮。 给定一个由小写英文字母组成的字符串的集合 S， 在每轮游戏开始时，双方会得到一个空的字符串， 然后两人轮流在该串的末尾添加字符，并且需要保证新的字符串是 S 中某个串的前缀，直到有一方不能操作，则不能操作的一方输掉这一轮。 新的一轮由上一轮输的人先手，最后一轮赢的人获得游戏胜利。 假定双方都采取最优策略，求第一轮先手的一方能否获胜。 Input 输入包含多组数据。 每组数据的第一行包含两个整数 n,k，分别表示字符串的数量和游戏的轮数。 接下来 n 行，每行一个由小写英文字母组成的字符串。 Output 对于每组数据输出一行，若先手能获胜输出 HY wins!，否则输出 Teacher wins! Sample Input 2 3 　　a 　　b 　　3 1 　　a 　　b 　　c Sample Output HY wins! 　　HY wins! HINT 1 ≤ n ≤ 1e5,1 ≤ k ≤ 1e9，保证所有字符串长度不超过 1e5， ...