Codeforces Round #276 (Div. 1)_html/css_WEB-ITnose

This session has been unrated due to a system problem

The questions are quite short and concise

A

The general theme of the questions It is

There are n queries (10^4), each query is to find the number with the most binary digits 1 in the interval [l, r]

The range of l, r is 10^ 18

Then there is greed. Just use l to be greedy from low to up. If 0 changes to 1, it will change to

long long l, r;int n;int main(){    scanf("%d", &n);    for(int i = 0; i < n; i++) {        scanf("%I64d%I64d", &l, &r);        for(int j = 0; j < 61; j++) {            long long tmp = 1LL << j;            if(l & tmp) continue;            else if((l ^ tmp) <= r) l ^= tmp;        }        printf("%I64d\n", l);    }    return 0;}

B

Given a sequence a, length 2*10^5, the range of each number is 10^6

Then ask for the largest a[i]%a[j] where the requirement is a[i > >

is to mark any a[i] as 1, then

scan from 1 to mx and count the largest a[i] smaller than the current number, where mx should be 2000000

Then enumerate, for each number, enumerate the multiples

If the number is x and the multiple is y, then find the largest a[i] smaller than x * y , use a[i] - x *(y -1) to find a possible solution

C No pitfalls

bool v[2111111];int pre[2111111];int a[222222];int n;int main() {    scanf("%d", &n);    for(int i = 0; i < n; i++) {        scanf("%d", &a[i]);        v[a[i]] = 1;    }    int mx = 2000005;    for(int i = 1; i < mx; i++) {        pre[i] = pre[i - 1];        if(v[i - 1]) pre[i] = i - 1;    }    int ans = 0;    for(int i = 1; i < mx; i++) {        if(!v[i]) continue;        for(int j = 2 * i; j < mx; j += i) {            ans = max(ans, pre[j] + i - j);        }    }    printf("%d\n", ans);    return 0;}

D

Give a sequence length 10^6

Then To group, each group is a certain continuous subsequence in this sequence and cannot be empty

Then calculate a maxvalue - minvalue for each group

Finally sum up

Ask how Grouping, this sum is maximal

The bare dp equation is dp[i] =max( dp[j- 1] mx[j][i] - mi[j] [i] )

Definitely not. The complexity is too high

There are two ways to do it.

1. We regard this sequence as consisting of a number of single-increasing and single-declining sequences,

Then obviously, divide this sequence into several of these A continuous subsequence with a single increase and a single decrease will be optimal

Then for a pole, there are two situations, left or right, whichever is optimal

2. Change the dp equation

int a[1111111];long long dp[1111111];int main() {    int n;    scanf("%d", &n);    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);    int pos = 1;    for(int i = 2; i <= n; i++) {        dp[i] = dp[pos - 1] + abs(a[i] - a[pos]);        dp[i] = max(dp[i], dp[pos] + abs(a[i] - a[pos + 1]));        if(a[i] >= a[i - 1] && a[i] >= a[i + 1]) pos = i;        if(a[i] <= a[i - 1] && a[i] <= a[i + 1]) pos = i;    }    printf("%I64d\n", dp[n]);    return 0;}

There are two situations

First, the value of the current position may be the maximum value

Then dp[i] =(dp[j- 1] - mi[j][i] ) a[i]

Another way is that the current position is the minimum value,

dp[i] = (dp[j - 1] mx[j][i]) - a[i]

In other cases, it is an invalid state, even if you update it Will affect the results

For these two cases

will (dp[j- 1] - mi[j][i] ) and (dp[j - 1] mx[j] [i]) Just perform maintenance

Maintenance is not as complicated as this formula shows

When reaching the i position, we only need to take the largest dp[j before the current position ], and then assuming that a[i] is the maximum value and minimum value, update these two formulas

and you can find that all situations are covered

E didn't do it. Leave a hole

int main() {    int n;    scanf("%d", &n);    long long ans = 0, x = 0, y = 0;    int a;    for(int i = 0; i < n; i++){        scanf("%d", &a);        if(!i || ans - a > x) x = ans - a;        if(!i || ans + a > y) y = ans + a;        ans = max(ans, x + a);        ans = max(ans, y - a);    }    printf("%I64d\n", ans);    return 0;}