BearChild's Blog

我也不知道题目名字是什么 Time Limit: 10 Sec Memory Limit: 512 MB Description 给定一个序列A[i]，每次询问l,r，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串 Input 第一行n，表示A数组有多少元素 　接下来一行为n个整数A[i] 　接下来一个整数Q，表示询问数量 　接下来Q行，每行2个整数l，r Output 对于每个询问，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串 Sample Input 9 　1 2 3 4 5 6 5 4 3 　5 　1 6 　1 7 　2 7 　1 9 　5 9 Sample Output 6 　6 　5 　6 　4 HINT N,Q<=50000 Solution 直接上线段树，记录一下一个区间内：左边最长，右边最长，整体最优。再分一下不下降和不上升即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545 ...

数据结构C Time Limit: 20 Sec Memory Limit: 512 MB Description Input Output Sample Input Sample Output HINT Solution 首先，D操作为删除操作显然不可做，又发现这道题可以离线处理，那么我们考虑倒着来，维护加入操作。 那么这时候，D操作就变为了合并操作，那么这时候我们只需要维护一个：可以支持单点修改、查询第 k 大、信息可合并的数据结构即可。 显然构建若干棵权值线段树即可！对于每个联通块维护一棵线段树，用并查集判断两点是否在一个块内。 这时候，D操作显然判断一下两点是否在一个联通块内，不在则合并两棵线段树；Q操作就是查询第 k 大，在树上二分即可；C操作就是原来值个数-1，新加入值个数+1。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737 ...

相关分析 Time Limit: 10 Sec Memory Limit: 128 MB Description Frank对天文学非常感兴趣，他经常用望远镜看星星，同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离，半径等等。 Frank不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间（比如亮度和半径）是否存在某种关系。 现在Frank要分析参数X与Y之间的关系。 他有n组观测数据，第i组观测数据记录了x_i和y_i。 他需要一下几种操作 1 L,R：用直线拟合第L组到底R组观测数据。 用xx表示这些观测数据中x的平均数，用yy表示这些观测数据中y的平均数，即 xx=Σx_i/(R-L+1)(L<=i<=R) yy=Σy_i/(R-L+1)(L<=i<=R) 如果直线方程是y=ax+b，那么a应当这样计算： a=(Σ(x_i-xx)(y_i-yy))/(Σ(x_i-xx)(x_i-xx)) (L<=i<=R) 你需要帮助Frank计算a。 2 L,R,S,T： Frank发现测量数据第L组到底R组数据有误差，对每个i满足L ...

魔法 Time Limit: 10 Sec Memory Limit: 256 MB Description Input Output 仅一行一个整数表示答案。 Sample Input 4 10 　　7 2 8 5 Sample Output 2 HINT Solution 我们找一下规律，显然发现是就是Σa[i]*C(n-1,i-1)。然后问题主要就转化为了怎么快速求组合数C(n,i)在模一个非质数情况下的值。 首先我们先确定一个式子： 然后我们立马想到了一个暴力分解质因数的方法。就是记录所有的(n-i+1)和(i)的质因数，然后用上面的质因数个数减去下面的质因数个数，剩下的乘起来，就不用求取模了。 但是我们发现，这样显然会TLE，我们考虑如何优化。优化的话显然就是要找到一个办法不把多的质因数都彻底分解出来。我们来继续思考： 我们可以先求出模数的质因数，再对于(n-i+1)和(i)分解质因数。这时候如果质因数和模数的质因数一样，由于不互质没有逆元，就把它记录下来，等下用快速幂乘起来就行了。那么这时候其余的质因数就可以直接求逆元了，由于模数不是质数，我们运用这个公式：（phi ...

String Problem Time Limit: 10 Sec Memory Limit: 64 MB Description Input Output Sample Input 1 　　3 　　135 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　0 0 3 　　1 0 0 　　4 0 0 Sample Output 3 HINT Solution 官方题解： 首先将点分为3类 第一类：Pij 表示第i个点和第j个点组合的点，那么Pij的权值等于w[i][j]+w[j][i]（表示得到的价值） 第二类：原串中的n个点每个点拆出一个点，第i个点权值为 –a[s[i]] （表示需要的花费） **第三类：**对于10种字符拆出10个点，每个点的权值为 -(b[x]-a[x]) 那么我们可以得到一个关系图 ，对于第一类中的点Pij，如果想要选择Pij，你就必须要选中第二类中的点i和j，对于第二类中的点如果你想选中第i个点，其对应的字符s[i]，那么就必须选中第三类中s[i] 对应的点，因为每个种类的点 ...

看电影 Time Limit: 10 Sec Memory Limit: 259 MB Description 到了难得的假期，小白班上组织大家去看电影。但由于假期里看电影的人太多，很难做到让全班看上同一场电影，最后大家在一个偏僻的小胡同里找到了一家电影院。但这家电影院分配座位的方式很特殊，具体方式如下： 1. 电影院的座位共有K个，并被标号为1…K，每个人买完票后会被随机指定一个座位，具体来说是从1…K中等可能的随机选取一个正整数，设其为L。 2. 如果编号L的座位是空位，则这个座位就分配给此人，否则将L加一，继续前面的步骤。 3. 如果在第二步中不存在编号L的座位，则该人只能站着看电影，即所谓的站票。小白班上共有N人（包括小白自己），作为数学爱好者，小白想知道全班都能够有座位的概率是多少。 Input 输入文件第一行有且只有一个正整数T，表示测试数据的组数。 第2～T+1行，每行两个正整数N,K，用单个空格隔开，其含义同题目描述。 Output 输出文件共包含T行。第i行应包含两个用空格隔开的整数A,B，表示输入文件中的第i组数据的答案为A/B。（注意，这里要求将答案化为既约分 ...

tower Time Limit: 10 Sec Memory Limit: 256 MB Description Nick近在玩一款很好玩的游戏，游戏规则是这样的： 有一个n*m的地图，地图上的每一个位置要么是空地，要么是炮塔，要么是一些BETA狗，Nick需要操纵炮塔攻击BETA狗们。 攻击方法是：对于每个炮塔，游戏系统已经给出它可以瞄准的方向(上下左右其中一个），Nick需要选择它的攻击位置，每一个炮塔只能够攻击一个位置，炮塔只能够向着它的瞄准方向上的某个位置发动攻击，当然炮塔也可以不进行攻击。炮塔威力强大，它可以且仅可以消灭目标位置上所有的BETA狗。出于安全考虑，游戏系统已经保证不存在一个炮塔能够瞄准另外一个炮塔，即对于任意一个炮塔，它所有可能的攻击位置上不存在另外一个炮塔。而且，如果把炮塔的起点和终点称为炮弹的运行轨迹，那么系统不允许两条轨迹相交f包括起点和终点）。现在，选定目标位置以后，每一个炮塔同时开炮，你要告诉Nick，他最多可以干掉多少BETA狗。 Input Output 一行一个整数表示答案。 Sample Input 4 5 　　0 0 -2 0 0 　　- ...

算术天才⑨与等差数列 Time Limit: 10 Sec Memory Limit: 128 MB Description 算术天才⑨非常喜欢和等差数列玩耍。 　有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。 　他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。 　当然，他还会不断修改其中的某一项。 　为了不被他鄙视，你必须要快速并正确地回答完所有问题。 　注意：只有一个数的数列也是等差数列。 Input 第一行包含两个正整数n,m，分别表示序列的长度和操作的次数。 　第二行包含n个整数，依次表示序列中的每个数a[i]。 　接下来m行，每行一开始为一个数op， 　若op=1，则接下来两个整数x,y，表示把a[x]修改为y。 　若op=2，则接下来三个整数l,r,k，表示一个询问。 　在本题中，x,y,l,r,k都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。 Output 输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。 Sample Input 5 3 　1 3 2 5 ...

方格取数 Time Limit: 5 Sec Memory Limit: 64 MB Description 在一个n*n的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。 Input 第一行一个数n；接下来n行每行n个数描述一个方阵 Output 仅一个数，即最大和 Sample Input 2 　1 2 　3 5 Sample Output 6 HINT n<=30 Main idea 给定一个矩阵，取了一个点就不能取上下左右的点了，求能取出的最大价值。 Solution 求的显然是最大权独立集，最大权独立集=总权-最小权覆盖集，对于最小权覆盖集我们用最小割来解。 由于取了一个点，不能取上下左右的点，即i±1 or j±1，那么显然是一个二分图，根据奇偶分类。 然后就是一个最小割的模型，我们左边的点向上下左右的点连边，容量为INF(必然不是割)，然后跑最大流即可。 Code 123456789101112131415161718192021222324252627282930313233343536373839 ...

人员雇佣 Time Limit: 20 Sec Memory Limit: 259 MB Description 作为一个富有经营头脑的富翁，小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,（我们用Ei,j表示i经理对j经理的了解程度），即当经理i和经理j同时被雇佣时，经理i会对经理j做出贡献，使得所赚得的利润增加Ei,j。当然，雇佣每一个经理都需要花费一定的金钱Ai，对于一些经理可能他做出的贡献不值得他的花费，那么作为一个聪明的人，小L当然不会雇佣他。 然而，那些没有被雇佣的人会被竞争对手所雇佣，这个时候那些人会对你雇佣的经理的工作造成影响，使得所赚得的利润减少Ei,j（注意：这里的Ei,j与上面的Ei,j 是同一个）。 作为一个效率优先的人，小L想雇佣一些人使得净利润最大。你可以帮助小L解决这个问题吗？ Input 第一行有一个整数N<=1000表示经理的个数 第二行有N个整数Ai表示雇佣每个经理需要花费的金钱 接下来的N行中一行包含N个数，表示Ei,j，即经理i对经理j的了解程度。（输入满足Ei,j=Ej,i） Output 第一 ...