Codeforces Round #697 (Div. 3 A-G)题解(新鲜)

记录一下div3第一次$ak$,虽然是因为这次很简单的原因…不过还是很开心hhh

$A,B$太简单了就不写了,然后下面每一题都写了比较详细的题解^_^.

1475C. Ball in Berland(容斥原理)

因为只选择两组男女关系

枚举当前选择第$i$组,然后去$[i+1,n]$选择一组男女关系

如果不考虑冲突关系,答案直接加上$n-i$

然而后面$n-i$个可能和这个男生有冲突,需要减掉

后面$n-i$个可能和这个女生有冲突,需要减掉

这样写可能多减了,因为有的组男女同时和第$i$组冲突

所以需要加上后面$n-i$组中男女关系和第$i$组相同的对数

就是一个容斥原理,$P(a\cup b)=P(a)+P(b)-P(ab)$

男女关系是一个二元组,用$map$来存

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5+10;
int n1,n2,k,l[maxn],r[maxn],L[maxn],R[maxn];
typedef pair<int,int>p;
map<p,int>mp;
signed main()
{
	int t; cin >> t;
	while( t-- )
	{
		long long ans=0;
		cin >> n1 >> n2 >> k;
		for(int i=1;i<=k;i++)
			scanf("%d",&l[i]);
		for(int i=1;i<=k;i++)
			scanf("%d",&r[i]);
		for(int i=1;i<=k;i++)	mp[p(l[i],r[i])]++,L[l[i]]++,R[r[i]]++;
		for(int i=1;i<=k;i++)
		{
			mp[p(l[i],r[i])]--; L[l[i]]--; R[r[i]]--;
			if( i==k )	break;
			int pre = k-i;
			ans += pre-L[l[i]]-R[r[i]]+mp[p(l[i],r[i])];
		//	cout << pre-L[l[i]]-R[r[i]]+mp[p(l[i],r[i])] << endl;
		}
		cout << ans << endl;
		mp.clear();
	}
}

1475D. Cleaning the Phone(二分+前缀和)

因为$b_i$只有$1$和$2$两种,考虑分成$a1,a2$两个数组装相应的$a_i$

$a1$里的$a_i$的$b_i=1$,那么$a1$里的物品具有明显的优劣关系,$a_i$越大的越好

所以$a1,a2$按照$a_i$从大到小排序

枚举$a1$数组取前$i$个物品

此时可以使用二分去快速得到一个最小的$index$使得取走前$index$大的$a2$元素

满足条件,然后更新答案即可

dp似乎是行不通的(可能可以???)…

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5+10;
const int inf = 1e15;
int t,n,m,a[maxn],b[maxn],a1[maxn],a2[maxn],pre[maxn];
bool com(int a,int b){ return a>b; }
signed main()
{
	int t; cin >> t;
	while( t-- )
	{
		cin >> n >> m;
		for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
		for(int i=1;i<=n;i++)	scanf("%lld",&b[i]); 
		a1[0]=a2[0]=0;
		for(int i=1;i<=n;i++)
		{
			if( b[i]==1 )	a1[++a1[0]] = a[i];
			else	a2[++a2[0]] = a[i];
		}
		sort( a1+1,a1+1+a1[0],com );
		sort( a2+1,a2+1+a2[0],com );
		for(int i=1;i<=a2[0];i++)	pre[i] = pre[i-1]+a2[i];
		//ö��ѡ��s��
		int ans = inf,sum=0;
		for(int i=1;i<=a1[0];i++)
		{
			sum+=a1[i];
			if( sum>=m ){ ans=min(i,ans); break; }
			int yu = m-sum;
			int index = lower_bound( pre+1,pre+1+a2[0],yu )-pre;
			if( index==a2[0]+1 )	continue;
			ans = min( ans,i+index*2 );
		} 
		int index = lower_bound( pre+1,pre+1+a2[0],m )-pre;
		if( index!=a2[0]+1 )
			ans = min( ans,index*2 );
		if( ans==inf )	cout << -1 << endl;
		else	cout << ans << endl;
	}
}

1475E.Advertising Agency(排序)

由于选择的数字需要最大

那么首先把$a$数组排序,从大到小选$k$个肯定是最大的

然后为什么最大值有几种方案呢??

因为和$a_k$相等的有很多

设从大到小选的过程中选了$x$个$a_k$

数组中一共有$sum$个$a_k$

那么方案数是$C_{sum}^x$

除了和$a_k$相等的,其他数字都不能变动

比$a_k$大的都进来了,小的进来答案会变小。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn =1e5+10;
const int mod = 1e9+7;
int n,t,a[maxn],k,fac[maxn];
bool com(int a,int b){ return a>b; }
int quick(int x,int n)
{
	int ans = 1;
	for( ;n;n>>=1,x=x*x%mod )
		if( n&1 )	ans = ans*x%mod;
	return ans;
}
int C(int n,int m)
{
	if( n<m )	return 0;
	return fac[n]*quick( fac[m]*fac[n-m]%mod,mod-2 )%mod;
}
signed main()
{
	fac[0] = 1;
	for(int i=1;i<=1000;i++)	fac[i] = fac[i-1]*i%mod;
	cin >> t;
	while( t-- )
	{
		cin >> n >> k;
		for(int i=1;i<=n;i++)	scanf("%lld",&a[i] );
		sort( a+1,a+1+n,com );
		int ans = 0, x=-1e9, sum = k;
		for(int i=1;i<=k;i++)
		{
			if( a[i]!=a[i-1] )	x=a[i];
		}
		for(int i=1;i<=n;i++)
		{
			if( a[i]==x )	ans++;
			if( a[i]>x )	sum--;
		}
		//��ans��ѡ��sum
		printf("%lldn",C(ans,sum) ); 
	}
}

1475F. Unusual Matrix(构造,模拟)

发现每一行,每一列如果操作,必然是奇数次操作

否则,偶数次的操作和不操作没有区别。

而且,当$a_{i,j}==b_{i,j}$时每个格子被操作偶数次

当$a_{i,j}!=b_{i,j}$时这个格子被操作奇数次

设$ro{w}_i$为第$i$行操作次数,$li{e}_j$为第$j$列操作的次数

那么$a_{i,j}$的操作次数等于$ro{w}_i+li{e}_j$

假如我们枚举第一行的操作次数,那么由于$a_{1,1}$到$a_{1,n}$(第一行)的操作次数已知

那么不久可以直接解得$co{l}_1$到$co{l}_n$吗

然后由于$a_{1,1}$到$a_{n,1}$(第一列)的操作次数已知,不久可以解得$ro{w}_2$到$ro{w}_n$吗

现在已知$row$和$lie$,叫你去判断每个格子是否合法不会判断吗??

所以只需要分第一行操作偶数次和奇数次讨论一下就好了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn =1009;
const int mod = 1e9+7;
int n,t;
int row[maxn],lie[maxn];
char a[maxn][maxn],b[maxn][maxn];
bool ok()
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
		if( a[i][j]==b[i][j]&&(row[i]+lie[j])%2==0 )	continue;
		else if( a[i][j]!=b[i][j]&&(row[i]+lie[j])%2==1 )	continue;
		else	return false;
	return true;
}
signed main()
{
	int t; cin >> t;
	while( t-- )
	{
		cin >> n;
		for(int i=1;i<=n;i++)	scanf("%s",a[i]+1);
		for(int i=1;i<=n;i++)	scanf("%s",b[i]+1);
		//第一行不操作 
		row[1] = 0;
		for(int i=1;i<=n;i++)
			if( a[1][i]==b[1][i] )	lie[i] = 0;
			else	lie[i] = 1;
		for(int i=2;i<=n;i++)
			if( a[i][1]==b[i][1] )	row[i] = lie[1];
			else	row[i] = lie[1]^1;
		if( ok() )	{ printf("YESn"); continue; }
		row[1] = 1;
		for(int i=1;i<=n;i++)
			if( a[1][i]==b[1][i] )	lie[i] = 1;
			else	lie[i] = 0;
		for(int i=2;i<=n;i++)
			if( a[i][1]==b[i][1] )	row[i] = lie[1];
			else	row[i] = lie[1]^1;	
		if( ok() )	printf("YESn");
		else	printf("NOn");	
	}
}

1475G. Strange Beauty(dp+优化)

考虑最终状态

数组中任意两个数都是彼此的因子(倍数)

那么如果从小到大排序,一定有$a_i\%a_{i-1}==0$

于是我们一开始就对$a$数组从小到大排序,按照这个规则去$dp$

定义$f[i]$为以$a_i$结尾,在$[1,a_i]$最多可以选多少个数字

那么对于每一个$i$,去$[1,i-1]$找一个符合条件的$j$满足$a_i\%a_j==0$

$$f[i]=max(f[i],f[j]+1)$$

但是这样复杂度是$O(n^2)$

不难发现符合条件的$a_j$都是$a_i$的因子,于是我们直接去枚举$a_i$的因子进行转移

复杂度降到$O(nsqrt(n))$

#include <bits/stdc++.h>
using namespace std;
const int maxn =2e5+10;
const int mod = 1e9+7;
int f[maxn],a[maxn],id[maxn];
signed main()
{
	int t; cin >> t;
	while( t-- )
	{
		int n,ans=0; cin >> n;
		for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
		sort( a+1,a+1+n );
		for(int i=1;i<=n;i++)
		{
			f[i] = 1;
			for(int j=1;j*j<=a[i];j++)
			{
				if( a[i]%j!=0 )	continue;
				int last = a[i]/j;
				f[i] = max( f[i],f[id[j]]+1 );
				f[i] = max( f[i],f[id[last]]+1 );
			}
			id[a[i]] = i;
			ans = max( ans,f[i] );
		}
		printf("%dn",n-ans);
		for(int i=1;i<=200000;i++)	f[i] = id[i] = 0;
	}
}

最后

以上就是漂亮白猫为你收集整理的Codeforces Round #697 (Div. 3 A-G)题解(新鲜)的全部内容，希望文章能够帮你解决Codeforces Round #697 (Div. 3 A-G)题解(新鲜)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。