codeforces #441 B Divisiblity of Differences【数学/hash】
1 second
512 megabytes
standard input
standard output
You are given a multiset of n integers. You should select exactly k of them in a such way that the difference between any two of them is divisible by m, or tell that it is impossible.
Numbers can be repeated in the original multiset and in the multiset of selected numbers, but number of occurrences of any number in multiset of selected numbers should not exceed the number of its occurrences in the original multiset.
First line contains three integers n, k and m (2 ≤ k ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — number of integers in the multiset, number of integers you should select and the required divisor of any pair of selected integers.
Second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109) — the numbers in the multiset.
If it is not possible to select k numbers in the desired way, output «No» (without the quotes).
Otherwise, in the first line of output print «Yes» (without the quotes). In the second line print k integers b1, b2, ..., bk — the selected numbers. If there are multiple possible solutions, print any of them.
3 2 3
1 8 4
Yes
1 4
3 3 3
1 8 4
No
4 3 5
2 7 7 7
Yes
2 7 7 【题意】:给你n个数a[i],让你找出一个大小为k的集合,使得集合中的数两两之差为m的倍数。 若有多解,输出任意一个集合即可。
【分析】:若一个集合中的数,两两之差为m的倍数,则他们 mod m 的值均相等。所以O(N)扫一遍,对于每个数a:vector v[a%m].push_back(a) 一旦有一个集合大小为k,则输出。
【代码】:
#include<bits/stdc++.h>
using namespace std; int main(){
int n,k,m;
cin>>n>>k>>m;
int arr[m]={};
long int val[n];
for(int i=;i<n;i++){
cin>>val[i];
arr[val[i]%m]++;
}
int pos=-;
for(int i=;i<m;i++){
if(arr[i]>=k){
pos=i;
break;
}
}
if(pos==-){
cout<<"No"<<endl;
}
else{
cout<<"Yes"<<endl;
int i=;
while(k--){
while(val[i]%m!=pos){
i++;
}
cout<<val[i]<<" ";
i++;
}
cout<<endl;
}
return ;
}
#include<bits/stdc++.h>
using namespace std; int a[], b[]; int main()
{
int n, k, m;
scanf("%d%d%d", &n, &k, &m);
memset(b, , sizeof(b));
for(int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
b[a[i]%m]++;
}
int len = ;
for(int i = ; i <= ; i++)
{
if(b[i] >= k)
{
for(int j = ; j <= n && len < k; j++) if(a[j] % m == i) a[len++] = a[j];
}
}
if(len == ) puts("No");
else
{
puts("Yes");
for(int i = ; i < len; i++) printf("%d%c", a[i], i == len - ? '\n' : ' ');
}
return ;
}
最新文章
- Spark——SparkContext简单分析
- 系统定位在iOS8中的改变
- 新的篇章--Python
- 利用Abot爬虫和visjs 呈现漫威宇宙
- Java Socket编程(转)
- PE-1 &; 暴模|容斥
- CANopen DS301协议中文翻译V03版
- chromiun 学习《二》 目录结构 +启动流程
- 【HDU 4150】Powerful Incantation
- MVC3系列~Html.BeginForm与Ajax.BeginForm
- MySQL源码之Thread cache
- 阻止文件不被上传到iCloud-b
- jquery之ajax中国乱码的解决方案
- Selenium+Python进行web自动化测试(Demo+API)
- 发布时一键添加html中的css标签和script标签版本号来防止浏览器缓存
- 乡下人设计模式——SOLID之六大原则
- Django 的命令及简单例子
- View事件体系
- Abp + MongoDb 改造默认的审计日志存储位置
- Asp.Net 之 Web.config 配置文件详解
热门文章
- [CF1077C]Good Array
- [Leetcode] Linked list cycle 判断链表是否有环
- innodb_force_recovery
- Codeforces Round #526 (Div. 2) E. The Fair Nut and Strings
- 工作总结-js插件
- javascript中arguments的应用——不定项传参求和
- centos7装机时更改网卡名为eth0操作
- 卡片选项页面 JTabbedPane 的使用
- [bzoj1717][Usaco2006 Dec]Milk Patterns 产奶的模式——后缀数组
- [bzoj2152]聪聪可可——点分治