2024牛客暑期多校训练营4
IR101
·
·
个人记录
LCT
思路：反向考虑，动态维护直径，LCA维护点点距离，集合合并直径更新即可，答案必然是直径端点之一,这样会有一个倍增的内存，会卡常数，更简单的方式是并查集直径合并求解
diamond:
#include<iostream>
#include<queue>
using namespace std;
typedef long long int ll;
#define PII pair<int,int>
#define endl '\n'
const int N = 1e6 + 1;
int n, m;
int dep[N], fa[N][20];
PII dot[N];
int p[N];
struct node {
int x, y, st;
};
int h[N], e[N * 2], ne[N * 2], idx;
inline void add(int a, int b) {
e[++idx] = b; ne[idx] = h[a]; h[a] = idx;
}
int LCA(int a, int b) {
if (dep[a] < dep[b])swap(a, b);
for (int i = 19; i >= 0; --i) {
if (dep[fa[a][i]] >= dep[b]) {
a = fa[a][i];
}
}
if (a == b)return a;
for (int i = 19; i >= 0; --i) {
if (fa[a][i] != fa[b][i]) {
a = fa[a][i];
b = fa[b][i];
}
}
return fa[a][0];
}
void BFS(int u) {
queue<int> q;
q.push({u});
for (int i = 1; i <= n; i++) {
dep[i] = 1e7;
}
dep[u] = 1;
dep[0] = 0;
while (!q.empty()) {
auto t = q.front();
q.pop();
for (int i = h[t]; i; i = ne[i]) {
int v = e[i];
if (dep[v] > dep[t] + 1) {
dep[v] = dep[t] + 1;
fa[v][0] = t;
q.push(v);
for (int i = 1; i <= 19; ++i) {
fa[v][i] = fa[fa[v][i - 1]][i - 1];
}
}
}
}
}
int getdist(int a, int b) {
return dep[a] + dep[b] - 2 * (dep[LCA(a, b)]);
}
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
void init() {
for (int i = 1; i <= n ; ++i) {
p[i] = i;
h[i] = 0;
dot[i].first = dot[i].second = i;
}
idx = 0;
for (int i = 0; i <= 2 * n; i ++) {
e[i] = ne[i] = 0;
}
}
int a, b, x;
node q[N];
int pa,pb;
void solve() {
cin >> n;
//n = 1e6;
init();
for (int i = 1; i < n; ++i) {
// a = b = 1;
cin >> a >> b >> x;
// a=i;
// b=i+1;
// x=i;
// g[a].push_back(b);
// g[b].push_back(a);
add(a, b);
add(b, a);
q[i] = {a, b, x};
}
BFS(1);
// dfs1(1, 0), dfs2(1, 1);
auto merge = [&](int a, int b) {
pa = find(a), pb = find(b);
p[pa] = pb;
auto [p1, p2] = dot[pa];
auto [t1, t2] = dot[pb];
PII &res = dot[pb];
if (getdist(t1, t2) < getdist(p1, p2)) res = {p1, p2};
int dist = getdist(res.first, res.second);
for (auto &x : {p1, p2})
for (auto &y : {t1, t2}) {
int cur_dist = getdist(x, y);
if (dist < cur_dist) {
dist = cur_dist;
res = {x, y};
}
}
return getdist(res.first, res.second);
};
for (int i = 1; i < n ; ++i) {
auto &[x, y, st] = q[i];
merge(x, y);
pa = find(st);
auto &[l, r] = dot[pa];
cout << max(getdist(l, st), getdist(r, st)) << ' ';
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Zero
思路：对二项式进行展开，对l前缀和一下，得出答案即可
diamond：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define endl '\n'
const int mod=998244353;
const int N=1e5+7;
int suml[31][N];
int cnt[N];
int inv[N];
int c[31][31];
int pw[N];
void init () {
for (int i = 0; i < 31; i ++ ) {
for (int j = 0; j <= i; j ++ ) {
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1){
res=res*a%mod;
}
a=a*a%mod;
b>>=1;
}
return res;
}
void solve() {
int n,k;
cin>>n>>k;
string s;
cin>>s;
s=" "+s;
init();
// cout<<c[3][2]<<endl;
pw[0]=inv[0]=1;
int d= ksm(2,mod-2);
for (int i = 1; i <=n ; ++i) {
pw[i]=pw[i-1]*2%mod;
inv[i]=inv[i-1]*d%mod;
}
// cout<<inv[3]<<' ';
for (int i = 1; i <=n ; ++i) {
cnt[i]=cnt[i-1];
if(s[i]=='?')cnt[i]++;
for (int j = 0; j <=k ; ++j) {
suml[j][i]=suml[j][i-1];
if(s[i]!='0'){
suml[j][i]+=ksm(mod-i,k-j)*pw[cnt[i-1]]%mod;
suml[j][i]%=mod;
}
}
}
int ans=0;
int ls=1;
for (int r = 1; r <=n ; ++r) {
if(s[r]=='0'){
ls=r+1;
}
else {
for (int i = 0; i <= k; ++i) {
ans +=c[k][i]*ksm(r+1,i)%mod*inv[cnt[r]]%mod*(suml[i][r]-suml[i][ls-1]+mod)%mod;
ans%=mod;
}
}
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0);
int t=1;
// cin>>t;
while (t--){
solve();
}
}