Divide by Zero 2021 and Codeforces Round #714 (Div. 2)
2021/4/25 10:25:50
本文主要是介绍Divide by Zero 2021 and Codeforces Round #714 (Div. 2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 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; }
这篇关于Divide by Zero 2021 and Codeforces Round #714 (Div. 2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享