D. Optimal Partition

题意：
给你长度为 $n$ 的数组 $a$ ，将其划分为任意数量的连续子串，一个子串 $\sim r$ 的价值为
$sign(\sum_{i = l}^{r}a_i)*(r-l+1)$
问可以划分出来的子串价值之和最大是多少
思路：
考虑 $d p$ ,定义 $d p [i]$ 表示前 $i$ 个数字可以达到的最大价值，前缀和 $s u m [i]$ 表示前 $a$ 中前 $i$ 个数字之和
于是我们可以得到一个暴力的 $d p$ 转移方程

for(int i=1;i<=n;i++) 
{
	f[i]=-INF;
	for(int j=0;j<i;j++)
	{
		if(sum[i]-sum[j]>0) f[i]=max(f[i],f[j]+(i-j));
		if(sum[i]==sum[j]) f[i]=max(f[i],f[j]);
		if(sum[i]-sum[j]<0) f[i]=max(f[i],f[j]+(j-i));
	}
}

时间复杂度 $O(n^2)$
观察发现，转移过程只可能与三个数有关： $f [j] ? j, f [j], f [j] + j$
于是我们只需要构造一棵表示前缀和大小的权值线段树，在树上同时维护上面的三个数字即可

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define pb push_back
typedef long long ll;
using namespace std;
const int maxn=5e5+7;
ll a[maxn],n,s[maxn],f[maxn];
vector<ll>v;
int getnum(int x)
{
	return lower_bound(v.begin(),v.end(),x)-v.begin();
}
struct tree
{
	int l,r,v1,v2,v3;
	int mid(){return l+r>>1;}
}tre[maxn<<2];
void pushup(int num)
{
    tre[num].v1=max(tre[2*num].v1,tre[2*num+1].v1);
	tre[num].v2=max(tre[2*num].v2,tre[2*num+1].v2);
	tre[num].v3=max(tre[2*num].v3,tre[2*num+1].v3);
}
void build(int num,int l,int r)
{
	tre[num].l=l,tre[num].r=r;
	if(l==r)
	{
		 tre[num].v1=tre[num].v2=tre[num].v3=-inf;return;
	}
	int mid=tre[num].mid();
	build(2*num,l,mid);
	build(2*num+1,mid+1,r);
	pushup(num);
}
tuple<int,int,int> query(int num,int l,int r)
{
	if(tre[num].l==l && tre[num].r==r)
	{
		return make_tuple(tre[num].v1,tre[num].v2,tre[num].v3);
	}
	int mid=tre[num].mid();
	if(l>mid)
	return query(2*num+1,l,r);
	else if(r<=mid)
	return query(2*num,l,r);
	else
	{
		auto [a1,a2,a3]=query(2*num,l,mid);
		auto [b1,b2,b3]=query(2*num+1,mid+1,r);
		return make_tuple(max(a1,b1),max(a2,b2),max(a3,b3));
	}
}
void update(int num,int n,tuple<int,int,int> k)
{
	auto [a1,a2,a3]=k;
	if(tre[num].l==tre[num].r)
	{
		tre[num].v1=max(tre[num].v1,a1);
		tre[num].v2=max(tre[num].v2,a2);
		tre[num].v3=max(tre[num].v3,a3);
		return;
	}
	int mid=tre[num].mid();
	if(n<=mid) update(2*num,n,k);
	else update(2*num+1,n,k);
	pushup(num);
}
signed main()
{
	int T;
	scanf("%lld",&T);
	while(T--)
	{
		v.clear();
		scanf("%lld",&n);
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]),f[i]=-inf;
		for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i],v.pb(s[i]);
		v.pb(0);v.pb(-1e18);v.pb(1e18);
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		int sz=v.size();
		build(1,0,sz);
		update(1,getnum(0),make_tuple(0,0,0));
		for(int i=1;i<=n;i++)
		{
			int x=getnum(s[i]);
			auto a1=query(1,0,x-1);
			f[i]=max(f[i],get<0>(a1)+i);
			auto a2=query(1,x,x);
			f[i]=max(f[i],get<1>(a2));
			auto a3=query(1,x+1,sz-1);
			f[i]=max(f[i],get<2>(a3)-i);
			update(1,x,make_tuple(f[i]-i,f[i],f[i]+i));
		}
		printf("%lld\n",f[n]);
	}
}

E. Half Queen Cover

题意：
在棋盘上一个皇后可以同时攻击自身所在的行，列，以及一条对角线，方式如图
攻击方式
给你 $n ? n$ 大小的棋盘，求最少放置的皇后数量，以及每个皇后的放置位置，可以使皇后的攻击覆盖整个棋盘
思路：
为了避免重复攻击，应该尽可能的将皇后放置在行，列，对角线均不同的位置
假设我们当前摆放了 $k$ 个皇后，如果不考虑对角线，剩余部分应该是一个 $(n ? k) ? (n ? k)$ 的正方形，这个正方形有 $2 ? (n ? k) ? 1$ 条对角线
那么我们只要 $k > = s ? (n ? k) ? 1$ 即可，然后保证 $k$ 个皇后行，列，对角线各不相同

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=2e5+7;
int main()
{
    int n;
	scanf("%d",&n);
    int ans=(2*n+1)/3;
    cout<<ans<<endl;
    for(int i=1,j=1;i<=ans;i++)
    {
		if(j>ans)j=2;
        printf("%d %d\n",i,j);
        j+=2;
    }
}

F. Edge Elimination

题意：
给你一颗树，若树上有一条边两侧的点的度数和为偶数，则可将该边删去，求该树上的边是否可以完全删除，若可以，请输出删除的顺序
思路：
若一条边在删除时，两点的度数均为偶数，我们称之为偶数边，若均为奇数，称之为奇数边
可以发现，与同一个点连接的 $k$ 条边中，若 $k$ 为偶数，则偶数边数量等于奇数边，否则，奇数边数量等于偶数边数量加一，而删除的过程一定是奇数边和偶数边交替进行的
而树上的叶子节点连接的边一定属于奇数边，于是我们就可以通过递归来判断边的奇偶性能否满足上述要求，如果可以满足，就一定存在合法解
在输出答案时，考虑树上每个节点的父节点以及路径为一，只需要递归让奇偶依次使用即可

#include<bits/stdc++.h>
#define pb push_back
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
typedef pair<int,int> PII;
const int maxn=2e5+7;
int num,n,head[maxn],ok,parity[maxn],pre[maxn];
struct road{int b,c,nex;}r[2000005];
void add(int a,int b,int c){r[num].b=b;r[num].c=c;r[num].nex=head[a];head[a]=num++;}
vector<PII>ans;
void dfs(int u,int fa)
{
	int odd=0,even=0;
	for(int i=head[u];~i;i=r[i].nex)
	{
		int v=r[i].b;
		if(v==fa) continue;
		pre[v]=u;
		dfs(v,u);
		if(parity[v]==1) odd++;
		else even++;
	}
	if(u!=1)
	{
		if(odd<=even) parity[u]=1,odd++;
		else parity[u]=0,even++;
	}
	if(even>odd || odd-even>1) ok=0;
}
void slove(int u)
{
	vector<int>p[2];
	int cnt=0;
	for(int i=head[u];~i;i=r[i].nex)
	{
		cnt++;
		int v=r[i].b;
		if(pre[u]==v) p[parity[u]].pb(u);
		else p[parity[v]].pb(v);
	}
	for(int i=cnt%2,j=1;j<=cnt;j++,i=(i+1)%2)
	{
		int num=p[i].back();
		if(num==u) printf("%d %d\n",u,pre[u]);
		else slove(num);
		p[i].pop_back();
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		num=0;ans.clear();ok=1;
		for(int i=1;i<=n;i++) head[i]=-1;
		for(int i=1;i<n;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			add(a,b,0);add(b,a,0);
		}
		dfs(1,-1);
		if(ok) 
		{
			puts("YES");
			slove(1);
		}
		else puts("NO");
	}
}