好菜，B都没做出来。。
B. Sonya and Exhibition
一开始被样例给迷惑了，一直在想如何根据区间进行构造，但怎么写都感觉有bug。。
实际上玫瑰花和茉莉花交叉排序就行了。
我是真的菜啊。
#include<bits/stdc++.h>
using namespace std;
int main()
{int n,m;scanf("%d %d",&n,&m);int l,r;for(int i=1;i<=m;i++)scanf("%d %d",&l,&r);for(int i=1;i<=n;i++){printf("%d",i%2);}puts("");
}D. Sonya and Matrix
这个题没怎么想。。我们最开始可以知道第一个没出现完整的数和最大的数，然后我们可以枚举行列，根据行列求出0所在的位置，再判断一下是否符合输入即可。
#include<bits/stdc++.h>
using namespace std;int a[1000005];
bool flag;
int mx=-1;
int id;
int tmpp[1000005];bool check()
{for(int i=1;i<=mx;i++)if(a[i]!=tmpp[i])return 0;return 1;}
void work(int n,int m)
{int y=id;int Left=m-id;Left=max(Left,y-1);int x=mx-Left+1;if(x<=0||y<=0||x>n||y>m)return;memset(tmpp,0,sizeof(tmpp));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)tmpp[abs(i-x)+abs(j-y)]++;if(check()){flag=1;cout<<n<<' '<<m<<endl;cout<<x<<' '<<y<<endl;}}
int main()
{int t;scanf("%d",&t);int tmp;for(int i=1;i<=t;i++){scanf("%d",&tmp);a[tmp]++;mx=max(mx,tmp);}for(int i=0;i<=mx+1;i++)if(a[i]<i*4){id=i;break;}for(int i=1;i<=sqrt(t)&&!flag;i++)if(t%i==0){if(!flag)work(i,t/i);if(!flag)work(t/i,i);}if(!flag)puts("-1");}E. Sonya and Ice Cream
E题又看错题意了。。
实际上我们可以推出所在的连续的线肯定在直径上，那么我们可以枚举直径上的起点，答案即为max(直径上的点到其子树的最大距离,直径的两个端点到枚举的线的两个端点的最大距离)
所以我们首先得求出直径有哪些点，然后维护直径的端点到直径的点的距离。
其次我们还得求出直径上的点到其子树的最大距离。
我们在枚举直径上的起点时，可以用单调队列来维护当前线段的点到其子树的最大距离，然后再与直径端点到线段端点的距离比较即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct Edge
{int u,v,dist;int nxt;Edge(int _u,int _v,int _d,int _nxt):u(_u),v(_v),dist(_d),nxt(_nxt) {}Edge() {}
} edges[maxn*2];
int head[maxn],tot;
void addedge(int u,int v,int d)
{edges[tot]=Edge(u,v,d,head[u]);head[u]=tot++;
}
int n,k;
int pre[maxn+1];
int dist[maxn+2];
int maxlen;
bool vis[maxn+3];
void dfs(int u,int fa)
{pre[u]=fa;for(int i=head[u]; ~i; i=edges[i].nxt){int v=edges[i].v;if(v==fa||vis[v])continue;int d=edges[i].dist;dist[v]=dist[u]+d;maxlen=max(maxlen,dist[v]);dfs(v,u);}
}
vector<int>V1;
int theLen[maxn];
void solve1()
{dist[1]=0;dfs(1,-1);int idx,maxdis=-1;for(int i=1; i<=n; i++){if(maxdis<dist[i]){maxdis=dist[i];idx=i;}}int st=idx;dist[st]=0;dfs(st,-1);maxdis=-1;for(int i=1; i<=n; i++){if(maxdis<dist[i]){maxdis=dist[i];idx=i;}}while(idx!=-1){V1.push_back(idx);idx=pre[idx];}reverse(V1.begin(),V1.end());for(int i=0; i<V1.size(); i++)theLen[i]=dist[V1[i]];
}
int MaxLen[maxn+5];
void GetMaxLen()
{k=min(k,(int)V1.size());for(int i=0; i<V1.size(); i++)vis[V1[i]]=1;for(int i=0; i<V1.size(); i++){dist[V1[i]]=0,maxlen=0;dfs(V1[i],-1);MaxLen[i]=maxlen;}
}void solve2()
{deque<pair<int,int> >Q;Q.clear();int j=0;int ans=1e9;for(int i=0; i<=V1.size()-k; i++){while(j<i+k){while(!Q.empty()&&Q.back().first<MaxLen[j])Q.pop_back();Q.push_back(make_pair(MaxLen[j],j));j++;}while(!Q.empty()&&Q.front().second<i)Q.pop_front();ans=min(ans,max({Q.front().first,theLen[i],theLen[V1.size()-1]-theLen[i+k-1]}));}cout<<ans<<endl;
}
int main()
{memset(head,-1,sizeof(head));scanf("%d %d",&n,&k);int u,v,d;for(int i=1; i<n; i++){scanf("%d %d %d",&u,&v,&d);addedge(u,v,d);addedge(v,u,d);}solve1();GetMaxLen();solve2();
}逻辑还是很清晰的，但还有一点需要注意的是，当所给的k大于直径上的点个数时，我们这时就用不到k个了。所以我们需要判断一下k与直径上的点的个数的大小。