题目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;
