#765 div2
https://codeforces.com/contest/1625
A:
题目:
现在给出 n 个数字,每两个数字的不相似的度为两个数字二进制对应位置不同的和,现在要你构造一个数字使他的二进制数字对给出的n个数字不相似度和最小。
思路:
毫无疑问,对于二进制某个位置来说,我们希望 0 和 1 哪个出现的多我们就构造哪个这样就让相似度尽可能小。
代码
void solved()
{
int n, k;
cin >> n >> k;
for(int i = 0; i <= k; i++) pos[i][1] = pos[i][0] = 0;
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
for(int j = 0; j < k; j++)
{
if((x >> j) & 1) pos[j][1]++;
else pos[j][0]++;
}
}
int ans = 0;
for(int i = k - 1; i >= 0; i--)
{
if(pos[i][0] < pos[i][1]) ans += pow(2, i);
}
cout << ans << endl;
}
B:
题目:
现在给你 n 个数字,你可以选择两短长度相同的区间,必须存在一个位置他们都相等,求这样的区间最大长度。
思路:
因为必须存在一个位置数字相同,所以我们对每两个相同的数字来说,把他们划到一个合法的区间。将区间以这个相同的数字划分,我们肯定希望前面越多越好,也希望后面越多越好。前面的区间长度限制在前面的数字的位置,后面区间的长度限制在第二个数字后面的长度。我们希望这两个都尽量大,所以我们每次选择相邻最近的两个相同数字,这样后面和前面的区间是比其他选择最优的。
代码
void solved()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], pos[a[i]].clear();
int ans = 0;
for(int i = n; i >= 1; i--)
{
int x = a[i];
if(pos[x].size() == 2)
{
pos[x][0] = pos[x][1];
pos[x][1] = i;
ans = max(ans, pos[x][1] + n - pos[x][0]);
}
if(pos[x].size() == 1)
{
ans = max(ans, i + n - pos[x][0]);
pos[x].push_back(i);
}
if(pos[x].size() == 0)
pos[x].push_back(i);
}
if(ans == 0) cout << -1 << endl;
else
cout << ans << endl;
}
C:
题目:
现在存在一段路,路被一些路牌分成了几段,对于每段路,你只能跑左边路牌上写的速度。
现在你可以拆掉 k 个路牌,问你通过这段路的最小时间是多少
思路:
DP
状态表示 dp[i][j]
第 i 个路牌选择,还可以剩下 j个路牌可以选的时间。
属性 : 最小值
状态计算:dp[i][j]
因为我们需要知道当前路牌的上一个没被拆的路牌是哪个,所以枚举一下前面的路牌。`
代码
void solved()
{
cin >> n >> l >> k;
for(int i = 1; i <= n; i++) cin >> dis[i];
for(int i = 1; i <= n; i++) cin >> v[i];
dis[++n] = l;
for(int i = 0; i <= n; i++) for(int j = 0; j <= k; j++) dp[i][j] = 2e15;
dp[1][k] = 0;
for(int i = 2; i <= n; i++)
{
for(int j = 1; j < i; j++)
{
for(int p = 0; p <= k; p++)
{
if(k >= i - j - 1 + p)
dp[i][p] = min(dp[i][p], dp[j][p + (i - j - 1)] + v[j] * (dis[i] - dis[j]));
}
}
}
int ans = 2e15;
for(int i = 0; i <= k; i++)
{
ans = min(ans, dp[n][i]);
}
cout << ans << endl;
}