HDU 6025

从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;
}