BearChild's Blog

减法 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: 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 ...

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: 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: 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的 ...

合唱队 Time Limit: 4 Sec Memory Limit: 64 MB Description Input Output Sample Input 4 　1701 1702 1703 1704 Sample Output 8 HINT Main idea 给定一个元素两两不相等的目标序列，每次按照给定方式将一个元素加入到序列当中，问得到目标序列的方案有几种。（加元素的方式：如果加的这个元素比上一个加入的元素小的话则放在队头，否则放在队尾）。 Solution 发现题目要求的是方案数，并且没有什么一眼看过去的规律，不可能是找规律了，那么我们想到了区间DP。 　　由于题目给定的加入元素的方式，我们可以清楚的知道新元素要么加在队头要么加在队尾，所以说在某种程度上这个序列是连续的（或者说有特殊的性质），并且对于新加入的元素的位置的影响只跟上一次的加入元素有关。 　　根据这个特殊性质我们想到了区间DP，令f[l][r][0\1]表示区间l~r中现在加入的元素放在队头\队尾。 　　那么显然，初值即为f[i][i][0]=1或f[i][i][1]=1，并且如果放在队头的话f[l] ...

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， ...

石子游戏 Time Limit: 10 Sec Memory Limit: 256 MB Description Input Output 输出T行，表示每组的答案。 Sample Input 3 　　1 　　1 　　2 　　1 　　0 0 　　3 　　1 2 2 　　4 4 4 4 Sample Output 1 　　0 　　6 HINT Solution 这显然是一道博弈论的题目。我们发现这是一个树结构，仔细看了一下，发现这显然是一个阶梯Nim的模型。 我们将所有和同n奇偶的值XOR起来就可以得到SG。我们先判断一下，若SG=0则显然必败，否则必胜。 然后我们开始计算方案，枚举每一个节点，目标显然就是要让SG=0。 由于XOR的消去率，根据题意，可以分 2 种情况分别讨论：（根据SG异或值判断是加入还是取出。） 1. 从父亲那加入值，显然就是需要 ( SG^a[这个点] ) - a[这个点的父亲] <= a[这个点]，这样才可以通过加入若干个值使得SG=0； 　　2. 把值给儿子，显然需要 (SG^a[这个点]) <= a[这个点]，这样才可以通过拿走若干的值使得 ...