A simple Blog for wyx I've been down the bottle hoping.
3837: [Pa2013]Filary
发表于: | 分类: Oi | 评论:0 | 阅读:120

这是我做过的最玄学题目没有之一

你首先需要分析出来每个数字在答案中的贡献的概率至少是$\frac{1}{2}$

证明非常简单,假设$m=2$,这个答案就是最小是$\frac{n}{2}$了

然后我们就可以疯狂乱搞了思考正确的算法了

我们先瞎jb随机一个数字出来,然后让所有数字和他做差,将差值分解质因数

所有质因数中出现次数的最大值加上与$a_i$相等的数的个数就是选取i的情况下的最优解

按照定义来的算法……不需要解释吧……然后为了最大化$m$,需要将所有相同位置的因数乘在一起

然后给每个位置随机一个权值,全部异或起来求出Hash值,排序后扫一遍统计即可

分解质因数的时候需要高妙的预处理,大概就是先把质数筛出来然后看一下他是那个数字来的,这样就能$log$分解质因数了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
const int M = 1e7+1;
const int P = 664600;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int n, x, a[N], b[N], maxv;
int p[P], tot, ans1, ans2, T;
int last[P], now, v[M], cnt, pos[P];
int tmp[32], fac, vis[P];

struct data{
    int cnt, hash, num;
    data () {
        cnt = hash = 0;
        num = 1;
    }
    data (int _cnt,int _hash,int _num) 
    :cnt(_cnt), hash(_hash), num(_num){}

    bool operator < (const data &z) const {
        return hash < z.hash;
    }
}c[P];

inline void solve(int x,int y) {
    register int i, j, k;
    for(i=0;i<fac;++i) vis[tmp[i]] = 0;
    for(fac=0;x!=1;vis[v[x]]*=p[v[x]],x/=p[v[x]]) 
        if(!vis[v[x]]) 
            tmp[fac++] = v[x], vis[v[x]] = 1;
    for(i=0;i<fac;++i) {
        k = vis[tmp[i]];
        if(last[tmp[i]] ^ T) {
            last[tmp[i]] = T;
            c[j=pos[tmp[i]] = ++now] = data(0,0,k);
        }
        else j = pos[tmp[i]];
        c[j].cnt ++, c[j].hash ^= y;
        if(c[j].num > k) c[j].num = k;
    }
}

int main() {
    c[0].hash = -1;
    n = read();
    register int i,j;
    for(i=0;i<n;++i) {
        a[i] = read();
        while(!b[i]) b[i] = rand();
        if(a[i] > maxv) maxv = a[i];
    }
    for(int i=2;i<=maxv;++i) {
        if(!v[i]) p[v[i] = ++tot] = i;
        for(j=1;p[j]*i<=maxv;++j) {
            v[i*p[j]] = j;
            if(i%p[j] == 0) break;
        }
    }
    for(T=1;T<=4;++T) {
        for(x=a[rand()%n],i=cnt=now=0;i<n;++i) 
            if(a[i] != x) solve(abs(a[i]-x),b[i]);
            else cnt ++;
        sort(c+1,c+now+1);
        for(j=0,i=1;i<=now;++i) 
            if(c[i].hash ^ c[j].hash) {
                if(j) {
                    if(c[j].cnt + cnt > ans1) ans1 = c[j].cnt + cnt, ans2 = c[j].num;
                    else if(c[j].cnt + cnt == ans1 && c[j].num > ans2) ans2 = c[j].num;
                }
                j = i;
            }
            else 
                c[j].num *= c[i].num;
        if(c[j].cnt + cnt > ans1) ans1 = c[j].cnt + cnt, ans2 = c[j].num;
        else if(c[j].cnt + cnt == ans1  && c[j].num > ans2) ans2 = c[j].num;
    }
    cout <<ans1 << " " << ans2 << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP