Tree Destruction - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:树的直径。
定理：在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。 第一次dfs1(),从任意一个点,到达的最远的点必然是直径两端的其中一个。 再从找到的端点开始dfs1(),找到另一个端点。这样就可以o(n)确定该树的直径.得到直径的端点S和T. 再两次dfs2(),分别得到S和T到达其他每个点的距离. 之后就可以从度为1的点x开始删除,每次都选和x更远的端点.并且删除x. 最后再处理剩下的直径的点.
int n;
vector<int> vct[200005];
int S=0,T=0,maxd=0,tag=0,typ=0;
int dis[2][200005];
int du[200005];
vector<array<int,3>> ans;
int sum=0;
queue<int> que;
void dfs1(int s,int d,int fa){ 求从s点出发,可以达到最远的点.if(d>maxd){if(!tag) S=s;else T=s;maxd=d;}for(auto v:vct[s]) if(v!=fa) dfs1(v,d+1,s);
}
void dfs2(int s,int d,int fa){ 从端点S/T出发到达其他点的距离dis[typ][s]=d;for(auto v:vct[s]) if(v!=fa) dfs2(v,d+1,s);
}
void process(int op){while(que.size()){int cur=que.front();que.pop();du[cur]--;if(op==1){if(dis[0][cur]>=dis[1][cur]) ans.emplace_back(array{S,cur,cur}),sum+=dis[0][cur];else ans.emplace_back(array{T,cur,cur}),sum+=dis[1][cur];}else if(op==2) ans.emplace_back(array{S,cur,cur}),sum+=dis[0][cur];for(auto v:vct[cur]) {du[v]--;if(du[v]==1) que.emplace(v);}}
}
题意:从树上选两个叶子节点，把他们的距离加到ans中，并且删去其中一个节点。求剩下一个点时的ans最大值。
Tree Destruction
https://www.luogu.com.cn/problem/CF911F
定理：在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。
第一次dfs1(),从任意一个点,到达的最远的点必然是直径两端的其中一个。
再从找到的端点开始dfs1(),找到另一个端点。这样就可以o(n)确定该树的直径.得到直径的端点S和T.
再两次dfs2(),分别得到S和T到达其他每个点的距离.
之后就可以从度为1的点x开始删除,每次都选和x更远的端点.并且删除x.
最后再处理剩下的直径的点.
void solve(){ 补B 选叶子 o(n)cin>>n;for(int i=1;i<=n-1;i++){int u,v; cin>>u>>v;vct[u].emplace_back(v);vct[v].emplace_back(u);du[u]++,du[v]++;}tag=0,maxd=0,dfs1(1,0,0);tag=1,maxd=0,dfs1(S,0,0);typ=0,dfs2(S,0,0);typ=1,dfs2(T,0,0);for(int i=1;i<=n;i++) if(du[i]==1&&i!=S&&i!=T) que.emplace(i);du[S]=0,du[T]=0;process(1);que.emplace(T);process(2);cout<<sum<<endl;for(auto a:ans) cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
}DivRem Number - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:
N%m=N-(N/m)*m 移项N=(m+1)*(N/m), 那么(m+1)是N的因子 , 那么枚举N的因子即可
题意:给定N,求满足(N/m)=N%m的m的总和. 除法全都是向下取整
DivRem Number
https://www.luogu.com.cn/problem/AT_diverta2019_d
N%m=N-(N/m)*m
移项N=(m+1)*(N/m), 那么(m+1)是N的因子 , 那么枚举N的因子即可
void solve(){ 补G o(sqrt(N))int N; cin>>N;int ans=0;for(int i=0;i<=sqrt(N);i++){if(N%(i+1)==0){ i是在枚举m的值,但是i不是因子,i+1才是因子int x=N/(i+1); 另一个因子if(i!=0&&N==(i+1)*(N/i)) ans+=i;if(x-1!=0&&N==x*(N/(x-1))) ans+=x-1; x=m+1,那么m=x-1.}}cout<<ans;
}Beautiful Mirrors - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:还是不懂。。
const int mod=998244353;
int quickpow(int a,int b){int res=1;while(b){if(b&1) res*=a,res%=mod;a*=a,a%=mod;b>>=1;}return res;
}
定义f[i]为到达第i天，并且第i天也快乐的期望天数.
思路:第i天询问失败，从头开始。此时概率为1-p，消耗天数为f[i-1]+1+f[i]。乘上概率，代价为(1-pi)(f[i-1]+1+f[i]).
第i天询问成功。此时概率为p，消耗天数为f[i-1]+1。乘上概率，代价为pi*(f[i-1]+1).
那么f[i]=pi*(f[i-1]+1)+(1-pi)(f[i-1]+1+f[i]).
整理有f[i]=( (f[i-1]+1) / (pi/100) ). 注意除法取mod用逆元.
此处解释,询问失败时消耗天数为 f[i-1]+1+f[i] 是因为：
当前要重新回到第i天，所以需要加f[i]. 而到达第i天之前需要先到达i-1天并且再+1才能回到第i天.
还是不懂。。为什么不用考虑回到i-2天然后加一天到达i-1天，然后再加一天回到第i天?i-3?i-4?..
官方题解: https://codeforces.com/blog/entry/71995
𝑒𝑖=1+𝑝𝑖⋅𝑒𝑖+1+(1−𝑝𝑖)⋅𝑒1 --ei为在第i个镜子前变得开心的预期天数.
Beautiful Mirrors
https://www.luogu.com.cn/problem/CF1265E
void solve(){ 补A 期望dp入门..int n; cin>>n;int cur=0;for(int i=1;i<=n;i++){int p; cin>>p;p*=quickpow(100,mod-2),p%=mod; p/100取mod的结果:p乘100的逆元cur=(cur+1)*quickpow(p,mod-2),cur%=mod; (cur+1)乘p的逆元}cout<<cur;
}Flat Subsequence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:这题赛时就秒了。
倒序遍历，如果当前数字是x，那么在[x-k,x+k]区间中找到最长的长度. o(nlogn)可以的 因为是倒序遍历，那么x点在区间中找到的点必然是x后面的。
#define lc p<<1
#define rc p<<1|1
const int N=300005;
typedef struct node{int p,l,r,maxn,tag; maxn是区间的最长长度是多少
}node;
node tr[4*N*2]; 开双倍，因为a+k=6e5
int n,k;
int arr[N];
void build(int p,int l,int r){tr[p]={p,l,r,0,0};if(l==r) return;int mid=(l+r)>>1;build(lc,l,mid);build(rc,mid+1,r);
}
void pushup(int p){tr[p].maxn=max(tr[lc].maxn,tr[rc].maxn);
}
void pushdown(int p){int tag=tr[p].tag;if(tag){tr[lc].maxn=max(tr[lc].maxn,tag);tr[rc].maxn=max(tr[rc].maxn,tag);tr[lc].tag=max(tr[lc].tag,tag);tr[rc].tag=max(tr[rc].tag,tag);tr[p].tag=0;}
}
void update(int p,int l,int r,int x){if(l<=tr[p].l&&r>=tr[p].r){tr[p].maxn=max(tr[p].maxn,x);tr[p].tag=max(tr[p].tag,x);return;}pushdown(p);int mid=(tr[p].l+tr[p].r)>>1;if(l<=mid) update(lc,l,r,x);if(r>mid) update(rc,l,r,x);pushup(p);
}
int query(int p,int l,int r){if(l<=tr[p].l&&r>=tr[p].r) return tr[p].maxn;pushdown(p);int res=0;int mid=(tr[p].l+tr[p].r)>>1;if(l<=mid) res=max(res,query(lc,l,r));if(r>mid) res=max(res,query(rc,l,r));return res;
}
H-有点 单调队列优化dp 的意思，但是有待斟酌..在遍历过的的数字中,找一个和当前差值满足条件的,并且是最长的。
线段树！倒序遍历，如果当前数字是x，那么在[x-k,x+k]区间中找到最长的长度. o(nlogn)可以的
因为是倒序遍历，那么x点在区间中找到的点必然是x后面的。
void solve(){ H 线段树--一发入魂！cin>>n>>k;int maxa=0;for(int i=1;i<=n;i++) {cin>>arr[i];maxa=max(maxa,arr[i]);}build(1,0,maxa+k);int ans=1;for(int i=n;i>=1;i--){int cur=query(1,max(0ll,arr[i]-k),arr[i]+k)+1;update(1,arr[i],arr[i],cur);ans=max(ans,cur);}cout<<ans;
}
