标签：2024.1 龙身 int abc335 back MAXN 补题 push dis
开篇碎碎念
总是以开篇碎碎念开写，不加这个有点不太舒服qwq，又是一个周一，开始酣畅淋漓的学习（摸鱼）把之前欠债补一补然后看一下概率
abc 335
总览
是23号vp的，出了ABD三题，CWA了一发但是没de出来（没找到错误样例）赛后补了C和E
C.Loong Tracking
很简单真的很简单！！！发现数据如果每次移动更新所有龙身的位置的话铁T（en？），然后观察一下数据范围，觉得应该每次查询O(1)出结果，然后想到用龙头的位置表示龙身，毕竟龙身是跟着龙头走的。
但是发现构造了几组数据，然后每组数据的所有龙身位置输出都是对的，就不知道怎么错的。
赛后洛谷翻题解，发现思路大致相同。直到我在后面发现一行小字...
我一拍大腿（呜呜好疼），把所有++cnt拆出来写了，于是就过了（呜呜呜）
E.Non-Decreasing Colorful Path
题意：
有n个点，m条边，每个边有不同的数值，问从1走到n最多可以经过多少个不同的数，要求走过的数列是不减数列。
思路：
首先第一个就是建边，理论上是给出的无向边，但因为我们要找的是不降序列，所以当该边的左右两个端点的值不相等的时候就会变成由低指向高点的有向边。
虽然有可能走不到点n，但是同样能走到点n的情况下优先走能走的中点数最小的。
然后进行了一个类似于dfs的放缩。
这里是E题的代码捏
```
#include
using namespace std;
const int MAXN=2e5+10;
int a[MAXN],vis[MAXN],dis[MAXN];
vectore[MAXN];
int ans,n,m;
bool cmp(int x,int y){
return a[x]<a[y]; }="" void="" dfs(int="" x){="" vis[x]="1;" for(auto="" i:e[x]){="" if(vis[i])continue;="" if(a[x]<a[i]="" &&="" dis[x]+1="">dis[i]){
dis[i]=dis[x]+1;
dfs(i);
}
if(a[x]==a[i] && dis[x]>dis[i]){
dis[i]=dis[x];
dfs(i);
}
}
vis[x]=0;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
if(a[u]>a[v])e[v].push_back(u);
else if(a[v]>a[u])e[u].push_back(v);
else{
e[u].push_back(v);
e[v].push_back(u);
}
}
for(int i=1;i<=n;i++){
sort(e[i].begin(),e[i].end(),cmp);
}
dis[1]=1;
dfs(1);
cout<<dis[n]<<endl; }="" ```="" <="" details="">
ABC 336
E读假了目前没法补
ABC 337
DE轻松补完qwq
标签：2024.1,
龙身,
int,
abc335,
back,
MAXN,
补题,
push,
dis
From： https://www.cnblogs.com/muyi-meow/p/17995281