526互联

5.22-5.28

发布时间 2023-06-10 00:24:41作者: 一棵木头罢辽

C. LIS or Reverse LIS?

Problem - C - Codeforces

构造，思维

题意：

​ 给出n个元素，重新对元素进行排列使得其左右其左右两边的最长上升子序列最短的长度最大。

思路：

​ 首先，要使得左右最小的最大，左右的最长上升子序列的长度之差肯定最小。尝试构造一下就可以发现，由于是上升子序列，所以一个数最多在两边各出现一次，也即是一个数最多会对答案产生两次贡献。

​ 那么我们只需要用一个map来储存一个数出现了多少次，那么它对答案的贡献就是\(min(cnt, 2)\)，对所有数字计算它们的总贡献，除以2后就是答案（将每个数平均分布在序列的两边，最终的得到的就是\(sum/2\)）

void QAQ(){
	cin >> n;
	map<int, int> mp;
	int cnt = 0; 
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		mp[x] ++;
		if(mp[x] <= 2) cnt ++;
	}
	cout << (cnt + 1)/ 2 << endl;
	
}

一开始做这题的时候一直在想着怎么去构造出这个序列再去数数，但由于各种细节问题导致答案总是查了一点，最后无奈去看了题解发现根本不用构造出串具体长什么样子，只需要算出答案就可以了。

吸取到的教训是对于没有要求输出具体答案的题目，其大概率可以通过直接计算得出答案而不是实现后去反推答案。

D1. Zero-One (Easy Version)

Problem - D1 - Codeforces

贪心，思维

题意：

​ 分别有初始串a和结果串b，每次可以在a中选取任意两个元素使其取反，如果这两个元素相邻，其代价为x，否则代价为y。问是否通过n次操作让ab串相等，如果可以输出最小的消耗

​ 对于easy version，题目保证了x≥y

思路：

​ 首先我们先来思考什么情况下不能被满足。假设当前有p个位置的元素不一样，我们从中选取任意两个位置，要想改变它们有两种实现方法：

  • 直接选取当前的两个，消耗x如果它们相邻，消耗y如果它们不相邻，不相同的位置个数-2
  • 选取一个中转站，分别进行两次y操作，消耗为2y，不相同的位置个数-2

​ 可以发现，无论进行那种操作，每次对不相同的位置个数影响一定是2，也就是说，如果当前不相同的个数为1，则最终一定无法被完全消去。

​ 基于x≥y的条件来想想怎么实现。我们上面已经分析过，由于x≥y，所以我们肯定是选不相邻的来配对消去是最优的。在不相同的个数cnt≥4的情况下，我们可以证明一定可以让所有都通过不相邻的删去，消耗为\(cnt/2*y\)。但当cnt = 2的时候，如果当前两个不相邻，我们仍然可以通过消耗y来删去，但如果当前两个相邻，我们就只能通过消耗a或是2y来消去，这个时候需要特殊判断

\[\begin{cases}\frac{cnt}{2}\times y\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ cnt\ ＞2\ \ or 不相邻 \\ min(x, y \times2)\ \ \ \ \ \ \ \ 相邻\end{cases} \]

代码和hard version一起给出

D2. Zero-One (Hard Version)

Problem - D2 - Codeforces

dp

题意：

​ 见easy version，区别在于没有保证x≥y。

思路：

​ 很容易意识到需要dp。

​ 由于没有了x≥y的限制条件，我们再分析一下题目给的样例就可以发现，对于x≥y的情况，我们只需要和之前一样去处理就可以得出答案，不需要另外增加。需要另外考虑的是x＜y的情况。

​ 对于x＜y，我们很明显可以想到当相邻的时候我们只需要考虑x就可以了（因为x一定小于2y），当不相邻的时候，我们可以通过y来把它们消去，但同时，也可能是通过（pos1-pos2）* x来消去，这就是我们需要dp的地方。

​ 其次，对于多个不相同的位置，把邻近的位置一起消去一定比跳着位置消去更优。

​ 所以，对于每一个相邻的对，我们都要考虑用x操作来消去它们，消耗为（pos1-pos2）* x，同时也考虑用y去消去它（这里不用担心是否会出现相邻的时候选择y的情况，因为题目要求x＜y，只要dp状态没有想错最终相邻的时候一定是选择x更优）。则列出状态转移方程为

\[dp[i] = min(dp[i - 2] + 2 * x (pos[i] - pos[i - 1]), dp[i - 1] + y) \]

​ 其中，我们选择2x而不是x是因为如果要消去一对，后面的y就会统计两次，相对应的，为了避免这种倍数的误差，选择将x也乘2

void QAQ(){
	cin >> n >> x >> y;
	int cnt = 0;
	string a, b;
	cin >> a >> b;
	a = " " + a;
	b = " " + b;
	int idx = 0;
	for(int i = 1; i <= n; i ++){
		if(a[i] != b[i]){
			pos[++idx] = i;
		}
	}
	if(idx & 1){
		cout << "-1\n";
		return;
	}
	if(x >= y){
		if(idx == 2 && pos[1] + 1 == pos[2]){
			cout << min(x, y * 2) << endl;
			return;
		}
		cout << idx / 2 * y << endl;
	} 
	else{
		for(int i = 1; i <= idx; i ++) dp[i] = INF;
		dp[0] = 0;
		dp[1] = y; //只有一个，不可能用消去，所以只考虑y
		for(int i = 2; i <= idx; i ++){
			dp[i] = min(dp[i - 2] + 2 * x * (pos[i] - pos[i - 1]), dp[i - 1] + y);
		}
		cout << dp[idx] / 2 << endl;
        //注意由于前面是两倍统计，输出答案时要除以2
	}
}

​ 进一步，另外一种dp思路与上面类似，分成了两种情况讨论。

​ 如果当前i为偶数，则前面一共有偶数个位置需要改变，我们一定能让第i-1个和第i个相邻x消去，或者让第i个和前面任意一个位置y消去，考虑这两种情况中小的那个

\[dp[i]=min(dp[i-2] + x * (pos[i]-pos[i-1]), dp[i-1] + y) \]

​ 如果当前i为奇数，无法保证当前位能找到一位与其y消去，但可以与前一位x消去

\[dp[i]=min(dp[i-2] + x * (pos[i] - pos[i -1]), dp[i-1]) \]

void QAQ(){
	cin >> n >> x >> y;
	int cnt = 0;
	string a, b;
	cin >> a >> b;
	a = " " + a;
	b = " " + b;
	int idx = 0;
	for(int i = 1; i <= n; i ++){
		if(a[i] != b[i]){
			pos[++idx] = i;
		}
	}
	if(idx & 1){
		cout << "-1\n";
		return;
	}
	if(x >= y){
		if(idx == 2 && pos[1] + 1 == pos[2]){
			cout << min(x, y * 2) << endl;
			return;
		}
		cout << idx / 2 * y << endl;
	} 
	else{
		for(int i = 1; i <= idx; i ++) dp[i] = INF;
		dp[0] = dp[1] = 0;
        //注意初始化，位置1无法于前面进行x消去，直接继承dp[i-1]也即是dp[0]
		for(int i = 2; i <= idx; i ++){
			if(i & 1){
				dp[i] = min(dp[i - 2] + x * (pos[i] - pos[i - 1]), dp[i - 1]);
			}
			else{
				dp[i] = min(dp[i - 2] + x * (pos[i] - pos[i - 1]), dp[i - 1] + y);
			}
		}
		cout << dp[idx] << endl;
	}
}

​ 另外还有一种与区间dp取两端类似的思想，我们只把所有需要改变的位置单独拿出来，那么就是每次可以选择左边两个，右边两个，左右各一个消去，每次消去的花费不同，问怎么样能让花费最小

​ 对于左右的不同位置，我们一共有三种策略消除，这里有一个小贪心就是，将一个位置和与其相邻的位置消去，在操作1中一定是最优的，而为了更好地利用操作2的特性，我们将两个相隔较远的数消去才是最优的。

\[\begin{cases} cost(l,l+1)+f[\ l+2\ ][\ r\ ]\\ cost(r−1,r)+f[\ l\ ][\ r−2\ ]\\ cost(l,r)+f[\ l+1\ ][\ r−1\ ] \end{cases} \]

​ 在这里，我们使用记忆化搜索来完成

int geet(int l, int r){
	if(l + 1 == r){
		return min(x, y * 2);
	}
	return min(x * (r - l), y);
}
 
int dfs(int l, int r){
	if(l > r) return 0;
	if(dp[l][r] != -1) return dp[l][r];
	int res = INF;
	res = min(res, dfs(l + 1, r - 1) + geet(pos[l], pos[r]));
	res = min(res, dfs(l + 2, r) + geet(pos[l], pos[l + 1]));
	res = min(res, dfs(l, r - 2) + geet(pos[r - 1], pos[r]));
	return dp[l][r] = res;
}
 
void QAQ(){
	cin >> n >> x >> y;
	int cnt = 0;
	string a, b;
	cin >> a >> b;
	a = " " + a;
	b = " " + b;
	int idx = 0;
	for(int i = 1; i <= n; i ++){
		if(a[i] != b[i]){
			pos[++idx] = i;
		}
	}
	if(idx & 1){
		cout << "-1\n";
		return;
	}
	if(x >= y){
		if(idx == 2 && pos[1] + 1 == pos[2]){
			cout << min(x, y * 2) << endl;
			return;
		}
		cout << idx / 2 * y << endl;
	} 
	else{
		for(int i = 1; i <= idx; i ++){
			for(int j = 1; j <= idx; j ++){
				dp[i][j] = -1;
			}
		}
		cout << dfs(1, idx) << endl;
	}
}

C. Set Construction

Problem - C - Codeforces

思维，构造

题意：

​ 一共有n个数组，每个数组里只出现\(1-n\)内的数字，且每个数字只出现一次，数组里不需要出现全部\(1-n\)的数字。现在给出每个数组间的关系，对于第\(i\)行第\(j\)个数字，为1则认为\(a_i\)是\(a_j\)的真子集，为0则不是。需要我们输出一组满足题目要求的数组集。

思路：

​ 最初的想法是建图然后用拓扑排序来做，是可行解。但实际上题目保证了给出的数组一定有解，所以可以用更简单的方法解决，即初始化每个集合都为该行自己，对于每行如果为1就把该行行号加入对应的集合中就可以了。

拓扑排序

void QAQ(){
	cin >> n;
	vector<int> e[n + 1];
	vector<int> inn(n + 1);
	string s;
	for(int i = 1; i <= n; i ++){
		cin >> s;
		for(int j = 0; j < n; j ++){
			if(s[j] == '1'){
				e[i].push_back(j + 1);
				inn[j + 1] ++;
			}
		}
	} 
	queue<int> q;
	for(int i = 1; i <= n; i ++){
		if(inn[i] == 0) q.push(i);
	} 
	set<int> ans[n + 1];
    //需要从指向其的集合中继承其所有元素，用set去重
	int k = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		ans[u].insert(k);//为每次取出的集合添加全新的元素，保证指向它的是其子集
		k ++;
		for(auto v : e[u]){
			inn[v] --;
			if(inn[v] == 0) q.push(v);
			for(auto x : ans[u]){//从当前集合将元素继承到指向的集合中
				ans[v].insert(x); 
			}
		}
	}
	for(int i = 1; i <= n; i ++){
		cout << ans[i].size() << " ";
		for(auto x : ans[i]) cout << x << " ";
		cout << endl;
	}
}

直接插入

void QAQ(){
	cin >> n;
	vector<int> ans[n + 1];
	for(int i = 1; i <= n; i ++){
		ans[i].push_back(i);
		string s;
		cin >> s;
		s = " " + s;
		for(int j = 1; j <= n; j ++){
			if(s[j] == '1'){
				ans[j].push_back(i);
			}
		}
	}
	for(int i = 1; i <= n; i ++){
		cout << ans[i].size() << " ";
		for(auto x : ans[i]) cout << x << " ";
		cout << endl;
	}
}

B. Magic, Wizardry and Wonders

Problem - B - Codeforces

思维，构造

题意：

​ 原长为n的数组，内部所有元素都小于l，我们每次取出数组中最后两个元素，将二者相减之后的结果放回原数组末尾，最后剩下一个数字d，输出一种原数组的可行解

思路：

​ 手写模拟一下会发现，对于最后剩下的数字，无论原长奇偶，其都等于原数组中所有奇数项减去所有偶数项，即\(\sum_{i=1}^n (-1)^{i + 1}a_i\)。

​ 首先，我们可以判断下成立条件，对于最后剩下的数，最大的值就是奇数项全取l，偶数项全取1，反之则为最小的值。只需要判断d是否在范围内即可。

​ 接下来，我们假设当前数组所有数字都为1

	+ 当前d > 0，在奇数项上不断加，直到达到l或者d = 0
	+ 当前d < 0，在偶数项上不断加，直到达到l或者d = 0

void QAQ() {
	cin >> n >> d >> l;
	int even = n / 2, odd = (n + 1) / 2;
	if(d > odd * l - even || d < odd - even * l){
		cout << "-1" << endl;
		return ;
	}
	d -= odd - even;
	for(int i = 1; i <= n; i ++) ans[i] = 1;
	l --;
	if(d > 0){
		int k = 1;
		while(k <= n && d > 0){
			if(d > l){
				ans[k] += l;
				k += 2;
				d -= l;
			}
			else{
				ans[k] += d;
				d = 0;
			}
		}
	}
	else if(d < 0){
		int k = 2;
		while(k <= n && d < 0){
			if(d < - l){
				ans[k] += l;
				k += 2;
				d += l;
			}
			else{
				ans[k] += -d;
				d = 0;
			}
		}
	} 
	if(d){
		cout << "-1" << endl;
		return ;
	}
	for(int i = 1; i <= n; i ++){
		cout << ans[i] << " ";
	}
	cout << endl;
}