Codeforces Round #148 (Div. 1)_html/css_WEB-ITnose-HTML Tutorial-php.cn

wool sequence means that a continuous subinterval can be found in a sequence such that the interval XOR value is 0

Then what you want is the number of sequences that do not include this situation

The data range in the question is, choose between 0~2^m - 1 n numbers as a sequence

n and m are both 10^5

Think about it carefully.

The first one has 2^m-1 situations

The second one has 2^m-2 situations because it cannot be the same as it

The third one cannot It is the same as the second digit, and cannot be the same as the XOR value of the first two digits. There are 2^m-3 situations

and so on, to get the formula

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

Copy after login

is given A sequence a and a value h

Divide the sequence into two parts, some part can be empty

Then the f function formula is calculated like this

If the two numbers are in the same Part

The value of the f function is the sum of the two numbers

If they are not in the same part, the sum of the two numbers plus h

Find a partition that maximizes the f function The difference between the value and the minimum value is the smallest

There is a greedy solution,

That is, the maximum value of f must be related to the largest ones in the sequence

The minimum value must be related to the smallest ones in the sequence

Here I get the smallest 5 and the largest 5

Directly enumerate and put the first or second part. But

Why is this okay?

Think about it carefully.

It can be found that no other situation is better than this

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

Copy after login

A rootless tree

Directed edge

Start from no more than two points on the tree and traverse all points,

Ask the minimum number of directions of directed edges that need to be changed

Then it is a tree dp

Enumerate the root as the first point,

Then the Two points require dp

If you traverse all the points from the root downward, the direction of the edges that need to be modified is easy to calculate, and the number of edges that need to be modified for each point to access all its own subtrees is also easy to calculate

Then open the array dp[n][2]

dp[u][0] represents how many edges need to be modified from u to the root

dp[u][1 ] indicates how many edges need to be modified from following to u

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

Copy after login

You won’t leave a hole

You only know how to do it after watching ACMonster. In fact, Still very blurry

There is a directed graph, the length of the sides are all the same

n<=100

Someone wants to start from the starting point To get to the end point, you must take a bus

Then there are several buses with their own starting points and end points

It is guaranteed that one bus will leave every second, which means that as soon as the person reaches a certain point, he can Transfer to the corresponding bus

Then these buses are very strange. From its starting point to the end point, it will randomly take the shortest path to the past

Now ask, the smallest (he is in the worst case The number of transfers)

is to find a route that minimizes the number of bus transfers in the worst case scenario

This is because it is to find the number of transfers , so this picture cannot follow the dp method of dag

First preprocess the shortest path between any two points

and then save the bus lines that must pass through each point

Then dp backwards

From the end point to the starting point dp

Very violent

Let dp[i][j] mean that the person is at point i and in car j The minimum number of transfers

But there are two situations

One is that this point must be on this bus line

One is that this point may be on this bus line On the bus route or not on this bus route

The first case is the final legal solution

The second one is used to assist the first one

Then when updating, for each point, enumerate the buses, and then check whether the adjacent points of this point are legal relative to this path, which means that the adjacent points should be closer to the end of the path. One step,

Even if this point does not appear on this bus route, it must be updated. This is to allow those later key points to be updated. In fact, it is equivalent to virtualizing this bus. The lines are extended

For these legal adjacent points, when selecting the worst

and then enumerating transfers, this point must be on this bus line, because The transfer must be at these points, otherwise the worst case scenario is that you can't wait for the bus

Then if the optimal value is updated, then the entire dp will repeat the process

int dis[111][111], dp[111][111];vector<int>g[111], bus[111];int bx[111], by[111], m, n, t, src, des;bool pass[111][111];int main(){    int u, v;    scanf("%d%d%d%d", &n, &m, &src, &des);    for(int i = 1; i <= n; i++)        for(int j = 1; j <= n; j++)            if(i != j) dis[i][j] = INF;    for(int i = 0; i < m; i++) {        scanf("%d%d", &u, &v);        dis[u][v] = 1;        g[u].push_back(v);    }    for(int k = 1; k <= n; k++) {        for(int i = 1; i <= n; i++) {            for(int j = 1; j <= n; j++)                if(dis[i][j] > dis[i][k] + dis[k][j])                    dis[i][j] = dis[i][k] + dis[k][j];        }    }    m = 0;    scanf("%d", &t);    while(t--) {        scanf("%d%d", &u, &v);        if(dis[u][v] != INF) {            m++;            bx[m] = u;            by[m] = v;        }    }    for(int i = 1; i <= m; i++) {        u = bx[i], v = by[i];        for(int j = 1; j <= n; j++) {            if(dis[u][v] == dis[u][j] + dis[j][v]) pass[i][j] = 1;            for(int k = 1; k <= n; k++) {                if(k != j && dis[u][k] == dis[u][j] && dis[k][v] == dis[j][v]) {                    pass[i][j] = 0;                    break;                }            }            if(pass[i][j]) bus[j].push_back(i);        }    }    for(int i = 1; i <= n; i++) {        for(int j = 1; j <= m; j++) {            if(i == des && pass[j][i]) dp[i][j] = 0;            else dp[i][j] = INF;        }    }    bool flag = 1;    while(flag) {        flag = 0;        for(int i = 1; i <= n; i++) {            for(int j = 1; j <= m; j++) {                int mx = -1;                for(int k = 0; k < g[i].size(); k++) {                    v = g[i][k];                    if(dis[i][by[j]] != dis[v][by[j]] + 1) continue;                    //if(!pass[j][i] || !pass[j][v]) continue;                    mx = max(mx, dp[v][j]);                }                if(mx != -1 && mx < dp[i][j]) {                    dp[i][j] = mx;                    flag = 1;                }                for(int k = 0; k < bus[i].size(); k++) {                    v = bus[i][k];                    if(dp[i][v] + 1 < dp[i][j]) {                        dp[i][j] = dp[i][v] + 1;                        flag = 1;                    }                }            }        }    }    int ans = INF;    for(int i = 1; i <= m; i++)        if(pass[i][src]) ans = min(ans, dp[src][i] + 1);    if(ans == INF) ans = -1;    printf("%d\n", ans);    return 0;}

Copy after login