ARC 122 简要题解

A - Many Formulae

考虑对于每个数分别算其贡献。

通过枚举该数前面的符号，借助一个非常简单的 \(\mathrm{DP}\)（\(f_{i,0/1}\) 表示 \(i\) 个符号，最后一个符号为 \(+/-\) 的方案数），我们可以很轻松的求出一个数对最终答案的贡献。

总时间复杂度为 \(O(n)\)。

/*---Author:HenryHuang---*/

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;

const int p=1e9+7;

int dp[maxn][2];

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int n;cin>>n;

	dp[1][0]=dp[1][1]=1;

	for(int i=2;i<n;++i){

		dp[i][1]=dp[i-1][0];

		dp[i][0]=(dp[i-1][0]+dp[i-1][1])%p;

	}

	int ans=0;

	dp[0][0]=1;

	for(int i=1;i<=n;++i){

		int x;cin>>x;

		ans=(ans-1ll*x*dp[i-1][1]%p*dp[n-i][0]%p+p)%p;

		ans=(ans+1ll*x*dp[i-1][0]%p*(dp[n-i][0]+dp[n-i][1])%p)%p;

	}

	cout<<ans<<'\n';

	return 0;

}

B - Insurance

猜想答案一定在某个数处取得，所以把所有数排序计算出所有的答案取个 \(\min\) 即可。

更为靠谱的做法的是，这个函数显然是个凸函数，你可以直接三分，你也可以直接排序过后取中位数的位置计算答案。

总时间复杂度为 \(O(n\log_2n)\)，排序为复杂度瓶颈。

/*---Author:HenryHuang---*/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+5;

ll a[maxn];

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int n;cin>>n;

	ll S=0;

	for(int i=1;i<=n;++i){

		cin>>a[i];

		S+=a[i];

	}

	sort(a+1,a+n+1);

	ll ans=(1ll<<60);

	ll sum=0;

	for(int i=1;i<=n;++i){

		sum+=a[i];

		ans=min(ans,n*a[i]+2*S-2*sum-2*(n-i)*a[i]);

	}

	cout<<setprecision(10)<<fixed<<(double)ans/2.0/n<<'\n';

	return 0;

}

C - Calculator

注意到任意一个正整数 \(n\) 均可以表示为若干个斐波那契数的和。（证明大概可以数学归纳法，在此不再赘述）

然后原问题中 \(3,4\) 操作交替可以组成斐波那契数，然后斐波那契数可以一起递推。

然后随便搞搞就行了，注意一些可能的细节，例如可能递推到最后某一项落在 \(y\) 上需要特殊处理。

还有一种方法，你大概可以找到 \(\phi \times n\)，其中 \(\phi\) 是黄金分割比。然后令 \(x=n,y=\phi \times n\)，倒着做，处理一些必要的边界即可。

/*---Author:HenryHuang---*/

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

ll f[100];

vector<int> ans;

int flag[100],tag[100];

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	ll n;cin>>n;

	f[0]=f[1]=1;

	for(int i=2;i<=88;++i) f[i]=f[i-1]+f[i-2];

	for(int i=88;i>=1;--i){

		if(n>=f[i]) n-=f[i],ans.emplace_back(i);

	}

	int now=ans[0],tim=0;

	for(auto x:ans){

		if((now&1)==(x&1)){

			tag[x]=1;

			flag[x]=1;

		}

		else{

			tag[x+1]=2;

			flag[x+1]=1;

		}

	}

	ll x=0,y=0;

	vector<int> Ans;

	if(now&1) Ans.emplace_back(2),Ans.emplace_back(3),tim=1;

	else Ans.emplace_back(1),Ans.emplace_back(4),tim=0;

	for(int i=now-1;i>=1;--i){

		if(flag[i]){

			if(tag[i]==1){

				if(tim==1) Ans.emplace_back(1);

				else Ans.emplace_back(2);

			}

			else{

				if(tim==1) Ans.emplace_back(2);

				else Ans.emplace_back(1);

			}

		}

		if(tim==1) Ans.emplace_back(4);

		else Ans.emplace_back(3);

		tim^=1;

	}

	cout<<Ans.size()<<'\n';

	for(auto u:Ans){

		cout<<u<<'\n';

		if(u==1) ++x;

		if(u==2) ++y;

		if(u==3) x=x+y;

		if(u==4) y=x+y;

	}

//	cout<<x<<' '<<y<<'\n';

	return 0;

}

D - XOR Game

注意到如果存在一对完美匹配，使得每对匹配的数的异或的最大值为 \(x\)，那么一定可以构造一组解使得最终答案为 \(x\)。

构造显然，按照匹配构造即可。

所以 Alice 在这个游戏里没啥用，全看 Bob 操作

所以现在问题转化为了找一对完美匹配，使得每对匹配的数的异或的最大值最小。

我们从高位到低位考虑。

若当前位置 \(0\) 的个数和 \(1\) 的个数均为偶数个，那么我们可以将其内部两两匹配使得答案在这一位上全部为 \(0\)，分开递归继续计算即可。
否则我们只需要在对于每一个当前位置为 \(0\) 的数，求出其与当前位置为 \(1\) 的数的异或的最小值即可。注意到此时我们并不需要递归继续计算，因为其他位置对答案的贡献在这一位上都是 \(0\)，一定比我们求出的这个异或的最小值更小。

然后做完了。

总时间复杂度为 \(O(n\log_2\max{a_i})\)。

/*---Author:HenryHuang---*/

/*---Never Settle---*/

/*---Never Enough---*/

#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+5;

struct TRIE{

	int ch[maxn*30][2],cnt,rt;

	void clear(){

		for(int i=0;i<=cnt;++i) ch[i][0]=ch[i][1]=0;

		cnt=rt=0;

	}

	void insert(int x){

		int now=rt;

		for(int i=29;i>=0;--i){

			int v=((x&(1<<i))!=0);

			if(!ch[now][v]) ch[now][v]=++cnt;

			now=ch[now][v];

		}

	}

	int query(int x){

		int now=rt;

		int ans=0;

		for(int i=29;i>=0;--i){

			int v=((x&(1<<i))!=0);

			if(ch[now][v]) now=ch[now][v];

			else now=ch[now][v^1],ans+=(1<<i);

		}

		return ans;

	}

}trie;

int solve(vector<int> a,int bit){

	if(bit==-1||a.size()==0) return 0;

	vector<int> zero,one;

	for(auto x:a){

		if(x&(1<<bit)) one.emplace_back(x);

		else zero.emplace_back(x);

	}

	if(zero.size()%2==0)

		return max(solve(zero,bit-1),solve(one,bit-1));

	else{

		trie.clear();

		for(auto x:zero) trie.insert(x);

		int ans=(1<<30);

		for(auto x:one) ans=min(ans,trie.query(x));

		return ans;

	}

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int n;cin>>n;

	n<<=1;

	vector<int> v;

	for(int i=1;i<=n;++i){

		int x;cin>>x;

		v.emplace_back(x);

	}

	cout<<solve(v,29)<<'\n';

	return 0;

}

E - Increasing LCMs

一个数 \(a_i\) 能够作为重排过后的最后一个数，当且仅当前面数的 \(\mathrm{lcm}\) 不是其倍数。

形式化的，即 \(\gcd(\mathrm{lcm}_{j\neq i}\{a_j\},a_i)<a_i\)。

稍微变形一下，可以得到 \(\mathrm{lcm}_{j\neq i}\{\gcd(a_j,a_i)\}<a_i\)。

按照这个式子暴力模拟递归做就行了。

时间复杂度为 \(O(n^3\log_2\max a_i)\)。

/*---Author:HenryHuang---*/

/*---Never Settle---*/

/*---Never Enough---*/

#include<bits/stdc++.h>

#define eps 1e-6

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b){

	if(!b) return a;

	return gcd(b,a%b);

}

vector<ll> ans;

void solve(vector<ll> a){

	if(a.size()==1){

		ans.emplace_back(a[0]);

		return ;

	}

	for(int i=0;i<a.size();++i){

		int flag=1;

		ll lcm=1;

		for(int j=0;j<a.size();++j){

			if(j==i) continue;

			ll owo=gcd(a[j],a[i]);

			ll qaq=gcd(lcm,owo);

			if(log(a[i])-log(lcm/qaq)-log(owo)>eps){

				lcm=lcm/qaq*owo;

			}

			else{

				flag=0;

				break;

			}

		}

		if(flag){

			ans.emplace_back(a[i]);

			vector<ll> tmp;

			for(int j=0;j<a.size();++j){

				if(j==i) continue;

				tmp.emplace_back(a[j]);

			}

			solve(tmp);

			break;

		}

	}

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int n;cin>>n;

	vector<ll> v;

	for(int i=1;i<=n;++i){

		ll x;cin>>x;

		v.emplace_back(x);

	}

	solve(v);

	if(ans.size()!=n) cout<<"No\n";

	else{

		cout<<"Yes\n";

		reverse(ans.begin(),ans.end());

		for(auto x:ans) cout<<x<<' ';

		cout<<'\n';

	}

	return 0;

}

F - Domination

场上没人过的神题。

首先注意到如果两个红点 \((x_i,y_i),(x_j,y_j)\)，如果 \(x_i\le x_j,y_i\le y_j\)，那么显然不需要考虑 \((x_i,y_i)\) 这个点，因为 \((x_j,y_j)\) 的限制显然更为严格。

那么所有的红点会自左上到右下大约排成一行，将其按照左上到右下编号。

然后有一个比较显然的转化：

每个红点右上有 \(k\) 个蓝点，等价于将这些蓝点分成 \(k\) 组，使得每组蓝点覆盖所有红点。

假设 \(k=1\)。

考虑如果一个蓝点要覆盖 \([l,r]\) 这个区间内的所有红点，那么他的坐标 \((X,Y)\) 应该满足 \(X\ge x_r,Y\ge y_l\)。

也就是说，如果一个蓝点原来的位置为 \((bx,by)\)，其覆盖 \([l,r]\) 的代价为 \(\max(0,x_r-bx)+\max(0,y_l-by)\)。

我们可以考虑构造这样的一个坐标系：

在 \(y\) 轴上往下走一单位有 \(1\) 的代价，在 \(x\) 轴上往右走有 \(1\) 的代价。

然后在 \(by\) 与 \(bx\) 之间连一条代价为 \(0\) 的边。

则最后覆盖 \([l,r]\) 这个区间的代价就是 \(y_l\) 到 \(x_r\) 的最短路。

推广到覆盖 \([1,n]\) 的情况是类似的。

若 \(k\) 更大，问题就转化为了一个最小费用流问题。

时间复杂度为 \(O(k(n+m)\log_2(n+m))\)。

/*---Author:HenryHuang---*/

/*---Never Settle---*/

/*---Never Enough---*/

#include<bits/stdc++.h>

using namespace std;

const int inf=1e9;

const int maxn=5e5+5;

typedef long long ll;

int n,m,s,t,k;

vector<pair<int,int> > R,B;

vector<int> X,Y;

struct edge{

	int to,nex,w,v;

}e[maxn*30];

int head[maxn],cur[maxn],cnt=1;

void add(int a,int b,int c,int d){

	e[++cnt]=(edge){b,head[a],c,d};

	head[a]=cnt;

}

void addedge(int a,int b,int c,int d){

	add(a,b,c,d),add(b,a,0,-d);

}

int vis[maxn],vi[maxn];

ll flow,cost;

ll dis[maxn],h[maxn];

bool DJ(){

	for(int i=0;i<=t;++i) dis[i]=(1ll<<60),cur[i]=head[i],vi[i]=0;

	priority_queue<pair<ll,int> > Q;

	dis[t]=0;

	Q.emplace(-dis[t],t);

	while(!Q.empty()){

		ll d;int u;tie(d,u)=Q.top();Q.pop();

		if(vi[u]) continue;

		vi[u]=1;

		for(int i=head[u];i;i=e[i].nex){

			int v=e[i].to;

			if(e[i^1].w&&dis[v]>dis[u]+h[u]-h[v]+e[i^1].v){

				dis[v]=dis[u]+h[u]-h[v]+e[i^1].v;

				Q.emplace(-dis[v],v);

			}

		}

	}

	for(int i=0;i<=t;++i) if(dis[i]<(1ll<<60)) h[i]+=dis[i];

	return dis[s]<(1ll<<60);

}

int dfs(int u,int in){

	if(u==t) return in;

	int out=0,tmp;

	vis[u]=1;

	for(int &i=cur[u];i;i=e[i].nex){

		int v=e[i].to;

		if((!vis[v])&&e[i].w&&h[v]-h[u]+e[i].v==0&&(tmp=dfs(v,min(in,e[i].w)))){

			e[i].w-=tmp,e[i^1].w+=tmp;

			in-=tmp,out+=tmp;

			if(!in) break;

		}

	}

	if(!out) dis[u]=0;

	vis[u]=0;

	return out;

}

void MCMF(){

	while(DJ()){

		ll tmp=dfs(s,inf);

		flow+=tmp,cost+=tmp*h[s];

	}

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	cin>>n>>m>>k;

	for(int i=1;i<=n;++i){

		int x,y;cin>>x>>y;

		R.emplace_back(x,y);

	}

	for(int i=1;i<=m;++i){

		int x,y;cin>>x>>y;

		B.emplace_back(x,y);

	}

	sort(R.begin(),R.end());

	int now=0;

	for(int i=0;i<n;++i){

		while(now&&R[now-1].second<=R[i].second) --now;

		R[now]=R[i];++now;

	}

	n=now;R.resize(n);

	for(auto u:R){

		X.emplace_back(u.first);

		Y.emplace_back(u.second);

	}

	for(auto u:B){

		X.emplace_back(u.first);

		Y.emplace_back(u.second);

	}

	sort(X.begin(),X.end());

	sort(Y.begin(),Y.end());

	X.erase(unique(X.begin(),X.end()),X.end());

	Y.erase(unique(Y.begin(),Y.end()),Y.end());

	int sx=X.size(),sy=Y.size();

	s=sx+sy+1,t=sx+sy+2;

	for(int i=0;i<sx-1;++i){

		addedge(i,i+1,inf,X[i+1]-X[i]);

		addedge(i+1,i,inf,0);

	}

	for(int i=0;i<sy-1;++i){

		addedge(sx+i+1,sx+i,inf,Y[i+1]-Y[i]);

		addedge(sx+i,sx+i+1,inf,0);

	}

	for(auto &u:R){

		u.first=lower_bound(X.begin(),X.end(),u.first)-X.begin();

		u.second=lower_bound(Y.begin(),Y.end(),u.second)-Y.begin();

	}

	for(auto &u:B){

		u.first=lower_bound(X.begin(),X.end(),u.first)-X.begin();

		u.second=lower_bound(Y.begin(),Y.end(),u.second)-Y.begin();

	}

	for(int i=0;i<n-1;++i)

		addedge(R[i].first,R[i+1].second+sx,inf,0);

	addedge(s,R[0].second+sx,k,0);

	addedge(R[n-1].first,t,k,0);

	for(auto u:B){

		int x,y;tie(x,y)=u;

		addedge(y+sx,x,1,0);

	}

	MCMF();

	cout<<cost<<'\n';

	return 0;

}

巴特西

ARC 122 简要题解

ARC 122 简要题解

A - Many Formulae

B - Insurance

C - Calculator

D - XOR Game

E - Increasing LCMs

F - Domination

最新文章

热门文章