AtCoder Petrozavodsk Contest 001

发表于

链接

A B C D E F G H I J
$\color{green}{\texttt{+}}$ $\color{green}{\texttt{+5}}$ $\color{green}{\texttt{+}}$ $\color{green}{\texttt{+2}}$ $\color{red}{\texttt{+3}}$ $\color{red}{\texttt{+4}}$

C. Vacant Seat

题解

不妨假定 $0$ 位置答案是 $0$。每次询问 $x$，如果回答 $=x\bmod 2$，那么 $>x$ 范围一定有空位，否则 $<x$ 范围内一定有空位。

直接二分即可。对于 $0$ 位置是 $1$ 同理。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
char s[10];
int qry(int x)
{
	printf("%d\n",x);fflush(stdout);
	scanf("%s",s);
	if(s[0]=='V') exit(0);
	return s[0]=='M';
}
int main()
{
	int n;scanf("%d",&n);
	int x=qry(0);
	int l=0,r=n-1;
	while(r-l>3)
	{
		int mid=(l+r)>>1;
		if((qry(mid)^x)==(mid&1)) l=mid+1;
		else r=mid-1;
	}
	for(int i=l;i<=r;i++) qry(i);
	return 0;
}

D. Forest

题解

考虑还要连接 $n-m-1$ 条边，对应选出 $2(n-m-1)$ 个点。

显然每个连通块至少选一个点，此时一定选最小的。除此之外再从剩下点中选。如果不够选就是无解。

容易归纳证明这样永远存在一种方案使得每次连接的都是两个不同连通块的点。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 100010
using namespace std;
int f[N],a[N],g[N];
int find(int x){return x==f[x]?f[x]:(f[x]=find(f[x]));}
priority_queue<int,vector<int>,greater<int>>q;
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	int d=2*(n-m-1);
	if(d==0){puts("0");return 0;}
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),g[i]=i,f[i]=i;
	for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),++x,++y,f[find(x)]=find(y);
	for(int i=1;i<=n;i++) if(a[g[find(i)]]>a[i]) g[find(i)]=i;
	long long ans=0;
	for(int i=1;i<=n;i++) if(i==f[i]) ans+=a[g[i]],--d;
	for(int i=1;i<=n;i++) if(g[find(i)]!=i) q.push(a[i]);
	while(d --> 0)
	{
		if(q.empty()){puts("Impossible");return 0;}
		ans+=q.top(),q.pop();
	}
	printf("%lld\n",ans);
	return 0;
}

E. Antennas on Tree

题解

考虑一个结论：最后点集合法当且仅当以任意点为根时所有子树中至多只有一个子树没有选择任何一个点。充分性和必要性都比较显然。

由此可以推出最优策略只会选择叶子。

首先可以发现二度点不会造成任何影响，直接缩掉。然后可以发现相邻的若干个叶子（连接与同一个点的叶子）至多只有一个不选。不相邻的叶子因为它们路径上必然存在一个叶子被选了（因为二度点被缩了），所以不会有任何关系。

最后答案就是叶子个数减去有叶子相邻的节点个数。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define N 100010
using namespace std;
vector<int>g[N];
int deg[N];bool vis[N];
queue<int>q;
int main()
{
	int n;scanf("%d",&n);
	if(n==1){puts("0");return 0;}
	if(n==2){puts("1");return 0;}
	for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),++x,++y,g[x].push_back(y),g[y].push_back(x);
	for(int i=1;i<=n;i++) deg[i]=g[i].size();
	int s1=0,s2=0;
	for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i),++s1;
	while(!q.empty())
	{
		int u=q.front();vis[u]=true;q.pop();
//		printf("- %d\n",u);
		for(int v:g[u]) if(deg[v]>1)
		{
			--deg[v];
			if(deg[v]==1 && g[v].size()<=2) q.push(v);
		}
	}
	for(int i=1;i<=n;i++) if(g[i].size()!=deg[i] && !vis[i]) s2++;
	if(s2==0){puts("1");return 0;}
	printf("%d\n",s1-s2);
	return 0;
}

F. XOR Tree

题解

考虑链异或等价于两个端点处分别异或。令每个点的点权是它周围边权的异或和，容易发现以点 $u$ 为端点的所有链权值异或和恰好就是 $u$ 的点权。

这样处理之后相当于给定一个序列 $x_i$，每次可以选择两个位置异或某个值。考虑将 $x$ 分成尽可能多地可重集，每个可重集的元素异或和为 $0$，答案就是 $n$ 减去可重集个数。

显然 $0$ 单独划分为可重集，两个相同元素一定独自划分成可重集。最后还剩下不超过 $15$ 个元素，直接子集 dp 即可。复杂度 $O(3^{15}+n)$。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 100010
using namespace std;
int val[N],f[N];bool can[N];
int main()
{
	int n;scanf("%d",&n);
	for(int i=1,u,v,w;i<n;i++) scanf("%d%d%d",&u,&v,&w),++u,++v,val[u]^=w,val[v]^=w;
	for(int s=0;s<1<<16;s++) if(!(s&1))
	{
		int v=0;
		for(int i=1;i<16;i++)
			if(s>>i&1) v^=i;
		if(!v) can[s]=true;
	}
	int al=0,m=0;
	for(int i=1;i<=n;i++)
		if(val[i]) al^=1<<val[i],m++;
	int ct=__builtin_popcount(al);
	m=(m-ct)/2;
	for(int s=1;s<=al;s++) if(can[s])
	{
		f[s]=1;
		for(int t=s&(s-1);t;t=(t-1)&s) if(can[t])
			f[s]=max(f[s],f[s^t]+1);
	}
	printf("%d",m+ct-f[al]);
	return 0;
}

G. Colorful Doors

题解

首先考虑全 $1$ 的情况怎么处理：容易发现当 $n$ 为偶数时可以每 $4$ 个 $1$ 划分一段，每段填 1 2 1 2 即可。而 $n$ 是奇数时则不行。

考虑如何证明 $n$ 是奇数时无解：假设我们令每个位置指向下一个位置，即 $1\rightarrow 2\rightarrow 3\cdots$，特别的 $2n\rightarrow 1$。显然这构成一个置换，不妨用 $p_i$ 表示。

每次加入一个传送门的过程等价于交换和 $p_i$ 和 $p_j$ 的权值。最后全部为 $1$ 等价于最后只有一个大环，但是当 $n$ 是奇数时意味着逆序对奇偶性会改变，而偶环个数奇偶性与逆序对奇偶性相同，所以最后一定不会构成一个大环，也就不可能全是 $1$。

考虑扩展。首先可以发现如果一个传送门左右经过的状态为 0|1，那么另一个一定是 1|0。如果一个传送门左右都是 $0$，那么另一个也必须是。所以我们可以把所有 0|0 状态的传送门找出来，两两随意匹配，然后可以认为这两个 0 合并了。

对于 1|0|1 状态的情况，可以直接让两个传送门匹配实现这一效果。但后果是最后 1 的个数可能不匹配。考虑如果只有一个 1|0|1 只能直接匹配，而如果有 1|0|1...1|0|1，我们可以在四个位置填 1 2 2 1，然后在外部设置一个传送门到内部，可以发现我们让置换的奇偶性改变了，所以两种方式中一定有一种方案让最后剩下的 1 个数为 $4$ 的倍数。

最后特别的，如果出现 1|0|1|0|1 的状态，容易证明内部的 $0$ 无法互相匹配，所以只能当做 1|0|1 处理。

复杂度 $O(n)$。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 200010
using namespace std;
char s[N];
int a[N],res[N],pos[N],cnt,m;
void add(int x,int y)
{
    while(res[x]) x--;
    while(res[y]) y++;
    pos[x]=y;pos[y]=x;
    res[x]=res[y]=cnt--;
}
void do_last()
{
    vector<int>tmp;
    int p1=0,p2=0;
    for(int i=1;i<=m;i++){tmp.push_back(i);if(pos[i]) i=pos[i];}
    // for(int i=1;i<=m;i++) printf("%d ",res[i]);puts("");
    // for(int i:tmp) printf("%d ",i);
    for(int i:tmp) if(!res[i])
    {
        if(!p1 && !p2) p1=i;
        else if(!p2) p2=i;
        else if(!p1) add(p2,i),p2=0;
        else add(p1,i),p1=0;
    }
}
int main()
{
    int n;scanf("%d%s",&n,s+1);cnt=n;
    m=n*2;
    for(int i=1;i<m;i++) a[i]=s[i]-'0';
    a[0]=a[m]=1;
    int c=0;
    for(int i=1;i<m;i++) if(!a[i] && !a[i+1]) ++c;
    if(c&1){puts("No");return 0;}
    for(int i=1,p=0;i<m;i++) if(!a[i] && !a[i+1]){if(p) add(p,i+1),p=0;else p=i+1;}
    for(int i=1,p=0;i<m-2;i++) if(!a[i] && a[i+1] && !a[i+2]) add(i+2,i+3);
    int tt=0;
    for(int i=1;i<m;i++) if(!a[i] && a[i+1] && !res[i+1]) ++tt;
    if(tt<=1 || (cnt-tt)%2==0)
    {
        for(int i=1;i<=m;i++) if(!a[i] && a[i+1] && !res[i+1]) add(i,i+1);
        if(cnt&1){puts("No");return 0;}
        do_last();
    }
    else
    {
        int s1=0,s2=0;
        for(int i=1;i<=m;i++) if(!a[i] && a[i+1] && !res[i+1])
        {
            if(!s1) s1=i;
            else if(!s2) s2=i;
            else add(i,i+1);
        }
        add(s1,s2+1),add(s2,s1+1);
        bool ca=false;
        for(int i=1;i<=m;i++)
            if(!res[i] && (i<s1 || i>s2)){ca=true;add(i,s1+2);break;}
        if(!ca){puts("No");return 0;}
        do_last();
    }
    puts("Yes");
    for(int i=1;i<=m;i++) printf("%d ",res[i]);
    return 0;
}

H. Generalized Insertion Sort

题解

容易发现如果是一条以 $0$ 为端点的链，直接贪心将 $0$ 节点的值往后面用类似插入排序的方式插入即可做到 $O(n)$。

然后考虑如果是一个毛毛虫（一条链的每个点挂了若干叶子），考虑如果 $0$ 处的值是某个叶子的，直接往那个叶子上扔，否则往链另一端扔。容易发现这样经过 $O(n)$ 次操作可以处理所有叶子的值，然后再花 $O(n)$ 处理主链。

如果是一个大毛毛虫（一条主链上挂了若干链），考虑如果 $0$ 处的值是某个副链的，用类似插入排序处理，否则找到最深的属于某个副链的点插入。容易发现第二种操作对每个点至多进行一次，所以仍然是 $O(n)$ 次操作。

对于一般情况，考虑每次取出所有叶子以及其上方的所有二度点塞入集合 $S$，全部一起处理。如果 $0$ 处的值是某个副链的，用类似插入排序处理，否则找到最深的属于 $S$ 的点插入。容易分析得到这样一次操作是 $O(n)$ 的。而设 $F(n)$ 表示上述操作需要执行 $n$ 次的树大小最小值，容易发现 $F(n)=2F(n-1)+1$，此时是一个满二叉树。所以总操作次数是 $O(n\log n)$。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define N 2010
using namespace std;
int fa[N],deg[N],a[N],dep[N];
vector<int>ans;
void turn(int x)
{
    ans.push_back(x);
    int p=a[1];
    for(int y=x;y;y=fa[y]) swap(a[y],p);
}
bool fi[N];
int vis[N],n;
vector<int>p[N];int ed[N],pt;
void init()
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=pt;i++) p[i].clear();
    pt=0;
    for(int i=1;i<=n;i++) if(!deg[i] && !fi[i])
    {
        ++pt;
        p[pt].push_back(i);vis[i]=pt;
        for(int u=fa[i];deg[u]==1;u=fa[u]) p[pt].push_back(u),vis[u]=pt;
        reverse(p[pt].begin(),p[pt].end());
        ed[pt]=p[pt].back();
    }
    for(int i=1;i<=pt;i++)
        for(int u:p[i]) if(fa[u]) deg[fa[u]]--;
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d",&fa[i]),fa[i]++,deg[fa[i]]++;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),++a[i];
    for(int i=2;i<=n;i++) dep[i]=dep[fa[i]]+1;
    while(!vis[1])
    {
        init();
        while(true)
        {
            if(vis[a[1]])
            {
                int x=vis[a[1]],u=p[x].back();
                if(!ed[x]) break;
                while(u!=ed[x] && a[u]>a[1]) u=fa[u];
                turn(u);fi[ed[x]]=true;ed[x]=fa[ed[x]];
            }
            else
            {
                int u=0;
                for(int i=1;i<=n;i++) if(vis[a[i]] && !fi[i] && dep[i]>dep[u]) u=i;
                if(!u) break;
                turn(u);
            }
        }
    }
    for(int i=1;i<=n;i++) if(a[i]!=i) throw;
    printf("%d\n",(int)ans.size());
    for(int u:ans) printf("%d\n",u-1);
    return 0;
}