题上要求找长度为偶数的路径。根据常识可知 偶 = 偶 + 偶 = 奇 + 奇。所以我们可以考虑深度，算出每个节点的深度，深度为偶数的和偶数组合，深度奇数的和奇数组合。因为x到y和y到x属于一条路，不考虑顺序，所以答案是个组合数。也是就其中a、b分别为深度为奇、偶数的节点个数注意结果炸int #include<bits/stdc++.h> using namespace std; vector<int>e[1<<17]; long long a,b; void dfs(int x,int f,int dep){ if(dep&1) a++; else ...

前缀异或和一边计数即可。枚举i为已经计数的区间右边界，然后以i为左端点，看后面的区间有多少个区间异或和是已经计数的加上即可。对于区间右边界的更新，假设现在已有a、b、c 现在加入一个d，产生的贡献就是[a,d]、[b、d]、[c、d]、[d,d]新增的四个区间 根据a^b=c b=a^c 可以用前缀和之间进行异或得到注意数组大小应该开到(1<<17)-1 因为(1<<16)<1e5  #include<bits/stdc++.h> using namespace std; int mp[1<<17]; int sum[1<<10...

。。只会AB签到 A：就是说对于每个字符为J的位置，如果他同一列下方有I，同一行右边有O，答案就加1那么直接对每行维护字符O的后缀和，对每列维护I的后缀和 遍历字符集，为J的时候就是两个相乘即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=3e3+5; int n,m; char a[maxn][maxn]; ll so[maxn][maxn],si[maxn][maxn]; int main(){ ios::sync_with_stdio(0); cin&gt...

思路：一开始的想法就是直接每个点去dfs树形dp后取最大，复杂度n^2看到数据范围后 想法直接见祖宗了 然后就去学了一下二次扫描和换根法。简单介绍一下。其实第一步就是上面说的dfs树形dp。随便选取一个点为根，假设我们选1，则dp[root]表示以root为根的子树的最大流量。对于root的子节点son我们这样考虑，如果son的度为1，则dp[root] += e(root,son) 其中e(root,son)表示root到son这条河道的流量限制。如果son的度不为1则dp[root] += min( dp[son],e(root,son) ) 什么意思呢 就是说我子树的流量可能允许很大，但...

写两种做法吧。第一种是直接重心性质，第二种是树形dp+换根。 一、利用重心性质：下面是树的重心的性质：1.树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。2.把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。3.一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。4.一棵树最多有两个重心，且相邻。摘自百度百科 这题就考察到了树的重心的第一个性质即树中所有点到重心的距离和最小，而此题所求的最小的w，就是所有点到重心的距离之和。 所以考虑dfs树形dp求出重心，然后bfs求出每个点距离重心的距离进行累加求和即可。 #include &lt...

A-打怪因为我先手，我的攻击力如果大于怪物的血量，那么我就能杀无数个，输出-1即可考虑到我先手，所以先把怪物的血扣掉一次，然后就是怪物先手了，计算出我的血量能够让怪物打我几次，以及我需要打几下怪物才能死即可。 #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int t; cin >> t; while (t--) { int a, b, x, y; cin >> a >> b >> x >> y; if (b ...

思路：dp[i][j][k] 表示对于前i天一共工作了j天现在连续工作了k天的最小花费 滚动数组优化掉第一维(不然会MLE)if(s[i]=='0') 为0只能休息dp[j][0]=min(dp[j][0],dp[j][k])if(s[i]=='1')dp[j][0]=min(dp[j][0],dp[j][k]) 选择休息dp[j][k]=min(dp[j][k],dp[j-1][k-1]+k) 选择工作然后发现s[i]==1 选择休息和s[i]==0的转移方程一样所以dp[j][0]=min(dp[j][0],dp[j][k]) &&if(s[i]=='1') dp[j][k...

思路经典题，比较简单因为要求中位数，所以拿两个优先队列去维护，一个大顶堆，一个小顶堆大顶堆维护比较小的那一半，堆顶就是中间数了。小顶堆维护比较大的那一半，堆顶自然就是中间数。如果序列是奇数个的时候，不妨把多的一个放在大顶堆内，那么答案就是大顶堆的 堆顶了当两个堆都不为空时候，边插入，边比较堆顶大小即可。 #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0); int _;cin>>_; while(_--){ int cas,n;cin>>cas&gt...

A注意题上说了，ai序列是不降序列，那么对于Σai * i来说，大的数自然是在后面更好啦。所以说至少移动k个位置，那么我们就只让他动k个位置，这样保证减少的数尽可能小，保证结果尽可能大。那么我们首先求出最开始的ans=Σai * i 然后对k+1后的枚举一个数字往前移动k位，对结果的影响就是：i-1-k到i-1这一段的数字统一向右移动了一位，增加的价值就是这一段的和，考虑前缀和维护即可，那么a[i]从当前位置去到了i-k，那么就应该减去a[i] * k 在加上a[i] * (i-k) #include<bits/stdc++.h> using namespace std; type...

思路：看到树的题，第一想法往往就是先考虑dfs这题我们可以知道，叶子节点是一定要染色的，因为他染色是一个从叶子节点往父亲节点更新的过程。那么我们应该考虑dfs应该要维护什么？首先我们肯定是贪心的策略去做，就是我选了叶子节点开始染色，那么染过色的地方就尽量不要去选，这应该是最优策略。但其实这样是有错误的考虑这样一种情况 1<-2<-3<-4 这是其中一条链，假设k1=1,k2=1,k3=3,k4=2按照上面的做法，我们从4开始染色，ok，3和4已经染色成功，然后继续2开始染色，ok，2染色成功，最后把根染色这样操作次数要3次。其实正确答案应该是2.4开始染色，3和4覆盖，3染色...

思路：暴力的话复杂度很高，所以考虑倍增去找往上跳f[i][j]表示i节点往上跳能买的第1<<j个节点的位置跑一遍dfs处理出来所有点往上跳的可以购买的第j个位置在哪 然后每次询问复杂度只要logn即可倍增应该先往大的跳，比如从1到5，应该从128，64，32，16，8，4，2，1 这样跳这样的话1+4 直接到了5，相反如果从小的跳1+1+2<5 1+1+2+4=8>5 这样还需要往回跳处理较麻烦 #include <bits/stdc++.h> using namespace std; const int maxn=2e5+5; vector<int&...

思路：我们知道树是联通的，即任意两点之间一定是可以到达的，那么题意等价能将这棵树分成多少个联通块，并且最多只能分解k个联通块那么其实这棵树的结构是怎么样的我们并不在乎只需要考虑当前节点和上一个节点是不是要在同一个连通块即可所以考虑dpdp[i][j]表示前i个节点分成j个联通块的方案数转移方程易得dp[i][j]=dp[i-1][j]+(k-(j-1))*dp[i-1][j-1]即 要么第i个和第i-1个同一块 要么在剩下的k-(j-1)块中选一块注意块和块是互不相同的 比如1在第一块 23在第二块 和1在第二块 23在第一块这是两种方案边界的话就是dp[0][0]=1 #include&lt...

A题意其实有点迷(其实是自己读题没认真)就是只要问字符串是不是由若干个"mq"组成所以长度奇数的肯定就是No(不过数据貌似没有mqmqm这种？试了下竟然ac了)否则就去看奇数位置是不是m 偶数位置是不是q 都是的话就Yes 不然就No #include<bits/stdc++.h> using namespace std; int main(){ int q;cin>>q; while(q--){ string s;cin>>s; int len=s.size(); if(len&1) {puts("No");continue;} int flag=...

思路：求l到r的个数 转换为求1到r的个数 减去 1到l-1的个数可以看到 l和r的长度长达1e9 如果暴力算每个的话 光是枚举x就要1e9可能会想到枚举约数，但是这样也还不够，复杂度还是高的批爆枚举约数是肯定没错的，问题是考虑如何去优化可以考虑去枚举以x为最高位的 区间的约数的个数比如求最高数码x=1 枚举的区间的约数就是 [1,2) [10,20） [100,200） [1000,2000)…这样有个好处 就是最高位的数都是一样的 就不需要特意去计算了这样就够了吗？远远不够 就拿[1e8,2e8）这个区间来说 跑完这个 1s估计也用完了 还差最后一个优化点，也就是最重要的一点 除法分块下面...