题目链接：https://nanti.jisuanke.com/t/A1998题目大意：给你一棵树，有两个操作：1 L X:树的L深度的节点权值+=X2 X：查询X的子树的权值和 #include <bits/stdc++.h> #define LL long long using namespace std; LL s[200005], n=200005; void add(LL x,LL z) {for (LL i=x;i<=n;i+=(i&(-i))) s[i]+=z;} LL ask(LL x) {LL ans=0;for (LL i=x;i>0;i...

题目链接：https://nanti.jisuanke.com/t/A1990题目大意： 给你一个字符串其中包含+, -, *, '(', ')',数字(正整数)，'d'(优先级最高)。xdy表示投掷x次y面的骰子。现在问你这个表达式可能的最大值和最小值是多少？ 思路：对一个xdy我们维护一个[L, R]最小值：x。最大值：x*y。把表达式求值的板子改一下就AC了。 #include<bits/stdc++.h> using namespace std; struct Interval { int L, R; Interval() {} Interval...

题目大意： 思路：我们考虑每堆石头要么在1之前拿走，要么在1后拿走。 #include <bits/stdc++.h> #define DB double using namespace std; int a[100005]; int main(){ int n; scanf("%d", &n); DB ans=0; for(int i=1; i<=n; i++){ scanf("%d", &a[i]); if(i>1){ an...

题目链接：luogu.com.cn/problem/CF570D题目大意： 思路：轻重链启发式合并，cut[i][j]:维护深度为i的j单词个数。如果查询时，有<=1的单词个数为奇数就可以组成回文串。 #include <bits/stdc++.h> using namespace std; char s[500005], c[500005]; vector<int> G[500005]; vector<pair<int, int> > q[500005]; int siz[500005], son[500005], dfn[50000...

题目链接：https://ac.nowcoder.com/acm/contest/904/E题目大意：思路：裸的树上轻重链启发式合并 #include <bits/stdc++.h> #define LL long long using namespace std; int a[100005];//dfs序的颜色 int b[100005];//i节点的颜色 int c[100005];//颜色桶 int dfn[100005];//dfs序 int s[100005];//子树节点个数 int son[100005];//重链节点 int ans[100005]; int no...

题目链接：https://nanti.jisuanke.com/t/39277 题目大意：给你一棵树。每条边一边权。我们一共有n*(n+1)/2的点对(u, v)。对每个点对，假设deep[v]<deep[u]那么u-v的最短路径上的所有点属于集合E。问有多少个deep[v']< deep[u']并且v', u'属于E。并且v'到u'的最短路路径边权异或和为0。 思路：这个应该按贡献来算。因为一条路径的异或为0， 这条路一定存在应该LCA，树上启发式合并。 1 子树间产生贡献 例如root的子树之间异或为0，那么u的子节点到v的子节点都会包含这条路径。产生贡献ans+=s...

题目链接：https://ac.nowcoder.com/acm/problem/16564题目大意：思路：线段树的模板题，我们考虑用二分来写。因为是第一个，那么就可以二分了。用差分得到需求。遍历是否满足。 #include <bits/stdc++.h> #define LL long long using namespace std; int a[1000005], l[1000005], r[1000005]; LL sum[1000005], s[1000005]; int n, m; int slove(int x){ memset(s, 0, sizeof(s...

题目链接：https://ac.nowcoder.com/acm/problem/19809题目大意：思路： #include <bits/stdc++.h> #define LL long long using namespace std; LL x[1005], y[1005], z[1005]; LL a[1005], b[1005], c[1005]; LL s[1005][1005], f[1005][1005], s1[1005][1005], s2[1005][1005]; int main(){ int n, m; scanf("%d%d&q...

题目链接：https://nanti.jisuanke.com/t/A1948题目大意：给你一个n * m的矩阵。有k个黑块。问有多少个不包含黑块的矩阵。 思路：时间给你2秒。我们考虑n * m * m的写法。枚举每个点作为右下角。再枚举矩阵的宽。如图：以右下角0号点为矩阵的右下角的矩阵个数。枚举x。为矩阵的左边界。如图0和0-4都会产生一个矩形。ans+=H枚举x到前一个位置。如图0和1-5都会产生一个矩形。ans+=H枚举x到前一个位置。如图0和1-3都会产生一个矩形。ans+=H枚举x到前一个位置。如图0和1-3都会产生一个矩形。ans+=H枚举x到前一个位置。如图0和1-2都会产生一...

题目链接：https://nanti.jisuanke.com/t/A1951题目大意：有n道题，分别有a[i]和b[i]属性。如果你在时间T去做它。那么你得到的分数是T*a[i]+b[i]。而且它有s个前置题目。你必须把这些题写完才能写这题。(0<n<=20, |a[i], b[i]|<=1e9)问能得到最大分数。 思路：状压DP：f[s]：写完s集合的最大分数。开始写复杂了。s集合是否是一个可能的集合。我预处理了g[i]：写i题时，前面必须写完的题目。然后每个s判断了一下已经存在的点。再判断要下个要转移的点。比较简洁的思路：我们只要预处理了g[i]：i前置的题，和上面的不...

题目链接：https://nanti.jisuanke.com/t/A1955题目大意：给出一个只含数字的字符串，求出字符串中所有本质不同的字符串所表示的十进制数的和 思路：哈希是回文自动机的裸题。用Manacher +hash可以A。Manacher找出所有的回文子串。用hash拉链法去个重。记录区间的十进制的哈希前缀和。直接求一个字串的贡献。这题hash不用自然溢出会WA。 #include <bits/stdc++.h> using namespace std; #define LL long long const int maxn=2000005; const int M...

题目链接：https://nanti.jisuanke.com/t/A1956题目大意：定义f[i]函数代表i=a * b的对数，其中a和b都不能是平方数的倍数，a * b与b * a不相同，t组样例，给出n，求1~n的f[i]之和。 思路：整除分块：1.我们可以用整除分块求出1-n的所有数的因子个数。那么就是所有的i=a*b的对数。然后我们考虑怎么把不满足条件的对数去掉。 2.i=a * b对于每个平方数的倍数x。他可以作为a或者b。x会对所有的x的倍数产生2个不合法的贡献。如果我们把所有的[1, 2e7]的x筛出来。用整除分块求不合法的贡献。 3.我们看2可以发现我减多了。例如36=4 *...

题目链接：https://ac.nowcoder.com/acm/contest/6234/H题目大意：有一棵n节点的树，每个节点上有权值，希望你把他的k-1条边拆开。形成k棵子树，每棵树的权值为节点权值的和。问这k棵子树的最大权值最小为多少？ 思路：二分，然后我们思考，对于一个节点，他会和若干子节点连接，并且可能和祖先节点连接思路：先二分一下，这个最小值。然后在树上能不能分成为<=k棵子树。我们怎么贪心的分树：对这个树，我们先处理2,5,6,7。一定是2和若干的子节点在一起，那么其他的每个子节点都会形成一颗树。我们希望2上连接的子节点越多越好并且权力和<=mid。那么对5, 6,...

题目链接：https://ac.nowcoder.com/acm/contest/6234/H题目大意：你可以按题目规则规则一个矩阵然后问你从(Sr, Sc)到(Tr, Tc)的最大分数，如果(x, y)没有访问过，那么你从(i, j)访问到(x, y)得到发分数为V(i, j)*V(x, y)。 思路：因为vij>0那么我们一定是把所有的点访问完的代价最大。然后每个点向周围四个方向连边就是求一个最大生成树。优化：我们从题目可以知道边权<10000，边可以桶排。得到n-1条边就break。 #include<bits/stdc++.h> #define LL long ...