更好的阅读体验：http://www.abmcar.top/archives/codeforcesround765div2
完整代码：https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Codeforces%20Round%20%23765%20(Div.%202)
A. Ancient Civilization
题目大意：
给你n个二进制下长度小于k的数，让你求一个数，使它和其余数的二进制上的不同的个数最少
思路：
一道不怎么简单的A题，统计所有数每一位的个数，判断某一位的0多还是1多来构造答案
代码：
string intToString(int x)
{
string ans = "";
while (x)
{
ans = ans + (char)(x % 2 + '0');
x = x / 2;
}
return ans;
}
void work()
{
cin >> n >> m;
map<int, int> M;
for (int i = 1; i <= n; i++)
{
int temp;
cin >> temp;
string nowString;
nowString = intToString(temp);
for (int j = 0; j < nowString.size(); j++)
if (nowString[j] == '1')
M[j]++;
}
ll nowNum = 0;
for (int i = 0; i < m; i++)
if (M[i] * 2 > n)
nowNum += (1 << i);
cout << nowNum << endl;
}
B. Elementary Particles
题目大意：给你一个长度为n的数组，让你求两个最长的子区间使得其中有一位相同
思路：
从相同的位入手，我们发现如果要使得子区间长度最长，那这两个区间应该是尽可能重叠的，也就是说他们再相同的哪一位上是相邻的，比如相同位的数是1，那么这两个1中间没有另一个1，否则我们可以构造出一个更长的子区间，因此，我们记录所有相同的数出现的位置遍历找最长，时间复杂度On
代码：
void work()
{
cin >> n;
vector<int> nums(n + 1);
for (int i = 1; i <= n; i++)
cin >> nums[i];
map<int, vector<int>> M;
for (int i = 1; i <= n; i++)
M[nums[i]].push_back(i);
int ans = 0;
for (auto it : M)
{
for (int j = 0; j + 1 < it.second.size(); j++)
{
int nowPos = it.second[j] + 1;
int nextPos = it.second[j + 1] + 1;
ans = max(ans, min(nowPos, nextPos) + min(n - nowPos, n - nextPos));
}
}
if (ans == 0)
ans = -1;
cout << ans << endl;
}
C. Road Optimization
题目大意：
给你一段路，路上有n个路牌限速，限速后每公里要花ai分钟，给你这段路的总长度m，以及你可以去掉k个路牌，问最小通过这段路的时间
思路：
简化一下模型，想不想一个取个不去的01背包，只是这个问题里还有当前速度这个因素，有点像那种分层图，
因此我们用dp[i][j][k]表示在第i个路牌已经去掉j个限速时当前速度为k的最小花费时间
i j的范围都是500，而k我们知道虽然可能很大，但实际非常少，因此我们用map来保存
对于每一个状态dp[i][j][k]，它可以转移到dp[i+1][j][k]，这种情况下不去掉这个路牌
如果当前限速比新路牌小，我们可以选择去掉路牌，转移到dp[i+1][j+1][v[i]]
值得注意的是这种写法需要给定一个初值，
而且最后也要判断一下最后的一段距离
代码：
int n, m, k;
vector<int> d, v;
map<int, int> dp[616][616];
signed main()
{
Buff;
#ifdef Debug
freopen("temp.in", "r", stdin);
freopen("temp.out", "w", stdout);
#endif
cin >> n >> m >> k;
d.resize(n + 2);
v.resize(n + 2);
for (int i = 1; i <= n; i++)
cin >> d[i];
for (int i = 1; i <= n; i++)
cin >> v[i];
dp[1][0][v[1]] = 0;
for (int i = 2; i <= n; i++)
{
for (int j = 0; j <= k; j++)
{
for (auto it : dp[i - 1][j])
{
dp[i][j][v[i]] = min(dp[i][j][v[i]], dp[i - 1][j][it.first] + it.first * (d[i] - d[i - 1]));
if (dp[i][j][v[i]] == 0)
dp[i][j][v[i]] = dp[i - 1][j][it.first] + it.first * (d[i] - d[i - 1]);
if (it.first < v[i])
{
dp[i][j + 1][it.first] = min(dp[i][j + 1][it.first], dp[i - 1][j][it.first] + it.first * (d[i] - d[i - 1]));
if (dp[i][j + 1][it.first] == 0)
dp[i][j + 1][it.first] = dp[i - 1][j][it.first] + it.first * (d[i] - d[i - 1]);
}
}
}
}
int ans = 1e12;
for (int j = 0; j <= k; j++)
for (auto it : dp[n][j])
{
// cout << j << " " << it.first << " " << it.second << endl;
ans = min(ans, it.second + it.first * (m - d[n]));
}
cout << ans << endl;
return 0;
}