AtCoder Beginner Contest 362 补题
E - Count Arithmetic Subsequences
题目大意
求出在序列 \(a_1,a_2,\cdots,a_n\) 中所有长度为 \(k\in[1,n]\) 的非连续等差子序列数量，对 \(998244353\) 取模。
\(1\leq n\leq 80\)
思路
设 \(f_{i,k,v}\) 表示以 \(i\) 结尾长度为 \(k\) 的差为 \(v\) 的子序列数量。则枚举 \(j\) 确定差，则 \(v=a_i-a_j\)。于是可以转移：
\[f_{i,k,v}=\sum_{j=2}^{i-1}f_{j,k-1,a_i-a_j}
\]
其中推一下 \(k\leq 2\) 的情况设为边界即可。
代码
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const ll MAXN=80+5;
const ll MOD=998244353;
ll n,a[MAXN];
map<ll,ll>dp[MAXN][MAXN];
ll ans[MAXN];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
dp[i][1][0]=1;
for(int j=1;j<i;++j){
dp[i][2][a[i]-a[j]]++;
}
ans[1]++;
ans[2]+=i-1;
ans[2]%=MOD;
}
for(int k=3;k<=n;++k){
for(int i=3;i<=n;++i){
for(int j=i-1;j>=2;--j){
dp[i][k][a[i]-a[j]]+=dp[j][k-1][a[i]-a[j]]%MOD;
dp[i][k][a[i]-a[j]]%=MOD;
ans[k]+=dp[j][k-1][a[i]-a[j]]%MOD;
ans[k]%=MOD;
}
}
}
for(int i=1;i<=n;++i){
cout<<ans[i]<<" ";
}
return 0;
}
F - Perfect Matching on a Tree
题目大意
给出一个节点个数为 \(n\) 的树，将它分成 \(\lfloor\frac{n}{2}\rfloor\) 个点对，使得点对的距离之和最大，输出一组可行的方案。
\(2\leq n \leq2\times10^5\)
思路
直接这么做显然是不好的，可以考虑转成一条边的贡献。设以 \(u\) 为根的字数大小 \(s_u\)。则对于点对和可以转化成
\[\sum_{i=1}^{n-1} \min(s_{u_i},n-s_{u_i})
\]
那么为了让它最大我们希望让每一个子树大小平均，自然选择重心即可。这样的话我们输出方案就可以随便连，只要不在同一颗子树即可。那就按子树顺序放进一个序列 \(a\) 里，然后根如果 \(n\) 为奇就不选，否则放进最初或最后随便匹配一下即可。之后按顺序输出 \((a_i,a_{i+\lfloor\frac{n}{2}\rfloor})\)
代码
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const ll MAXN=2e5+5;
vector<ll>adj[MAXN];
ll n;
ll sz[MAXN],core,num;
void dfs(ll u,ll fa){
sz[u]=1;
ll val=-1e18;
for(auto v:adj[u]){
if(v==fa){
continue;
}
dfs(v,u);
val=max(val,sz[v]);
sz[u]+=sz[v];
}
val=max(val,n-sz[u]);
if(val<num){
num=val;
core=u;
}
}
ll a[MAXN],tot;
void ga(ll u,ll fa){
if(u!=core){
a[++tot]=u;
}
for(auto v:adj[u]){
if(v==fa){
continue;
}
ga(v,u);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
num=1e18;
for(int i=1;i<n;++i){
ll u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,0);
if(!(n&1)){
a[++tot]=core;
}
ga(core,0);
for(int i=1;i<=n/2;++i){
cout<<a[i]<<" "<<a[i+n/2]<<endl;
}
return 0;
}