Codeforces ラウンド #276 (ディビジョン 1)_html/css_WEB-ITnose

システムの問題のため、このセッションは評価されていません

質問は非常に短く簡潔です

A

質問の主なアイデアは次のとおりです

質問はn個（10^4）あります、各質問は [l ,r] で、区間

l 内で最も多くの 2 進ビット 1 を持つ数値を見つけることです。r の範囲は 10^18

それから、それは貪欲です。 低い位置から上に貪欲に l を使用するだけで、0 が 1 に変化する場合、範囲を超えない限り変化します。 a の場合、長さは 2*10^ です。 5、各数値の範囲は 10 ^6 です

次に、a[i] >= a[j] を必要とする最大の a[i]%a[j] を求めます

この範囲を見ると、基本的には次のようになります特別なカード nlognlogn

試してみてください 案の定

それから、nlogn

の方法があります

つまり、任意の a[i] を 1 としてマークし、それから

1 から mx までスキャンして、最大の a[このうち、mx は 2000000 でなければなりません

次に、それぞれの数値の倍数を列挙します

数値が x で、倍数が y の場合、より小さい最大の a[i] を見つけます。 x * y、a[ i] - x *(y -1) を使用して可能な解を見つけます

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

C 落とし穴はありません

D

長さ10^ 6

次に、グループ化する必要があります。各グループは、このシーケンス内の特定の連続した部分シーケンスであり、空にすることはできません

次に、各グループの最大値と最小値を計算します

最後に合計します

この合計をグループ化する方法を尋ねますは最大です

裸の dp 方程式は dp[i] =max( dp[j- 1] + mx[j][i] - mi[j][i] )

絶対に不可能です。複雑さが高すぎます

それには 2 つの方法があります。

1. このシーケンスは、多数の単一増加シーケンスと単一減少シーケンスで構成されていると見なされます。

したがって、明らかに、このシーケンスを単一増加と単一減少のいくつかの連続したサブシーケンスに分割するのが最適です。 -減少

次に、極については、左または右の 2 つの分割状況があります。最適な方を選択してください

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

2. dp 方程式を変更します

2 つの状況があります

1 つ目は現在位置です。値は最大値である可能性があります

次に、 dp[i] =(dp[j- 1] - mi[j][i] )+ a[i]

別の方法では、現在位置は次のようになります。最小値

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

それ以外の場合は無効な状態であり、更新しても結果には影響しません

これについては、どちらの場合も

(dp[j- 1] - mi[j][i] ) と (dp[j - 1] + mx[j][i]) を維持するだけです

メンテナンス中はそうではありません この式が示すように複雑です

i 位置に到達したら、現在の位置より前の最大の dp[j] を取得し、a[i] が最大であると仮定するだけで済みますこれら 2 つの式を更新するための最小値、つまり、しかし

はすべての状況をカバーするために見つけることができます

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

E はそれをしませんでした。穴を残してください