😍

这题的关键在于不等式的化解，化出来之后就是一道简单的dp题了。不等式中包含两个数字的位置，乍一看，选择的数字位置不同，比较结果也不相同。如果能证明位置(i,j),位置(j,k)都满足不等式的话，位置(i,k)也满足不等式，这题就简单了。遇到有指数的不等式，很自然的想到两边取对数 于是我们发现实际上就是需要求出的值递增的子序列种数。用表示以第i个位置为结尾可以得到的这样的子序列的种数，则 答案 = 所有可能的子序列 = #include<bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i < (b); ++i...

最优解 要求树上路径的点权乘积和，有点麻烦，不妨先定一个根之后求出从根节点到各个点的路径乘积和。然后对于u->v的路径，假设他们的最近公共祖先为p，那么路径为u->...->p->...->v。只要求出u->p的乘积和，p->v的乘积和即可。这样就转换成了一个前缀乘积除以另一个前缀乘积的形式，利用逆元进行除法运算。这里使用倍增数组求最近公共祖先，复杂度，总的时间复杂度空间复杂度，如果使用其他算法求lca，如树链剖分或tarjan算法，空间复杂度可达 #define ll long long int mod = 1e9 + 7; int qm(int a...

最优题解 这题可以贪心的在树上求解。首先，叶子节点如果比m小，则肯定和父节点连在一起，如果当前节点结合它向下连通的节点综合大于等于m，则肯定切断和父亲节点的连接更好。按这个思路贪心求出最多可以划分的连通块数目和k做比较即可。时间复杂度和空间复杂度都是 vector<int> g[200055]; int sum[200055]; int dfs(int u, int f, int m){ int ans = 0; for(int v: g[u]){ if(v == f) continue; ans += dfs(v, u, m); ...

最优题解 容易发现这是一棵树，1为根。那么走到牛妹所在的x的最大花费相当于x的子树中的通道都不走，x到根节点的通道只走一次，其他通道全走两次。用sz[x]表示x子树中通道数量,dep[x]表示根到x的通道数量，那么对于特定的x，答案就是2n-2-2sz[x]-dep[x]时间复杂度和空间复杂度都是 vector<int> g[200055]; int sz[200055], dep[200055]; void dfs(int u, int f){ sz[u] = 0; dep[u] = dep[f] + 1; for(int v: g[u]) if(v!=f) df...

普通解法 对于每个查询都用dfs在树上暴力模拟一遍污染时间复杂度最高可达空间复杂度 vector<int> g[200055]; int a[200005]; void dfs(int u, int f, int x, int d){ if(d<0) return; a[u] += x; for(int v: g[u]) if(v != f) dfs(v, u, x, d-1); } vector<int> solve(int n, int m, vector<int&g...

最优题解 因为要求最小值最大化，所以考虑二分答案则检查全部k组数字和都大于等于mid是否可行。可以直接贪心的去取段，如果不满mid就一直取直到满足为止。满足了就截断。时间复杂度空间复杂度 int solve(int n, int k, vector<int> &a){ assert(a.size() == n); int l = 0, r = 1e9; int ans; while(l <= r){ int cnt = 0; int mid = (r+l)>>1; int cu...

最优题解 这道题首先要解决：最少经过几天，一个异次元空间会存在恰好k个物质相当于求满足的最小的x。利用扩展欧几里得解同余方程可得。那么牛牛只要在那天把空间冻上就可以了。现在可以考虑二分答案，检查是否有m个空间的x是大于等于mid的。当然直接排序后取第m小也是可以的时间复杂度算出来的天数可以存储在原本的a数组中，不使用额外空间，所以空间复杂度 long long exgcd(long long a,long long b,long long& x,long long &y){ if(b==0) { x=1;y=0; return a; ...

最优解法 容易发现，答案是满足二分性质的。二分答案，然后考虑怎么检查mid作为中数是否可行。令所有大于等于mid的数字都为1，所有小于mid的数字都为-1，则相当于取一段长度大于等于k的数字使得数字和非负。用前缀和的思想，枚举右端点，然后维护的前缀和最小值来得到以为右端点长度大于等于k的连续段数字和最大值。当存在最大值非负的时候表明合法。时间复杂度因为只需要维护前缀最小和当前前缀和，所以可以省去前缀和数组的使用，空间复杂度 int solve(int n, int k, vector<int> &a){ assert(a.size() == n); int ...

最优解 看到要使得最小值最大，则想到二分答案。二分这个最小值，现在判断是否可以分出m份大于等于这个最小值的石堆。直接枚举每一堆石子然后看能分出几堆满足条件的石堆即可。二分次数上界为,每次检查的复杂度为,总的时间复杂度只使用了常数个临时变量，空间复杂度 int solve(int n, long long m, vector<int> &a){ assert(a.size() == n); int l = 1, r = 1e9; for(int i = 0; i < n; ++i) r = min(r, a[i]); int ans = ...

最优解 考虑建立一棵字典树，一个字符串为另一个字符串的前缀，当且仅当它对应的节点是另一个节点的祖先。所以我们建立完字典树之后，标记一下每个结点作为字符串的终点几次。最后从根开始往下搜索，当搜索到一个结束位置的时候，如果这个结束位置只代表一个字符串那么就统计入答案，不然就不统计。并且搜到一个结束位置就不用往下搜了，因为下面即使搜到了结束位置也不可能是原根，当前的结束位置必然会是它的祖先。时间复杂度和空间复杂度都是 int ch[1000005][26]; int is_over[1000005]; int dfs(int u){ if(is_over[u]){ retur...

最优解 我们只需要知道，对于每个字符串，它的每个前缀在前面的字符串中出现了几次。然后我们按每一位的字母的贡献算，第i位的字母对答案的贡献为的前位作为前缀在前面的字符串中出现了几次。所以我们可以建立字典树去统计和查询字符串前缀的信息。空间复杂度和时间复杂度都是 int ch[1000005][26]; int sz[1000005]; long long solve(int n, vector<string> s){ long long ans = 0; int tot = 0; int rt = ++tot; memset(ch[rt], 0, sizeof...

最优解 考虑动态规划 表示前个字符中，"niuniu"的前个字符选择的方案数。那么对于第的位置来说，如果当前出现的是'n'，则可以更新"n"和"niun"的方案数，'i'可以更新'ni'和'niuni'的方案数，'u'可以更新'niu'和'niuniu'的方案数。那么判断一下每个位置的字母并以此为依据转移即可。时间复杂度可以通过滚动数组将空间复杂度由降到不加滚动数组优化版本： int dp[100005][6] int solve(string s){ int mod = 1e9 + 7; for(int i = 1;...