Lut本科回忆录

算是最近做的几道题里觉得值得回顾一下的吧

ABC295_D
题意：给定一个由0~9组成的字符串S, 且$|S| <= 5e5$，求存在多少个$l,r$满足$S_l,...S_r$中满足每个数字出现偶数次个

思路：假设我们只考虑 $l$ 到 $r$ 中的一种数字，如果我们求该数字的个数前缀和，如果满足题意的话那么 $sum[r] - sum[l - 1] = 0 (mod 0) $，那么显然这俩个的奇偶性是相同的。
那么我们可以用map来从前往后记录每种出现的状态的个数，用pre[i][j]来记录数字i到j位置出现的个数。
长度为10的状态st表示每一个数字出现个数的奇偶性

#include <bits/stdc++.h>
#define rep(i, n, m) for(int i = n; i <= m; ++i)
#define per(i, n, m) for(int i = n; i >= m; --i)
#define ll long long
using namespace std;
const int N = 5e5 + 10;
string st;
int pre[10][N];
ll ans;
map<string, int> p;
void cal(int u){
    rep(i, 0, 9) st[i] = pre[i][u] % 2 + '0';
    //更新当前每个状态出现个数的奇偶性
    if(p.count(st))ans += 1ll * p[st];
    p[st] ++;
}
int main(){
    string s; cin >> s;
    int n = s.size(); s = ' ' + s;
    st.resize(10); //初始化状态st
    rep(i, 0, 9) st[i] = '0';
    p[st] ++; 
    rep(i, 1, n){
        rep(j, 0, 9){
            pre[j][i] = pre[j][i - 1] + (j == s[i] - '0');
        }
        cal(i);
    }
    cout << ans;
    return 0;
}

ABC295_E
题意：给定 $n, m, k$,
和一个长度为 $n$ 的数组，为$A_1,A_2...A_n$ ,
其中$1<=k<=n<=2000, 1<=m<=2000, 0<=A_i<=m$
我们可以选择其中为0的位置，其值随机为 $1到m$ 的一个值，然后求对该数组排序后$A_k$的期望值

思路：据我们所知期望值$E(x)=∑i*p_{x=i} =∑ p_{x>=i} $，那么对于本题，对于每个$i∈(1,m)$,我们求排序后k位置上的$A_k >= i$的概率对答案的贡献

其中，我们统计原数组中比i大的数字个数tar和等于0的个数ze，我们若要第k位大于等于i，则还需要$n-k+1-tar$ 个大于等于i的数，如果我们定义此时的$tar=n-k+1-tar$，则当tar小于0时，无论怎么操作都能满足要求，此时对答案的贡献为1.
假设我们需要的$tar-ze>0$时，说明没有足够的0来满足题目要求，所以此时对答案的贡献都是0
倘若以上情况都不是，我们的贡献为$C_{ze}^jp^j(1-p)^{ze-j}$,其中p为选中的都是大于i的情况，即$p=(m-i+1)/m$
因为这题的数值都很小，可以用地推求组合数的方法写

#include <bits/stdc++.h>
#define rep(i, n, m) for(int i = n; i <= m; ++i)
#define int long long
using namespace std;
const int N = 2e3 + 10, MOD = 998244353;
int a[N], C[N][N];
int qmi(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans % MOD;
}
signed main(){
    //求组合数
    rep(i, 0, N - 1){
        rep(j, 0, i){
            if(j == 0) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
    int n, m, k; cin >> n >> m >> k;
    rep(i, 1, n) cin >> a[i];
    int ans = 0;
    rep(i, 1, m){
        int tar = n - k + 1, ze = 0;
        rep(j, 1, n){
            if(a[j] >= i) tar --;
            else if(a[j] == 0) ze ++ ;
        }
        if(tar < 0 || tar - ze > 0){
            // 如果满条件
            if(tar < 0) ans ++;
            continue;
        }
        int p = (m - i + 1) * qmi(m, MOD - 2) % MOD;
        // pp = 1 - p
        int pp = ((1 - p) % MOD + MOD) % MOD;
        //此时必须需要选择的 0 的个数为 tar ~ ze
        rep(j, tar, ze){
            int x = qmi(p, j), y = qmi(pp, ze - j);
            int num = C[ze][j] % MOD * x % MOD * y % MOD;
            ans = (ans + num) % MOD;
        }
    }
    cout << ans;
}

How far away
一道LCA题，算板子吧

题意：给定T组数据，每组数据有一棵树，给定$n,m$，分别为点数和边数，然后$n-1$行输入两个点及其边长，然后m组询问，每次查询两个结点的最近公共祖先

思路：我们利用倍增的思想，用 $f[i][j]$ 记录$i$结点往上$(1 << j)$ 的祖先，用 $dist[i] $记录$i$到根节点的深度,同时用一个$cost[i][j]$同样用倍增的思路记录路径长度
其中我们用

  	for(int i  = 1; i <= n; ++ i){
   	lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}

来地推$lg[i]$

#include <iostream>
#define rep(i, n, m) for(int i = n; i <= m; ++i)
#define per(i, n, m) for(int i = n; i >= m; --i)
using namespace std;
const int N = 8e5 + 10;
int w[N], h[N], ne[N], e[N], cnt, lg[N], dist[N], f[N][30], cost[N][30];
void add(int a, int b, int c){
     e[cnt] = b, w[cnt] = c, ne[cnt] = h[a], h[a] = cnt++;
}
void dfs(int u, int fa){
    dist[u] = dist[fa] + 1; //u的深度+1
    f[u][0] = fa; //u的上一个祖先时fa
    for(int i = 1; i <= lg[dist[u]]; ++ i){
		//倍增更新祖先和路径长度
        f[u][i] = f[f[u][i - 1]][i - 1];
        cost[u][i] = cost[f[u][i - 1]][i - 1] + cost[u][i - 1];
    }
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(j != fa){
			//更新上一层路径
            cost[j][0] = w[i];
            dfs(j, u);
        }
    }
}
int LCA(int a, int b){
    int ans = 0;
	//我们默认使得a的深度大于等于b的深度
    if(dist[a] < dist[b]) swap(a, b);
    //我们将a上升到与b同一深度的位置，同时给ans增加贡献
	while(dist[a] > dist[b]) 
        ans += cost[a][lg[dist[a] - dist[b]] - 1],
        a = f[a][lg[dist[a] - dist[b]] - 1];
    if(a == b) return ans;
	//二者仍然不相等，将a和b同时上升到公共祖先的儿子
    for(int i = lg[dist[a]] - 1; i >= 0; --i){
        if(f[a][i] != f[b][i]){
            ans += cost[a][i];
            ans += cost[b][i];
            a = f[a][i], b = f[b][i];
        }
    }
    return ans + cost[a][0] + cost[b][0];
}
int main()
{
    //ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while(T--){
   		memset(h, -1, sizeof h);
    	int n, m, s; cin >> n >> m;
   		 for(int i  = 1; i <= n; ++ i){
        	lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	    }
    	rep(i, 1, n - 1){
        	int a, b, c; cin >> a >> b >> c;
       		add(a, b, c); add(b, a, c);
    	}   
    	dfs(1, 0); //我们默认以1为根节点深搜
    	while(m --){
        	int a, b; cin >> a >> b;
        	cout << LCA(a, b) << '\n';
    	}
    }
    return 0;
}