7月15日

T1

原题在这里

暴力解法

首先，很容易想到

O(n^2)

的暴力解法，循环枚举

i

与

j

即可，但

n

范围是

10^6

，

O(n^2)

很显然会炸掉，所以需要优化掉一层循环。

正解思路

我们可以一个一个的分析，先解决

and

。思考

n

年后，会发现什么都分析不出来(起码本蒟蒻什么都没想出来)，接着，我们可以把

and

与

or

合起来分析，很快就能发现:

\sum_{i = 1}^{n} \sum_{j = 1}^{i-1} (a_i \, and \, a_j + a_i \, or \, a_j) = \sum_{i = 1}^{n} \sum_{j = 1}^{i-1} (a_i + a_j)

继续拆解可得:

\sum_{i = 1}^{n} \sum_{j = 1}^{i-1} (a_i + a_j) = (\sum_{i=1}^{n} a_i) \times (n - 1)

实现

CPP

for(int i=1;i<=n;i++)
{
    sum+=a[i];
}
sum*=(n-1);

接下来分析

xor

(异或)
异或中，相同为零，不同为一。
按常规思路，我们会发现异或什么规律都没有，就算与

and

或

or

一起分析也什么规律都找不到。

那我们就得换一种思路了，从异或的本质想，异或是一种按位处理的运算，所以就可以一位一位地去计算收益，只要统计一下

n

个数中每一位的

0,1

数量再通过小学5年级的乘法原理，就可以计算出每位收益，累加就可以了。时间复杂度达到了

O(63n)

,成功优化到了线性级。

实现

CPP

for(int i=1;i<=63;i++)
{
	num_1=0;
	num_0=0;
	for(int j=1;j<=n;j++)
	{
		if(a[j]%2==1)
		{
			num_1++;
		}
		else
		{
			num_0++;
		}
		a[j]/=2;
	}
	sum+=num_1*num_0*wei;
	//cout<<num_1<<" "<<num_0<<" "<<wei<<endl;;
	wei*=2;
}

附上AC代码

CPP

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],sum,he[1000005],wei=1,num_1,num_0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
        sum+=a[i];
	}
    sum*=(n-1);
	for(int i=1;i<=63;i++)
	{
		num_1=0;
		num_0=0;
		for(int j=1;j<=n;j++)
		{
			if(a[j]%2==1)
			{
				num_1++;
			}
			else
			{
				num_0++;
			}
			a[j]/=2;
		}
		sum+=num_1*num_0*wei;
		//cout<<num_1<<" "<<num_0<<" "<<wei<<endl;;
		wei*=2;
	}
	cout<<sum;
	return 0;
}

T2

原题在这里

暴力解法

O(n^3)

思路：分别枚举两个点，再判断这两个点是否可以是领导牛对。

O(n^2)

思路：先看哪些点可以满足条件二，再分别计算有几个牛的队列里有可以满足条件二的点，最后统计一下就好了。

个人思路

我是从

O(n^2)

思路中优化解出的。
先看第一步，判断是否满足条件二，可以先用

O(n)

求出

G

与

H

的数量，再通过前缀和求出列表中

G

与

H

的数量，比较一下就可以了。
再拆第二步，列表中有的是

i+1 \sim E_i

,可以看做是第

i+1 \sim E_i

个奶牛被存在他人列表里的个数加一，这一步可以使用离散化优化至

O(n)

，这样，原本的

O(n^2)

就变成了

O(4n)

，成功再次优化到了线性级。

个人AC代码

CPP

#include<bits/stdc++.h>
using namespace std;
long long sumG,sumH,ansG,ansH,sanG[100005],sanH[100005],ans;
long long n,b[100005],heG[100005],heH[100005],li[100005],cnt;
char a[100005];
int main()
{
	//freopen("cow.in","r",stdin);
	//freopen("cow.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]=='G')
		{
			sumG++; 
			heG[i]=heG[i-1]+1;
			heH[i]=heH[i-1];
		}
		else
		{
			sumH++;
			heG[i]=heG[i-1];
			heH[i]=heH[i-1]+1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		if(a[i]=='G')
		{
			if(heG[b[i]]-heG[i-1]==sumG)
			{
				ansG++;
				cnt++;
				li[cnt]=i;
			}
			else
			{
				sanG[i]++;
				sanG[b[i]+1]--;
			}
		}
		if(a[i]=='H')
		{
			if(heH[b[i]]-heH[i-1]==sumH)
			{
				ansH++;
				cnt++;
				li[cnt]=i;
			}
			else
			{
				sanH[i]++;
				sanH[b[i]+1]--;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		sanG[i]+=sanG[i-1];
		sanH[i]+=sanH[i-1];
	}
	for(int i=1;i<=cnt;i++)
	{
		int now=li[i];
		if(a[now]=='G')
		{
			ans+=sanH[now];
		}
		if(a[now]=='H')
		{
			ans+=sanG[now];
		}
	} 
	cout<<ans+ansG*ansH;
	return 0;
}

~~屎山代码，勿喷~~

8月15日

T1

暴力思路

O(n^2)

思路：枚举，判断，没什么好说的。

O(n^2-)

思路：先枚举一个质数，看那个数中有几个能被这个质数整除，根据这个判断即可。

正解思路

与

O(n^2-)

思路相似，也是先枚举一个质数，但正解是通过一个桶计算每个数出现的次数，再用跳跃的方式累加，这样就可以把

O(n)

的循环变成

O(log_n)

1e6

的数据完全可以通过。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],ans=1,check[1000005],maxx,tong[1000005];
void check_()
{
	for(int i=2;i<=1000000;i++)
	{
		if(check[i]==0)
		{
			for(int j=i*2;j<=1000000;j+=i)
			{
				check[j]=1;
			}
		}
	}
}
int main()
{
	//freopen("gcd.in","r",stdin);
	//freopen("gcd.out","w",stdout);
	check_();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		tong[a[i]]++;
	}
	for(int i=2;i<=1000000;i++)
	{
		if(check[i]==0)
		{
			int sum=0;
			for(int j=i;j<=1000000;j+=i)
			{
				sum+=tong[j];
			}
			if(sum==n)
			{
				cout<<"not coprime";
				return 0;
			}
			if(sum>=2)
			{
				ans=2;
			}
		}
	}
	if(ans==1)
	{
		cout<<"pairwise coprime";
	}
	if(ans==2)
	{
		cout<<"setwise coprime";
	}
	return 0;
}

小测题解

文章操作

7月15日

T1

暴力解法

正解思路

附上AC代码

T2

暴力解法

个人思路

个人AC代码

8月15日

T1

暴力思路

正解思路

代码

相关推荐

评论

小测题解