程序员进阶之算法练习（九十五）
题目1
题目链接 题目大意： 有n个整数的数组a，现在需要构造一个1到n的排列b； 令𝑐𝑖 = 𝑎𝑖−𝑏𝑖，希望最终𝑐𝑖 出现尽可能多的不同整数。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤40000) 每个样例两行 第一行整数𝑛(1≤𝑛≤4⋅1e4) 第二行整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤1e9)
输出： 每个样例一行，输出符合要求的1-n排列。
Examples input 3 1 100000 2 1 1 3 10 3 3
output 1 2 1 1 3 2
题目解析： 当n=1时，只有1个解； 当n=2时，假如a1<a2,那么令c[1]=a1-2,c[2]=a2-1，由于a1<a2且2>1，那么c1必然<c2; 当n=3时，同理我们可以把3、2、1依次与数组中较小值进行匹配，可以保证最终的值各不相同。
class Solution {
static const int N = 201010;
pair<int, int> a[N];
int b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i].first;
a[i].second = i;
}
sort(a, a + n);
for (int i = 0; i < n; ++i) {
b[a[i].second] = n - i;
}
for (int i = 0; i < n; ++i) cout << b[i] << " ";
cout << endl;
}
}
}
ac;题目2
题目链接 题目大意： 有一个长度为n的01字符串s，现在可以构造另外一个长度为n的字符串L，这个字符串有x个字符为1； 现在想知道当x为0、1、2、3、、、、n时，字符串s和l每个字符按照位置进行异或操作后，最终生产的字符串是否为回文串； 比如说s=101011，当x=2时，我们可以构造字符串L为010100，这样生成的字符串为111111，是回文串；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100000) 每个样例两行 第一行整数𝑛，表示字符串长度 (1≤𝑛≤1e5) 第二行字符串s
输出： 每个样例一行，输出长度为n+1的字符串，第i个字符为1表示可以构造有i个字符1的字符串l，使得最终生成字符串是回文串。
Examples input 5 6 101011 5 00000 9 100100011 3 100 1 1
output 0010100 111111 0011111100 0110 11
题目解析： 首先对字符串进行回文串匹配，初始cnt=1，假如某个位置无法匹配回文串的要求，我们用cnt++记录； 这样cnt就可以表示回文串中不匹配的数量，不匹配只有01和10两种情况，此时需要一个字符串1和一个字符0，来进行异或操作；
那么最终x应该要>=cnt，因为需要提供足够多的1来修正不匹配的字符； 但是x也不能太多，因为需要有cnt数量的0来做匹配，最终x要<=n-cnt； 那是否满足cnt <= x <= n-cnt就有解呢？ 还要考虑回文串中，是否为奇数。 如果回文串为偶数，那么最终的x - cnt的数量还需要是奇数； 如果回文串为奇数，存在最中间的位置可以任意操作，那么x - cnt可以为奇数或者偶数。
class Solution {
static const int N = 201010;
char str[N];
int ans[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> str;
int cnt = 0;
for (int i = 0; i < n / 2; ++i) {
if (str[i] != str[n - i - 1]) ++cnt;
}
if (!cnt) ans[0] = ans[n] = 1;
else ans[0] = ans[n] = 0;
for (int i = 1; i < n; ++i) {
ans[i] = 0;
if (i >= cnt && i <= (n - cnt)) {
if ((i - cnt) % 2 == 0) { // 剩下为偶数，没有问题
ans[i] = 1;
}
else {
if (n % 2) ans[i] = 1; // 中间有留1个位置，可以随意变
}
}
}
for (int i = 0; i <= n; ++i) putchar('0' + ans[i]);
cout << endl;
}
}
}
ac;题目3
题目链接 题目大意： 有一个整数数组s，长度为n；一个数组的MEX值，就是该数组没有出现过的非负整数的最小值，比如说 MEX({0,1,2,4}) = 3 . 现在Alice和Bob两个人在玩游戏，Alice先手。游戏规则如下： Alice可以添加一个整数𝑥(0≤𝑥≤1e9)到数组中，要求该整数在数组中没有； Bob可以移除一个整数y，y必须要小于最近一次Alice添加的整数x，并且该数字在数组存在； Alice的目标是尽可能让数组最终的MEX值更大，Bob的目标是让最终的MEX值尽可能小。
现在让你扮演Alice，使得最终MEX尽可能大。
输入： 第一行，整数𝑡 表示t次游戏 (1≤𝑡≤100000) 每个样例有多行： 第一行整数𝑛(1≤𝑛≤1e5) 第二行整数数组s (0≤𝑠1<𝑠2<…<𝑠𝑛≤1e9) 接下来有多行，每行一个整数y： 如果y>=0，表示Bob从数组中移除该数字； y=-1，表示该次游戏结束；
输出： 每个样例若干行，每行一个整数x，表示要添加的整数；
Examples input 3 5 1 2 3 5 7
7
5
-1
3 0 1 2
0
-1
3 5 7 57
-1 output 8
57
0
3
0
0
样例解释： 样例一的整个操作过程 {1,2,3,5,7 } → {1,2,3,5,7,8 } → {1,2,3,5,8 } → {1,2,3,5,8,57 } → {1,2,3,8,57 } → {0,1,2,3,8,57 }. 最终游戏结束 MEX(𝑆)=4
题目解析： 题目看起来复杂，其实分析下Alice和Bob的策略，会发现逻辑比较简单： Alice想要MEX值尽可能大，那么必须从小开始填充未出现的字符； Bob想要MEX值尽可能小，那么必须从小开始移除出现的字符；
那么为了让题目交互起来更加简单： 先手采用这样的策略，先填充一个数字。 后手移除任何数字，都选择添加该数字。
class Solution {
static const int N = 101010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
map<int, int> h;
for (int i = 0;i < n; ++i) {
int tmp;
cin >> tmp;
h[tmp] = 1;
}
int first = -1, second = -1;
for (int i = 0; i < n + 10; ++i) {
if (h.find(i) != h.end()) continue;;
if (first == -1) {
first = i;
}
else if (second == -1) {
second = i;
break;
}
}
cout << first << endl;;
while (true) {
int p;
cin >> p;
if (p == -1) break;
cout << p << endl;
}
}
}
}
ac;题目4
题目链接 题目大意： 有若干个城市在洪水后被冲毁，现在需要重建； 我们用n x m的矩阵来表示，每个元素都代表一个城市，元素为0表示城市被摧毁，元素为1表示该城市被重建了； 城市重建有两种方式，首先是指定若干个城市直接重建； 另外一种方式，是由其他城市协助重建，可以被协助重建的条件是： 当且仅当这个城市在横、竖两个方向上，都有相邻的城市已经被重建。 比如说 10 11 右上角的城市就可以被协助重建。
现在想知道最少需要指定多少个城市，才能让所有城市都被重建。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例一行，整数 𝑛 and 𝑚 (2≤𝑛,𝑚≤100 )
输出： 每个样例一行，输出满足要求的最小重建数量。
Examples input 3 2 2 5 7 3 2
output 2 7 3
题目解析： 首先从小样例情况开始分析，容易知道n=2，m=2的情况是： 01 10 或者 10 01 剩下的城市协助重建即可。
当增加到3x3时候，考虑可以直接从2x2的基础上开始思考，并且为了充分利用协助重建，我们可以假设2x2已经完全重建。 110 110 000 这样我们很容易想到，只需要在右下角添加 一个1，剩下的1可以自动补齐。
至此，我们很容易得到一个策略，就是不断在右下角添加数字，得到一个最优解。
class Solution {
static const int N = 201010;
int dir[4][2] = {1,1, -1,1, 1,-1, -1,-1};
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
/*
01000
10000
00100
00011
*/
cout << 2 + max(n - 2, m - 2) << endl;
}
}
}
ac;题目5
题目链接 题目大意： 给出一个n个节点的树，现在每次可以选择两个节点，将两个节点之间的最短路径上，所有节点都合并成一个节点，类似下图的操作：
和原来节点相连的边，改为和新合并成的点相连。
问，最少要进行多少次操作，剩下的节点只有1个。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例第一行，整数 𝑛 (2≤𝑛≤100000) 接下来n-1行，整数 𝑢𝑖 and 𝑣𝑖 ，表示两个点之间存在一条边 (1≤𝑢𝑖,𝑣𝑖≤𝑛,𝑢𝑖≠𝑣𝑖 )
输出： 每个样例一行，输出满足要求的最小操作次数。
Examples input 4 4 1 2 1 3 3 4 9 3 1 3 5 3 2 5 6 6 7 7 8 7 9 6 4 7 1 2 1 3 2 4 4 5 3 6 2 7 6 1 2 1 3 1 4 4 5 2 6
output 1 3 2 2
题目解析： 题目给出来的图，就比较好分析。 每次操作都会减少若干个节点，最终是从n个节点变成1个节点，这是一个节点数量单调递减的过程。 那么可以知道，每次应该尽可能多的去选择节点，比如说从根节点到叶子节点作为一条路径，我们每次选择两条最长的路径，组成一条当前树上的最长路径，进行合并。 但是这种做法，如何证明就是最优解？有没有可能局部最优会破坏全局最优。 在思索和这个过程的时候发现，沿着上面的思路，每次选择两条到叶子节点的路径，融合之后就会减少一个叶子节点。当不存在叶子节点的时候，就只剩下一个节点。 这个过程的最优性也比较容易保证，对于有m个叶子节点的树，每次操作只能减少2个叶子节点。最优解就是m/2。
剩下的问题，就是如何确定根节点？ 答案就是不需要根节点，从任意点出发，只有一个点相连就是叶子节点，计算叶子节点数量即可。
class Solution {
static const int N = 201010;
vector<int> g[N];
int dfs(int u, int fat) {
int ret = g[u].size() == 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (v == fat) continue;;
ret += dfs(v, u);
}
return ret;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i <= n; ++i) g[i].clear();
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cout << (dfs(1, 0) + 1) / 2 << endl;
}
}
}
ac;