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

A

wool シーケンスは、区間 XOR 値が 0 になるようなシーケンス内で連続した部分区間が見つかることを意味します

そして、見つかるのは、次の要素を含まないシーケンスの数です。この状況

質問のデータ範囲は、0~2^m - 1 から n 個の数値を数列として選択します

n と m は両方とも 10^5

よく考えてください。

最初のものは 2^m-1 個の状況があります

2 番目のものはそれと同じであることはできません、2^m-2 個の状況があります

3 番目のものは 2 番目のものと同じであることはできませんし、最初の 2 つと同じです。XOR 値は同じです。2^m-3 通りの状況があります

類推すると、式

(2^m-1)*(2^m-2)* が得られます。 .*(2^m-n)

int mod = 1000000009;int main(){    int n, m;    scanf("%d%d", &n, &m);    if(m < 20 && (1 << m) <= n ) {        printf("0\n");        return 0;    }    long long ans = 1;    for(int i = 0; i < m; i++) {        ans = ans * 2LL % mod;    }    long long res = 1;    for(int i = 1; i <= n; i++) {        long long tmp = ans - i;        if(tmp < 0) tmp += mod;        res = res * tmp % mod;    }    printf("%I64d\n", res);    return 0;}

B

シーケンス a と値 h が与えられた場合

シーケンスを 2 つの部分に分割し、一部の部分は空にすることができます

その後、f 関数は次のように計算されます

2つの数値が同じ部分にある場合

f関数の値は2つの数値の合計です

2つの数値が同じ部分にない場合は、2つの数値の合計にhを加えます

検索f 関数の最大値と最小値の差を最小化する分割です

1 つあります。貪欲なスキーム

は、f の最大値がシーケンス内の最大値に関連している必要があることを意味します

最小値はシーケンス内の最小値に関連している必要があります

ここで最小の5と最大の5を取得します

列挙の最初または2番目の部分を直接入力するだけです

なぜこれで大丈夫なのですか

慎重に考えてください。

この場合、他に優れた状況はないことがわかります

int n, h;struct node {    int x, id;}p[111111], tmp[15];int ans[111111];bool cmp(node x, node y) {    return x.x < y.x;}vector<node>lft, rht;int main(){    scanf("%d%d", &n, &h);    for(int i = 0; i < n; i++) {        scanf("%d", &p[i].x);        p[i].id = i;    }    sort(p, p + n, cmp);     int cnt = 0;    if(n > 10) {        for(int i = 0; i < 5; i++) tmp[cnt++] = p[i];        for(int i = n - 5; i < n; i++) tmp[cnt++] = p[i];    } else {        cnt = n;        for(int i = 0; i < n; i++) tmp[i] = p[i];    }    int vs[12];    int d = INF;    int num = 0;    for(int i = 0; i < (1 << cnt); i++) {        lft.clear();        rht.clear();        for(int j = 0; j < cnt; j++) {            node x = tmp[j];            if((1 << j) & i) {                lft.push_back(x);            } else rht.push_back(x);        }        int mx = 0;        int mi = INF;        int sz1 = lft.size();        for(int j = 0; j < sz1; j++) {            for(int k = j + 1; k < sz1; k++) {                mx = max(mx, lft[j].x + lft[k].x);                mi = min(mi, lft[j].x + lft[k].x);            }        }        int sz2 = rht.size();        for(int j = 0; j < sz2; j++) {            for(int k = j + 1; k < sz2; k++) {                mx = max(mx, rht[j].x + rht[k].x);                mi = min(mi, rht[j].x + rht[k].x);            }        }        for(int j = 0; j < sz1; j++) {            for(int k = 0; k < sz2; k++) {                mx = max(mx, lft[j].x + rht[k].x + h);                mi = min(mi, lft[j].x + rht[k].x + h);            }        }        if(d > mx - mi) {            d = mx - mi;            num = 0;            for(int j = 0; j < sz1; j++) vs[num++] = lft[j].id;        }    }    printf("%d\n", d);    for(int i = 0; i < n; i++) ans[i] = 2;    for(int i = 0; i < num; i++) ans[vs[i]] = 1;    for(int i = 0; i < n; i++) printf("%d ", ans[i]);    printf("\n");    return 0;}

C

根のない木

有向エッジ

開始点は 2 つだけです要点、すべての点を横断し、

変更する必要がある有向エッジの方向の最小数を尋ねます

それはツリー dp です

最初の点としてルートを列挙します、

次に 2 番目の点には dp が必要です

場合すべてのポイントをルートから下にトラバースすると、変更する必要があるエッジの方向を計算するのが簡単です。また、独自のすべてのサブツリーにアクセスするために各ポイントで変更する必要があるエッジの数を計算するのも簡単です。

次に、配列 dp[n][2 ] を開きます

dp[u][0] は、u からルートまで変更する必要があるエッジの数を表します

dp[u][1] は、変更する必要があるエッジの数を表しますフォローから変更しました

struct node {    int v, w;    node() {}    node(int _v, int _w) {v = _v; w = _w;}};vector<node> g[3333];int ss[3333], dp[3333][2];int total;void dfs0(int u, int f, int x) {    total += x;    ss[u] = ss[f] + x;    int sz = g[u].size();    for(int i = 0; i < sz; i++) {        int v = g[u][i].v;        int w = g[u][i].w;        if(v == f) continue;        dfs0(v, u, w);    }}void dfs(int u, int f, int x) {    if(f == 0) {        dp[u][0] = dp[u][1] = 0;    } else {        dp[u][1] = dp[f][1] + x;        dp[u][0] = min(dp[f][0], dp[f][1]) + !x;    }    int sz = g[u].size();    for(int i = 0; i < sz; i++) {        int v = g[u][i].v;        int w = g[u][i].w;        if(v == f) continue;        dfs(v, u, w);    }}int n;int main(){    int u, v;    scanf("%d", &n);    for(int i = 1; i <= n; i++) g[i].clear();    for(int i = 1; i < n; i++) {        scanf("%d%d", &u, &v);        g[u].push_back(node(v, 0));        g[v].push_back(node(u, 1));    }    int ans = INF;    for(int i = 1; i <= n; i++) {        ss[i] = 0;        total = 0;        dfs0(i, 0, 0);        dfs(i, 0, 0);        for(int j = 1; j <= n; j++) ans = min(ans, total - ss[j] + min(dp[j][0], dp[j][1]));    }    printf("%d\n", ans);    return 0;}

D.

Leave a Hole No way

E

ACMonsterを見た後でのみやり方を知っていますが、まだ非常に曖昧です

有向グラフがあり、辺の長さはすべて同じです

n 始点から終点まで行きたい場合は、次のことを行わなければなりませんバス

その後、独自の始点と終点を持つバスがいくつかあります

毎秒1台のバスが送られることが保証されており、その人が特定の場所に到着するとすぐに、対応するバスに乗り換えることができますある地点のバス

すると、これらのバスは非常に奇妙です。始点から終点まで、ランダムに過去への最短経路をたどります

さあ、最小のパス (最悪の場合の乗り換え回数) を尋ねてください。

最悪の場合のバスの乗り換え回数が最小になるルートを見つけるためです

乗り換え回数を求めるためなので、この画像はdagのdp法では使えません

最初の前処理任意の 2 点間の最短経路

次に、各点を通過する必要があるバス ラインを保存します

次に、dp を逆に実行します

終点から始点への dp を実行します

非常に暴力的です

dp[i][j にさせます] 人が点 i でバス j に乗っているときの最小乗り換え回数を表します

しかし、状況は 2 つあります

1 つは、この点はこのバス路線上になければならないということです

1 つは、この点はこのバス路線上にある可能性があるということですまたは、このバス ルート上にありません

最初のケースは、最終的な法的解決策です

2 番目のケースは、最初のケースを支援するために使用されます

その後、更新するときに、ポイントごとにバスを列挙し、隣接しているかどうかを確認しますこのポイントのポイントは、このパスに対して有効です。つまり、隣接するポイントはパスの終点に一歩近づく必要があります。

このポイントがこのバス ルートに表示されない場合でも、更新する必要があります。後の重要なポイントを更新できるようにすることは、実際には、それを仮想化し、バス ルートを拡張することと同じです

これらの合法的な隣接ポイントについて、最悪のポイントを選択し、転送を列挙します。これらのポイントで乗り換えを行う必要があるため、ポイントはこのバス線上にある必要があります。そうでない場合、最悪の状況はバスを待つことができないことです

その後、最適値が更新されたら、このプロセスを dp 全体に対して繰り返します

れーい