D. Divide and Equalize (AC 补题)

题面

原题链接

题面大意翻译:

给定一系列数字。

可以在这列数字中取两个数 $a_i$ 和 $a_j$ ( $i \neq j$ )

取 $a_i$ 的一个因子 $x$ 。

将 $a_i$ 变成 $\frac{a_i}{x}$ ，把 $a_j$ 变成 $a_j \cdot x$ 。

问是否能根据任意次操作，使得最后这列数字都相等。

例如:

[100,2,50,10,1]

取 $a_3 = 50$ 和 $a_2 = 2$ ， $x = 5$ 。将 $a_3$ 变成 $\frac{a_3}{x}=10$ ，将 $a_2$ 变成 $a_2 \cdot x = 10$ 。此时列表变成[100,10,10,10,1]。
取 $a_1 = 100$ 和 $a_5 = 1$ ， $x = 10$ 。将 $a_1$ 变成 $\frac{a_1}{x}=10$ ，将 $a_5$ 变成 $a_2 \cdot x = 10$ 。此时列表变成[10,10,10,10,10]。

在两次操作后，我们成功将这个列表的元素都变成了相同的数字。

我们只需要输出能否通过任意次操作来完成这个目标。

思路

选定一个数的一个因子，让它自身除以这个因子，让一个别的数乘以这个因子。

抽象来看，可以看作是这个数的因子转移到了另一个数身上。

所以首先第一步就是把列表里的数字都拆成质因数的乘积。

虽然可以转移任意的因子，但拆成质因数后更好判断能不能转移。

如何判断可以完成目标呢？给个例子：

这个列表[125,8,27]

拆成质因数就是$$[555, 222, 333]$$

通过转移他们的质因数，我们可以把它变成$$[235,235,235]$$。

也就是变成了[30,30,30]。

注意到实际上就是将他们不同的质因数平均分配给 $n$ 个元素。

所以我们可以只需要搜集质因数的个数，看最后的总个数是否是n的整数倍就可以了。

代码


#define fi(i,l,r) for(int i=l;i<=r;i++)

void divided(int x, unordered_map<int,int>& umap) //提取x的质因数并保存在哈希表里
{
    int i = 2;
    while (i * i <= x) {
        while (x % i == 0) {
        umap[i]++;
        x /= i;
        }
        i++;
    }
    if (x > 1) umap[x]++; //如果x自己就是质数的话就不会进入上面的循环，所以要加个特殊判断
    return;
}

void solve()
{
    int n;
    cin >> n;
    int a;
    unordered_map<int, int> umap;
    fi(i, 0, n - 1) {
        cin >> a;
        divided(a, umap);
    }
    for (auto& e : umap) {
        if (e.second % n != 0) { //如果有个质因数的个数不满足是n的整数倍，那么最后就不可能完成目标
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E. Block Sequence (AC 补题)

题面

原题链接

题目大意翻译:

给定一个列表，它需要被分成多个区块(blocks)。每个区块的第一个数字 $x$ 表示该区块的长度，后面会跟着 $x$ 个元素。

可以删去这个列表的任意数字，问需要至少删除几个数字才能让这个列表满足以上条件。

例如:

[1,2,3,4,5]

删去1和5两个数字，列表可以被分为[[2,3,4]]。

[5,6,3,2]

删去任意数字都不能满足条件，只能全删了，回答是4。

思路

这题可以用动态规划的思路来解决。

定义dp[i]存储的是要让从 $i \to n$ 的序列满足条件的最小操作次数。

如果选择删去第 $i$ 个元素的话，dp[i] = dp[i+1] + 1。

如果不删的话就是dp[i] = dp[i+a[i]+1]。它作为序列头，自己自然就等于下个序列的头了。

特别的，当i+a[i]+1 > n时说明必须要删掉当前的数才能满足条件。

代码

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n), dp(n, n+1);
    fi(i, 0, n - 1) {
        cin >> a[i];
    }
    dp[n - 1] = 1;
    auto getNum = [&n, &dp](int x) {
        if (x > n) return n + 1;
        if (x == n) return 0;
        return dp[x];
    };
    for (int i = n - 2; i >= 0; --i) {
        dp[i] = min(dp[i + 1] + 1, getNum(i + a[i] + 1));
    }
    cout << dp[0] << '\n';
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F. Minimum Maximum Distance (AC 补题)

题面

原题链接

题目大意翻译：

给定一个无向无环图，上面标记了几个节点。找出一个节点到达所有节点的距离最短，输出这个节点到达最远一个标记节点的距离。

例如:

在这个图中2,6,7是标记节点，根据计算可以得出节点1或节点3到达最远标记节点的距离最小。

①到达最远的标记节点是⑥和⑦，距离为2。

③到达最远的标记节点是②，距离为2。

思路

我们首先从任意一个标记节点 $v_1$ 出发，找到离它最远的标记节点 $v_2$ 。

再从 $v_2$ 出发找到离它最远的标记节点 $v_3$ (可能仍为 $v_1$ )，记录 $v_2$ 到 $v_3$ 的距离 $distance$ 。

最终答案就是 $\frac{distance}{2}$ 。

特别的，当只有一个标记节点的时候直接返回0。

代码

vector<vector<int>> m;
 
void dfs(int v, int past, vector<int>&d)
{
	if (past != -1) d[v] = d[past] + 1;
	for (int& u:m[v]) {
		if(u!=past) dfs(u, v, d);
	}
}
 
void solve()
{
	int n, k;
	cin >> n >> k;
	m.assign(n, vector<int>(0));
	vector<int> mark(k);
	fi(i, 0, k-1) {
		cin >> mark[i];
		--mark[i];       //它的数据从1开始，这里改成从0开始
	}
	int a, b;
	fi(i, 1, n - 1) {
		cin >> a >> b;
		a--, b--;
		m[a].push_back(b);
		m[b].push_back(a);
	}
	if (k == 1) {    //只有一个节点的情况
		cout << 0 << '\n';
		return;
	}
	vector<int> d1(n);  //存的是从v1到i位置的距离
	dfs(mark[0], -1, d1);
	int v2 = mark[0];
	for (int& num : mark) {
		if (d1[v2] < d1[num]) v2 = num;
	}
	vector<int> d2(n);
	dfs(v2, -1, d2);
	int v3 = mark[0];
	for (int& num : mark) {
		if (d2[v3] < d2[num]) v3 = num;
	}
	cout << ((d2[v3] + 1) >> 1) << '\n';      //为什么要+1？只有+1才能过
	return;
}

记第一次codeforces比赛(下)

D. Divide and Equalize (AC 补题)

题面

思路

代码

E. Block Sequence (AC 补题)

题面

思路

代码

F. Minimum Maximum Distance (AC 补题)

题面

思路

代码