CF R967 (CF2001) VP记录

2024年08月30日 CF补全计划约1.6k字预计需要6分钟

solved（3/6）

CF2001A Make All Equal

题意

您将得到一个循环数组 $a_1, a_2, \ldots, a_n$ 。您最多可以对 $a$ 执行 $n - 1$ 次以下操作：

设 $m$ 为 $a$ 的当前大小，您可以选择任意两个相邻的元素，其中前一个元素不大于后一个元素(特别是， $a_m$ 和 $a _1$ 是相邻的， $a_m$ 是前一个)，并只删除其中一个。换句话说，选择一个整数 $i$ ( $1 \leq i \leq m$ )其中 $a_i \leq a_{(i \bmod m) + 1}$ 成立，并从 $a$ 中删除 $a_i$ 或 $a_{(i \bmod m) + 1}$ 中的一个。

您的目标是找到使 $a$ 中的所有元素相等所需的最少操作数。

思路

这个真的很简单，我们考虑有一个数，如果他前面的数比他小，那么就可以直接删去，如果比它大就继续向前看。

我们会发现，无论如何我们都可以删去前面的数，所以我们可以保留出现次数做多的数，这样的操作次数最少。

code

cpp

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

int n,t,cnt[110],ans;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		ans=0;memset(cnt,0,sizeof cnt);
		scanf("%d",&n);
		_F(i,1,n)
		{
			int x;
			scanf("%d",&x);
			cnt[x]++;
			ans=max(ans,cnt[x]);
		}
		printf("%d\n",n-ans);
	}
	return 0;
}

CF2001B Generate Permutation

题意

有一个长度为 $n$ 的整数序列 $a$ ，其中每个元素的初始值为 $-1$ 。

美雪有两台打字机，第一台打字机从左往右写字母，指针最初指向 $1$ ，另一台打字机从右往左写字母，指针最初指向 $n$ 。

美雪会选择其中一台打字机进行以下操作，直到 $a$ 变成 $[1, 2, \ldots, n]$ 的排列。

写数：将数组 $a$ 中不存在的最小正整数写入元素 $a_i$ ， $i$ 是指针指向的位置。这种操作只有在 $a_i = -1$ 时才能执行。
回车：将指针返回到初始位置（例如，第一台打字机为 $1$ ，第二台为 $n$
移动指针：将指针移动到下一个位置，假设 $i$ 是指针在执行此操作前所指向的位置，如果美幸使用的是第一台打字机，则为 $i := i + 1$ ，否则为 $i := i - 1$ 。只有在操作之后， $1 \le i \le n$ 成立时，才能执行此操作。

你的任务是构造长度为 $n$ 的任意排列 $p$ ，使得无论美雪使用哪台打字机， $a = p$ 所需的最小回车操作次数都相同。

思路

首先先理解一下题面，其实就是一个只向右找，一个只向左找，找不到了再回起始点，让你构造一组数据，使得按 $[1,2,\ldots,n]$ 的顺序去找，从左右两端开始的次数一样。（玛德，越讲越不明白了，实在不理解就去看一下样例吧）

观察样例的第三组数据发现，似乎好像就是把最小的树放中间然后剩余的左右放。验证一下是对所有的奇数都是正确的。那么对偶数呢？手算一下 $4$ 个数的情况，发现无解，于是猜测对于所有偶数都无解。然而事实就是这样的。

于是就是简单的写代码了。

code

cpp

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

int n,t;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		if(!(n&1))
			puts("-1");
		else
		{
			_F(i,1,n/2)
			{
				printf("%d %d ",i,n-i+1);
			}
			printf("%d\n",n/2+1);
		}
	}
	return 0;
}

CF2001C Guess The Tree

题意

这是一个交互题。

Misuki 选择了一棵有 $n$ 节点的秘密树，索引从 $1$ 到 $n$ ，并要求你使用以下类型的查询来猜测它：

“? a b” 会告诉你哪个节点 $x$ 最小化了 $|d(a,x) - d(b,x)|$ ，其中 $d(x,y)$ 是节点 $x$ 和 $y$ 之间的距离。如果存在多个这样的节点，Misuki 会告诉你哪个节点最小化了 $d(a,x)$ 。

用最多 $15n$ 次查询找出树的结构！

思路

~~这是我写过的第一道正经的交互题~~不过并没有遇到太大的阻碍就是了。

首先分析题意，我们可以得知，返回的节点是询问两个点路径上的中点。我们会发现当返回的点是询问的 $a$ 点时，a b 之间有一条边，这个手玩样例可以发现。

我们考虑用若干组操作还原一条链，很显然用类似分治的操作去对半分还原。边界条件就是当返回的点正好是询问的点时在询问的两点之间连边。

我们让1号点不动，然后扫描其他的点，还原所有的链。

但是很显然，这样的询问次数还是太多了，我们考虑优化。我们为每一个点打上一个标记，当它已经与1联通时标记为一，我们会发现，如果中点已经被标记了，那么我们只需再去链接右半部分就行了因为左半部分已经联通了。

但是在当这棵树退化成一条链且节点从小到大排列的时候，我们就会发现我们的算法非常的极限，因为每一次操作只更新了一个节点。

所以就有另一个想法，我们将节点的访问顺序随机一下序，这样就很难被卡了。

文章分类

一言

文章归档

最新文章

CF R967 (CF2001) VP记录

CF2001A Make All Equal

题意

思路

code

CF2001B Generate Permutation

题意

思路

code

CF2001C Guess The Tree

题意

思路

code