• A. Array and Peaks
  • 题意
  • 解题思路
  • Code
• B. AND Sequences
  • 题意
  • 解题思路
  • Code

A. Array and Peaks

传送门

题意

给你一个n表示的是这个数组的长度，并且数组的元素只能有[1,n]范围内唯一的数确定，然后给你一个k表示的是你构造的数组的高峰数目，高峰指的是 中间元素比两边元素大eg: 1 3 2 ，3就是这个数组的一个高峰

解题思路

很明显我们会发现高峰数是有一个取值范围的[0,(n-1)/2]，在这个范围内是我们能取到的正确高峰，我们不难发现，我们要想构造完最多的高峰我们用到的作为高峰数一定是后面的(n-1)/2个数，那么我们就可以先输出一个当前元素，然后再输出一个高峰元素，这样构造即可，不懂请看代码

Code

#include<bits/stdc++.h>
using namespace std;

int t,n,k;

int main()
{
	cin>>t;
	while(t--) {
		cin>>n>>k;
		if(k > (n-1)/2) {
			puts("-1");
			continue;
		}
		int cnt = k;
		for(int i = 1,j = n;i <= n-k; ++i) {
			printf("%d ",i);
			if(cnt)
				printf("%d ",j),cnt--,j--;
		}
		puts("");
	}
	
	
	return 0;
}

B. AND Sequences

传送门

题意

给你一个长度为n的数串，问你在这个数串的全排列中有多少中情况满足 i从1开始，取到n-1，使得a1&a2&……ai=ai+1 &ai+2 & an

解题思路

很明显这是一道组合数学的问题，然后从题目给的样例来看我们能知道我们求得结果是不需要去重的(去重难写得多)

通过题目的这种&操作我们可以得到一下几个结论

1.我们构造的数串最左边和最右边一定是最小的值，注意这里不一定是初始串的最小数

2.任意几个不相等的数&起来不大于这几个数的最小值，eg 2 & 1 = 0

3.我们计算的组合数不需要去重

这样我们先扫一遍数组，所有数&起来，得到一个最小值，看这个数的个数m如果小于2的话，那么显然构造不了，否则的话就可以直接用组合数m*(m-1)* A(n-m,n-m),注意对1e9+7取模

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod = 1000000007;

ll t,n;

const int N = 200005;

map<ll,ll> vis;
ll a[N];


int main()
{
	scanf("%lld",&t);
	while(t--) {
		scanf("%lld",&n);
		vis.clear();
		scanf("%lld",&a[1]);
		ll min_k = a[1];
		vis[a[1]]++;
		for(int i = 2;i <= n; ++i) {
			scanf("%lld",&a[i]);
			min_k &= a[i];
			vis[a[i]]++;
		}
		if(vis[min_k] < 2) {
			puts("0");
			continue;
		}
		ll ans = (vis[min_k] % mod *(vis[min_k] - 1) % mod ) % mod;
		ll len = n - 2; 
		for(int i = 2;i <= len; ++i) {
			ans = (ans % mod * i % mod) % mod;
		}
		printf("%lld\n",ans);
	}
	
	return 0;
}