CQU_HYX-CSDN博客

原创 codeforces 449D

题目给你1e61e6个数，你需要找出有多少子序列，他们的值andand起来为0。思路设f(s)f(s)表示状态为ss，ss中为1的位一定是1，为0的位可能为1的可选数字的个数，g(s)g(s)表示状态ss中为1的位的个数。那么可以由容斥原理得到ans=∑220s=0(−1)g(s)∗(2f(s)−1)ans = \sum_{s=0}^{2^{20}}(-1)^{g(s)}*(2^{f(s)}-1)核

2016-09-03 15:44:53 788

原创 HDU5833

每个数的质因子的大小不超过2000，2000以内质数大概300个。因为要选取若干数，使得他们乘起来是完全平方数，等价于把他们质因数的质数加起来，各质因数质数%2\%2为00考虑每个aia_{i}都是一个列向量，每个ai,ja_{i,j}就是第ii个数的第jj个质因子的次数，那么要求的就是对于每一行都有∑0≤j<nai,j≡0 mod 2\sum_{0 \leq j < n }a_{i,j} ≡ 0

2016-08-15 19:27:04 929

原创 HDU5834解题报告

树形dpdp套路题，但是转移有点麻烦。一个很显然的想法就是先dfsdfs一次把子树搞完，然后再dfsdfs加上其父节点对当前节点的影响。写的略辣眼睛，调试了好久。。dp[0][u],dp[1][u]dp[0][u],dp[1][u]分别表示以u为根，走回来和不走回来的最大值，第一次dfsdfs很简单，普通的套路，第二次的时候，我们先把父亲节点对于即将访问的儿子节点的影响排除掉，再dfsdfs，然后

2016-08-15 19:19:06 1578 2

原创 HDU5829 ntt

题意：给你一个AA数组。你要输出所有的T[k]T[k]。T[k]T[k]是指AA数组的所有子集中前kk大的数的和的和。首先破此题需要以下一些知识。FFTFFT的原理，NTTNTT的板子(P需要是费马素数）假设一个数gg对于PP来说是原根，那么gig^i mod Pmod \space P的结果两两不同,且有 1<g<P,0<i<P1<g<P, 0<i<P,那么gg可以称为是PP的一个原根,归根到底就

2016-08-12 19:37:04 1985 2

原创 2016多校第六场，HDU5793,5794,5795,5798,5800,5802,5803

这场状态不对劲，打的很差，该出的题都没看（莫名卡水题），sb博弈的表也能打错。A题打表也用太久时间，自己的板子都是错的（全世界找板子），还被题目吓住（钦定看不懂就是神题）。队内合作方式有点问题。HDU5793这是个打表很快就能发现等比性质的题。但是赛上我写了个矩阵快速幂（真不知道当时怎么想的）。。。这个题就递推比较劲，此处解释下。要求∑0≤k1,k2,...,km≤n∏1≤j<mCkjkj+1% 1

2016-08-05 20:30:24 1598

原创 2016多校联合第5场部分题解 HDU5780,5781,5783,5784,5785,5787,5791,5792

5780∑gcd(xa−1,xb−1)\sum gcd(x^a-1,x^b-1)这个式子可以把里面拆开成多项式，变式为∑(x−1)∗gcd(1+x+...+xa−1,1+x+...+xb−1)\sum (x-1)*gcd(1+x+...+x^{a-1}, 1+x+...+x^{b-1})然后由于gcd(1+x+...+xa−1,1+x+...+xb−1)=(1+x+...+xgcd(a,b))gcd

2016-08-04 10:24:55 678

原创 codeforces 414C 分治思想运用

这个题很劲啊。搞了我一下午。。大意是：给你一个2n2^n长度的随意的数组，有mm次查询，每次从左到右把数组依次分成长度为qiq_{i}的块，将其reversereverse，问每次翻转之后逆序对数多少比较难想的一道题。有些逆序对的结论很显然，设一段区间segseg的逆序对数为aa那么翻转这个区间之后的逆序对数为C2|seg|−aC_{|seg|}^2-a当然不能有重复的数出现，如果有重复的数出现，还

2016-07-29 20:13:53 474

原创 2016多校第四场 HDU5769

给你一个字符xx和一个串ss，让你找ss有多少不同的子串包含字符xx设s1,s2s_{1},s_{2}，当其长度不同或者某位字符不同则不同。此类题一般都是要枚举一维，然后往后找，每次加前面未出现过的新串。为了方便去重，这道题可以先用后缀数组处理出来sa,heightsa,height数组。然后从字典序小的开始往大的找。把xx出现的位置丢进可变长数组vv，可以构成合法串的开始位置就是xx的位置idid

2016-07-29 14:38:00 496

原创 2016多校联合第四场 HDU5768

给你[l,r][l,r]区间，问有多少数，是77的倍数，并且modmod任何p[i]≠a[i]p[i] \ne a[i]容斥容斥+中国剩余定理中国剩余定理。我先吐槽下刘汝佳CRTCRT板子，简直垃圾，太相信板子，半小时的题强行卡我3小时。。分析一下题，再看看数据范围，一眼容斥。设Pi,PjP_{i},P_{j}是两个素数。那么modmod他们分别等于ai,aja_{i},a_{j}的数在[1,lcm

2016-07-28 18:28:32 501

原创 2016多校联合第三场 HDU5760

给你个nn，然后nn个数，你要找到一个最长的序列ss，输出其长度，并且输出不同的ss的个数。ss序列必须是回文的，并且中间最小，往两边依次增大，可以相等。s1s_{1}与s2s_{2}不同当且仅当长度不同或者存在某位s1[i]!=s2[i]s_{1}[i] != s_{2}[i]这个dp比较难。n范围比较小，先把aa数组离散化。方便之后处理。再预处理两个数组pre[i][j]pre[i][j] nx

2016-07-27 17:58:09 734

原创 2016多校联合第三场 HDU5758 Explorer Bo

题目大意: 给定一颗树，每次任意选取两个点，两点之间的所有边被标记，此次操作对答案的贡献为路径的长度；问在最少选取次数的情况下整个树被标记的最小答案。思路：对于第一个问题，最少选取次数显然是(叶子节点+1)/2。对于第二个问题，我们需要根据叶子节点总数的奇偶分类。偶数时：叶子节点必然是两两配对。每一个点由于要标记父节点，除根节点外对于奇数个叶子节点的子树我们只需要延伸一条链，而对于偶数个叶子节点的子

2016-07-27 12:54:17 1015 2

原创 2016多校第三场 HDU 5755

2016-07-26 21:20:03 1005

原创 2016多校联合第二场 HDU5741解题报告

题意：给你一个数组，v[i]v[i]表示：当i为偶数是表示0的个数，当i为奇数是表示1的个数。然后要你查询一堆区间，是否能找到某个区间[l,r][l,r]使得0的个数等于aa,1的个数等于bb题解说的很奇妙，涨了姿势。我们可以这么想，对于一个确定的aa，那么必然存在一段区间[bl,br][b_{l}, b_{r}]那就可以抽象成一连串离散的点集了(设a是横坐标，b是纵坐标设a是横坐标，b是纵坐标)上

2016-07-26 10:12:25 616

原创 codeforces 319C div1 189

题目链接http://codeforces.com/contest/319/problem/C题意：给你一个n表示有n棵树，第一棵树高度一定为1，往后高度一定递增。然后有一个b数组。减少任意一颗树的高度1的话费是b[i]，那么a[i]a[i]一定等于0，并且a[j]>0,j>ia[j] > 0, j > i。这个dp不是很明显。因为第一棵树高度为1，肯定首先砍掉，通过样例我们发现砍第一次不需要cos

2016-07-25 15:42:10 625

原创 2016多校联合第二场 HDU5739 Fantasia 解题报告

这道题当时赛上过的队比较少读了一遍就没怎么管了。赛后仔细想了想感觉并不是特别难做，tarjan的时候对割点进行处理就行了，写的时候才发现细节巨多堪比模拟。题目大意：对于一个带点权的图，定义每个连通分量对图权重的贡献为分量里所有点权的乘积，不同分量之间就求和是整个图总权值。又定义ziz_{i}为删去ii点后图的权值，求S=(∑ni=1i⋅zi)mod(109+7)S= (\sum_{i = 1}^ni

2016-07-22 15:46:59 1236

原创 2016多校联合第二场 HDU5735 Born Slippy 解题报告

此题赛上没注意看，后来补题看了下，发现完全懵逼。。再去看了官方题解，我只想说：出题人收下弱等膝盖。。题目大意：给一颗树，每个点有个权值wiw_{i}。从s点（1）开始走到树上某个点v时会产生一个v1,v2,...,vedv_{1}, v_{2}, ... , v_{ed}的序列然后这条路径的价值然后我们可以任意选取一个子序列v1,v2,...,vedv_{1}, v_{2}, ... , v_{ed

2016-07-22 15:39:00 806

原创 HDU5745解题报告暴力压位

Problem Description Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string p=p1p2…pm. So, he wants to generate as many as possible pattern s

2016-07-22 11:47:10 1352 10

原创 2016多校联合第一场 HDU5731解题报告

题意：给你一个n*m的矩阵，你需要用1*2或者2*1的多米诺骨牌将其全部覆盖，并且使得没有一条横线或者竖线通过矩阵如果不看条件，此题是赤裸裸的轮廓线基础dp，赛场上利用轮廓线把行的情况处理出来，但是列就懵逼了。思路：首先我们用一个数组d[n][m]来存轮廓线dp求出来的值：n行m列的矩阵随意放置全部覆盖的方法数，然后状压竖向分割线，状压之后，把每一块的长度保存下来丢进v数组。然后从小到大枚举行的长度

2016-07-20 16:12:58 1672

原创 UESTC第十四届校赛A题解题报告

太弱，什么都不会（Qrz）给你一个n，然后你要用一个序列构成0到n的所有数（构成方法就是从序列中选若干个数加起来）问你有多少种这样的序列，{1,2,3}和{1,3,2}是相同的序列首先，看下n范围5000，复杂度肯定是n^2打表。然后赛上各种推不出状态。。。其实，肯定有一维状态要表示整个序列的和，那么就是dp[i]，i为整个序列的和的方法数。然后尝试转移会发现很迷茫。。显然再加一维，考虑

2016-04-07 19:32:30 410

原创莫比乌斯反演升级版 HDU 4746

题目意思，给你一个Q，表示有Q组数据，对于每组数据给你三个数n, m, c 设f(i)表示为i的质因数个数,f(1) = 0 你要求出f(gcd(a, b)) <= c的对数思路：如果不考虑任何东西，最暴力最暴力的方法就是枚举a枚举b然后一个一个试，当然这么不行的。我们需要用到Mobius函数优化下运算速度,设B(i) 为 i | gcd(x, y)的对数设A(i)

2016-03-23 23:26:23 431

原创 HDU 1487高斯消元

2016-03-17 00:16:31 434

原创 Codeforces 45C

一道比较好的题，虽然不难，不过该考察的细节都考察了，不容易ac 很显然的概率dp dp[i][j] 表示前i个区间，选取了j个区间有首位为1的概率，然后答案就是求和。坑点1：统计数位的时候，细节很多稍不注意就弄错。坑点2：统计数位的时候，用Ull才能防止1e18*10爆炸坑点3：要统计首位为1的区间为0的情况坑点4：概率是求和，而不是dp[i][j] = max(dp[i-1][j

2016-03-13 22:05:54 369

原创 HDU 1818 RP problem解题报告

一开始，我想的是建一个矩阵，然后尽量多的乘，做快速幂，做到后面会自然稳定，但是没去实现，考虑到一个问题，每个点的出度不一样，所以不是简单的求和，而且后面改边又要做矩阵快速幂，会tle。后来学了发高斯消元，这道题充分利用了高斯消元的性质，因为改边只会影响最后一列，所以改一次边，就再在矩阵后面添加一列，增光。最后，只需要枚举到底选取哪一列能使得答案最优就行了。//// Created by

2016-03-07 23:49:37 363

原创 UVA11741 轮廓线动态规划（矩阵加速）

本来我以为看了刘汝佳的讲解之后我已经懂了轮廓线dp，直到做了这道题，才发现，你认为你懂了一种思想，只是你没有更深的了解和应用这种思想而已。做了这道题，终于比较懂原理了，对矩阵的用法也加深了好多，同时明白了，动态规划中状态的转移和图论有着很相似的地方。每个状态可以达到的状态连一条边，如果在某个阶段，存在一种转移方式，所有的状态都按照这种转移方式来转移，那么就可以把这种转移方式存到图上，一般用矩

2016-03-02 00:59:17 413

原创利用动态规划将逻辑函数化简到最简形式

2016-02-29 22:58:01 1094

原创南京2013区域赛C题，HDU4804

* 队友用dfs过了，回来学了发轮廓线dp，现学现卖。* **看过轮廓线后，觉得这玩意儿好神奇，写起来比dfs顺手多了，虽然两者的思想其实都是差不多的，都是从一个合法状态通过边转移到另一个状态，dfs难写，长，轮廓线好写，容易写错。思路必须要清晰。不说废话了，轮廓线的经典之处在于每次枚举旧的状态。通过旧的状态走到新状态的时候，旧的状态先左移一位，再建立新状态，

2016-02-28 23:40:32 610

原创 ZOJ3537 解题报告及总结

题目意思就是给你一个多边形，先判断是否是凸包，然后再划分成一个一个三角形，求最小代价，两点之间画一条线的最小代价为 abs(xi + xj) * abs(yi + yj) % p才做的时候，想法是枚举划分的线，根据分治的思想，大的多边形拆成两个小多边形，然后记忆化，复杂度超高难写不说（因为要记录i节点的nxt节点编号，不停地变来变去），还不知道wa在哪。。后来想了下，既然最后一定是一个一个的三

2016-02-25 20:01:46 478

原创 HDU 4518 解题报告

1到1e11的斐波那契数很少，显然可以预处理出来。然后枚举这些数，假设其为k，那么可以利用二分数位dp去查找第k个F数，calc（x)就是要求出1-x有多少个F数。这里的问题是，怎么表示状态。因为斐波那契数是字符串，而且数位dp是一个字符一个字符加上去的，无论是用map映射，还是hash数组，都不好转移，我们利用ac自动机里面，每个单词的结尾部分的节点值就表示这个单词，那么状态就完美解决

2016-02-02 21:57:33 399

原创 HDU 4560解题报告

根据题目的意思，我们设比赛场次为c，二分这个场次，然后建边跑网络流，看看最后流量能不能等于n*c即可。建边是最难得地方。。源点s，汇点t 因为每个人要演出c次，那么s向每个歌手连一条容量为c的边。把每个流派拆成两个点k, k’点分别表示擅长和不擅长的点那么每个歌手向k和k’都连一条容量为1的边，表示每场次演唱一首歌。然后k’点向k点连一条容量为C（限制）的边，表示整个演唱场次下

2016-02-02 21:50:17 310

原创 codeforces132C

题意：有个乌龟在一条线上走，初始位置为1 给你一串FT字符串代表指令，F代表朝着当前前进的方向走一步，T代表转向，再给你转换次数n，每次可以把T变F，F变T，同一个指令可以变多次问你在转换了n次的情况下，走的最远距离（假设初始位置为0，最远左边为o则答案为abs(o - 0)）很恶心的dp dp[i][j][k][l] 已经执行了i指令，已经改变了j次，当前位置为k，朝向为l是否合法

2016-01-22 23:36:58 437

原创 codeforces 258B

很经典的思路啊，比赛的时候没怎么多想，其实还很简单的。题意：有7个party，然后有m个数字，1-m，每个party可以选择其中一个数字，4和7是幸运的字符，每个数字有多个幸运字符比如4447有四个。问你第一个party选的数字的幸运字符个数严格大于其他party选择的数字的幸运字符个数的和的选择方法数。用数位dp预处理出1-m之间幸运字符个数为i数字数为c[i],然后枚举第一个p

2016-01-22 23:29:17 370

原创 codeforces 264B

题意很简单，给你n个严格上升的数字ai，然后你要求出最大的子序列，满足相邻的数字不互质我的思路比较奇葩，首先唯一分解每个ai，然后通过他的质因子来寻找可能出现的转移的地方，然后dp[i] = max(dp[i], dp[k] + 1) 如果直接这样做会tle，然后我们想想，最靠前的边价值越小，不带转移的必要，所以我估算了下概率，舍掉80%的边直接不转移，然后就过了。。//// Crea

2016-01-22 23:24:00 294

原创 codeforces 148E

2016-01-22 23:20:24 567

原创 codeforces 257C解题报告

这破题，开始不知道是算法挂了，和正确答案的差距很小，还以为是精度不够。。题意：有个初始的坐标(0, 0) 然后有n个人的坐标(xi, yi) 你的任务就是求出最小的扇形的角度，覆盖所有的人，扇形r无限大一开始直接atan2(y, x)求出角度，然后加PI排个序，最大减最小输出，wa到死。这题该先存下角度，然后排个序，在枚举最接近的两个点，假设这两个点之间的扇形区域就是我们求的区域的补，那么只需

2016-01-22 23:17:12 337

原创寒假第二弹之莫比乌斯反演

以我个人的理解，容斥其实是一种特殊的莫比乌斯反演，莫比乌斯反演是容斥的推广应用。在容斥中，常常需要判断某些值是加还是减，且复杂度很高，但是用莫比乌斯反演函数往往能很快的解决这类问题。具体的莫比乌斯反演的初级内容见acdreamer的博客http://blog.csdn.net/acdreamers/article/details/8542292此处提出莫比乌斯反演的两个公式和重要推论![重要

2016-01-13 22:04:29 418

原创 FFT总结

FFT，快速傅里叶变换，其实也没那么神秘，就是一种变换方式罢了。在音频视频传送中有很多应用，此处不赘述，只谈谈其在算法竞赛中的用途。FFT，一般用来快速乘，当然还有些其他应用。比如给你a，b，两个数，他们很大，超过了10w位，n^2的乘法就显得太慢。而FFT就是能nlogn时间解决此类问题的算法。对于一个多项式A(x) = a0+a1*x+a2*x^2+...+an-1*x^(n-1)这种是

2016-01-12 16:25:58 704

原创 HDU 3021题解

因为树的收益超过了木桩消耗的三倍，所以如果有树能够被围住，那么把这个树围住收益肯定最优。所以先来一次凸包求出木桩最大维护多边形。然后枚举树，把在多边形内的树添加到inS里面,接下来就是找到包围inS集合里面所有树的最小环了。我们发现规定方向就可以用floyd找到最小环，我在这里规定逆时针方向为正，在原来木桩的点的集合，任取两个点出来，如果i -> j边在inS里面所有点的右边，或者点在边上，就连

2015-12-22 08:49:47 473

原创 HDU3240题解

分析：一看就知道是卡特兰数卡特兰数的公式：令h(0)=1,h(1)=1，catalan数满足递推式[1] ：h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n>=2)例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

2015-12-20 21:03:35 560

原创 HDU 2588题解

分析：要求到给出的n中，小于等于n与n的最大公约数大于等于m的对数，因为n特别大，xjb暴力显然不行的。发现我们可以枚举出大于等于m的最大公约数k，算出有多少个(x, n)=k，求和就是答案。由于最大公约数确定后，用n除以k，由高斯定理知道，剩下的数的个数就是在n中k的倍数的个数，由于不能让k改变，所以求出剩下的数和n/k互质的数的个数，即1~n/k中与n/k互质的数的个数。

2015-12-20 19:17:41 362

原创 UVA 10559解题报告

一般的动态规划题，都是当前的决策不会影响到未来。而这类动态规划的题目中，当前的决策是会影响到未来的，并且这道题中，不仅仅是当前的决策影响到未来，因为价值是加起来的平方，所以以前的决策会和现在的决策一起影响未来的。因此不能简单的把之前的决策的影响在以前就消去，而是多开一维状态来记录之前的影响。 dp[l][r][k]表示要消去l,r的小方块，并且剩下k个和col[r]颜色相同的方块留给未来使用的最

2015-12-06 22:13:51 419

空空如也

空空如也