嵊州D4T1 翻车 rollover 真的翻车了
翻车
【问题描述】
有一天,小武找到了翻车王,给了他n个整数a1,a2,a3,…an,翻车王需要选择其中的k个数,使得选出的k个数中任意两个的差都可以被m整除。
选出的数可以重复,但不可以超过这n个数中该数的个数。
翻车王不想翻车,所以需要你的帮助。
【输入格式】
第一行包括3个整数n,k,m(2 ≤ k ≤ n ≤ 100000,1 ≤ m ≤ 100000),n,k,m意义见题面。
第二行包括n个数a1,a2,a3,…an(0 ≤ ai ≤ 1000000000)。
【输出格式】
如果不可以选出k个数,使得选出这k个数中任意两个的差都可以被m整除,那么输出“No”。
否则,在第一行输出“Yes”。在第二行输出这k个整数b1,b2,...bk(所选的数字),两两数之间有一个空格。
如果有多种选择k个数字的方案,请输出任意一种。
【输入输出样例】
rollover.in | rollover.out |
4 3 5 2 7 7 7 |
Yes 2 7 7 |
【数据说明】
20%的数据n ≤ 15
50%的数据n ≤ 1000
另外20%的数据m ≤ 1000
100%的数据2 ≤ k ≤ n ≤ 10^5,1 ≤ m ≤ 10^5,0≤ ai ≤10^9
题解
暴力--
用一个循环找开头
for(int i=0;i<n;i++){
flag[i]=1;
if(findnext(a+i,1)) return 0;
flag[i]=0;
}
flag[i]是用来标记第i个书有没有用过了的
if(flag[i]==1)
continue;
findnext()返回bool值
用来判断有没有
#include<bits/stdc++.h>
using namespace std;
int n,k,m;
int a[];
bool flag[];
bool findnext(int now[],int len){
if(len>k) return ;
if(len==k) {
cout<<"Yes"<<endl;
for(int i=;i<len;i++)
cout<<now[i]<<" ";
return ;
}
for(int i=;i<n;i++)//寻找下一个
{
//
// for(int debug=1;debug<=len;debug++) cout<<now[debug]<<" ";
// cout<<endl;
//
if(flag[i]==)
continue;
bool flagnext=;
for(int j=;j<len;j++)
flagnext=flagnext&&(a[i]-now[j])%m==;
if(!flagnext) continue;
//else
int flagn = ;
flag[i]=;
now[len]=a[i];
flagn = findnext(now,len+);
now[len]=;
flag[i]=;
return flagn;
}
return ;
}
int main(){
// freopen("rollover.in","r",stdin);
// freopen("rollover.out","w",stdout);
cin>>n>>k>>m;
for(int i=;i<n;i++)
cin>>a[i];
for(int i=;i<n;i++){
flag[i]=;
if(findnext(a+i,)) return ;
flag[i]=;
}
cout<<"No";
return ;
}
中间的注释(debug)是开始用来调试的。
暴力++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
const int inf=0X7f7f7f7f;
using namespace std;
int n,k,m,ans=,t=inf;
int main()
{
// freopen("rollover.in","r",stdin);
cin>>n>>k>>m;
long long a[n+],sum[n+];
for(int i=;i<=n;i++)
{
cin>>a[i];
sum[a[i]%m]++;
}
for(int i=;i<m;i++)
{
if(sum[i]>=k)
cout<<"Yes"<<endl;
t=i;
break;
}
if(t==inf)
cout<<"No";
else
for(int i=;i<=n;i++)
{
if(a[i]%m==t);
{
ans++;
if(ans<=k)
cout<<a[i]<<" ";
else break;
}
}
return ;
}
源码来源:https://www.cnblogs.com/YYCether666/p/11185389.html
本来以为会超时的,没想到呀!
std
有关于最小公倍数的数论题
结论:
证明:
设d=gcd(a,b)
a=a'd
b=b'd
所以gcd(a',b')=1,即a',b'互质
题中:a+b是a*b的因子
所以(a'+b')d | a'd*b'd
两边约掉一个d
a'+b' | a'b'd
所以a'+b'<=d
又因为题中:(a'+b')d<=n
所以a'+b'<=sqrt(n)
设k=a'+b'
φ(k)=
等待明天std的下发。。。
最新文章
- 入手了[云梯的VPN]--水文
- iOS架构师之路:慎用继承
- 第六天 做的app不会改变什么
- 在特定的action里使用validates
- PHP 读取逐条数据库记录,以及提交下拉菜单选项
- LeetCode258:Add Digits
- hadoop拾遗(五)---- mapreduce 输出到多个文件 / 文件夹
- iOS开发——图形编程OC篇&;粘性动画以及果冻效果
- windows 2008 R2 Activition
- while死循环问题-输入字符就会死循环
- 我自己的style
- Hibernate级联操作和载入机制(二) cascade and fetch
- LOG4J日志级别详解
- MySQL 处理海量数据时的一些优化查询速度方法
- Qt笔记之QGADGET
- ARM Cortex M0 程序映像和启动流程
- Event Recommendation Engine Challenge分步解析第二步
- 第三节《Git重置》
- $(document).ready()方法和window.onload有什么区别?
- git使用遇到的坑
热门文章
- WPF Calendar 日历控件 样式自定义
- 【全面解禁!真正的Expression Blend实战开发技巧】第七章 MVVM初体验-在DataGrid行末添加按钮
- 关于SetLength报Out of memory的研究及解决办法
- Win8 Metro(C#)数字图像处理--2.45图像雾化效果算法
- 调用其它UI文件
- WPF如何判断PNG中的点是透明的
- ArcGIS for Desktop入门教程_第八章_Desktop学习资源 - ArcGIS知乎-新一代ArcGIS问答社区
- vs编译在win xp电脑上运行的win32程序遇到的问题记录(无法定位程序输入点GetTickCount64于动态链接库KERNEL32.dll)
- WPF 中RichTextBox控件用法细讲
- Linux简单文本处理