最优题解 可以发现，每次牛牛所在格子的列数必定+1，则在当前格子的方案数只与上一格3个格子的方案数有关。所以用表示从(1,1)到(i,j)的方案数，如果(i,j)有障碍物那么方案数就是0，否则等于走一步能到达它的格子的方案数的累加。因为是按列推进的，所以为了cache友好，把第一维作为列，第二维作为行时间和空间复杂度都是 int dp[100005][3];//dp(i,j)表示从(1,1)到(j+1,i)的方案数。 int vis[100005][3]; int solve(int n, int m, vector<int> &x, vector<int> &...

最优解 考虑动态规划用表示牛牛到第层的方案数，则等于所有的和，满足：因此可以使用f数组的奇数项的前缀和和偶数项的前缀和进行转移。因为f数组中需要的只是的值，所以f值可以在计算的过程中只用临时变量存储。实际存储的值是和，其中表示所有i为偶数的的和,表示所有i为奇数的的和，那么实际上就等于。对于积水的台阶，因为保证a是以升序给出，所以用一个指针维护下一个积水的台阶就可以不使用额外空间去记录积水台阶了。空间复杂度，时间复杂度 int solve(int n, int m, vector<int>& a) { int mod = 1e9 + 7; i...

最优题解 因为是一个环，所以可以把整个数组复制一份加在后面来为每个位置选择最优决策点。问题等价于求：选取最长的一段没有重复的数字定义dp(i)的含义：设截取的段以第个珠子为右端点的话，它的左端点至少要大于对于位置i的珠子，这个位置要么单独一个珠子作为一段，要么会和第个珠子连在一起，所以同时要保证这个颜色的珠子是唯一的，所以要记录每个颜色最后一次出现的位置last[x]，所以在dp的过程中记录答案即可。需要map存放每个数字最后一次出现的位置，空间复杂度时间复杂度取决于如何记录每个数字最后一次出现位置，使用map存则每次查询时间复杂度,总的时间复杂度。若是使用unordered_map或是哈希表...

最优解法 解法1：动态规划用表示以位置为结尾，长度大于等于的所有子段中最大的子段和。那么考虑转移：以位置为结尾的大于等于k的子段分为两种： 长度刚好等于，这种情况下最大子段和等于这个数字的和 长度大于，这种情况下最大子段和等于 需要前缀和数组和dp数组辅助求解，空间复杂度，时间复杂度 long long dp[100005]; long long sum[100005]; long long solve(int n, int k, vector<int> &a){ assert(a.size() == n); memset(dp, 0, sizeof d...

最优题解 考虑动态规划，用表示所在位置横坐标不超过,纵坐标不超过的情况下用掉把钥匙最多可以获得多少金币。那么这个地方如果使用钥匙，那么最多可以获得 这么多的金币。如果不使用钥匙的最大值就是此处的dp值。两者取其大。时间复杂度和空间复杂度都是 int dp[505][505][6]; int mp[505][505]; int solve(int n, int k,vector<int> &x, vector<int> &y, vector<int> &a){ memset(dp, 0, sizeof dp); mems...

最优解法 可以发现，每一列能拿到的最多金币数取决于他上一列拿了多少金币。考虑动态规划用代表位于第i列第j行最多可以赚多少金币，那么对于它可以被更新（如果对应的格子在跑道内）。时间复杂度因为需要开dp辅助数组。空间复杂度 int dp[100005][3]; int solve(int n, vector<int> &a1, vector<int> &a2, vector<int> &a3, vector<int> &m){ dp[0][0] = a1[0];dp[0][1] = a2[0];dp[0][2]...

普通解法 可以发现，如果可以兑换出张票，那么[1,x]张票都可以兑换出。如果不可以兑换出x张票，那么[x,inf]张票都不可能兑换出。所以这个答案是满足二分性质的。我们二分这个答案，考虑检查x张***是否可以兑换出来。如果要换x张票，如果气球数量大于x，它就可以用于兑换其他气球。否则它需要被其他气球补全。所以按照这个逻辑去检查是否可行即可。 int solve(int a, int b, int c){ int l = min(min(a, b), c); int r = max(max(a, b), c); int ans = l; while(l <=...

最优题解 存下每个点可以直接到达的点，形成一棵树。如果我们简单的每次发生提升的直接遍历这个点可以到达的点，那么当每次找的点的度数都很大的时候，会超时。（比如节点1有20000个儿子，节点1发生了100000次提升）但是我们可以先存下每个节点提升的次数，最后再整个遍历一遍来求出答案。这样每个点只会被父亲访问一次，时间复杂度。因为需要存下每个点可以到达的点，以及预存次数，空间复杂度 vector<int> g[200005]; int a[200005], d[200005]; void dfs(int u, int fa){ d[u] += a[u]; d[fa] += a[...

普通解法 每次交换直接交换。每次查询都暴力匹配，存下现在可能的最长公共前缀长度len然后对于每个新串只要匹配前len个字符即可。时间复杂度。显然这个时间复杂度不足以通过此题。 vector<int> solve(int n, vector<string>& s, int m, vector<int> &op, vector<int>& l, vector<int>& r) { vector<int> ans; for(int i = 0; i < m; ...

最优解法 对于一次旋转操作，可以通过递归去旋转它的每个儿子。但是显然这么做会超时。注意到对一个结点的操作作用于它的所有子节点，而在它的某个子节点再操作一次这整个子节点为根的子树就可以消除掉之前的一次旋转。所以可以通过给结点打懒标记的方式去控制旋转。最后进行中序遍历的时候如果当前结点被标记过，那么把它的两个儿子也标记起来，并交换两个儿子。时间复杂度因为需要懒标记数组，所以空间复杂度 int ch[100005][2]; int lz[100005]; void dfs(int u, vector<int> &ans){ if(u == 0) return; i...

最优解法 考虑对所有X国的单词建立字典树，并且字典树上存储对应的牛客单词的下标而不是存整个单词。查询的时候直接在字典树上查询就可以了。建树时间复杂度,查询复杂度，所以总的时间复杂度为。空间复杂度为建立字典树需要消耗的空间，为 int ch[500000][26]; int to[500000]; vector<string> solve(int n, vector<string> s, vector<string> t, int m, vector<string> g){ memset(ch, 0, sizeof ch); me...

普通解法 对于每个方案位置，暴力枚举所有居民位置。时间复杂度,空间复杂度. vector<int> solve(int n, int m, vector<int> a, vector<int> x){ vector<int> t(m); for(int i = 0; i < m; ++i){ t[i] = 2e9; for(int j = 0; j < n; ++j) t[i] = min(t[i], abs(x[i]-a[j])); }return t; }最优解法 首先对所有...

最优解法 用二进制[0~7]代表每一列的种花情况。用代表有列且最后一列的种花情况为，通过枚举有列的最后一列花的情况来转移。可以用滚动数组优化空间复杂度。因为每一列种花情况只有5个状态是有效的，所以总的时间复杂度为，滚动数组优化后只用了一个2*8的辅助数组，空间复杂度可以视为。 int solve(int n){ int mod = 1e9 + 7; int dp[2][8]; memset(dp, 0, sizeof dp); int cur = 0, pre = 1; dp[0][0] = 1; for(int i = 0; i < n; ++i...

普通解法 除了群主牛牛，每个群友都有一个等级大于他的人作为朋友，那么最终是一个以牛牛为根的树。所以对于每个群友，一直往上找到第一个等级足够处理这个群友产生的问题上级，并统计答案。当这个树是一个链的时候，最差时间复杂度为只用到少量中间变量存储计算值，空间复杂度 vector<int> solve(int n, vector<int> a, vector<int> p, vector<int> k){ vector<int> ans(n, 0); ...