【题目描述】风见幽香非常喜欢玩一个叫做 osu!的游戏，其中她最喜欢玩的模式就是接水果。 由于她已经DT FC 了The big black, 她觉得这个游戏太简单了，于是发明了一个更加难的版本。首先有一个地图，是一棵由 n 个顶点、n-1 条边组成的树（例如图 1给出的树包含 8 个顶点、7 条边）。这颗树上有 P 个盘子，每个盘子实际上是一条路径（例如图 1 中顶点 6 到顶点 8 的路径），并且每个盘子还有一个权值。第 i 个盘子就是顶点a_i到顶点b_i的路径(由于是树，所以从a_i到b_i的路径是唯一的)，权值为c_i。接下来依次会有Q个水果掉下来，每个水果本质上也是一条
【题目描述】小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。 例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。 现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。 【输入】第一行包含两个整数N,Q，表示星球的数量和操作的数量。星球从1开始编号。 接下来的Q行，每行是如下两种格式之一： A x y 表示
题目描述给定一棵n个点的树，点带点权。 有m次操作，每次操作给定x,y，表示修改点x的权值为y。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 输入输出格式输入格式： 第一行，n,m，分别代表点数和操作数。 第二行，V1,V2,...,Vn，代表nn个点的权值。 接下来n−1行，x,y，描述这棵树的n−1条边。 接下来m行，x,y，修改点x的权值为y。 输出格式： 对于每个操作输出一行一个整数，代表这次操作后的树上最大权独立集。 保证答案在int范围内 输入输出样例输入样例#1： 复制10 10
-11 80
原题地址 感觉还是很妙一个题，自己想了一会，看标签后茅塞顿开。发现这个题的操作一直在用数列已经有的部分去覆盖一部分。因为一直在用原来的，有点可持久化的意思。发现其实我只要维护一个数据结构，可以把原来的一段提取出来插入到一个位置，并且可以维护区间加区间和以及可以可持久化即可，这里的可持久化是为了不影响原来已有的部分，对于所有的修改都在新点上操作。这样的数据结构就只有可持久化平衡树了。非旋Treap的可持久化和线段树差不多，只要有修改的地方拉一个新点起来就行了。时间复杂度O(n log n)，空间常数很大，注意不要爆空间。#include<cstdio>
#include<alg
题目链接：https://loj.ac/problem/2537 考虑到题目是一颗二叉树，有一个简单的O(N^2)的DP做法。f(i,j)表示i号点取值为数集中第j大数的概率，每一次我们从子树合并上来。j被取到有两种情况：j更大并且当前选择的是最大值 j更小并且当前选择的是最小值分情况讨论，发现要转移需要一个选到比j小的值的概率和(比j大的可以直接用1减比j小的)。那么我们维护两个前缀和(对两边的元素分别计算)，即可完成一次合并。 如何优化这个算法呢？假设两边子树可以产生的j值集合分别为A，B。考虑A值域上这样连续的一段数：满足不存在B[i]使得A[l]<=B[i]<=A
题目描述 输入输出格式输入格式： 第一行有一个整数N(3<N<2000)，表示登陆地带的大小是2×N。随后的两行每一行有N个整数（其绝对值不超过10^6），表示对应的矩形土地的适用度评估值，各个整数之间用一个空格隔开。 输出格式： 只有一行输出，为整数M，即所确定的实验基地的适用度。 输入输出样例输入样例#1： 复制4
-1 2 -3 4
5 6 7 8 输出样例#1： 复制31 不知道为什么N会是2000而不是10^6。这道题
题目描述为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。 如果把公园看成一个M*N的矩形，那么花坛可以看成一个C*D的矩形，绿化带和花坛一起可以看成一个A*B的矩形。 如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么， 绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度 为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。 输入输出格式输入格式： 第一行有6个正整数M,N,A,B,C,D 接下来一个M*N的数字矩阵，其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度
题目描述有一个长度为n的字符串，每一位只会是p或j。求一个最长子串，使得不管是从左往右还是从右往左取，都保证每时每刻已取出的p的个数不小于j的个数。(1≤n≤1 000 000) 输入输出样例输入样例#1： 复制6
jpjppj 输出样例#1： 复制4 遇到个数有关的问题首先把j看做-1，p看做1。这样就是要从左往右从右往左每个位置的前缀和都非负，处理原数组[前/后]缀和为pre[i]、suf[i]。 考虑对于位置i，先分别处理i向右最长能延伸到的地方和向左最长能延伸到的地方，记为R[i]和L[i]。这就相当于找到
Sylvia是一个热爱学习的女孩子。 前段时间，Sylvia参加了学校的军训。众所周知，军训的时候需要站方阵。 Sylvia所在的方阵中有 n×m" data-mce-tabindex="0">n×m 名学生，方阵的行数为 n" data-mce-tabindex="0">n，列数为 m" data-mce-tabindex="0">m。 为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从 1" data-mce-tabindex="0">1 到 n&a
地址：https://loj.ac/problem/2585 说一说我和这道题的故事吧。APIO2018现场：和moonzero在一个考室，前一天才好不容易会使用linux系统后一天就要上考场了，非常的方。打开problems，首先映入眼帘的便是 A.新家。毫不犹豫先打了5分暴力，然后去打了T3，T2的暴力。回头来准备肝T1，发现自己会Subtask2的7分暴力。然后死也没调出来，400个set把自己送胸牌了。下来moonzero告诉我他更窒息，写了400个splay………………嗯，叙旧就叙到这里了，前几天又想起这道题，发现有了思路。接下来我们来看看APIO这道亲民的码农题的做法吧。首先我们容
Rockdu's Blog