BUPT2017 wintertraining(15) #5A HDU 4456 题意 给你一个n行n列的格子,一开始每个格子值都是0.有M个操作,p=1为第一种操作,给格子(x,y)增加z.p=2为询问与格子(x,y)的曼哈顿距离不超过z的格子值的和. (1 ≤ n ≤10 000, 1 ≤ m ≤ 80 000)  题解 这道题如果数据不大,那就可以直接用二维的树状数组来做. 方法1:二维树状数组 因为数据比较大,所以要离线处理并且离散化一下修改的值,再用二维树状数组: 查询的是菱形,我们把

题意:给一个矩阵,两种操作1:修改单点的权值,2:查询和某个点曼哈顿距离小于r点的权值和 题解:先旋转坐标轴,(x,y)->(x-y,x+y)然后就变成了cdq分治裸题,子矩阵和和单点修改一维时间,二维xcdq,三维ybit //#pragma GCC optimize(2) //#pragma GCC optimize(3) //#pragma GCC optimize(4) //#pragma GCC optimize("unroll-loops") //#pragma co

hdu 5618 Jam's problem again #include <bits/stdc++.h> #define MAXN 100010 using namespace std; int n,k,T,xx; int ans[MAXN],c[MAXN],f[MAXN]; struct Node{ int x,y,z,id; }a[100010],b[100010]; inline int read(){ char ch; bool f=false; int res=0; while (

[题目链接] http://acm.hdu.edu.cn/showproblem.php?pid=3507 [题目大意] 将长度为n的数列分段,最小化每段和的平方和. [题解] 根据题目很容易得到dp[j]=min(dp[k]+(s[j]-s[k])2),因为是从前往后转移,且决策单调,因此在CDQ分治的同时进行分治DP即可. [代码] #include <cstdio> typedef long long LL; const int N=500005; int n,M,t; LL f[N],

[题目链接] http://acm.hdu.edu.cn/showproblem.php?pid=5730 [题目大意] 给出一个数组w,表示不同长度的字段的权值,比如w[3]=5表示如果字段长度为3,则其权值为5,现在有长度为n的字段,求通过不同拆分得到的字段权值乘积和. [题解] 记DP[i]表示长度为i时候的答案,DP[i]=sum_{j=0}^{i-1}DP[j]w[i-j],发现是一个卷积的式子,因此运算过程可以用FFT优化,但是由于在计算过程中DP[j]是未知值,顺次计算复杂度是O(

题目链接:hdu 3842 Machine Works 详细题解: HDU 3842 Machine Works cdq分治 斜率优化 细节比较多,好好体会一下. 在维护斜率的时候要考虑x1与x2是否相等,这里要处理一下. #include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; typedef pair<int,ll>P;

Shell Necklace Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 647    Accepted Submission(s): 287 Problem Description Perhaps the sea‘s definition of a shell is the pearl. However, in my view,

Sean owns a company and he is the BOSS.The other Staff has one Superior.every staff has a loyalty and ability.Some times Sean will fire one staff.Then one of the fired man’s Subordinates will replace him whose ability is higher than him and has the h

这就是一个三维排序的问题,一维递减,两维递增,这样的问题用裸的CDQ分治恰好能够解决. 如同HDU 4742(三维排序,一个三维都是递增的) 由于最小字典序比較麻烦,所以要从后面往前面做分治.每一个点的dp值表示以这个点为起点.最长能够延伸多长. 本来是想依照Li排序,可是这样做在cdq的时候实在是太难以处理了.所以就依照idx排序.也就是不须要排序. 然后依照Ri排序,对于左边,保证右边的每一个R值大于左边的值.并用树状数组维护Li(由于Li须要递减.所以树状数组恰好能够维护右边的Li小于左边

Mr. Zstu and Mr. Hdu are taking a boring class , Mr. Zstu comes up with a problem to kill time, Mr. Hdu thinks it’s too easy, he solved it very quickly, what about you guys? Here is the problem: Give you two sequences L1,L2,...,Ln and R1,R2,...,Rn. Y

题意:一段长为 i 的项链有 a[i] 种装饰方式,问长度为n的相连共有多少种装饰方式 分析:采用dp做法,dp[i]=∑dp[j]*a[i-j]+a[i],(1<=j<=i-1) 然后对于这种递推式,也就是dp[i]等于前j个dp数组和a数组的卷积,然后可看所有的 一看n是1e5,所以暴力超时,然后采用cdq分治加速,这种卷积递推通常采用cdq分治加速 cdq的话很简单了,就是先递归左边,算左对右的贡献,递归右边就行,一半一半更新 #include <cstdio> #inclu

题意:给你1e5个点(x,y,z),对于每一个点询问有多少个点(x1,y1,z1)满足x1<=x&&y1<=y&&z1<=z 分析:(官方题解奉上)很显然让你找(x,y,z)(x,y,z)都大于别的(x,y,z)(x,y,z),当然厉害的人可以用树套树水一下,但正解写的是CDQ分治,以xx为第一关键字排序,以yy为第二关键字来找,以zz为第三关键字建一个树状数组找就好了,当然等于的情况可以实现前做一下. #include <cstdio> #i

题目链接 给n个操作, 第一种是在x, y, z这个点+1. 第二种询问(x1, y1, z1). (x2, y2, z2)之间的总值. 用一次cdq分治可以将三维变两维, 两次的话就变成一维了, 然后最后一维用树状数组维护. 对于每个询问, 相当于将它拆成8个点. 注意第二次cdq分治的时候l可能小于r. 所以这里的return条件是l <= r而不是l == r. 找了好久... #include <bits/stdc++.h> using namespace std; #defin

题目链接 dp[n] = sigma(a[i]*dp[n-i]), 给出a1.....an, 求dp[n]. n为1e5. 这个式子的形式显然是一个卷积, 所以可以用fft来优化一下, 但是这样也是会超时的. 所以可以用cdq分治来优化. cdq分治就是处理(l, mid)的时候, 将dp[l]...dp[mid]对dp[mid+1]...dp[r]做的贡献都算出来. #include <bits/stdc++.h> using namespace std; #define pb(x) pus

题意:给n个点,求每一个点的满足 x y z 都小于等于它的其他点的个数. 析:三维的,第一维直接排序就好按下标来,第二维按值来,第三维用数状数组维即可. 代码如下: cdq 分治: #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #

Pinball Game 3D Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1137    Accepted Submission(s): 477 Problem Description RD is a smart boy and excel in pinball game. However, playing common 2D

Jam's problem again Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 640    Accepted Submission(s): 210 Problem Description Jam like to solve the problem which on the 3D-axis,given N(1≤N≤100000)

题意:给定N个组合,每个组合有a和b,现在求最长序列,满足a不升,b不降. 思路:三位偏序,CDQ分治.   但是没想到怎么输出最小字典序,我好菜啊. 最小字典序: 我们倒序CDQ分治,ans[i]表示倒序的以i为结尾的最长序列,如果当前的ans[i]==目前最大,而且满足序列要求,就输出. #include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; ; int q[maxn]

Do you like painting? Little D doesn't like painting, especially messy color paintings. Now Little B is painting. To prevent him from drawing messy painting, Little D asks you to write a program to maintain following operations. The specific format o

Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough. Suppose the shell necklace is a sequence of