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);
//headconst int N = 1e3 + ;
int a[N];
bool vis[N];
int main() {
int n, tot = ;
scanf("%d", &n);
for (int i = ; i <= n; i++) a[i] = i;
int pre = n, now;
while(tot--) {
random_shuffle(a+, a++n);
for (int i = ; i <= n; i++) {
printf("0 %d\n", a[i]);
fflush(stdout);
scanf("%d", &now);
if(now < pre) {
vis[a[i]] = true;
}
pre = now;
}
}
for (int i = ; i <= n; i++) if(!vis[i]) return *printf("1 %d\n", i);
return ;
}
思路: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);
//headconst int N = 8e6 + , M = 2e6 + ;
int R[N], a[M], b[M];
struct Complex {
double x, y;
Complex(double _x=, double _y=) : 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 = ; i < n; i++) if(i < R[i]) swap(x[i], x[R[i]]);
for (int i = ; i < n; i<<=) {
Complex wn(cos(pi/i), type*sin(pi/i));
for (int j = ; j < n; j+=i<<) {
Complex w(, );
for (int k = ; 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 = ;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
m = max(m, a[i]);
A[a[i]] = {, };
}
for (int i = ; i <= n; i++) {
B[m-a[i]] = {, };
} int l = , L = ;
for (l = ; l < *m+; l <<= ) L++;
for (int i = ; i < l; i++) {
R[i] = (R[i>>]>>)|((i&)<<L-);
} fft(A, l, );
fft(B, l, );
for (int i = ; i < l; i++) A[i] = A[i] * B[i];
fft(A, l, -);
for (int i = ; i <= m; i++) b[i] = (int)(A[i+m].x/l + 0.5);
for (int i = ; i <= m; i++) {
bool f = true;
for (int j = i; j <= m; j += i) {
if(b[j]) {
f = false;
break;
}
}
if(f) {
printf("%d\n", i);
exit();
}
}
return ;
}
