[Codeforces Round #642 (Div. 3)] ABCDEF题解

A. Most Unstable Array

思路：

当\(n=1\)时答案为\(\text 0\)，

当\(n=2\)时答案为\(\mathit n\)，

当\(n=3\)时答案为\(2*n\)，

代码：
int main()
{
#if DEBUG_Switch
	freopen("C:\\code\\input.txt", "r", stdin);
#endif
	//freopen("C:\\code\\output.txt","r",stdin);
	int t;
	t = readint();
	while (t--)
	{
		ll n, k;
		n = readll();
		k = readll();
		if (n == 1)
		{
			printf("0\n");
		} else if (n == 2)
		{
			printf("%lld\n", k);
		} else
		{
			printf("%lld\n", k * 2ll );
		}
	}
 
	return 0;
}

B. Two Arrays And Swaps

思路：

简单贪心，对数组\(a,b\)分别sort之后，当前数组\(\mathit b\)中的最大值比数组\(\mathit a\)中的最小值大时让其交换。

代码：
int n;
int k;
int a[maxn];
int b[maxn];
 
int main()
{
#if DEBUG_Switch
	freopen("C:\\code\\input.txt", "r", stdin);
#endif
	//freopen("C:\\code\\output.txt","r",stdin);
	int t;
	t = readint();
	while (t--)
	{
		n = readint();
		k = readint();
		int sum = 0;
		repd(i, 1, n)
		{
			a[i] = readint();
			sum += a[i];
		}
		repd(j, 1, n)
		{
			b[j] = readint();
		}
		sort(a + 1, a + 1 + n);
		sort(b + 1, b + n + 1);
		repd(i, 1, k)
		{
			if (a[i] < b[n - i + 1])
			{
				sum += b[n - i + 1] - a[i];
			}
		}
		printf("%d\n", sum );
	}
 
	return 0;
}

C. Board Moves

思路：

手花一下样例\(n=5\)，可以发现，每一个cell都移动到最中间的\((\frac{n+1}{2},\frac{n+1}{2})\)的cell消耗最小。

而cell移动的成本是切比雪夫距离：

　　平面上两个点\(（x1，y1）,（x2，y2）\)之间的距离为\(max（ |x1-x2 | , | y1 - y2 | ）\)。

而切比雪夫距离会随着cell的\(max(i,j)\)在变化，所以枚举一下\(max(i,j)\)即可。

代码：
int main()
{
#if DEBUG_Switch
	freopen("C:\\code\\input.txt", "r", stdin);
#endif
	//freopen("C:\\code\\output.txt","r",stdin);
	int t;
	t = readint();
	while (t--)
	{
		int n = readint();
		ll ans = 0ll;
		repd(i, 2, (n + 1) / 2)
		{
			ans += 1ll * ((i + i - 1) * 4ll - 4) * (i - 1);
		}
		printf("%lld\n", ans );
	}
 
	return 0;
}

D. Constructing the Array

思路：

维护一个以区间长度更大为第一标准，以区间的左端点值更小为第二标准的优先队列，然后模拟下题意即可。

代码：

const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
struct node
{
	int l, r;
	int len;
	node() {}
	node(int __l, int __r)
	{
		l = __l;
		r = __r;
		len = r - l + 1;
	}
	bool operator < (const node & b) const
	{
		if (len != b.len)
		{
			return len < b.len;
		} else
		{
			return l > b.l;
		}
	}
};
priority_queue<node> q;
int a[maxn];
int main()
{
#if DEBUG_Switch
	freopen("C:\\code\\input.txt", "r", stdin);
#endif
	//freopen("C:\\code\\output.txt","r",stdin);
	int t;
	t = readint();
	while (t--)
	{
		int n = readint();
		q.push(node(1, n));
		int id = 1;
		while (!q.empty())
		{
			node temp = q.top();
			q.pop();
			int l = temp.l;
			int r = temp.r;
			if (temp.len & 1)
			{
				a[(temp.r + temp.l) / 2] = id++;
				int mid = (temp.r + temp.l) / 2;
				if (l <= mid - 1)
				{
					q.push(node(l, mid - 1));
				}
				if (mid + 1 <= r)
				{
					q.push(node(mid + 1, r));
				}
			} else
			{
				a[(temp.r + temp.l - 1) / 2] = id++;
				int mid = (temp.r + temp.l - 1) / 2;
				if (l <= mid - 1)
				{
					q.push(node(l, mid - 1));
				}
				if (mid + 1 <= r)
				{
					q.push(node(mid + 1, r));
				}
			}
		}
		repd(i, 1, n)
		{
			printf("%d%c", a[i], i == n ? '\n' : ' ' );
		}
	}

	return 0;
}

 

E. K-periodic Garland

思路：

枚举\([0,k-1]\)作为目标亮灯位置\(index\)对\(\mathit k\)取模后的数值，

然后通过预处理过的前缀和算出有多少灯必须灭掉，

对于剩余的亮灯部分通过动态规划来求解操作次数最小的满足条件情况。

定义状态：

\(dp[i][0]\)代表到第\(i\)个以及之前所有的灯都是灭掉时的最小成本。

\(dp[i][1]\)代表到第\(i\)个灯时，只有\(\mathit i\) 以及之前若干灯（可能为0）为点亮时的最小成本。

转移方程见代码。

在通过处理一个后缀和维护就可以动态规划转移时得到答案。

代码：
int a[maxn];
int n, k;
int sum[maxn];
std::vector<int> v;
int cnt[maxn];
int dp[maxn][2];
int main()
{
#if DEBUG_Switch
	freopen("C:\\code\\input.txt", "r", stdin);
#endif
	//freopen("C:\\code\\output.txt","r",stdin);
	int t;
	t = readint();
	while (t--)
	{
		n = readint();
		k = readint();
		repd(i, 1, n)
		{
			scanf("%1d", &a[i]);
		}
		repd(i, 1, n)
		{
			sum[i] = sum[i - 1] + a[i];
		}
		// special
		if (n == 1)
		{
			printf("0\n");
			continue;
		}
		// else
		int ans = n;
		repd(i, 1, k)
		{
			int now = 0;
			int j;
			v.clear();
			v.pb(0);
			for (j = i; j <= n; j += k)
			{
				v.pb(a[j]);
				now += sum[j - 1] - sum[max(j - k, 0)];
			}
			if (j > n) {
				j -= k;
				now += sum[n] - sum[j];
			}
			int len = sz(v) - 1;
			for (j = len; j >= 1; --j)
			{
				cnt[j] = cnt[j + 1] + v[j];
			}
			int w = inf;
			for (j = 1; j <= len; ++j)
			{
				if (v[j] == 1)
				{
					dp[j][1] = min(dp[j - 1][1], dp[j - 1][0]);
					dp[j][0] = dp[j - 1][0] + 1;
				} else
				{
					dp[j][1] = min(dp[j - 1][1] + 1, dp[j - 1][0] + 1);
					dp[j][0] = dp[j - 1][0];
				}
				w = min(w, min(dp[j][1], dp[j][0]) + min(cnt[j + 1], (n - j) - cnt[j + 1]));
			}
			now += w;
			ans = min(ans, now);
			// clear
			for (j = 1; j <= len; ++j)
			{
				cnt[j] = 0;
				dp[j][0] = dp[j][1] = 0;
			}
		}
		printf("%d\n", ans );
	}
 
	return 0;
}

F. Decreasing Heights

思路：

通过分析可以发现，最优路径中一定有一个cell的height是固定值（没有被改变）。

那么我们不妨枚举每一个cell作为那个height是固定值的cell，然后计算当前约束下的最小花费。

设当前枚举的cell坐标为\((x,y)\)，则计算方法为：

\(dp[i][j]\)代表从\((x,y)\)移动到\((i,j)\)时的最小花费。

\(b[i][j]\)代表从\((x,y)\)移动到\((i,j)\)时的，cell\((i,j)\)的height。

转移方程见代码。

枚举部分的时间复杂度为:\(O(n*m)\)

计算部分的时间复杂度为:\(O(n*m)\)

所以总时间复杂度为：\(O(n^2*m^2)\).

代码：
int n, m;
ll a[maxn][maxn];
ll dp[maxn][maxn];
ll b[maxn][maxn];
const ll INF = 1e18;
 
ll solve(int x, int y)
{
	repd(i, 0, n + 1)
	{
		repd(j, 0, m + 1)
		{
			dp[i][j] = 1e18;
			b[x][y] = 1e18;
		}
	}
	dp[x][y] = 0ll;
	b[x][y] = a[x][y];
	for (int i = x; i >= 1; --i)
	{
		for (int j = y; j >= 1; --j)
		{
			if (i == x && j == y)
				continue;
			if (a[i][j] >= b[i + 1][j] - 1 && dp[i][j] > dp[i + 1][j] + (a[i][j] - b[i + 1][j] + 1) )
			{
				dp[i][j] = dp[i + 1][j] + (a[i][j] - b[i + 1][j] + 1) ;
				b[i][j] = b[i + 1][j] - 1;
			}
			if (a[i][j] >= b[i][j + 1] - 1 && dp[i][j] > dp[i][j + 1] + (a[i][j] - b[i][j + 1] + 1) )
			{
				dp[i][j] = dp[i][j + 1] + (a[i][j] - b[i][j + 1] + 1) ;
				b[i][j] = b[i][j + 1] - 1;
			}
		}
	}
	for (int i = x; i <= n; ++i)
	{
		for (int j = y; j <= m; ++j)
		{
			if (i == x && j == y)
				continue;
			if (a[i][j] >= b[i - 1][j] + 1 && dp[i][j] > dp[i - 1][j] + (a[i][j] - b[i - 1][j] - 1) )
			{
				dp[i][j] = dp[i - 1][j] + (a[i][j] - b[i - 1][j] - 1) ;
				b[i][j] = b[i - 1][j] + 1 ;
			}
			if (a[i][j] >= b[i][j - 1] + 1 && dp[i][j] > dp[i][j - 1] + (a[i][j] - b[i ][j - 1] - 1) )
			{
				dp[i][j] = dp[i][j - 1] + (a[i][j] - b[i ][j - 1] - 1) ;
				b[i][j] = b[i][j - 1] + 1 ;
			}
		}
	}
	return dp[1][1] + dp[n][m];
}
int main()
{
#if DEBUG_Switch
	freopen("C:\\code\\input.txt", "r", stdin);
#endif
	//freopen("C:\\code\\output.txt","r",stdin);
	int t;
	t = readint();
	while (t--)
	{
		ll ans = 1e18;
		n = readint();
		m = readint();
		repd(i, 1, n)
		{
			repd(j, 1, m)
			{
				a[i][j] = readll();
			}
		}
		repd(i, 1, n)
		{
			repd(j, 1, m)
			{
				ans = min(ans, solve(i, j));
			}
		}
		printf("%lld\n", ans );
	}
 
	return 0;
}