从n个数中选n-1个数字使得他们的gcd最大
思路：求一个前缀和一个后缀
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N],t[N],s[N]; int T,n,ans; int gcd(int x,int y) { if(y == 0) return x; return gcd(y,x % y); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); ans = 0; for(int i = 1;i <= n; ++i) { scanf("%d",&a[i]); if(i == 1) s[i] = a[i]; else s[i] = gcd(s[i - 1],a[i]); } t[n] = a[n]; for(int i = n - 1;i >= 1; --i) t[i] = gcd(t[i + 1],a[i]); for(int i = 1;i <= n; ++i) { if(i == 1) ans = max(ans,t[2]); else if(i == n) ans = max(ans,s[n - 1]); else ans = max(ans,gcd(s[i - 1],t[i + 1])); } printf("%d\n",ans); } return 0; }
类似的：从n个数中选n-1个数字使得他们的异或值最大
https://ac.nowcoder.com/acm/contest/549/D
#include<bits/stdc++.h> using namespace std; const int N = 5e6 + 10; int a[N],t[N],s[N]; int T,n,ans; int main() { while(~scanf("%d",&n)) { ans = 0; for(int i = 1;i <= n; ++i) { scanf("%d",&a[i]); if(i == 1) s[i] = a[i]; else s[i] = s[i - 1] | a[i]; } t[n] = a[n]; for(int i = n - 1;i >= 1; --i) t[i] = t[i + 1] | a[i]; for(int i = 1;i <= n; ++i) { if(i == 1) ans = max(ans,t[2]); else if(i == n) ans = max(ans,s[n - 1]); else ans = max(ans,s[i - 1] | t[i + 1]); } printf("%d\n",ans); } return 0; }
