hdu - 6186 and hdu - 6025

Posted by WildCow on May 22, 2018

CS Course

Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

Description

Little A has come to college and majored in Computer and Science.
Today he has learned bit-operations in Algorithm Lessons, and he got a problem as homework.
Here is the problem:
You are giving n non-negative integers , and some queries.
A query only contains a positive integer p, which means you
are asked to answer the result of bit-operations (and, or, xor) of all the integers except .

Input

There are no more than 15 test cases.
Each test case begins with two positive integers n and p
in a line, indicate the number of positive integers and the number of queries.
Then n non-negative integers follows in a line, for each i in range[1,n].
After that there are q positive integers in q lines, for each i in range[1,q].

Output

For each query p, output three non-negative integers indicates the result of bit-operations((and, or, xor)) of all non-negative integers except in a line.

Sample Input

3 3
1 1 1
1
2
3

Sample Output

1 1 0
1 1 0
1 1 0

Coprime Sequence

Time Limit: 1000 ms
Memory Limit: 131072 kB

Description

Do you know what is called “Coprime Sequence”? That is a sequence consists of n positive integers, and the GCD (Greatest Common Divisor) of them is equal to 1. “Coprime Sequence” is easy to find because of its restriction. But we can try to maximize the GCD of these integers by removing exactly one integer. Now given a sequence, please maximize the GCD of its elements.

Input

The first line of the input contains an integer $T(1≤T≤10)$, denoting the number of test cases. In each test case, there is an integer $n(3≤n≤100000)$ in the first line, denoting the number of integers in the sequence. Then the following line consists of $n$ integers $a_1,a_2,…,a_n(1≤a_i≤10^9)$, denoting the elements in the sequence.

Output

For each test case, print a single line containing a single integer, denoting the maximum GCD.

Sample Input

3
3
1 1 1
5
2 2 2 3 2
4
1 2 4 8

Sample Output

1
2
2


两道题的性质都是一样的

1、给你 $n$ 个数 $a_1,a_2,…,a_n$ 和 $q$ 次询问,每次询问给你一个数 $x$,输出除了 $a_x$ 外的剩下数字的 $and, or, xor$ 的结果。

2、给你 $n$ 个数 $a_1,a_2,…,a_n$ ,你需要输出删除一个数后剩下数字的 GCD 的最大值。

对于 $\oplus$ 运算,直接算出所有数字的异或后再异或一次 $a_x$
原理大概就是 $a \oplus b \oplus b = a$

当然也可以用下面的方法一起解决

须知 $and,or,xor$ ,GCD 的运算的结果均与顺序无关

我们以 $and$ 为例
先预处理一发所给数列的前缀 $and$ 和后缀 $and$ ,然后直接查询 x - 1 的前缀 $and$ 以及 x + 1 的后缀 $and$ ,再算一次 $and$ 就出来了
其余的同理
不过要注意一下初始化的不同


/// Hdu - 6186
#include <bits/stdc++.h>
using namespace std;  
  
const int N = 100010;  
  
int ma[N];  
int a1[N], a2[N];  
int b1[N], b2[N];  
int c;  
  
int main()  
{  
    int n, m;  
  
    while(scanf("%d%d", &n, &m) == 2){  
        for(int i = 1; i <= n; i ++){  
            scanf("%d", &ma[i]);  
        }  
        a1[0] = (1 << 31) - 1;/// & 运算的初始值要每一位都为1  
        b1[0] = 0;  
        c = 0;  
        for(int i = 1; i <= n; i ++){  
            a1[i] = a1[i - 1] & ma[i];  
            b1[i] = b1[i - 1] | ma[i];  
            c ^= ma[i];  
        }  
        a2[n + 1] = (1 << 31) - 1;  
        b2[n + 1] = 0;  
        for(int i = n; i > 0; i --){  
            a2[i] = a2[i + 1] & ma[i];  
            b2[i] = b2[i + 1] | ma[i];  
        }  
        for(int i = 0; i < m; i ++){  
            int x;  
  
            scanf("%d", &x);  
            printf("%d %d %d\n", a1[x - 1] & a2[x + 1], b1[x - 1] | b2[x + 1], c ^ ma[x]);  
        }  
    }  
  
    return 0;  
}  





/// HDU - 6025
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int ma[N];
int mb[N];
int mc[N];

int main()
{
    int ncase;
    int n;
    int li;
    int ans;

    scanf("%d", &ncase);
    while(ncase --){
        ans = -1;
        scanf("%d", &n);
        for(int i = 0; i < n; i ++){
            scanf("%d", &ma[i]);
            if(i == 0){
                mb[i] = ma[i];
            }
            mb[i] = __gcd(ma[i], mb[i - 1]);
        }
        mc[n - 1] = ma[n - 1];
        for(int i = n - 2; i >= 0; i --){
            mc[i] = __gcd(ma[i], mc[i + 1]);
        }
        li = n - 1;
        for(int i = 1; i < n; i ++){
            ans = max(ans, __gcd(mb[i - 1], mc[i + 1]));
        }
        ans = max(ans, mb[n - 2]);
        ans = max(ans, mc[1]);
        printf("%d\n", ans);
    }

    return 0;
}