9.5 上午 becoder 模拟赛总结 & 题解

T1 文本编辑器

说实话，看到题目的第一瞬间，我还以为 gm 第一道就放了平衡树。

一道链表的模板题，当然愿意也可以用平衡树写，不多说了，直接放代码(100pts)：

#define N 1000005
char s[N],t[N];
int now,pre[N],nxt[N];
int main(){
    scanf("%s%s",s+1,t+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++){
        if(t[i-1]=='L')
            nxt[pre[now]]=i,nxt[i]=now,pre[i]=pre[now],pre[now]=i,now=i;
        else
            pre[nxt[now]]=i,nxt[i]=nxt[now],pre[i]=now,nxt[now]=i,now=i;
        pre[0]=nxt[0]=0;
    }
    while(pre[now])  now=pre[now];
    for(int i=1;i<=n;i++)  printf("%c",s[now]),now=nxt[now];
}

T2 便利店

因为所有边的边权都是 \(1\)，所以我们的单源最短路就可以直接 \(O(m)\) 用广搜实现。

那题目就简单了，对于每个询问，先跑一次最短路，用一个 vector 存储每个点的最短路径可以从哪些点走过来，记为 \(pre\)。

然后就从终点 dfs 回去，将每个点的 \(pre\) 与它连边，这样我们连的所有边就都是最短路径上的了。

最后再从起点 dfs 一遍，求每个点的概率就行了，就典型的概率 DP，不做赘述。

时间复杂度 \(O(km)\)，代码如下(100pts)：

#define N 5005
bool vis[N];
queue<int> q;
double now[N],sum[N];
int n,m,k,num,d[N],rd[N];
vector<int> v[N],pre[N],nxt[N];
void bfs(int s){
    memset(d,0x3f,sizeof d),d[s]=0,q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(auto y:v[x]){
            if(d[y]==0x3f3f3f3f)  d[y]=d[x]+1,q.push(y);
            if(d[y]==d[x]+1)  pre[y].push_back(x);
        }
    }
}
void dfs1(int x){
    if(vis[x])  return;
    vis[x]=1;
    for(auto y:pre[x])  nxt[y].push_back(x),dfs1(y);
}
void dfs2(int x){
    for(auto y:nxt[x]){
        now[y]+=now[x]/nxt[x].size();
        if(++rd[y]==pre[y].size())  dfs2(y);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y),x++,y++;
        v[x].push_back(y),v[y].push_back(x);
    }
    scanf("%d",&k);
    for(int i=1,x,y;i<=k;i++){
        memset(vis,0,sizeof vis),memset(now,0,sizeof now);
        memset(rd,0,sizeof rd),scanf("%d%d",&x,&y);
        x++,y++,bfs(x),dfs1(y),now[x]=1,dfs2(x);
        for(int i=1;i<=n;i++)  pre[i].clear(),nxt[i].clear(),sum[i]+=now[i];
    }
    for(int i=1;i<=n;i++)  if(sum[i]>sum[num])  num=i;
    printf("%d\n",num-1);
}

T3 独立集

考虑状压 DP，设 \(dp_msk\) 表示 \(msk\) 的子集内独立集的数目，转移时从 \(msk\) 中任选一个元素 \(i\) 出来。

那么转移有两种情况：

第一种情况是 \(i\) 不在独立集中，那么 \(i\) 号点就不会影响其他的点，这个时候从 \(dp_{msk^(1<<i)}\) 转移过来。

第二种情况是 \(i\) 点在独立集中，这时就要求它的邻居都不在独立集中。

设 \(nei_i\) 表示 \(i\) 自己与邻居的集合，这个时候就从 \(dp_{msk^(msk \& nei_i)}\) 转移过来。

转移就是这样，代码如下(100pts)：

#define LL long long
const LL mod=1e9+7;
int n,m,ans,nei[26],dp[1<<26];
int main(){
	scanf("%d%d",&n,&m),dp[0]=1;
	for(int i=0;i<n;i++)  nei[i]|=(1<<i);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		nei[x]|=(1<<y),nei[y]|=(1<<x);
	}
	for(int i=1;i<(1<<n);i++)
		for(int j=0;j<n;j++)
			if(i&(1<<j))
				{dp[i]=((LL)dp[i]+dp[i^(1<<j)]+dp[i^(i&nei[j])])%mod;break;}
	for(LL i=1,po=233;i<(1<<n);i++,po=po*233%mod)  ans=(ans+po*dp[i])%mod;
	printf("%d\n",(ans+1)%mod);
}

T4 粉刷匠

我的做法被卡了，等我过了再来写...