Codeforces Global Round 19

这场构造题蛮多。

A. Sorting Parts

题意

有一长度为$n$的数组$a$，你能进行一次操作——选定一个整数$len$，升序排序$a[1\dots len]$和$a[len+1\dots n]$。

判断操作后存在数组$a$不为升序的情况。

题解

显然等价于$a$数组为升序

代码

int main(){
	int T;cin>>T;
	while (T--){
		int n;vec<int> v;
		cin>>n>>rtar(v,n);
		cout << (!is_sorted(all(v))?"YES":"NO") << endl;
	}
}

B. MEX and Array

题意

定义关于数组的价值函数$f(a)$为，对$a$分割成$c$个数组$b_1\dots b_c$，$c + \sum_{i = 1}^{c} \operatorname{mex}(b_i)$的最小值。

$\operatorname{mex}(a)$表示最小未在$a$数组中出现的最小非负整数。

求数组$a$的所有子串$as$的$f(as)$的和。

题解

先求出$a$数组的每一个区间的$mex$，然后区间DP。

代码

int D[101][101],DP[101][101];
int main(){
	int T;
	cin>>T;
	while (T--){
		int n;vec<int> v;
		cin>>n>>rtar(v,n);
		for (int len=1;len<=n;len++)
			for (int l=0,r=l+len-1;r<n;l++,r++){
				vec<int> vv(v.begin()+l,v.begin()+r+1);
				sort(all(vv));
				int w=0;
				while (w<vv.size()&&vv[w]==w) w++;
				D[l][r]=w;
			}
		
		memset(DP,0,sizeof(DP));
		for (int len=1;len<=n;len++)
			for (int l=0,r=l+len-1;r<n;l++,r++){
				DP[l][r]=D[l][r]+1;
				for (int i=l;i<r;i++){
					cmax(DP[l][r],DP[l][i]+DP[i+1][r]);
				}
			}
		int sum=0;
		for (int len=1;len<=n;len++)
			for (int l=0,r=l+len-1;r<n;l++,r++){
				sum+=DP[l][r];
			}
		cout<<sum<<endl;
	}
}

C. Andrew and Stones

题意

有长度为$n$的数组$a$，可以无限执行操作——选定$i<j<k$，令$a_j$减2，$a_i$和$a_k$加1。

求将数组中$a_2\dots a_{n-1}$置0的最小操作数。

题解

1. 全部都是偶数的情况，固定$i=1,k=n$即可，答案就是$\sum_{i=2}^{n-1}a_i$

2. 如果存在奇数，需要其他数字借他$1$个变成偶数

3. 考虑存在不能借给奇数让他变成偶数的情况

   1. $n=3$，$a_2$为奇数

   2. 因为在一个奇数变成偶数后又可以借出$1$个，所以如果存在大于$1$的奇数一定可以成功所以

      $a_2\dots a_{n-1}$全部都是$1$

代码

int main(){
	int T;
	cin>>T;
	while (T--){
		int n;vec<int> v;
		cin>>n>>rtar(v,n);
		multiset<int> odd,even;
		for (int i=1;i<n-1;i++){
			if (v[i]%2) odd.insert(v[i]);
			else even.insert(v[i]);
		}
		ll w=[&](){
			ll s=0;
			if (even.size()==0&&[&](){
				for (auto i:odd)
					if (i!=1)
						return false;
				return true;
			}()) return -1ll;
			if (even.size()==0&&odd.size()==1) return -1ll;
			for (auto i:odd) s+=(i+1)/2;
			for (auto i:even) s+=i/2;
			return s;
		}();
		cout<<w<<endl;
	}
}

D. Yet Another Minimization Problem

题意

给定两个长度为$n$的数组$a,b$。有价值函数$f(a)=\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2$。允许交换$a_i,b_i$，求$\min(f(a)+f(b))$。

题解

$f(a)=\sum_{i=1}^n (n-1)\cdot a_i^2 +\sum_{i=1}^{n} \sum_{j=i + 1}^{n} 2 a_i a_j$

$f(a)+f(b)=\sum_{i=1}^n (n-1)\cdot (a_i^2+b_i^2) +\sum_{i=1}^{n} \sum_{j=i + 1}^{n} 2 a_i a_j +\sum_{i=1}^{n} \sum_{j=i + 1}^{n} 2 b_i b_j$

不难发现不论怎么操作，$\sum_{i=1}^n (n-1)\cdot (a_i^2+b_i^2)$是个常数，尝试求$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} 2 a_i a_j +\sum_{i=1}^{n} \sum_{j=i + 1}^{n} 2 b_i b_j$的最小值。

加上$\sum_{i=1}^n(a_i^2+b_i^2)$，即可化为求$\sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j +\sum_{i=1}^{n} \sum_{j=1}^{n} b_i b_j$的最小值。

设$c=a\lor b$（$\lor$表示连接），显然$\sum_{i=1}^{2n}\sum_{j=1}^{2n} c_ic_j$是个常数。（操作对c的影响为调换两个元素的位置，这个函数对位置不敏感）

而$\sum_{i=1}^{2n}\sum_{j=1}^{2n} c_ic_j=\sum_{i=1}^{n} \sum_{j=1}^{n} c_i c_j +\sum_{i=n+1}^{2n} \sum_{j=n+1}^{2n} c_i c_j+\sum_{i=1}^{n} \sum_{j=n+1}^{2n} c_ic_j=\sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j +\sum_{i=1}^{n} \sum_{j=1}^{n} b_i b_j+\sum_{i=1}^{n} \sum_{j=1}^{n} a_ib_j$

要求$\sum_{i=1}^{n} \sum_{j=1}^{n} a_i a_j +\sum_{i=1}^{n} \sum_{j=1}^{n} b_i b_j$的最小值，即求$\sum_{i=1}^{n} \sum_{j=1}^{n} a_ib_j$的最大值。

$\sum_{i=1}^{n} \sum_{j=1}^{n} a_ib_j=\sum_{i=1}^{n}a_i \cdot \sum_{j=1}^{n} b_j$

显然$\sum_{i=1}^{n}a_i+\sum_{j=1}^{n} b_j$是个常数，设其为$S$；设$\sum_{i=1}^{n}a_i$为$Sa$

即求$\max\{(S-Sa)\cdot(Sa)\}$，对勾函数，用背包求$Sa$的值域，找出最靠近$S/2$的值即可。

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T> using vec=vector<T>;
template<class T>
T operator+=(vec<T>& a,T b){
	a.push_back(b);
	return move(b);
}
int main(){
	int T;
	cin>>T;
	while (T--){
		int n,sum=0;
		vec<int> a,b,c;
		cin>>n;
		for (int i=0,j;i<n;i++){
			cin>>j;
			sum+=j;
			c+=a+=j;
		}
		for (int i=0,j;i<n;i++){
			cin>>j;
			sum+=j;
			c+=b+=j;
		}
		constexpr int N=10000;
		using bT=bitset<N+1>;
		bT d;
		d[0]=1;
		auto add=[](bT &a,bT& b,int t){
			for (int w=N-t;w>=0;w--)
				if (a[w]) b[w+t]=1;
		};
		for (int i=0;i<n;i++){
			bT d2;
			swap(d2,d);
			add(d2,d,a[i]);
			add(d2,d,b[i]);
		}
		int r=sum/2;
		while (!d[r]) r--;
		ll ans=0;
		for (auto &i:a) ans+=(n-1)*i*i;
		for (auto &i:b) ans+=(n-1)*i*i;
		for (int i=0;i<c.size();i++)
			for (int j=i+1;j<c.size();j++)
				ans+=2*c[i]*c[j];
		ans-=2*r*(sum-r);
		cout<<ans<<endl;
	}
}

E. Best Pair

题意

给定长度为$n$的数组$a$，定义$cnt_x$为$a$中有多少个$x$。定义$f(x,y)=(cnt_x+cnt_y)\cdot(x+y)$。

给定$m$个$x_i,y_i$，$\forall i,f(x_i,y_i)$不为良定义。

求$f(x,y)$的最大值。

题解

枚举$cnt_x,cnt_y$，此时$f(x,y)$分别关于$x,y$单调，最大值为取$\max x$和$\max y$时。如果此对不为良定义，则添加${\max' x,\max y}$和$\max x,\max' y$。$\max' x$表示第二大的值。

代码

int main(){
	int T;cin>>T;
	while (T--){
		int n,m;
		vec<int> v;
		vec<pair<int,int>> xy;
		cin>>n>>m>>rtar(v,n)>>rtar(xy,m);
		sort(all(v));
		for (auto &[x,y]:xy) if (x>y) swap(x,y);
		sort(all(xy));
		using pT=pair<int,int>;
		auto findxy=[&xy](pT xyi){
			if (xyi.x>xyi.y) swap(xyi.x,xyi.y);
			auto r=lower_bound(all(xy),xyi);
			if (r==xy.end()) return false;
			return *r==xyi;
		};
		map<int,vec<int>> cv;
		for (int i=0,j=0;i<n;i=j){
			while (j<n&&v[i]==v[j]) j++;
			cv[j-i].pb(v[i]);
		}
		ll maxn=0;
		auto f=[&maxn,&findxy](ll cnt,const vec<int>& v1,const vec<int>& v2){
			using rIT=decltype(v1.rbegin());
			using ppT=pair<rIT,rIT>;
			set<ppT> sp;
			deque<ppT> check;
			auto add=[&](ppT xyi){
				if (sp.find(xyi)!=sp.end()) return ;
				sp.insert(xyi);
				check.pb(xyi);
			};
			add({v1.rbegin(),v2.rbegin()});
			while (check.size()){
				auto d=check.front();
				pT dv={*d.x,*d.y};
				check.pop_front();
				if (findxy(dv)||(d.x==d.y)){
					if (d.x+1!=v1.rend())
						add({d.x+1,d.y});
					if (d.y+1!=v2.rend())
						add({d.x,d.y+1});
				}else 
					cmax(maxn,cnt*(dv.x+dv.y));
			}
		};
		for (auto ci1=cv.begin();ci1!=cv.end();ci1++){
			const auto& [cnt1,v1]=*ci1;
			for (auto ci2=next(ci1);ci2!=cv.end();ci2++){
				const auto& [cnt2,v2]=*ci2;
				f(cnt1+cnt2,v1,v2);
			}
			f(cnt1+cnt1,v1,v1);
		}
		cout << maxn << endl;
	}
}

F. Towers

题意

给定一颗$n$个节点的树$T$，每个节点有$h_i$属性。你可以指定每个节点的$e_i$属性，称一个节点$x$被照亮当且仅当存在$u,v(u\not = v)$且$x$在$u-v$的路径上（$x$可以等于$u,v$）。求所有节点照亮时，$\sum e_i$最小值。

题解

观察到如果存在一个解的话，一个非叶子节点的$e$完全可以转移到叶子节点上，而且这点权值能覆盖到更多的节点。所以所有的非叶子节点的$e=0$。

考虑一颗根结点为$t$的子树$A$，假设$T-A$中存在一个$e_i=+\infin$的节点，那么要维护$t$节点被照亮，只需要令$A$中的一个叶子的$e\ge h_t$即可。用一个变量记录子树的叶子$e$的最大值，不满足累加答案即可。

最终递归到树根时，如果树根的$h$不是最大值就比较难处理，不妨选定$h$最大值的点为树根。那么只需让最大的儿子和次大的儿子提升到树根的$h$即可形成路径。

代码

int n;
vec<int> vv;
vec<vec<int>> G;
ll ans=0;
int dfs(int u,int p){
	int m1=0,m2=0;
	auto addm=[&](int dv){
		if (dv>m1) swap(dv,m1);
		if (dv>m2) swap(dv,m2);
	};
	for (auto& v:G[u])
		if (v!=p)
			addm(dfs(v,u));
	if (p==-1){
		ans+=(vv[u]-m1)+(vv[u]-m2);
	}else {
		ans+=max(vv[u]-m1,0);
		addm(vv[u]);
	}
	return m1;
}
int main(){
	cin>>n>>rtar(vv,n);
	G.resize(n);
	for (int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		u--;v--;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(max_element(all(vv))-vv.begin(),-1);
	cout << ans << endl;
}