今日得分：25+100+20

T1

题目大意：给定一棵n个节点的树，节点编号为1~n，初始时每个节点都未被占领。两个人轮流操作，每人每步操作会占领一个未被占领的节点，直到所有节点都被占领为止。 定义树上两点的距离为它们之间最短路径的边数，所有操作结束后，游戏的分值为先手占领的所有节点两两间的最大距离。先手希望这个分值尽可能小，而后手希望这个分值尽可能大。如果两人都采取最优策略行动，请问游戏的最终分值是多少。n<=1e5。

题解：

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline int re_ad()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
	return x*f;
}
int n;
int dis[100010],root,fa[100010],D;
int G[100010],H[100010];
vector<int> g[100010];bool jia1;
void dfs(int x)
{
	register int i,sz=g[x].size(),v;
	for(i=0;i<sz;++i)
	{
	v=g[x][i];if(v==fa[x])continue;
	dis[v]=dis[x]+2;fa[v]=x;dfs(v);
	}
}
void dfs2(int x)
{
	register int i,sz=g[x].size(),v;
	if(dis[x]==(D>>1))++G[x];
	if(dis[x]==(D>>1)-2)++H[x];
	for(i=0;i<sz;++i)
	{
	v=g[x][i];if(v==fa[x])continue;
	dis[v]=dis[x]+2-(jia1&&(x==root));
	fa[v]=x;
	dfs2(v);
	G[x]+=G[v];H[x]+=H[v];
	}
}
int main()
{
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	register int i,x,y;
	register int num1,num2,pl1=0,pl2=0,H3=0;
	n=re_ad();
	for(i=1;i<n;++i){x=re_ad();y=re_ad();g[x].push_back(y);g[y].push_back(x);}
	dfs(1);
	for(i=1;i<=n;++i)if(dis[i]>dis[root])root=i;
	memset(dis,0,sizeof(dis));fa[root]=0;
	dfs(root);
	for(i=1;i<=n;++i)if(dis[i]>dis[root])root=i;
	x=dis[root]>>1;D=dis[root];
	for(i=1;i<=(x>>1);++i)root=fa[root];
	if(x&1){
	++n;g[n].push_back(root);g[n].push_back(fa[root]);
	for(vector<int>::iterator it=g[root].begin();it!=g[root].end();++it){if((*it)==fa[root]){g[root].erase(it);break;}}
	for(vector<int>::iterator it=g[fa[root]].begin();it!=g[fa[root]].end();++it){if((*it)==root){g[fa[root]].erase(it);break;}}
	fa[n]=0;root=n;jia1=true;
	}
	fa[root]=0;memset(dis,0,sizeof(dis));
	dfs2(root);
	num1=num2=0;
	x=root;
	for(i=0;i<g[x].size();++i)
	{
	y=g[x][i];
	if(G[y]){++num1;if(G[y]>1)++num2;if(!pl1)pl1=y;else if(!pl2)pl2=y;}
	}
	if(jia1)--n;
	if(num1>=4||(num1==3&&(n&1))||(num1==3&&num2)||(num2>1)||(num2&&(n&1))){cout<<D/2<<endl;return 0;}
	if(num1==3||(num2)||(n&1)){cout<<D/2-1<<endl;return 0;}
	for(i=0;i<g[x].size();++i)
	{
	y=g[x][i];
	if(H[y])
	{
	if(y!=pl1&&y!=pl2)H3+=H[y];
	}
	}
	if(H3>1){cout<<D/2-1<<endl;return 0;}
	num2=0;
	if(H[pl1]>1)++num2;if(H[pl2]>1)++num2;
	if(num2>1||(H3&&num2)){cout<<D/2-1<<endl;return 0;}
	{cout<<D/2-2<<endl;return 0;}
}

T2

题目大意：给定二维平面上若干个红点（横坐标为负），若干个蓝点（横坐标为正）。 多次询问，每次要找到点权和最大的一对红蓝点 ，满足红点纵坐标小于蓝点纵坐标，且二者横坐标都在特定区间中，或都在特定区间外。 n <= 1e5, m <= 5e5，|坐标|<=1e9。

题解：考虑纵坐标在[l,r]中的所有点，分成[l,mid]和[mid,r]的两个区间，根据询问的性质，有左区间中的红点最大值和右区间中的蓝点最大值不会都不被选到（可以通过反证得到）。于是分治得到所有可能的答案点对，共有nlogn个，转化为二维数点问题。排序+树状数组即可。时间复杂度O(nlog^2n)（排序复杂度）。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline int re_ad()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
	return x*f;
}
inline int ma(int x,int y){return x>y?x:y;}
int n,n2,m,q,lsh[1500010];
struct node{int x,y,w,col;}a[200010];
bool cmp1(node x,node y){return x.y<y.y;}
struct nod{int l,r,id;}xw[500010],dd[4000010];
bool cmp2(nod x,nod y){return a[x.l].x<a[y.l].x;}
bool cmp3(nod x,nod y){return x.l<y.l;}
int cnt,tot;
int ans[500010],t[1500010];
void solve(int l,int r)
{
	if(l==r)return ;
	register int i,mid=(l+r)>>1,pla;
	solve(l,mid);solve(mid+1,r);
	pla=0;for(i=l;i<=mid;++i){if(!a[i].col&&a[i].w>a[pla].w)pla=i;}
	if(pla)for(i=mid+1;i<=r;++i)if(a[i].col)dd[++cnt]=(nod){pla,i};
	pla=0;for(i=mid+1;i<=r;++i){if(a[i].col&&a[i].w>a[pla].w)pla=i;}
	if(pla)for(i=l;i<=mid;++i)if(!a[i].col)dd[++cnt]=(nod){i,pla};
}
inline void add(int x,int nu){while(x<=m)t[x]=ma(t[x],nu),x+=x&(-x);}
inline int ask(int x){int ret=-1;while(x){ret=ma(ret,t[x]);x-=x&(-x);}return ret;}
int main()
{
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	register int i,j;
	n=re_ad();n2=n*2;
	for(i=1;i<=n;++i)
	{
	a[i].x=re_ad();a[i].y=re_ad();a[i].w=re_ad();a[i].col=0;lsh[++lsh[0]]=a[i].x;
	}
	for(i=n+1;i<=n2;++i)
	{
	a[i].x=re_ad();a[i].y=re_ad();a[i].w=re_ad();a[i].col=1;lsh[++lsh[0]]=a[i].x;
	}
	sort(a+1,a+n2+1,cmp1);
	solve(1,n2);sort(dd+1,dd+cnt+1,cmp2);
	q=re_ad();
	for(i=1;i<=q;++i)
	{
	xw[i].l=lsh[++lsh[0]]=re_ad();xw[i].r=lsh[++lsh[0]]=re_ad();ans[i]=-1;xw[i].id=i;
	}
	sort(lsh+1,lsh+lsh[0]+1);m=unique(lsh+1,lsh+lsh[0]+1)-lsh-1;
	for(i=1;i<=n2;++i)a[i].x=lower_bound(lsh+1,lsh+m+1,a[i].x)-lsh;
	for(i=1;i<=q;++i)
	{
	xw[i].l=lower_bound(lsh+1,lsh+m+1,xw[i].l)-lsh;xw[i].r=lower_bound(lsh+1,lsh+m+1,xw[i].r)-lsh;
	}
	sort(xw+1,xw+q+1,cmp3);
	j=1;memset(t,-1,sizeof(t));
	for(i=1;i<=q;++i)
	{
	while(j<=cnt&&a[dd[j].l].x<=xw[i].l){add(m+1-a[dd[j].r].x,a[dd[j].l].w+a[dd[j].r].w);++j;}
	ans[xw[i].id]=ma(ans[xw[i].id],ask(m+1-xw[i].r));
	}
	j=cnt;memset(t,-1,sizeof(t));
	reverse(xw+1,xw+q+1);
	for(i=1;i<=q;++i)
	{
	while(j>=1&&a[dd[j].l].x>=xw[i].l){add(a[dd[j].r].x,a[dd[j].l].w+a[dd[j].r].w);--j;}
	ans[xw[i].id]=ma(ans[xw[i].id],ask(xw[i].r));
	}
	for(i=1;i<=q;++i)printf("%d\n",ans[i]);
	return 0;
}

T3

题目大意：有R个红球，B个蓝球，还有一个绿球。以某种方式将它们排列成一排，令lR,lB,rR,rB表示绿球左/右边的红/蓝球个数，这种排列方案的分值为最大的整数x满足：lB*x<=lR且rB*x<=rR。请求出所有不同排列方案的分值之和，答案对998244353取模。注意同色小球是不可区分的。1<=R<=1e18,1<=B<=1e6。

题解：