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

A

wool sequence 表示一个序列中可以找到一个连续的子区间使得区间异或值为0

那么求的是不含这种情况的序列个数

题目中数据范围是，在0~2^m - 1中选n个数作为一个序列 

n和m都是10^5

仔细思考一下。

第一位 有2^m-1种情况

第二位由于不能跟其一样  有2^m-2种情况

第三位由于不能跟第二位一样，并且不能跟前两位的异或值一样，有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    <br>   <br>    <p class="sycode">   <br>  </p> B  <p>给出一个序列a和一个数值h</p>  <p>将序列划分为两部分，某部分可以为空</p>  <p>然后f函数式这么计算</p>  <p>如果两个数在同个部分</p>  <p>f函数的值就是两个数的和</p>  <p>不在同部分就两个数的和加上h</p>  <p>求一种划分使得f函数的最大值和最小值的差值最小</p>  <p><br> </p>  <p>有一种贪心方案， </p>  <p>就是f的最大值一定跟序列中最大的几个有关</p>  <p>最小值一定跟序列中最小的几个有关</p>  <p>这里我取得最小的5个和最大的5个</p>  <p>直接枚举放第一部分或者第二部分即可</p>  <p><br> </p>  <p>为啥这样可以</p>  <p>仔细想一下。</p>  <p>可以发现其他的任何情形都没有这种情况下优</p>  <p><br> </p>  <p></p>  <pre name="code" class="sycode">int n, h;struct node {    int x, id;}p[111111], tmp[15];int ans[111111];bool cmp(node x, node y) {    return x.x lft, rht;int main(){    scanf("%d%d", &n, &h);    for(int i = 0; i  10) {        for(int i = 0; i  mx - mi) {            d = mx - mi;            num = 0;            for(int j = 0; j   <br>  <br>  <p></p>  <p>C</p>  <p>一颗无根树</p>  <p>有向边</p>  <p>从树上不多于两个点出发，遍历所有的点，</p>  <p>问需要改变最少多少个有向边的方向</p>  <p>那么就是一个树dp了</p>  <p>枚举根作为第一个点，</p>  <p>然后第二个点就需要dp</p>  <p>从根往下遍历所有的点的话，需要修改边的方向很容易算出来，每个点访问自己所有子树需要修改的边数也很容易算</p>  <p>然后数组开 dp[n][2]</p>  <p>dp[u][0]代表从u走到根需要修改多少边</p>  <p>dp[u][1]表示从跟走到u需要修改多少边</p>  <p><br> </p>  <p></p>  <pre name="code" class="sycode">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   <br>  <br>  <p></p>  <p><br> </p>  <p>D.</p>  <p>留坑  不会</p>  <p><br> </p>  <p>E</p>  <p>看了ACMonster的才大约懂做，其实还是很模糊</p>  <p><br> </p>  <p>有个有向图，边的长度都一样</p>  <p>n  </p>
<p>有个人要从起点到终点去，必须做公交</p>  <p>然后有若干辆公交  有各自的起点和终点</p>  <p>保证每秒都有一辆公交发出，意思就是那个人一到某个点就可以换乘相应的公交</p>  <p>然后这些公交很奇怪， 从自己的起点到终点，它会随机走一条最短路径过去</p>  <p>现在问，最小的（他在最坏情况下的换乘次数）</p>  <p>就是寻找一条线路使得他在最坏情况下换乘bus的次数最小</p>  <p><br> </p>  <p>这个由于是求换乘次数，所以这个图就没法按dag那种dp方法</p>  <p>首先预处理任意两点间的最短路</p>  <p>然后把每个点必然经过的公交线路存下来</p>  <p>然后就倒着dp</p>  <p>从终点往起点dp</p>  <p>非常之暴力</p>  <p>令dp[i][j]表示人在点i在j车上时最小的换乘次数</p>  <p>但是有两种情况</p>  <p>一种是这个点一定在这个公交线路上</p>  <p>一种是这个点可能会在这个公交线路上或者就不在这个公交线路上</p>  <p>第一种情况是最终的合法解</p>  <p>第二种用来辅助第一种</p>  <p><br> </p>  <p>然后更新的时候，对于每个点，枚举公交车，然后看这个点的邻接点，相对于这个路径是不是合法的，意思就是邻接点离该路径的终点应该是更近一步的，</p>  <p>即使这个点不会出现在这个公交路径上，也要更新，这是为了让那些后面的关键的点可以更新到，其实就相当于虚拟了一下，将这个公交的线路给延伸了</p>  <p>对于这些合法的邻接点， 选择一条最糟糕的</p>  <p>然后枚举换乘的时候，就必须是这个点一定在这个公交线路上，  因为换乘一定是在这些点上才能换乘，不然最糟糕的情况是等不到车的</p>  <p>然后如果有最优值被更新，那么整个dp再重复这个过程 </p>  <p><br> </p>  <p></p>  <pre name="code" class="sycode">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  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   <br>  <br>  <p></p>  <p><br> </p>  <p><br> </p> </int>