题目链接：https://ac.nowcoder.com/acm/contest/51727/B 算法：前缀和+哈希   一眼n的范围是3e5，而且还有多组数据，所以直接暴力枚举子串肯定是寄，所以我们考虑优化，我们要找符合要求的子串即子串中字符'1','2','0'个数相等，我们不妨将字符'1'等效成1,'2'等效成1，'0'等效成-2，然后做一遍前缀和，当前缀和为0时，就是合法的子串，然后对该合法子串做哈希，每次枚举检查是否合法，加上合法答案即可 code: void solve(){ int n; string s; cin>>n>>s; map...

题目链接 https://ac.nowcoder.com/acm/contest/50309/G   思路:对于此类问题，可以归纳为：对于使用天平x次，我们可以在3x−32{3^x-3 \over 2}23x−3​个球中找到一个重量不一样的球，并且说出这个球相对于标准球是重了还是轻了。如果仅要求找出问题球，那么3x−12{3^x-1 \over 2}23x−1​个球即可，所以这道题可以对于输入的球的总数x和使用天平次数y，求出对于y次使用天平求出最大能辨别球的上限K，假若K>=x，即能实现，否则就不能实现      值...

题目链接:https://ac.nowcoder.com/acm/problem/14348  分析：读完题目我们可以发现，题目中频繁的涉及一个人和另一个人之间的关系，并且关系之间具有传递性，我们把所有认识的人看成一个集合，不难想到用并查集来维护所有相互认识的人构成的集合  int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x]; } //别忘了初始化 for(int i=1;i<=n;i++) p[i]=i; while(m--){ int x,y; scanf("%d%d",&x,&y); int pa=fi...

题目链接：https://ac.nowcoder.com/acm/problem/16526 分析：对于两个序列a,b，我们要求火柴之间定义的距离最小∑1n(ai−bi)2\sum_{1}^{n}(ai-bi)^2∑1n​(ai−bi)2，∑1n(ai−bi)2\sum_{1}^{n}(ai-bi)^2∑1n​(ai−bi)2=∑1nai2\sum_{1}^{n}ai^2∑1n​ai2+∑1nbi2\sum_{1}^{n}bi^2∑1n​bi2-2*∑1nai∗bi\sum_{1}^{n}ai*bi∑1n​ai∗bi,我们要求距离最小，因为前两项都是固定的，所以总体最小的时候要求最后一项最大即...

题目链接：https://ac.nowcoder.com/acm/problem/20259     首先这是一道比较经典的RMQ问题，找到X和Y年间的最值来进行判断真假 ，对于区间最值问题我们可以用一颗线段树来维护，然而这只是一个小判断，比较难的是判断maybe 。如果没有想好直接打代码会调很久很久...没错，就是我，搞了两天QAQ，好了，伤心事就不提了，我们来具体看看这道题该怎么分析      首先我们看看线段树中需要维护哪些值，左右边界必不可少，此外我们还要维护一个区间最大值sum。在判断maybe的时候还要...

题目链接：https://ac.nowcoder.com/acm/problem/50449 算法一（线段树）     我们很容易发现这是一道关于区间查询的问题，并且这道题没有区间修改或者单点修改，因此线段树中只有区间查询的操作。因此无脑写线段树即可，时间复杂度为O((n+m)logn)O((n+m)logn)O((n+m)logn) Code: #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int...

思路 很明显，我们只需要先预处理出来a数组的前缀和sum，然后暴力枚举，分别乘以风和雨的权值，res每次取最大值即可   注意数据溢出，开long long  accode #include<iostream> #include<algorithm> #include<cstring> #define int long long using namespace std; const int N=1e6+10; int t, n, a[N], k; int sum[N]; signed main(){ cin>>t; while(t--){ cin...

思路 模拟一下过程即可，注意所有的导向板只会被触发一次，哪怕方向和触发板相同，也会触发只是不计数，但板子之后还是不能用了   小车发射器发射完小车就会消失，不会影响小车的后续运动,所以在小车运动过程中check一下是否出界即可  acocde #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=110; char g[N][N]; int n,m,x,y,cnt; char temp='.'; bool solve(){ if(g[...

题目描述[链接：https://ac.nowcoder.com/acm/contest/44887/H] 思路：    题目给出了一个由 n个有权重的节点、n−1条无向边构成的一棵树我们可以首先dfs一遍，预处理出来所有点的度数是多少。 注意根节点为1，深度为0 void dfs(int u,int f){ for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(j!=f){ d[j]=d[u]+1; dfs(j,u); } } }      假若wi表示节点i得权重，那么我们可以表示出树上两点 a,b ...