小白月赛25

C白魔法师
题目链接https://ac.nowcoder.com/acm/problem/205862
知识点:图论、并查集
先将每个白色节点所对应的联通块中白色的个数进行预处理，dfs的过程中只有未访问还有子节点是白色才继续进行。(在这个过程中对res进行维护，因为有可能没有黑色节点不需要进行施法)
然后再将每个黑色节点中相连的白色联通块相加，再加上它本身施法变成白色来对res进行维护。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

vector<int> adj[N];
int n;
char s[N];
int ans[N];
bool st[N];
vector<int> in;

void dfs(int u) {
    in.push_back(u);
    st[u] = true;
    for(auto v : adj[u]) {
        if(!st[v] && s[v] == 'W')
            dfs(v);
    }
}

int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    for(int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int res = 0;
    for(int i = 1; i <= n; i++) {
        if(!st[i] && s[i] == 'W') {
            st[i] = true;
            in.clear();
            dfs(i);
            int sum = in.size();
            for(auto v : in)
                ans[v] = sum;         //将dfs中所有遍历过的点 都附上整个联通块的值 
            res = max(res, sum); 
        }
    }
    for(int i = 1; i <= n; i++) {
        if(s[i] == 'B') {
            int an = 1;
            for(auto v : adj[i]) {
                an += ans[v];
            }
            res = max(res, an);
        }
    }
    printf("%d", res);
    return 0;
}

G解方程
题目链接:https://ac.nowcoder.com/acm/problem/205829
由于是单调递增的函数，因此可以进行二分。
用while(>eps)会TLE（r - l无限不动）解决方法是用long double或二分足够多的次数如1000次二分

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;

double a, b, c;

double f(double x) {
    if(a == 1) return x + b * log(x);
    else if(a == 2) return x * x + b * log(x);
    else return x * x * x + b * log(x);
}

int main()
{
    cin >> a >> b >> c;
    double l = 1e-9, r = 1e9;
    for(int i = 0; i <= 10000; i++) {
        double mid = (l + r) / 2.0;
        if(f(mid) <= c) l = mid;
        else r = mid;
    }
    printf("%.8lf", l);
    return 0;
}

J异或和之和
知识点:位运算
思路:对没一位进行处理，在分别球每一位的贡献度
若该位有1则存在贡献度否则没有
三个数异或只有两种情况下该位是1
1 XOR 1 XOR 1
或
1 XOR 0 XOR 0
若该位有k个1则贡献度为
C（k，3）+C（k，1）*C(n - k， 2)
代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;  //由于a范围为1e18 是ll范围 
const int mod = 1000000007;
const int N = 200010;

ll n;
ll t[64];            //用来存储每一位1的个数

ll qpow(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
} 

ll inv(ll x) {  //求逆元 
    return qpow(x, mod - 2); 
}

ll f(ll x, ll y) {
    if(x < y) return 0;
    ll res = 1;
    for(ll i = 0; i < y; i++) {
        res = res * (x - i) % mod;
        res = res * inv(i + 1) % mod;
    }
    return res;
}

int main()
{
    scanf("%lld", &n);
    ll x;
    for(ll i = 0; i < n; i++) {
        scanf("%lld", &x);
        ll j = 0;
        while(x) {
            if(x & 1) t[j]++;
            j++, x >>= 1;
        }
    }
    ll sum = 0;
    for(int i = 0; i < 64; i++) {
        sum += (1ll << i) % mod * (f(t[i], 3) + f(n - t[i], 2) * t[i] % mod) % mod;
        sum %= mod;
    }
    printf("%lld", sum);
    return 0;
}