今日得分：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，

題解：