xiaoh's Blog

Practise like you never won, Perform like you never lost!

ABC173 Summary

发布于 2020-07-06 | 分类于 参赛总结 | 13分钟 | 2387字数

ABC173 Summary(2020-7-5 20:00~21:40)

xiaoh 2020-7-6

C-H and V

题意

给定一个h×wh\times w的方格表(1≤h,w≤61\leq h,w\leq 6),每一个格子为黑色或白色,可以选择任意多个行或列染成红色,求有多少种染法使恰好有kk个黑色格子剩下.(1≤k≤hw1\leq k\leq hw)

题解

对于每一行/列2h+w2^{h+w}考虑是否取即可.时间复杂度O(2h+w×hw)O(2^{h+w}\times hw).具体深搜步骤在此不详细说明了,只提一点可以使代码简洁一点的方法.我们用类似于二进制状压的方式去枚举可以使代码量大大减小.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=10;
int h,w,k;
bool mp[MAXN][MAXN];
int ans=0;
bool check(int x)
{
    int tmp[MAXN][MAXN];
    for(int i=1;i<=h;++i)
    for(int j=1;j<=w;++j) tmp[i][j]=mp[i][j];
    for(int i=0;i<=(h-1);++i)
    if(x&(1<<i))
    for(int j=1;j<=w;++j) tmp[i+1][j]=0;
    for(int i=h;i<=h+w-1;++i)
    if(x&(1<<i))
    for(int j=1;j<=h;++j) tmp[j][i-h+1]=0;
    int sum=0;
    for(int i=1;i<=h;++i)
    for(int j=1;j<=w;++j) sum+=tmp[i][j];
    return sum==k;
}
int main()
{
    cin>>h>>w>>k;
    for(int i=1;i<=h;++i)
    {
        string s;
        cin>>s;
        for(int j=0;j<w;++j)
        if(s[j]=='.') mp[i][j+1]=0;
        else mp[i][j+1]=1;
    }
    for(int i=0;i<=(1<<(h+w))-1;++i)
    if(check(i)) ++ans;
    cout<<ans<<endl;
	return 0;
}

D-Chat in a Circle

题意

有nn个人，每个人有一个友好度aia_i(1≤n≤2×105,1≤ai≤1091\leq n\leq 2\times 10^5,1\leq a_i\leq 10^9)，每个人可以按照我们规定的顺序依次进入，每个进入的人要按照我们安排的顺序插入圆圈的某个位置，其舒适值为其相邻两边的人的友好度的较小值，特别的，第一个人舒适值为00。求所有人的舒适值的和的最大值。

题解

首先，按照舒适度从大到小进入一定最优，证明显然。

接下来我们考虑如何更改进圈的位置使舒适值的和最大。经过大胆猜想，合理假设，观察样例 尝试，我们发现除了最大的数外，其余加入的每一个数至多被作为舒适值两次。记从大到小排序后的数组为bb，所以我们不妨猜想答案即为b1+∑i=2[k−12]b_1+\sum_{i=2}^{[\frac{k-1}{2}]}，中[x][x]为取下整。最终证明这个猜想是对的，时间复杂度O(nlog⁡n)O(n\log n)

当然我们也需要对此证明一下。由于新加入的每一个数都越来越小，因而对于每一个数bkb_k而言，其左边和右边最多能够有一个数能够将bkb_k作为其舒适度，不妨记其为p,qp,q,显然p,q<bkp,q<b_k,所以再次在bkb_k两侧插入时其舒适度为pp或qq,而不是bkb_k.而对于b1b_1而言，因为其左右侧都为一侧(只有一个数时插入第二个数即为其左侧又为其右侧)，所以仅能被计算一次。其余至多计算两次，显然，我们能够构造出符合条件的序列使其余每个数都被计算两次。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=200010;
int n;
long long a[MAXN];
long long ans=0;
int main()
{
    read(n);
    for(int i=1;i<=n;++i) read(a[i]);
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    for(int i=1;i<n;++i) ans+=a[(i+2)/2];
    write(ans),putchar('\n');
	return 0;
}

E-Multiplication 4

题意

给定nn个整数aia_i(1≤n≤2×105,∣ai∣≤1091\leq n\leq 2\times 10^5,|a_i|\leq 10^9)，你可以选kk个数(1≤k≤n1\leq k\leq n)，求其乘积的最大值。

题解

首先考虑何时答案可能为负数。当n=kn=k时，答案有可能为负数。且当kk为奇数且所有数都为负数时，答案为负数。证明显然。此时直接取绝对值最小的数乘在一起即可。

接下来考虑答案为正数的情况。首先我们先按照贪心选择绝对值最大的数乘在一起，若乘积为正数则直接输出，否则我们可以通过调整将其变为正数。

调整方法如下：

1.选择一个被选中的绝对值最小的一个负数minnminn将其换为未选中的绝对值最大的正数maxpmaxp

2.选择一个被选中的绝对值最小的一个正数minpminp将其换为未选中的绝对值最大的负数maxnmaxn

那么我们只需要考虑两者那个最小即可。显然答案为max⁡(ans×minnminp,ans×maxpmaxn)\max(\frac{ans\times minn}{minp},\frac{ans\times maxp}{maxn}).将ansans约掉之后对角相乘比大小即可。注意有可能有一种情况不存在需要特判。时间复杂度O(nlog⁡n)O(n\log n)

Code

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=200010;
int n,k;
long long a[MAXN];
int nump;
inline bool cmp(long long x,long long y)
{
	return abs(x)>abs(y);
}
int main()
{
	read(n),read(k);
	for(int i=1;i<=n;++i) read(a[i]);
	if(k==n)
	{
		long long ret=1;
		for(int i=1;i<=n;++i) ret*=a[i],ret%=mod;
		write((ret%mod+mod)%mod),putchar('\n');
		return 0;
	}
	for(int i=1;i<=n;++i)
	if(a[i]>=0) ++nump;
	if(nump==0&&k%2==1)
	{
		sort(a+1,a+n+1),reverse(a+1,a+n+1);
		long long ret=1;
		for(int i=1;i<=k;++i) ret*=a[i],ret%=mod;
		write((ret%mod+mod)%mod),putchar('\n');
		return 0;
	}
	stable_sort(a+1,a+n+1,cmp);//注意勿换成sort否则会莫名RE
	long long minp=2147483647,maxp=-1,minn=0,maxn=-2147483647;
	long long p1=0,p2=0,p3=0,p4=0;
	long long ans=1;
	for(int i=1;i<=k;++i) ans*=a[i],ans%=mod;
	if(ans>=0)
	{
		write(ans),putchar('\n');
		return 0;
	}
	for(int i=1;i<=k;++i)
	if(a[i]>=0&&a[i]<minp) minp=a[i],p1=i;
	else if(a[i]<0&&a[i]>maxn) maxn=a[i],p4=i;
	for(int i=k+1;i<=n;++i)
	if(a[i]>=0&&a[i]>maxp) maxp=a[i],p2=i;
	else if(a[i]<0&&a[i]<minn) minn=a[i],p3=i;
	if(minp==2147483647||minn==0)
	{
		ans=1;
		for(int i=1;i<=k;++i)
		if(i!=p4) ans*=a[i],ans%=mod;
		ans*=a[p2],ans%=mod;
	}
	else if(maxp==-1||maxn==-2147483647)
	{
		ans=1;
		for(int i=1;i<=k;++i)
		if(i!=p1) ans*=a[i],ans%=mod;
		ans*=a[p3],ans%=mod;
	}
	else if(minn*maxn>maxp*minp)
	{
		ans=1;
		for(int i=1;i<=k;++i)
		if(i!=p1) ans*=a[i],ans%=mod;
		ans*=a[p3],ans%=mod;
	}
	else
	{
		ans=1;
		for(int i=1;i<=k;++i)
		if(i!=p4) ans*=a[i],ans%=mod;
		ans*=a[p2],ans%=mod;
	}
	write(ans),putchar('\n');
	return 0;
}

F-Intervals on Tree

题意

给定一棵大小为nn的树(1≤n≤2×1051\leq n\leq 2\times 10^5)，记comp(l,r)comp(l,r)为编号在[l,r][l,r]间的点所构成的连通块的数量。求∑l=1n∑r=lncomp(l,r)\sum_{l=1}^{n}\sum_{r=l}^{n} comp(l,r).

题解

我们注意到一个点集SS的连通块数目为∣S∣−|S|-连通块内边的数目。所以所有点的贡献为n+2(n−1)+3(n−2)+⋯+n×1n+2(n-1)+3(n-2)+\dots+n\times 1，即所有区间的长度总和。接下来考虑减去边的贡献。对于边u,v(u<v)u,v(u<v)，当l≤ul\leq u且v≤rv\leq r使才会对区间产生贡献，所以产生的总贡献为u×(n−v+1)u\times (n-v+1).直接统计即可,时间复杂度O(n)O(n).

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=200010,LOGN=20;
long long n;
long long ans=0;
int main()
{
    read(n);
    for(long long i=1;i<=n;++i) ans+=i*(n-i+1);
    for(int i=1;i<n;++i)
    {
        long long u,v;
        read(u),read(v);
        if(u>v) swap(u,v);
        ans-=u*(n-v+1);
    }
    write(ans),putchar('\n');
	return 0;
}
  • 本文作者： xiaoh's Blog
  • 本文链接： ABC173 Summary
  • 版权声明： 本博客所有文章除特别声明外，转载请注明出处！
# 参赛总结
ACWing 96 奇怪的汉诺塔 题解 上一篇
洛谷 P2852 【USACO06DEC】Milk Patterns G 题解 下一篇
© 2019-2020 HsxyHao
Powered by Gridea
0%