11.5日志
1.Problem - B - Codeforces
该题的难点在于如何找到树的根,题目中也明确说明了k重刺猬图本质上是一棵树,那么我们就可以将其抽象成树来进行考虑,抽象成的树是一颗深度为k的满树并且每个非叶子节点都至少有三个节点,如果我们能知道根节点那么我们就可以通过遍历这棵树,当深度小于k的时候每个节点都应该有4个及以上的节点,根节点有>=3个节点,叶子节点无节点,这是很好判断的,那么我们如何找到根节点呢,一开始我尝试从叶子结点出发找到距离自己长度为k的点作为根节点,但这是错误的
形如该图a点到根节点确实是2但是a到b的距离也是2,这该怎么解决呢,可以借鉴dfs求树的直径的思想,我们从a开始跑dijkstra找一个距离a最远的点c,这样就可以保证找到的c其实是与a不同子树中的叶子节点,再从c跑一次dijkstra此时距离a和c距离都是k的点只有根节点满足,那么根节点就能找到了,说明在不知道根节点的情况下我们是可以通过两个不同子树的叶子节点找到根节点的前提是这是一颗满树(保证两个叶子节点距离根节点距离一样)
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<double , double> pdd;
const int N = 1e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
vector <int> g[N];
int n,k;
bool st[N];
int root = -1,din[N],dist1[N],dist2[N];
void dijkstra(int u,int dist[])
{
memset(st , 0 , sizeof st);
for(int i = 1 ; i <= n ; i++)
{
dist[i] = inf;
}
priority_queue <pii , vector <pii> , greater<pii> > heap;
heap.push({0 , u});
dist[u] = 0;
while(heap.size())
{
pii t = heap.top();
heap.pop();
int v = t.y,dis = t.x;
if(st[v])
{
continue;
}
st[v] = 1;
for(int i = 0 ; i < g[v].size() ; i++)
{
int j = g[v][i];
if(dist[j] > dis + 1)
{
dist[j] = 1 + dis;
heap.push({dist[j] , j});
}
}
}
}
bool dfs2(int u,int len)
{
st[u] = 1;
for(int i = 0 ; i < g[u].size() ; i++)
{
int j = g[u][i];
if(!st[j])
{
if(!dfs2(j , len + 1))
{
return 0;
}
}
}
if(len < k)
{
if(u == root)
{
return din[u] >= 3;
}else
{
return din[u] >= 4;
}
}else
{
return din[u] == 1;
}
}
int main()
{
IOS;
cin>>n>>k;
for(int i = 1 ; i < n ; i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
din[u]++,din[v]++;
}
for(int i = 1 ; i <= n ; i++)
{
if(din[i] == 1)
{
dijkstra(i , dist1);
break;
}
}
int maxn = -1,idx = 0;
for(int i = 1 ; i <= n ; i++)
{
if(dist1[i] > maxn)
{
maxn = dist1[i];
idx = i;
}
}
dijkstra(idx , dist2);
for(int i = 1 ; i <= n ; i++)
{
if(dist1[i] == dist2[i] && dist1[i] == k)
{
root = i;
break;
}
}
if(root == -1)
{
cout<<"No";
}else
{
memset(st , 0 , sizeof st);
if(dfs2(root , 0))
{
cout<<"Yes";
}else
{
cout<<"No";
}
}
}2.Problem - D - Codeforces
我们可以将题目想象成当ai < k的时候这个区间会解封不然都是处于冰冻状态,题目需要我们求出最小的k使得在每段解封区间长度相同的情况下解封的区间最多,假设一开始k = 0那么这个时候解封区间为0,我们由小到大枚举k但是k很大,但是n很小我们就发现答案只会是ai+1,也就是说我们只用枚举ai即可,我们可以用b数组记录下标后按照a的值由小到大排序,然后我们从小到大枚举bi表示枚举到bi的时候bi区间解封,接下来我们可以发现当一个区间解封会有三种状态
1.bi合并了左右两个已经解封的区间
2.bi作为bi-1/bi+1的右端/左端扩展了区间
3.bi自成一个新的区间
既然有关区间的合并那么就应该想到用并查集来维护,我们还需要维护没一个区间的大小并且我们还需要一个数组len来记录i长度的区间的数量以及一个变量tot来记录当前一共有多少区间,
第一种情况我们需要减去左右两边区间的长度,tot--,合并两边后加上新的区间长度
第二种我们减去左/右的区间后进行合并再加上新的区间长度
第三种tot++并且加上自己的长度
每当当前新解封区间进行完操作后的长度数量等于tot的时候代表此时是一个合法状态并且tot大于上一次的tot那么我们ans可以更新为a[b[i]] + 1
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<double , double> pdd;
const int N = 1e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
int n;
int a[N],b[N],p[N],siz[N];
bool st[N];
int len[N];
int find(int x)
{
if(p[x] != x)
{
p[x] = find(p[x]);
}
return p[x];
}
void merge(int a,int b)
{
int x = find(a),y = find(b);
p[x] = y;
siz[y] += siz[x];
}
bool cmp(int x,int y)
{
return a[x] < a[y];
}
int main()
{
IOS;
cin>>n;
for(int i = 1 ; i <= n ; i++)
{
cin>>a[i];
b[i] = i;
p[i] = i;
siz[i] = 1;
}
sort(b + 1 , b + n + 1 , cmp);
int tot = 0,ans = 0;
int maxn = -1;
for(int i = 1 ; i <= n ; i++)
{
int t = b[i];
st[t] = 1;
if(!st[t - 1] && !st[t + 1])
{
tot++;
}else if(st[t - 1] && st[t + 1])
{
tot--;
len[siz[find(t - 1)]]--;
len[siz[find(t + 1)]]--;
merge(t - 1 , t);
merge(t + 1 , t);
}else if(st[t - 1])
{
len[siz[find(t - 1)]]--;
merge(t - 1 , t);
}else if(st[t + 1])
{
len[siz[find(t + 1)]]--;
merge(t + 1 , t);
}
len[siz[find(t)]]++;
if(len[siz[find(t)]] == tot && maxn < tot)
{
maxn = tot;
ans = a[t] + 1;
}
}
cout<<ans;
}