建图跑个bfs就好了= - = #include <bits/stdc++.h> using namespace std; const int N=2e5+5; vector<int>v[N]; int vis[N],dis[N]; queue<int>q; void bfs() { while(q.size()) { int temp=q.front(); q.pop(); for(int i=0;i<v[temp].size();i++) { int pos=v[temp][i]; if(vis[pos]) continue; vis[pos]=1...

一个题目数据小就是那个题目的突破点(一般),比如这个题目,大家貌似都能想到n^2的,但是大家看一眼k的大小会发现,这题的突破点在k(这题不是水题= - =).考虑对于没种颜色做一次bfs,算出其他点到这种颜色的最短距离.代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e5+5,M=105; int w[N],ans[N]; vector<int>v[N]; int dis[N][M]; vector<int>col[M]; int vis[N]; queue<int&gt...

#include <bits/stdc++.h> using namespace std; const int N=2e5+5; struct vv{ int from,to; }; int vis[N];//不能走到重复点. vector<int>v[N]; vector<vv>ans; int deg[N];//度 queue<int>q; void bfs() { while(q.size()) { int temp=q.front(); vis[temp]=1; q.pop(); for(int i=0;i<v[temp].size...

#include <bits/stdc++.h> using namespace std; const int N=1e5+5,M=30; char s1[N],s2[N]; int fa[M]; struct vv{ int t,m; }; vector<vv>v; int f(int x) { if(fa[x]==x) return x; else return fa[x]=f(fa[x]); } int main() { int n,ans=0; cin>>n; for(int i=0;i<26;i++) fa[i]=i; scanf("%s",...

为什么打算重新写一下呢,因为最近一直在做并查集的题.emmm/现在讲两种dfs判断环的方式.对于无向图只需对另一一个点做一次dfs即可,因为任意一个点一定可以都到的. int vis[N]; void dfs(int u,int fa)//判断有没有环. { if(vis[u]) {flag=1;return;} vis[u]=1; for(int i=0;i<v[u].size();i++) { if(v[u][i]==fa) continue; dfs(v[u][i],u); } }//对于单个联通的无向图直接dfs一次即可.对于有向图呢?有向图做法和无向图做法大同小异.你的vis数...

贪心+并查集即可.选取集合众数,然后答案就是集合大小-集合众数了. #include <bits/stdc++.h> using namespace std; const int N=2e5+5; int a[N]; int fa[N]; vector<int>v[N]; int f(int x) { if(x==fa[x]) return fa[x]=x; else return fa[x]=f(fa[x]); } int main() { int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i&l...

直接贪心即可.1.首先考虑max,什么时候能取到max呢?显然是直接统计下每个位子的数量,然后数量大于>=3那么直接标记3个位子,假如是2那就看下左边有没有被标记,我们从左到右一个一个考虑嘛.假如没有被标记,那么显然是要标记左边和自身的,假如标记了,那么我就标记右边和自身,假如只有一个的话,就是看看自己的左边有没有标记,再看看自身有没有被标记,假如都被标记了,就标记右边呐...然后从头到尾扫一遍就完事.2.然后考虑min,什么时候取到min呢?假如把max看作一个分散的过程,那么min就是一个整合的过程,差值为2的区间都可以合并为1,然后貌似统计下就完事...代码如下: #include...

emmm,存26个字母的位子,然后用树状数组维护即可的水题...分块(= - =应该可以写,我以后会认真学分块的).代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e5+5,M=27; char s[N]; int n; int bit[M][N]; int lowbit(int x) { return x&(-x); } void insert(int pos,int val,int ch) { while(pos<=n) { bit[ch][pos]+=val; pos+=lowbi...

水啊2333,但是还是要练习的,毕竟有所收获.深度和树的直径是有关系的,画图即可.(最长链是树上两个点的最远距离..)1.先分配一个maxdep然后,假如最长链<深度-1直接-1,或者最长链>2*(深度-1).直接-1.2.否则直接分配?先分配一个maxdep个点,然后在树的另一旁分配maxlian-(maxdep-1)-1个点,其他点全接在最后一个点上就没了2333代码如下: #include <bits/stdc++.h> using namespace std; int main() { int n,d,h;//n个点,最长链为d,深度为h. scanf("%d%...

先预处理外围联通块,简单的dfs一下存下联通块大小和位子,然后把大小排个序,然后就取k-size()个,然后再涂满就结束了/ 代码如下:(写的有点丑,太长了) #include <bits/stdc++.h> using namespace std; const int N=55; char s[N][N]; char a[N][N]; int vis[N][N]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; struct vv{ int idx,idy,num; }v[N*N]; int id=0; bool cmp(vv aa,vv ...

直接连通图里的环判断有没有,有就是0,没有就是1.然后判环的方式有很多,我写了dfs,因为自己在练习嘛~挺好写的,只要你把你的想法写进dfs即可. #include <bits/stdc++.h> using namespace std; const int N=1e5+5; vector<int>v[N]; int flag=0; int vis[N]; void dfs(int u,int fa)//判断有没有环. { if(vis[u]) {flag=1;return;} vis[u]=1; for(int i=0;i<v[u].size();i++) { ...

似乎用牛客的人越来越少了mua.嗯,从今天开始写点题解呐呐呐...  就从陪队友做的cf题开始吧,emmm,马上到学校了,加油...这题挺简单的,因为它是要删叶子节点嘛,那你从根节点走下来的一定是只有正数才保留,且一定要满足我这个节点的元素的值>从根节点走下来那条路径的和,这里,我们使用树上前缀和即可解决/vov.如此记录前缀和以及子树大小就可以了吧...然后代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e5+5; vector<int>v[N]; int a[N],w[N],sz...

一个比较麻烦的模拟... #include <bits/stdc++.h> using namespace std; const int N=2e5+5; struct vv{ int id,t; bool operator<(const vv &b)const{ return b.t==t?id<b.id:t<b.t; } }a[4][N]; int k,m,n; int need; int num[4];//4个id的指针. set<vv>all,choose;//确实没有这个实力写这种模拟题... int sum[4][N]; int c...

考验你对于树状数组单点修改区间查询的理解... for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) { ans+=abs(a[i].x-a[j].x)*max(a[i].v,a[j].v); } }题目的要求是你对于这个表达式子的优化,我们先尝试去掉max,就将结构体的式子按v进行排序即可.然后我们用树状数组来维护x,具体怎么维护呢,我们肯定是要快速求出,假如我当前这个位子是a[i].x,我们肯定要快速求出a[i].x前面有多少个是小于它的,且还要知道前面那些数的和,同理我们也得知道后面有多少个是大于他的,至于后面的个数之和就是i-前面的和-1...