题目大意：有N(<=10)个人，需要把X*Y的蛋糕切成N等份，每次只能横／竖切一刀。求最大的长宽比的最小值。其中矩形的长宽比为长边与短边的比值。 https://ac.nowcoder.com/acm/problem/20272 数据比较小，N只有10，直接用了个dfs就解决了。考虑XY的蛋糕切成N份，子问题是max((X1/N)Y切成1份，(X(N-1)/N)*Y切成N-1份)等等的最小值。 不是很确定的复杂度分析:T(n)=4(T(1)+...+T(n-1))=>T(n)=T(n-1)+4T(n-1)=5*T(n-1)=>T(n)=5^n int X, Y; int N;...

题目大意：有一个矩阵，每行独立玩一个游戏，每次可以从头／尾取一个数并乘以2^i，希望总和最大。要求每行的总和最大值的和。矩阵很小(n,m <= 100)。 https://ac.nowcoder.com/acm/problem/16645 其实很简单，就是区间DP，每行单独做即可。考虑这一行第i到j个元素能组成的最大总和，那么dp[i, j] = max(2^1 * nums[i] + 2 * dp[i + 1, j], 2^1 * nums[j] + 2 * dp[i, j - 1])。 时间复杂度是O(r*c^2)。注意会爆long long，我用了__int128护体。 typed...

题目大意：有一个数组，每次询问数组的第L个到第R个数和某个数x的xor的总和最大的那个x。 https://ac.nowcoder.com/acm/problem/18979 其实很简单，没个bit可以分开，那么就是要么这个bit不变，要么全部flip，问哪种剩下的1个数多，只要能飞快地知道这一位0和1的个数就知道该不该flip了。用一个前缀和就可以存[0, R]的1的个数，那么就很容易知道[L, R]的1的个数，0的个数就是(R - L + 1)减去1的个数。 int N; #define MAXN 100005 int a[MAXN]; int Q; int L, R; #define M...

题目大意：给定一个数组，有N*(N+1)/2个子序列，这些子序列总共有多少个逆序对？ 对于没个arr[i] > arr[j], i < j，在总个数的贡献是(i + 1) * (N - j)。所以基本就跟算逆序对个数这个问题是一样的，无非就是在merge的时候不是算个数的总和而是算(N - j)的总和。这里我偷懒，直接用sort进行了merge时的排序，照说应该用inplace_merge或者是手写一个merge之类的。所以我的时间复杂度是O(nlog^2(n))，应该是O(nlog(n))就可以了。 然后WA了无数次，只好看看大神们的题解，原来是爆long long，所以换成了_...

https://ac.nowcoder.com/acm/problem/23413 题目大意：N次独立的赌博，每次要花3元，等可能赚1，2，3，4，问保本概率。 比较简单的技术DP，只需要知道每种总和的选法即可。状态转移也比较直接。 //Pr[X1+...Xn>=3*n] #include <iostream> #include <vector> using namespace std; long long gcd(long long x, long long y) { if (x > y) return gcd(y, x); if (x...

题目大意：Nx2列的扫雷，第二列没有雷，并且第二列每个数代表周围八个里面有多少雷。给定第二列的数，问有几种排法。 https://ac.nowcoder.com/acm/problem/20241 很经典的状态压缩DP。可以认为有一个01数组，然后知道每连续三位的总和。问有多少种方法。 ==== 仔细一想，其实如果知道第一第二个是多少就可以依次推出所有的雷，所以直接就是4*N次。答案最大也就是4（估计还达不到）。 int N; #define MAXN 10005 int cnt[MAXN]; ll dp[2][2][2]; ll doit() { // dp[i][curr][nxt] ...

https://ac.nowcoder.com/acm/problem/18386 题目大意：选取字符串最长的包含所有小写字母的substring的长度。 比较简单，用sliding window即可，维护一个left和right区间，每次right尽量伸长，left再减少一位。 #define MAXN 1000005 char s[MAXN]; int doit() { int n = strlen(s); // [l, r). int l = 0, r = 0; int ans = n; u_m<char, int> counter; while (l...

题目大意：有很多物品，每个物品有一个价值和deadline，放入每个物品需要1 unit time，最多可以购买多少总价值。 https://ac.nowcoder.com/acm/problem/50995 看了一下我的做法似乎和大家的不太一样，原来和之前某一道题类似是带反悔的贪心。 我的做法，就是将物品按照价值从大到小排序，然后每次将一个物品插入deadline之前最后那个空着的时间。这样应该比较直观是最优解，因为如果某个物品价值比后面都高，而且还能合法的插入，那么就应该选择它比较合算，否则总能替换成该物品。 难点是如何实现找到<=deadline的最大值，并且能删除一个值。刚开始用...

题目大意：有n个盒子，总共有m中可能颜色，问有多少种染色方式，使得相邻的盒子不相邻，且恰好有k中颜色。数据范围n和m都非常大，k不超过1E6。 https://ac.nowcoder.com/acm/problem/13884 如果n和m的范围不大，这题可以用一个DP来完成，即考虑前i个盒子恰好k种颜色的染发。那么(i,k)来自(i-1,k)并且选择这k种颜色中不是i-1的颜色的一种，有k-1种选法；或来自(i-1,k-1)并且选择剩下的m-(k-1)种颜色中的一种，有m-k+1种选法。时间复杂度为O(n*k)。 但是这道题显然要求更快，那么首先想到可以不妨假设选到的k种颜色就是1,2,......

题目大意：将一组物品分成两组，每个物品都可以不出现在任何一组。希望两组的重量差异不超过M，最大化总重量。 https://ac.nowcoder.com/acm/problem/19158 基本就是一个背包问题的变体，对于前i个物品，差异为gap时的最大总重量进行dp即可。转移为(i, gap) -> (i + 1, gap)和(i, gap) -> (i + 1, gap + wt[i + 1])和(i, gap) -> (i + 1, abs(gap - wt[i + 1]))。注意，gap的中间值是可以超过M的，需要给一个比较大的界，比如w1+...+wn。 #defi...

题目大意：一个最多两列最多100行的数字矩阵，从中选出K个不重叠的矩形，他们的数字之和最大是多少？ https://ac.nowcoder.com/acm/problem/20242 看到最多有两列，可以想到关于每一行的状态进行状态压缩DP，可能状态是：空，左边被占用，右边被占用，左右被不同矩形占用，左右被一个矩形占用。需要维护dp[R][S][N]表示到R行为止处于状态S已经使用N个矩形，最大的和是多少（如果不可能该和为-INF)。状态和个数的转移不难求得，比如dp[5][左右被不同矩形占用][用了5个矩形]可以来自dp[4][空][3], dp[4][左边被占用][4]，等等。 int N...

题目大意：一个迷宫里面有src和dst，src每次可以八个方向走一步，dst每次可以走两次，每次只能四个方向，不能走障碍物上。问最少多少次可以相遇。注意可以原地不动。 https://ac.nowcoder.com/acm/problem/23486 这题比较标准的双向BFS，注意可以原地不动。比如考虑这个case: A # # B应该要输出1，而不是NO #define MAXN 2000 int N,M; char grid[MAXN][MAXN]; VPII src_dirs={ {-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {...

题目大意：有n种扑克牌，每种有ci个。还有m张百搭牌。一个套牌是1,2,...,n或者用百搭牌代替其中任一张。最多可以造出几个套牌。 https://ac.nowcoder.com/acm/problem/19916 也许有纯数学的做法，但是能造出k个套牌显然也能造出k-1个套牌，所以feasibility符合单调性。可以使用binary search寻找最大的k，使得可以造出k个套牌。 对于k个套牌，第i中套牌必须使用max(0, k-ci)个百搭牌，而且每个百搭牌只能在一套里出现，所以总和不超过min(m, k)。 bool feas(ll cnt, VL& c, ll m) { ...

题目大意：有一些人可以站在mxn的格子里面，有一些格子不能站人，不能站在相邻格子，有几种站法。 https://ac.nowcoder.com/acm/problem/15034 这题就是一道很基本的状态压缩DP，时间复杂度是O(m2^n2^n)对于m=n=12刚好不会TLE。一开始没注意审题，注意支持多组数据。 ll doit(int n, int m, VI& grid) { int mask_size = (1 << m); VVL dp(n + 1, VL(mask_size, 0)); dp[0][0] = 1; for (int row = 0;...