牛客练习赛32

emm.还是要及时补博客鸭.好多博客都忘记写.当时做题的思想过一段时间就忘了呀.

A Phrase String

AC

题目大意:

构造一个01串.满足最低位和最高位是1.是回文串.长度是$max(v,k)$.v,k都是偶数.求01串转换成10进制最小.

题解:

tag:贪心
贪心的从中间往尽量的填1.

#include<bits/stdc++.h>
using namespace std;

int s[100100];
int v,k;
typedef long long LL;
const int MOD = 1e9+7;

int main(){
	//freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> v >> k;
    int x = max(v, k);
    int f = x/2 - (k-2)/2;
    memset(s, 0, sizeof s);
    s[0] = 1; s[x-1] = 1;
    for(int i = f, x = 0; x < (k-2); ++i, ++x){
        s[i] = 1;
    }
    LL ans = 0;
    LL two = 1LL;
    for(int i = 0; i < x; ++i){
        if(s[i]) ans = (ans + two) % MOD;
        two = two*2LL % MOD;
    }
    cout << ans << endl;
	return 0;
}

B Xor Path

WA

题目大意:

给定一棵n个点的树，每个点有权值。定义path(i,j)表示i到j的最短路径上.所有点的点权异或和.求最后所有path(i,j)的异或和.

题解:

tag:树

1
2
3

        E
    A       F
B  C  D    G H J

因为是异或.所以我们只要计算每个点参与异或了多少次.参与异或次数是奇数的话.是有贡献的.比如计算A参与异或了多少次.sz[i]表示以i为根的子树结点个数.sz[B]个结点和N-sz[A],sz[C],sz[D]个结点之间的最短路都要经过A.同理.sz[C]个结点和sz[B],sz[D],N-sz[A]个结点也要经过A.但是B->C和C->B(这里字母表示以它为根的整个子树的所有结点)重复计算了.所以应该这样计算:

$$B(C+D+(N-A)) + C(D+(N-A)) + D*(N-A) + (N-1)$$

说明一下:上面的N表示N个结点.A,B,C等字母表示以该字母为根的子树的结点个数.最后加上(N-1)是因为.A出发到其他所有结点的最短路肯定要经过A.注意叶子结点的特殊情况处理.

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MAX_N = 5*1e5+100;
vector<int> G[MAX_N];
int A[MAX_N], sz[MAX_N];
int N, ans;

void dfs(int u, int fa){
    sz[u] = 1; // 自己
    vector<int> vi; // 存以u为根的所有子树的结点个数.以及除去u为根的子树之外的结点个数
    int len = G[u].size();
    if(len == 1) vi.push_back(0); // 这个点是叶子结点.它的子树结点设置成0.为了统一下面的计算
    for(int i = 0; i < len; ++i){
        int v = G[u][i];
        if(v == fa) continue; // 访问过
        dfs(v, u); // 计算改孩子结点为根的子树
        sz[u] += sz[v]; // 加上
        vi.push_back(sz[v]); // 加入vi
    }
    vi.push_back(N - sz[u]); // 除去以u为根的子树的结点个数.\sum{vi_{i}^len1 == N-1}
    int len1 = vi.size();
    LL tmp = 0;
    int all = N-1;
    // 所有点经过u的次数
    for(int i = 0; i < len1; ++i){
        all -= vi[i];
        tmp += 1LL*vi[i]*all;
    }
    tmp += N-1; // 其他N-1到他的最短距离.
    if(tmp&1) ans ^= A[u]; // 个数是奇数是有贡献的
}

int main(){
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    int u,v;
    for(int i = 0; i < N-1; ++i){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i = 1; i <= N; ++i) cin >> A[i];
    ans = 0;
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

C Balls

AC

题目大意:

有一个盒子，里面有一个黑球和一个白球。每次随机取出盒子中的一个球，并将两个与取出球同色的球放进盒子（就是随机一种颜色将其个数+1）。
求n次取球后，盒子中白色球数目的期望。

题解:

tag:数学
emm.mmp.取n次之后盒子里面有n+2个球.黑白球一样期望一样.所以是$(n+2)/2$.

#include<bits/stdc++.h>
using namespace std;

int n;

int main(){
	//freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    printf("%.7f", (1.0*n+2.0)/2.0);
	return 0;
}