临时起意加塞
rnk20，\(20+0+10=30\)。
T1 Hunter
25pts 的暴搜是考场上写出来的。但少取模，挂了。
45pts 的状压是可惜的，实际上把暴搜改成记搜很容易解决。设 \(\text{dfs}(t,s)\) 表示第 \(t\) 轮、状态为 \(s\) 时的结果，然后记搜就容易。
正解很神奇。因为 1 号死亡的轮数等于在 1 号之前死亡的人数 \(+1\)，由于期望的线性性，就等于每个猎人在 1 号猎人之前死亡的概率之和（因为每死一个就有 \(1\) 的贡献，所以概率就是期望），而每个猎人比 1 号猎人先死的概率为 \(\dfrac{w_i}{w_1+w_i}\)，所以最终答案就是
\[\mathit{ans}=\left(\sum_{i=2}^n\frac{w_i}{w_1+w_i}\right)+1 \]不需要考虑别人的死法，因为这个 \(i\) 具有一般性。
感觉还是在于对期望的理解。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define int long long
#define inv(x) power(x,MOD-2)
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
constexpr int MAXN=1e5+5,MOD=998244353;
int n,w[MAXN],ans;
int power(int a,int b){
int res=1;
for(;b;a=a*a%MOD,b>>=1)if(b&1)res=res*a%MOD;
return res;
}
void add(int&x,int y){
x=x+y>=MOD?x+y-MOD:x+y;
}
signed main(){
freopen("hunter.in","r",stdin);
freopen("hunter.out","w",stdout);
n=read();
for(int i=1;i<=n;++i)w[i]=read();
for(int i=2;i<=n;++i)add(ans,w[i]*inv(w[1]+w[i])%MOD);
return write(ans+1),fw,0;
}
T2 Defence
思路对了，没调出来。
不难发现对于每个节点答案就是 \(\max(\text{区间中最长的 }\texttt 0,\text{左右两端的 }\texttt0\text{ 之和})\)。最终答案输出 \(\texttt{-1}\) 当且仅当这个节点没有 \(\texttt1\)。
所以就是一个线段树合并维护，每个节点维护当前区间最左的 \(\texttt1\)、最右的 \(\texttt1\)、最长的 \(\texttt0\) 串长。pushup 也很典型。最后用一个 DFS 把沿途的节点都合并上来，如果当前节点没有开就是 \(\texttt{-1}\)，否则是刚才说的统计答案。注意线段树合并的空间要开够。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define lp st[p].ls
#define rp st[p].rs
#define mid ((l+r)>>1)
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
constexpr int MAXN=1e5+5;
int n,m,q,rt[MAXN],ans[MAXN];
int head[MAXN],tot,tot2;
struct{int v,nxt;}e[MAXN];
void addedge(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
struct SegTree{
int ls,rs;
int mn,mx,dis;
}st[MAXN<<5];
void pushup(int p){
if(!lp){
st[p].mn=st[rp].mn;
st[p].mx=st[rp].mx;
st[p].dis=st[rp].dis;
}else if(!rp){
st[p].mn=st[lp].mn;
st[p].mx=st[lp].mx;
st[p].dis=st[lp].dis;
}else{
st[p].mn=st[lp].mn;
st[p].mx=st[rp].mx;
st[p].dis=max({st[lp].dis,st[rp].dis,st[rp].mn-st[lp].mx});
}
}
void insert(int l,int r,int k,int&p){
if(!p)p=++tot2;
if(l==r){
st[p].mx=st[p].mn=k;
st[p].dis=0;
return;
}
if(k<=mid)insert(l,mid,k,lp);
else insert(mid+1,r,k,rp);
pushup(p);
}
int combine(int x,int y,int l,int r){
if(!x||!y)return x+y;
if(l==r)return x;
st[x].ls=combine(st[x].ls,st[y].ls,l,mid);
st[x].rs=combine(st[x].rs,st[y].rs,mid+1,r);
pushup(x);
return x;
}
void dfs(int u){
for(int i=head[u];i;i=e[i].nxt){
dfs(e[i].v);
rt[u]=combine(rt[u],rt[e[i].v],1,m);
}
if(!rt[u])ans[u]=-1;
else ans[u]=max(m-st[rt[u]].mx+st[rt[u]].mn-1,st[rt[u]].dis-1);
}
int main(){
freopen("defence.in","r",stdin);
freopen("defence.out","w",stdout);
n=read(),m=read(),q=read();
for(int i=1,u,v;i<n;++i){
u=read(),v=read();
addedge(u,v);
}
for(int i=1,u,p;i<=q;++i){
u=read(),p=read();
insert(1,m,p,rt[u]);
}
dfs(1);
for(int i=1;i<=n;++i)write(ans[i]);
return fw,0;
}
T3 Connect
20pts 乱搞。
注意到 \(1\) 到 \(N\) 的路径唯一当且仅当存在一条 \(1\) 到 \(N\) 的链，且不在链上的连通块最多只和链上的一个点有连边。于是设 \(\mathit{dp}_{s,i}\) 表示当前点集为 \(s\)，\(1\) 到 \(N\) 的链的结尾为 \(i\)。我们并不需要考虑 \(\boldsymbol i\) 是否能在这个链上。然后有两种情况：
-
将当前端点和其他点集中的任意点连边。
-
将当前链再扩张一个端点 \(j\)，使结尾变为 \(j\)。
我们不用考虑结尾为 \(i\) 的情况，因为那种情况已经考虑过了。第一种情况也是同理，其他点集和这条链上其他点连边的情况也考虑过了。最终就是一个短小精悍的状压 DP。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define uid uniform_int_distribution
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
constexpr int MAXN=16;
int n,m,sum[(1<<15)+5],dis[MAXN][MAXN];
int dp[(1<<15)+5][16],val[(1<<15)+5][16];
int main(){
freopen("connect.in","r",stdin);
freopen("connect.out","w",stdout);
n=read(),m=read();
for(int i=1,u,v,w;i<=m;++i){
u=read(),v=read(),w=read();
dis[u][v]=dis[v][u]=w;
}
for(int s=1;s<1<<n;++s)
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
if(s&(1<<(i-1))&&s&(1<<(j-1)))
sum[s]+=dis[i][j];
for(int s=1;s<1<<n;++s)
for(int i=1;i<=n;++i)
if(!(s&(1<<(i-1))))
for(int j=1;j<=n;++j)
if(s&(1<<(j-1))&&dis[i][j])
val[s][i]+=dis[i][j];
memset(dp,-1,sizeof(dp));
dp[1][1]=0;
for(int s=1;s<1<<n;++s)
for(int i=1;i<=n;++i){
if(!~dp[s][i])continue;
for(int j=1;j<=n;++j){
if(s&(1<<(j-1))||!dis[i][j])continue;
dp[s|(1<<(j-1))][j]=max(dp[s|(1<<(j-1))][j],dp[s][i]+dis[i][j]);
}
int tmp=s^((1<<n)-1);
for(int j=tmp;j;j=(j-1)&tmp)
dp[s|j][i]=max(dp[s|j][i],dp[s][i]+val[j][i]+sum[j]);
}
return write(sum[(1<<n)-1]-dp[(1<<n)-1][n]),fw,0;
}