[综合] 洛谷 P1865 A % B Problem

水题水题 #include<cstdio> #include<vector> #include<cstring> #define_for(i,a,b)for(inti=(a);i<=(b);i++) #defineREP(i,a,b)for(inti=(a)...

[综合] 洛谷 P1338 末日的传说 （字典序 + 逆序对）

这道题需要对排列有深刻的理解和认识给出逆序对的个数，求改逆序对个数的字典序最小的排列那么既然是最小，那么一开始一段肯定是升序，一直到某个数后才开始改变即123……n-1nabcd……类似这样那么我们要求出这个n在哪里要字典序最小，就需要1到n这一段最长也就是说在a,b,c,d后面有尽量多的逆序对当数...

[综合] 洛谷 P1582 倒水 （二进制）

这道题实际上是考二进制 很容易看出杯子水量一定是2的i次方 所以n杯水最后剩下的水一定是n用二进制表示中1的个数 所以就枚举n来求什么时候1的个数小于k 那么这里有个优化，不然会超时 因为每次加的目的是要让1的个数变少，也就是要进位所以每次加上的是lowbit(n) #include<cstd...

[综合] 洛谷 P2152 [SDOI2009]SuperGCD （高精度）

这道题直接写了我两个多小时…… 主要是写高精度的时候还存在着一些小毛病，调了很久 在输入这一块卡了很久。 然后注意这里用while的形式写，不然会炸 最后即使我已经是用的万进制了，但是交上去还是有两个点超时 然后就开始漫长的改进，一直过不了那两个点。 然后突然发现，貌似这道题没有涉及到乘法。 那不就...

[综合] 洛谷 P1414 又是毕业季II （多个数的最大公因数）

这道题其实不难，但是我想复杂了 我想的是把每个数质因数分解，然后每次就枚举每个质因数 来求最小公倍数。 然后想了想这样复杂度将会非常的大，肯定超时然后看了题解发现不需要质因数分解，直接存因数的个数就好了c[i]表示i这个因数出现的次数。然后因为当k越小的时候答案越大（严格来说是大于等于），这是显而易...

[综合] 洛谷 P1134 阶乘问题

一开始只保留最后一位，交上去29 #include<cstdio> #include<cmath> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) #define_for(i,a,b)...

[综合] 洛谷 P1313 计算系数 （二项式定理）

这道题正好复习了二项式定理 所以答案就是a^n*b^m*c(n,k) 然后注意一些细节我一开始写组合数只写一行的组合数即c[0]=1;c[i]=c[i-1]*(n-i+1)/i但是因为要去模，同时式子里面有除法，所以不能用这种方式必须从头来推然后注意组合数推要从0开始 #include<cst...

[综合] Vijos 1456 最小总代价 （状压dp）

看到这道题n只有16，就可以想到状压dp 每个人只有经过或者没经过，那就用1表示经过，0表示没经过 但是不是当前在谁那里，所以再加一维来记录 所以f[state][i]表示在物品在i，当前的状态是state情况下的最小总代价 有几个细节要注意 （1）刷表法。要提前初始化为-1，然后然后每个起点为0...

[综合] Hdu 1429 胜利大逃亡（续） （bfs+状态压缩）

这道题的钥匙只有10个，可以压成二进制 这里有有句非常关键的话 (k&door[x][y])==door[x][y] 一开始以为只要(k&door[x][y])==1就可以了 后来发现如果door[x][y]为0的话，这句话就不对了。 所以要包含这里没有门的情况 所以要这么写 #in...

[综合] poj 3254 Corn Fields （状压dp）（棋盘dp）

状压dp入门题 因为当前行的状态只和上一行有关 所以可以一行一行来做 因为m<=12所以可以用二进制来表示放了或者没有放 0表示没放，1表示放 f[i][state]表示第i行状态为state的方案数 f[i][state]=sum(f[i-1][state']) 枚举行，然后枚举这一行和上一...

[综合] POJ 1185 炮兵阵地 （状压dp）（棋盘dp）

这题和poj3254很像，但是更复杂了一些 都属于棋盘里放东西，然后又各种各样的限制，然后求方案或者最大值 （1）上一道题距离要大于1，这道题是大于2。所以判断的时候变成 !(x&(x<<1)||(x&x<<2)) 然后关于有效状态数，可以自己输入最大的数据，...

[综合] poj 3311 Hie with the Pie （状压dp） （Tsp问题）

这道题就是Tsp问题，稍微加了些改变 注意以下问题 （1）每个点可以经过多次，这里就可以用弗洛伊德初始化最短距离 （2）在循环中集合可以用S表示更清晰一些 （3）第一维为状态，第二维为在哪个点，不要写混。 （4）在dp过程中0这个点是不用的，只用到1到n这个点 而实际上dp过程中用的是0到n-1，所...

[综合] HDU3001 Traveling （状压dp+三进制+Tsp问题总结）

（1）这道题最多可以走两次，所以有0，1，2三种状态，所以我们要用三进制 如果要用三进制，就要自己初始化两个数组，一个是3的n次方，一个是三进制数的第几位的数字是什么 voidinit() {three[0]=1;REP(i,1,11)three[i]=three[i-1]*3;REP(i,0,th...

[综合] poj 2288 Islands and Bridges （状压dp+Tsp问题）

这道题千辛万苦啊！ 这道题要涉及到当前点和前面两个点，那就设dp[state][i][j]为当前状态为state,当前点为i，前一个点为j 这个状态表示和之前做炮兵那题很像，就是涉及到三个点时，就多设一维表示前一个点（炮兵那题把点换成行） 这道题有很多细节需要注意 （1）计算路径长度。这道题一开始怎...

[综合] zoj 3471 Most Powerful（状压dp+Tsp问题+连续性问题）

上来直接一波敲键盘，直接套Tsp问题的代码 然后WA 发现貌似这道题没有连续性。 Tsp问题是一条路径，一个点到另一个点，多了一个限制，所以就需要加多一维 而这道题没有限制，也就是说那一维不需要加，我加了还WA 然后要搞清楚状态，在纸上可以写，写清楚了再敲代码 这道题一开始都是存在，初始状态是000...

[综合] poj 2663 Tri Tiling （状压dp+多米诺骨牌问题+滚动数组反思）

本来直接一波状压dpAC的 #include<cstdio> #include<cstring> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) #define_for(i,a,b)f...

[综合] poj 3420 Quad Tiling （状压dp+多米诺骨牌问题+矩阵快速幂）

还有这种操作？？？？？？ 直接用pre到now转移的方式构造一个矩阵就好了。 二进制长度为m，就构造一个长度为1<<m的矩阵 最后输出ans[(1<<m)-1][(1<<m)-1]就好了 牛逼！ #include<cstdio> #include<...

[综合] 二分总结

二分分为二分查找和二分答案。 设数组下标为1~n 二分查找。实际上就是一个有序数列中有一个解，然后搜一遍求这个解。而直接for循环暴搜一遍的话时间复杂度是O（n），而用二分查找可以降低时间复杂度，为O（logn）；而数组形象化出来的话就是0000010000000（0为无解，1为有解），二分就是要找...

[综合] 倍增算法总结 （ 含RMQ模板）

部分题目来自《算法竞赛设计进阶》 问题 给定一个长度为n的数列A，有m个询问，每次给定一个整数T，求出最大的k，满足a[1]，a[2]……a[k]的和小于等于T（不会打sigma） 第一反应是二分，这个时候的复杂度是logn 还有第二种解法，用倍增的思想，复杂度为logk（所求答案）。显然倍增要好...

[综合] LCA题集

点的距离（模板题） 树中两点间的距离就是d[u]+d[v]-2*d[lca(u,v)] #include<bits/stdc++.h> #defineREP(i,a,b)for(registerinti=(a);i<(b);i++) #define_for(i,a,b)for(re...