0+100+0，这也没啥好说的了，反正就差的一批吧……
\(T1\) \(Hunter\)
简单数论题，但 \(lyh\) 从来没有在考试的时候 \(A\) 过数论题。
考虑第一个人挂的时间 \(=\) 其他人比第一个人早挂的概率。
对于第 \(i\) 个人，简化问题，只留第一个人和第 \(i\) 个人，答案就是 \(\dfrac{w_i}{w_1+w_i}\)。
时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=998244353;
int n,w1,ans=1;
int qpow(int x,int y){int re=1;while(y){if(y&1) re=re*x%p;x=x*x%p,y>>=1;}return re;
}signed main(){freopen("hunter.in","r",stdin);freopen("hunter.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>w1;for(int i=2,w;i<=n;i++)cin>>w,ans=(ans+w*qpow(w+w1,p-2))%p;cout<<ans;return 0;
}
\(T2\) \(Defence\)
思维难度最低的。
很容易想到答案与最大的空缺长度有关，可以通过左移/右移完成，每次最大空缺长度 \(-1\)，所以答案就是最大的空缺长度。
但是有一个 \(bug\)，就是极左/极右两个区间，这时左移/右移就有了区别。可以看作一个环，所以这两个区间合并起来的长度还要和最大空缺长度取一个 \(\max\)。
合并字数信息想到线段树合并和 \(dsu\ on\ tree+set\)。前者 \(O(n\log n)\)，后者 \(O(n\log^2n)\)。本人考场选择了第二种方案（因为好想）。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
struct kl{int l,r;int f(){return r-l-1;}friend bool operator<(kl x,kl y){if(x.f()!=y.f()) return x.f()>y.f();return x.l<y.l;}
};set<kl>st[N];
int n,m,qu,ans[N],mn[N],mx[N];
set<int>q[N];vector<int>g[N];
void add(int x,int ad){if(q[x].count(ad)) return;auto it=q[x].lower_bound(ad);int r=(*it),l=(*(--it));st[x].erase({l,r});st[x].insert({l,ad});st[x].insert({ad,r});q[x].insert(ad);
}inline void dsu(int x){int sn=x,ms=st[x].size();for(auto y:g[x]){dsu(y),mn[x]=min(mn[x],mn[y]);mx[x]=max(mx[x],mx[y]);if(st[y].size()>ms)sn=y,ms=st[y].size();}if(mn[x]>m) return ans[x]=-1,void();swap(st[x],st[sn]),swap(q[x],q[sn]);for(auto y:g[x]){st[y].erase(st[y].begin(),st[y].end());while(q[y].size()){int now=(*q[y].begin());q[y].erase(now),add(x,now);}}kl c=(*st[x].begin());ans[x]=max(m-mx[x]+mn[x]-1,c.f());
}signed main(){freopen("defence.in","r",stdin);freopen("defence.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m>>qu;for(int i=1,u,v;i<n;i++)cin>>u>>v,g[u].push_back(v);for(int i=1;i<=n;i++){st[i].insert({0,m+1});q[i].insert(0),q[i].insert(m+1);mn[i]=m+1,mx[i]=0;}while(qu--){int u,p;cin>>u>>p,add(u,p);mx[u]=max(mx[u],p),mn[u]=min(mn[u],p);}dsu(1);for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";return 0;
}
\(T3\) \(Connect\)
好题好题。
考虑到最终形态一定是一条链上每个点挂一个点集，所以我们可以枚举链，然后再挂点集。
设 \(dp_{s,i}\) 表示目前已选集合为 \(s\)，链尾为 \(i\)，则转移方程为：
-
\(dp_{s\cup t,i}=\max(dp_{s\cup t,i},dp_{s,i}+calc(\{i\}\cup t))\)，其中\(calc(s)\) 表示集合 \(s\) 中的所有点间的边长和，保证 \(s\cap t=\emptyset\)。
-
\(dp_{s\cup\{i\},i}=\max(dp_{s\cup\{i\},i},dp_{s,j}+dis_{i,j})\)，其中 \(dis_{i,j}\) 表示 \(i,j\) 间边的长度，保证 \(i,j\) 间必须有边且 \(s\cap\{j\}=\{j\}\) 且 \(s\cap\{i\}=\emptyset\)。
时间复杂度 \(O(3^{(n-1)}n^2)\)，提前预处理，可以达到 \(O(3^{(n-1)}+2^nn^2)\)，可以通过。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20,M=1<<15;
int n,m,a[N],d[N][N],dat;
int dp[M][N],calc[M],ans;
void check(int s,int k){calc[s]=0;for(int i=1;i<=k;i++)for(int j=i+1;j<=k;j++)if(d[a[i]][a[j]]>0)calc[s]+=d[a[i]][a[j]];
}void dfs(int x,int s,int k){if(x>n) return check(s,k);dfs(x+1,s,k),a[k+1]=x;dfs(x+1,s|(1<<(x-1)),k+1);
}signed main(){freopen("connect.in","r",stdin);freopen("connect.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;memset(d,-0x3f,sizeof(d));memset(calc,-0x3f,sizeof(calc));memset(dp,-0x3f,sizeof(dp));for(int i=1,x,y,w;i<=m;i++)cin>>x>>y>>w,d[x][y]=d[y][x]=w,dat+=w;dfs(1,0,0),dp[1][1]=0;for(int s=3;s<(1<<n);s+=2)for(int i=1;i<=n;i++){if(!((s>>(i-1))&1)) continue;for(int t=((s-1)&s);t;t=((t-1)&s))dp[s][i]=max(dp[s][i],dp[t][i]+calc[(1<<(i-1))|(s^t)]);for(int j=1;j<=n;j++) if((s>>(j-1))%2&&d[i][j]>0)dp[s][i]=max(dp[s][i],dp[s^(1<<(i-1))][j]+d[i][j]);}cout<<dat-dp[(1<<n)-1][n];return 0;
}
