第一题：最长相等数（len）

题目描述

题解部分

循环结构——最长连续区间问题

解题思路：从左至右枚举每个数，如果当前数与上一个数相等，上个数所在的区间长度  ，否则重新建立一个新的区间，区间长度重置为  。

时间复杂度：

#include<bits/stdc++.h>using namespace std;const int N=2e5+5;int n;int len,maxx,u;//当前长度，最大长度，上一个数的值 int main(){ cin>>n;for(int i=1;i<=n;i++){  int x;//当前数的值   cin>>x;if(x==u){//如果与上一个数相等    len++;//长度+1    maxx=max(maxx,len);//比较出最大值   }else{   len=1;//否则长度初始化为1   }  u=x;//进入下一次迭代时当前数变成了上一个数  } cout<<maxx; return 0;}

第二题：坚持锻炼（run）

题目描述

题解部分

1. 模拟

解题思路：

与小学组同题，但数据增大到，会爆，开个就行，模拟过程可参照小学组第 题题解代码，不会超时。

时间复杂度：

2. 一元二次方程求根公式

有多种时间复杂度  的方法，可以解决  以内的数据，这里介绍一个一元二次方程求根公式的方法：

我们只需要知道第天赚的钱是多少即可。假设第天赚到的钱是，由于每天赚到  块钱的天数符合等差数列，利用等差数列求和公式得到  ,所以第  天赚的钱为  的正整数解。再利用一元二次求根公式即可。

时间复杂度：

#include<bits/stdc++.h>using namespace std;using ll=long long;const int N=2e5+5;int n,c,x;//c为一元二次方程的常数项,二次项一次项均为1ll ans;int main(){ cin>>n; c=-2*n; x=(-1+sqrt(1-4*c))/2;//求根公式 for(int i=1;i<=x;i++){//枚举转了赚i(i<=x)元的天数一共赚了多少钱   ans+=i*i; } ans+=(n-x*(x+1)/2)*(x+1);//赚(x+1)元的天数一共赚了多少钱  cout<<ans;return 0;}

第三题：开根号（sqrt）

题目描述

题解部分

分情况讨论 + 贪心

解题思路：

手搓样例有以下结论：

1. 当  为  时操作会进入循环
2. 当  时  最终会不断通过操作变成  或 

时间复杂度：

#include<bits/stdc++.h>using namespace std;using ll=long long;const int N=2e5+5;int t;ll x,k,ans;int main(){ cin>>t;while(t--){  cin>>x>>k;  ans=0;while(k){if(x==1){//特判当x=1的情况     ans+=k;    k=0;   }elseif(x==2){//当x=2时，进入循环     ans+=2*k;    k=0;   }elseif(x==3){//当x=3时，进入循环     ans+=4*k;    k=0;   }else{//当x>3时     ll a=sqrt(x);//a x开方后向下取整得到的数 if(a*a==x){//当x是完全平方数时，直接开方      x=a;     k--;     ans++;    }elseif((a+1)*(a+1)%2==x%2){//当x与a+1的平方奇偶性相同时      ans+=((a+1)*(a+1)-x)/2+1;//x一定优先走到a+1的平方再开方      x=a+1;     k--;    }else{//否则x一定与a+2的平方奇偶性相同      ans+=((a+2)*(a+2)-x)/2+1;//x一定优先走到a+2的平方再开方     x=a+2;     k--;    }   }  }  cout<<ans<<endl; }return 0;}

第四题：魔法（magic）

题目描述

题解部分

贪心-策略题

算法流程：

把操作记为代价，小朋友长高的长度记为贡献，可以把操作按代价与贡献的关系分为三类：

1. 当选中的小朋友与最高小朋友身高一致时，通过  的代价贡献为  。
2. 当选中的小朋友与最高小朋友相差  时，通过  的代价贡献为  。
3. 当最高的小朋友已经达到要求  时，如果选中的小朋友的身高  未达到  ，通过  的代价贡献为  。

利用贪心的局部最优策略，这三种步骤的优先级为。

时间复杂度：

#include<bits/stdc++.h>using namespace std;using ll=long long;const int N=1e6+5;ll n,m;int a[N];ll ans;int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1,greater<int>());//从大到小排序 if(a[1]>=m){//如果最高的小朋友已经达到m，后面不满足身高的小朋友只用选中一次 for(int i=2;i<=n;i++){if(a[i]<m) ans+=m-a[i]+1;  } }else{//否则的话优先将最高的两名交替拔高直至两者身高均为m   ans+=a[1]-a[2]+2;  a[2]=a[1]+1;  ans+=(m-a[1])/2*3+(m-a[1])%2*2;  ans+=(m-a[2])/2*3+(m-a[2])%2*2;for(int i=3;i<=n;i++){//除了最高的两个小朋友，其余小朋友均只用选中一次    ans+=m-a[i]+1;  } } cout<<ans;return 0;}

第五题：铁路涨价计划（ticket）

题目描述

题解部分

增量更新和最短路DAG均是最短路问题的常见策略。

解法1：正难则反+离线处理+增量更新+BFS

正难则反： 删边不易，考虑正难则反（加边），开始处于原本所有要删掉的边都没有加进图里的状态，然后逐个加边更新全图属性，进而得到答案。离线处理： 在处理查询问题时，不是边查询边处理而是存下所有查询后再进行处理，称为离线处理（与在线处理相对）。增量更新： 图论中增量指图里加入了 新点 或 新边 或 图中一条边或一个点的属性发生改变。更新指增量给全图属性带来的变化。图论的并查集、单源最短路都有这种思想，多源最短路应用增量更新思想的题目尤其多。

注意本题解中的代码能通过原题，但市赛仅能拿  分，超时一个点。

可以结合最短路DAG的思想，加边后仅观察能否将最短路变成原图最短路的点，那么时间复杂度可以优化到与最短路DAG等同。

时间复杂度： 优化后 

#include<bits/stdc++.h>using namespace std;const int N=1e5+5,M=2e5+5;int n,m,q;struct S{ int p,id;};struct S1{ int x,y;}edge[M];//存边 int a[M];//删的哪条边 vector<S> e[N];bool st[M];//标记删除边 int d[N][2],ans[M],cnt;//di0 原图最短路，di1加边前的最短路 void bfs(int s,bool f){ queue<int> q; q.push(s);while(q.size()){  int p=q.front();  q.pop();for(auto x:e[p]){   int j=x.p,id=x.id;if(st[id]) continue;//边还没有加进来，不能走 if(d[j][f]>d[p][f]+1){    d[j][f]=d[p][f]+1;if(d[j][1]==d[j][0]) cnt++;//与起点的距离和原图等同后答案+1     q.push(j);   }  } }}int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q;for(int i=1;i<=m;i++){  int x,y;  cin>>x>>y;  e[x].push_back({y,i});//记录边的属性   e[y].push_back({x,i});  edge[i]={x,y}; } fill(d[0],d[0]+N*2,1e9);//初始化  d[1][0]=d[1][1]=0; bfs(1,0);//跑一遍原图的最短路 for(int i=1;i<=q;i++) cin>>a[i],st[a[i]]=1;//离线处理  bfs(1,1);//跑一遍没加指定边的图的最短路 for(int i=1;i<=n;i++) ans[q]+=d[i][0]<d[i][1];//统计没加任何指定边的答案 for(int i=q;i;i--){  st[a[i]]=0;//标记可以走   cnt=0;  int x=edge[a[i]].x,y=edge[a[i]].y;if(d[x][1]>d[y][1]) swap(x,y);  bfs(x,1);//仅针对加的边上的两个点跑最短路更新全图属性   ans[i-1]=ans[i]-cnt;//这一次加边后减少了cnt个答案  }for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';//反向输出 return 0;}

解法二：最短路DAG+BFS

最短路DAG： 跑完一次最短路，每个点和在最短路中能成为它后继的点建立一个有向边，建立的新图很明显是个DAG，这种DAG叫最短路DAG。和树一样，DAG作为一种特殊的图有很多的特殊属性可以分析：在最短路DAG中，对于一个非源点的点，指向它的所有有向边被删掉（即入度变成  ）后，那么该点变为源点不可达（在原图中表现为不能通过最短路到达），它直接能到点入度减 。

时间复杂度：

#include<bits/stdc++.h>using namespace std;const int N=1e5+5;int n,m,q;struct S{ int p,id;};struct S1{ int x,y;}edge[N<<1];//存边 vector<S> e[N];int d[N],din[N],ans;//最短路距离   新图每个点的入度   答案 bool st[N<<1];//标记被删过的边 void bfs(){ queue<int> q; q.push(1);while(q.size()){  int p=q.front();  q.pop();for(auto x:e[p]){   int j=x.p;if(d[j]>d[p]+1){//记录新图每个点的入度     din[j]++;    d[j]=d[p]+1;    q.push(j);   }elseif(d[j]==d[p]+1){    din[j]++;   }  } }}void Erase(int x){if(st[x]) return;//如果这个边被删过  st[x]=1; int a=edge[x].x,b=edge[x].y;if(d[a]>d[b]) swap(a,b);//只用看可能被更新最短路的点 if(d[b]==d[a]+1){  din[b]--;//如果这条有向边被删除，b点入度减1 if(!din[b]){   ans++;//减为0时答案+1，并拓展出哪些点计入答案，哪些有向边也会被删除    queue<int> q;   q.push(b);while(q.size()){    int p=q.front();    q.pop();for(auto x:e[p]){     int j=x.p,id=x.id;;if(!st[id]&&d[j]==d[p]+1){//如果这条边没有被删过而且是新图的边       din[j]--;//重复之前的操作       st[id]=1;if(!din[j]){       ans++;       q.push(j);      }     }    }    }  } }}int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q;for(int i=1;i<=m;i++){  int x,y;  cin>>x>>y;  e[x].push_back({y,i});  e[y].push_back({x,i});  edge[i]={x,y}; } fill(d,d+N,1e9); d[1]=0; bfs();//跑一遍最短路，建新图 while(q--){  int x;  cin>>x;  Erase(x);  cout<<ans<<'\n'; }return 0;}

改题链接：

http://hu33.tech/contest/6a0c38844b52870861f44fd9