跳到主要内容

COCI2017/2018 部分题目题解2

修改
· 阅读需 7 分钟
laieahoy
laieahoy
管理员

A. Alkemija​

这道题需要注意的一点是替换的顺序不定，所以可以先做一些替换，得到一些原材料，再重新去合成，所以这就是一道很明显的拓扑序的题目，但建图的时候需要运用一些技巧，可以将某个替换需要的原材料与这个替换点连边（但是要 +n+n），再将改点与替换后的点连边，这样再去判拓扑序，如果某点没有入边了，这个点就是可以在最终集合中的。

Details

点击展开代码 代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;

const int N=1e5+5;
int n,m,k;
int a[N],ans[N],cnt,in[N<<1];
vector<int> g[N<<1];

void bfs()
{
	queue<int> q;
	for(int i=1;i<=m;i++) q.push(a[i]);
	while(q.size()){
		int t=q.front();
		q.pop();
		for(int i:g[t]){
			if(!(--in[i])){
				q.push(i);
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	cin>>k;
	for(int i=1;i<=k;i++){
		int l,r;
		cin>>l>>r;
		for(int j=1,x;j<=l;j++) cin>>x,g[x].push_back(n+i);
		in[n+i]=l;
		for(int j=1,x;j<=r;j++) cin>>x,g[n+i].push_back(x);
	}
	for(int i=1;i<=n;i++) in[i]=1;
	for(int i=1;i<=m;i++) in[a[i]]=0;
	bfs();
	for(int i=1;i<=n;i++){
		if(in[i]<=0) ans[i]=1,cnt++;
	}
	cout<<cnt<<"\n";
	for(int i=1;i<=n;i++){
		if(ans[i]) cout<<i<<" ";
	}

	return 0;
}

C. Vođe​

很明显可以看出是一道博弈论题，设 dp[i][j]dp[i][j] 表示：轮到第 ii 个人操作，且还剩 jj 个石子时，第 ii 个人所在的队伍是否能够获胜。现在考虑转移：

  • 若 a[i]==a[nexti]a[i]==a[next_i]，说明当前位置的动物与下一位置的是同一阵营，那么当 dp[next_i][j-1\~ j-k] 中有 11 时，dp[i][j]=1dp[i][j]=1;
  • 若 a[i]!=a[nexti]a[i]!=a[next_i]，说明当前位置的动物与下一位置的不是同一阵营，那么当 dp[next_i][j-1\~ j-k] 中没有 11 时，dp[i][j]=1dp[i][j]=1。 但这样的转移太慢了，大概能达到 O(NM2)O(NM^2) 级别，所以需要优化，我们发现，dp 的转移用到了同一个 ii 的一段连续区间，这就让我们想到了前缀和，维护一个 s[i][j]s[i][j] 表示 ∑t=1jdp[i][t]\sum_{t=1}^j dp[i][t]，于是：
  • 如果 nextinext_i 与 ii 同队，那 snext,j−1−snext,j−k−1>0s_{next,j-1}-s_{next,j-k-1}>0 则 dp[i][j]dp[i][j] 为 11；
  • 如果 nextinext_i 与 ii 异队，那 snext,j−1−snext,j−k−1<ks_{next,j-1}-s_{next,j-k-1}<k 则 dp[i][j]dp[i][j] 为 11。

注意 j−k−1j−k−1 可能为 −1−1，所以要将 ss 的下标移一位。

Details

点击展开代码 代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N=5005;
int n,m,k;
int a[N];
int dp[N][N],s[N][N];

int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) dp[i][0]=0;
	for(int j=1;j<m;j++){
		for(int i=1;i<=n;i++){
			int lim=min(j,k);
			if(a[i]==a[i%n+1]){
				dp[i][j]=(s[i%n+1][j]>s[i%n+1][j-lim]);
			}else{
				dp[i][j]=(lim+s[i%n+1][j-lim]>s[i%n+1][j]);
			}
			s[i][j+1]=s[i][j]+dp[i][j];
		}
	}
	for(int i=1;i<=n;i++) cout<<(dp[i][m-1]?a[i]:!a[i])<<" ";

	return 0;
}

D. Pictionary​

先转化一下题意，题目是将 gcd(a,b)=m−i+1gcd(a,b)=m-i+1 的点 a,ba,b 连边，根据 gcdgcd 的特性，可以转化为在第 day=m−d+1day=m−d+1 天（对应 dd 从 mm 递减到 11）将城市 dd 与其倍数 2d,3d,\ldot,≤n2d,3d,\ldot,\le n 依次连接。询问的是给定两点最早连通的天数。由于天数随 dd 的递减而单调递增，求两点最早连通时刻本质上等价于求加边过程中两点首次处于同一连通块时的边权。

可以通过构建 Kruskal 重构树 来解决。按天数从早到晚的顺序合并城市 dd 与其倍数所在的连通块。每次合并两个不同连通块时，新建一个重构树节点，将其点权设为当前天数 dayday，并将原先两连通块的代表元节点作为该新节点的左右儿子。利用并查集维护连通性，注意并查集的路径压缩仅用于查找代表元，重构树本身的父子关系需要用单独的数组保存。建树完成后，两城市 a,ba,b 最早连通的天数即为它们在重构树上最近公共祖先（LCA）的点权。

Details

点击展开代码 代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N=200005,LOG=19;
int n,m,q,tot;
int dsu[N],fa[N],ch[N][2],val[N],dep[N],dfn[N],seq[N];
int timer,st[N][LOG],lg[N];

int find(int x) {return dsu[x]==x?x:dsu[x]=find(dsu[x]);}

void merge(int x,int y,int day)
{
    x=find(x);y=find(y);
    if(x==y)return;
    ++tot;val[tot]=day;
    ch[tot][0]=x;ch[tot][1]=y;
    fa[x]=fa[y]=tot;
    dsu[x]=dsu[y]=dsu[tot]=tot;
}

void dfs(int u,int p)
{
    dep[u]=dep[p]+1;
    dfn[u]=++timer;
    seq[timer]=u;
    if(ch[u][0])dfs(ch[u][0],u);
    if(ch[u][1])dfs(ch[u][1],u);
}

void build()
{
    for(int i=2;i<=timer;++i)lg[i]=lg[i>>1]+1;
    for(int i=1;i<=timer;++i)st[i][0]=seq[i];
    for(int j=1;(1<<j)<=timer;++j)
        for(int i=1;i+(1<<j)-1<=timer;++i){
            int x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];
            st[i][j]=dep[x]<dep[y]?x:y;
        }
}

int lca(int x,int y)
{
    if(x==y)return x;
    if(dfn[x]>dfn[y])swap(x,y);
    int l=dfn[x]+1,r=dfn[y],k=lg[r-l+1];
    int a=st[l][k],b=st[r-(1<<k)+1][k];
    return fa[dep[a]<dep[b]?a:b];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>q;
    tot=n;
    for(int i=1;i<=2*n;i++) dsu[i]=i;
    for(int d=m;d;d--){
        int day=m-d+1;
        for(int x=d+d;x<=n;x+=d)merge(d,x,day);
    }
    dfs(find(1),0);
    build();
    while(q--){
        int x,y;
        cin>>x>>y;
        cout<<val[lca(x,y)]<<'\n';
    }

	return 0;
}