Yandex.Algorithm 2018, final round

思路:如果n这个位置加1的话,不同的数的个数要么不变,要么加1,反之,如果不同的数的个数减少,肯定不是n这个位置加1

我们random_shuffle()50次,每次把不是n的位置标记一下,这样有很大的概率把所有的不是n的位置都标记了

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 1e3 + 5;
int a[N];
bool vis[N];
int main() {
    int n, tot = 50;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) a[i] = i;
    int pre = n, now;
    while(tot--) {
        random_shuffle(a+1, a+1+n);
        for (int i = 1; i <= n; i++) {
            printf("0 %d
", a[i]);
            fflush(stdout);
            scanf("%d", &now);
            if(now < pre) {
                vis[a[i]] = true;
            }
            pre = now;
        }
    }
    for (int i = 1; i <= n; i++) if(!vis[i]) return 0*printf("1 %d
", i);
    return 0;
}

View Code

F Lazy Hash Table

思路:FFT

求最小的m使得任意两个数之间的差值都不是这个m的倍数

用FFT求任意两个数之间的差值

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 8e6 + 10, M = 2e6 + 5;
int R[N], a[M], b[M];
struct Complex {
    double x, y;
    Complex(double _x=0, double _y=0) : x(_x),y(_y) {};
    Complex operator + (Complex &t) {return Complex(x+t.x, y+t.y);}
    Complex operator - (Complex &t) {return Complex(x-t.x, y-t.y);}
    Complex operator * (Complex &t) {return Complex(x*t.x - y*t.y, x*t.y + y*t.x);}
}A[N], B[N];
void fft(Complex *x, int n, int type) {
    for (int i = 0; i < n; i++) if(i < R[i]) swap(x[i], x[R[i]]);
    for (int i = 1; i < n; i<<=1) {
        Complex wn(cos(pi/i), type*sin(pi/i));
        for (int j = 0; j < n; j+=i<<1) {
            Complex w(1, 0);
            for (int k = 0; k < i; k++, w=w*wn) {
                Complex X = x[j+k];
                Complex Y = w*x[j+k+i];
                x[j+k] = X + Y;
                x[j+k+i] = X - Y;
            }
        }
    }
}

int main() {
    int n, m = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        m = max(m, a[i]);
        A[a[i]] = {1, 0};
    }
    for (int i = 1; i <= n; i++) {
        B[m-a[i]] = {1, 0};
    }
    
    int l = 1, L = 0;
    for (l = 1; l < 2*m+2; l <<= 1) L++;
    for (int i = 0; i < l; i++) {
        R[i] = (R[i>>1]>>1)|((i&1)<<L-1);
    }
    
    fft(A, l, 1);
    fft(B, l, 1);
    for (int i = 0; i < l; i++) A[i] = A[i] * B[i];
    fft(A, l, -1);
    for (int i = 1; i <= m; i++) b[i] = (int)(A[i+m].x/l + 0.5);
    for (int i = 1; i <= m; i++) {
        bool f = true;
        for (int j = i; j <= m; j += i) {
            if(b[j]) {
                f = false;
                break;
            }
        } 
        if(f) {
            printf("%d
", i);
            exit(0);
        }
    }
    return 0;
}

View Code