当前位置: 代码迷 >> 综合 >> 【贪心(?)】2017-03-19realseq
  详细解决方案

【贪心(?)】2017-03-19realseq

热度:95   发布时间:2023-09-27 09:08:53.0

【贪心(?)】2017-03-19realseq
分析:
本题解并不严谨,如有证明或bug请指出(最好附反例)
首先,题目中强调了最多包含五位小数,那么就可以将每一个值乘上100000

(注意:乘了100000转整数时候,一定要加0.1,否则会出现精度问题!!巨坑!!)

如果x只在[A,B]中出现了1次,那么就可以看作出现的那个数本身
如果出现了多次,那么一定是某两个数之差。、
因为k十分的小,只有50,所以两两之差最多有只有1000多个
因此,有可能为x的数,也就是可行解的集合最多也就1000多个值

同时,我们还要筛去一些不合法的值:
1、如果为两两之差产生的数,那么这两个数必须是差数的倍数(如3,5的差2就是不合法的,因为3,5不是2的倍数)
2、这个值在[A,B]内每一个倍数都必须出现过。
3、这个值的因数不存在于集合内(否则它一定没有他的因子优)

到这里,我们就得到了一个可行解的集合,现在的任务就是把这个集合尽量缩小。下面就是不科学的地方了:
把集合的值从小到大依次枚举(因为值小的覆盖的数量,一定比值大的多)
如果当前的值可以将覆盖的范围变大,那么就将这个数放入解集。
最后一步,在解集中再找一边,筛去多余的值(即删去这个数覆盖范围不变)
最后的解集就是答案

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 60
using namespace std;
int n;
long long A,B,a[MAXN],al[MAXN*MAXN],vis[MAXN*MAXN],num[MAXN*MAXN],ans;
long long print[MAXN*MAXN];
vector<long long> pos;
long long bit[MAXN];
bool check(long long x){for(int i=0;i<pos.size();i++)if(x%pos[i]==0)return 0;long long y=(A+x-1)/x;int j=1;for(;y*x<=B&&j<=n;y++){for(;j<=n;j++)if(a[j]==y*x)break;if(n<j)break;}if(y<=B/x)return 0;return 1;
}
long long other(int x){long long res=0;for(int i=0;i<ans;i++)if(i!=x)res=res|num[i];return res;
}
int main(){double x;long long tot=0;freopen("realseq.in","r",stdin);freopen("realseq.out","w",stdout);bit[0]=1;for(int i=1;i<=50;i++)bit[i]=bit[i-1]*2;SF("%d",&n);SF("%I64d%I64d",&A,&B);A*=100000;B*=100000;for(int i=1;i<=n;i++){SF("%lf",&x);a[i]=1LL*(x*100000.0+0.5);}for(int i=1;i<=n;i++)for(int j=1;j<i;j++)if(a[i]%(a[i]-a[j])==0&&check(a[i]-a[j])){pos.push_back(a[i]-a[j]);}for(int i=1;i<=n;i++){int j=0;for(;j<pos.size();j++)if(a[i]%pos[j]==0)break;if(j==pos.size()){PF("%I64d.",a[i]/100000);PF("%05I64d\n",a[i]%100000);}}sort(pos.begin(),pos.end());for(int i=0;i<pos.size();i++){for(int j=1;j<=n;j++){if(a[j]%pos[i]==0)al[i]+=bit[j-1];}}for(int i=0;i<pos.size();i++){if((tot|al[i])>tot){num[ans]=al[i];print[ans++]=pos[i];tot=tot|al[i];  }}for(int i=0;i<ans;i++)if(other(i)==tot)print[i]=-1;//PF("(%I64d)",tot)for(int i=0;i<ans;i++){if(print[i]==-1)continue;PF("%I64d.",print[i]/100000);PF("%05I64d\n",print[i]%100000);}
}