程序员进阶之算法练习（七十五）
题目1
题目链接 题目大意： 给出整数n、a、b，询问是否存在由数字1到n组成的排列p和q，满足下面条件： 排列p和q的最长公共前缀长度是a； 排列p和q的最长公共后缀长度是b；
如果排列p和q存在，则输出Yes，否则输出No；
输入： 第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤1000) 每个样例一行 整数 𝑛, 𝑎, and 𝑏 (1≤𝑎,𝑏≤𝑛≤100).
输出： 每个样例一行，如果排列p和q存在，则输出Yes，否则输出No；
Examples input 4 1 1 1 2 1 2 3 1 1 4 1 1 output Yes No No Yes
题目解析： 有题目的意思可以知道，通常情况下，应该是a+b+c=n，其中a是公共前缀、b是公共后缀、c是中间部分。 那么有c=n-a-b，如果c>=2，那么只需要将c最左和最右部分的数字进行调换即可。 比如说n=6,a=2,b=2，那么有排列[1,2,3,4,5,6]，其中[1,2]是前缀，[5,6]是后缀，那么只需要将[3,4]调转得到[4,3]，最终生成新的排列[1,2,4,3,5,6]这样即可。
特殊情况，当a=b=n时，也是一种有解的方案。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, a, b;
cin >> n >> a >> b;
if ((n == a && n == b) || (n - a - b >= 2)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
}
ac;题目2
题目链接 题目大意： 有n个整数的数组，这些数字形成一个环，其中第1个和第n个相连； 初始化的时候，没有任何两个相邻数字相同，现在小明可以执行一个操作： 从数组中选择一个位置并移除该元素，剩下的元素继续形成一个环，如果有两个相邻元素的数字相同，则会随机消除其中一个数字，继续形成新的环； 以数组[1,2,4,2,3,2]为例，假如移除数字4，则形成环[1,2,2,3,2]；由于[2,2]相邻数字相同，会随机消除一个数字，则形成环[1,2,3,2]； 问，小明最多执行多少次操作。
输入： 第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤100) 每个样例第一行 整数 𝑛 (1≤𝑛≤100) 第二行是整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛)
输出： 每个样例一行，输出小明最大的操作次数。
Examples input 3 4 1 2 3 2 4 1 2 1 2 1 1 output 4 3 1
题目解析： 题目咋一看会比较难处理，尤其是消除数字之后形成新的环，每次可以选择的数字比较多； 那先简化下题目，将题目的给出数字抽象成1、2、3；（即使给出的是1、4、9，我们用1、2、3来替代也等价） 当只有1个数字时，结果是1； 有2个数字时，由于没有相邻元素相同，给出的数字必须是1、2、1、2、1、2，这样的形式，结果一定是n/2+1； 有3个数字时，我们以3为准，比较容易找出1、2、3或者2、1、3或者3、2、1等的序列，比如说数字32121321，我们只要看着3去消除右边的数字，肯定不会产生新的相邻相同元素；并且我们要保证数组中遗留3个元素，最终肯定可以完整消除，结果是n； 有4个数字时，类似3；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
map<int, int> h;
for (int i = 0; i < n; ++i) {
cin >> a[i];
h[a[i]] = 1;
}
if (h.size() == 1) cout << 1 << endl;
else if (h.size() > 2) cout << n << endl;
else cout << n / 2 + 1 << endl;
}
}
}
ac;题目3
题目链接 题目大意： 给出n个整数的数组，现在可以对数据进行多次操作； 每次操作可以选择两个元素a[i]或者a[j]，如果a[i]和a[j]相同，则可以把其中一个元素改为0，如果不相同则可以令较大值改为较小值；（i != j） 现在想知道，最少需要多少次操作，才能将整个数组变为0；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例俩行，第一行 整数 𝑛 (2≤𝑛≤100) 第二行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤100)
输出： 每个样例一行，最少的操作次数；
Examples input 3 3 1 2 3 3 1 2 2 3 1 2 0 output 4 3 2
题目解析： 由于题目的要求是将元素变成0，假如数组中存在元素0，那么每次操作可以把1个非零整数变成0，答案就是非0数量； 如果没有0，则看是否有元素相同，有的话只需增加1次操作，产生1个0之后，就可以重复上面的过程； 如果没有相同元素，那么就再增加1次操作，产生2个数值相同的元素，再重复上面的过程；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
int same = 0;
for (int i = 1; i < n; ++i) {
if (a[i] == a[i - 1]) {
same = 1;
}
}
int zero = 0;
for (int i = 0; i < n; ++i) {
zero += (a[i] == 0);
}
int ans;
if (zero > 0) {
ans = n - zero;
}
else if (same > 0) {
ans = n;
}
else {
ans = n + 1;
}
cout << ans << endl;
}
}
}
ac;题目4
题目链接 题目大意： 给出一个偶数长度的字符串，由0和1组成； 将字符串中相同字符组成的子串切分出来，比如说11001111可以切成 11、00 和 1111； 如果切出来的子串长度都是偶数，这个字符串就是good；
现在可以修改字符串中的字符，每次可以将某个位置的字符从0变成1，或者从1变成0； 问最少修改几次，才能将字符串修改成good；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例俩行，第一行 整数 𝑛表示字符串长度 (2≤𝑛≤1e5) 第二行字符串s；
输出： 每个样例一行，最少的操作次数；
Examples input 5 10 1110011000 8 11001111 2 00 2 11 6 100110 output 3 0 0 0 3
题目解析： good字符串，就是由多个长度为偶数的字符串组成； 那么对于字符串中的第1、2个元素，只要保证两个元素是相同，那么不管后面的3、4号元素是什么字符，都不会对good字符串的定义产生影响： 因为偶数+偶数=偶数；
于是题目简化为，将字符串两两切分，要保证所有子串的字符相同； 那么01和10需要修改1次，00和11不需要修改；
class Solution {
static const int N = 201010;
string str;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> str;
int ans = 0;
for (int i = 0; i < n; i += 2) {
if (str[i] != str[i + 1]) {
++ans;
}
}
cout << ans << endl;
}
}
}
ac;题目5
题目链接 题目大意： 给出一个偶数长度的字符串，由0和1组成； 将字符串中相同字符组成的子串切分出来，比如说11001111可以切成 11、00 和 1111； 如果切出来的子串长度都是偶数，这个字符串就是good；
现在可以修改字符串中的字符，每次可以将某个位置的字符从0变成1，或者从1变成0； 问最少修改几次，才能将字符串修改成good；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例俩行，第一行 整数 𝑛表示字符串长度 (2≤𝑛≤1e5) 第二行字符串s；
输出： 每个样例一行，最少的操作次数；
Examples input 5 10 1110011000 8 11001111 2 00 2 11 6 100110 output 3 0 0 0 3
题目解析： good字符串，就是由多个长度为偶数的字符串组成； 那么对于字符串中的第1、2个元素，只要保证两个元素是相同，那么不管后面的3、4号元素是什么字符，都不会对good字符串的定义产生影响： 因为偶数+偶数=偶数；
于是题目简化为，将字符串两两切分，要保证所有子串的字符相同； 那么01和10需要修改1次，00和11不需要修改；
题目增加要求，要输出最少的数量，容易知道当字符串为01和10的时候，结果可以是00，也可以是11； 当字符串为00和11的时候，结果无法修改； 可以得到状态转移方程：（dp[N][2], dp[i][0]表示第i个字符以0结尾，dp[i][1]第i个字符以1结尾) 01和10的情况有： dp[i/2][0] = min(dp[i/2 - 1][0], dp[i/2 - 1][1] + 1); dp[i/2][1] = min(dp[i/2 - 1][1], dp[i/2 - 1][0] + 1); 11和00的情况只能有dp[i/2][1]和dp[i/2][0]的值；
class Solution {
static const int N = 201010;
string str;
int dp[N][2];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> str;
int ans = 0;
for (int i = 0; i < n; i += 2) {
if (str[i] != str[i + 1]) {
++ans;
}
}
if (str[0] == str[1]) {
dp[0][0] = dp[0][1] = N;
dp[0][str[0] - '0'] = 1;
}
else {
dp[0][0] = dp[0][1] = 1;
}
for (int i = 2; i < n; i += 2) {
if (str[i] == str[i + 1]) {
dp[i/2][0] = dp[i/2][1] = N;
if (str[i] == '0') {
dp[i/2][0] = min(dp[i/2 - 1][0], dp[i/2 - 1][1] + 1);
}
else {
dp[i/2][1] = min(dp[i/2 - 1][1], dp[i/2 - 1][0] + 1);
}
}
else {
dp[i/2][0] = min(dp[i/2 - 1][0], dp[i/2 - 1][1] + 1);
dp[i/2][1] = min(dp[i/2 - 1][1], dp[i/2 - 1][0] + 1);
}
}
cout << ans << " " << min(dp[n/2 -1][0], dp[n/2 - 1][1]) << endl;
}
}
}
ac;