1、1734C Removing Smallest Multiples
题意：
给予你一个数组S，其中包含前n个正整数
你可以在S上执行以下操作任多次（包含0次）：
1、选择一个正整数i，（1 <= k <= n）,并且使得数组S中存在k的倍数，然后删除k的最小倍数，这次操作的成本是k
给你一个集合T,他是S的子集，求使S转换成T所需的最小操作成本，我们可以证明这种操作一定是可行的
思路：
假设现在操作的是i（1 <= i <= n），i是一定在S中存在的，但是i不一定在T中存在， 所以
1、当i在T中存在时，直接continue就行
2、当i不在T中存在时，需要从S中删除掉，此时的i可以被他的因数j删除掉，此时就需要考虑被那个符合条件并且不起冲突的因数删除，（由此可见是一个贪心问题），可以进行反向贪心枚举每个数可以用了删除那些数，反向枚举，cost[i]的值会被变的尽可能的最小
删除规定
当考虑数i可以删除那些数的时候
1、当i在T中存在是，由于每次删除只能删除这个数的最小倍数，此时最小是1倍，并且他不需要删除，所以此时i并不可以用来删除任何一个数
2、当i在T中不存在的首，由于没有1倍的数，所以此时S中存在的最小倍数是2倍，删除2 * i之后，S中最小的是3 * i可以一次删除下去，但是当3 * i在T中存在时，由于3 * 不可被删除，所以之后的4 * i和5 * i之后就不能被删除
时间复杂度是：O（nlogn）
代码；
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int a[N];
int cost[N];
void solve() {
int n;
scanf("%d", &n);
memset(cost, 0, sizeof cost);
for (int i = 1; i <= n; i ++ ) {
scanf("%1d", &a[i]);
}
ll ans = 0;
for (int i = n; i >= 1; i -- ) {
for (int j = i; j <= n; j += i) {
if(a[j]) break;
cost[j] = i;
}
}
for (int i = 1; i <= n; i ++ ) {
if(!a[i]) ans += cost[i];
}
printf("%lld\n", ans);
}
int main() {
int t;
scanf("%d", &t);
while (t -- ) {
solve();
}
return 0;
}
2、1733D1 Zero-One (Easy Version)
题意:
这个题是一个题的简单模式，给予你两个二进制字符串，长度n < 3000并且x >= y,你可以进行一下操作任意次数（可以是0次）
1、选择两个节点 l 和 r （l < r）
2、将a[l]改为 1 - a[l]并且将a[r]改为1 - a[r]
3、如果l + 1 = r这个代价就是x，相反的话代价就是y
你需要找到最小的花费使得字符字符串a和字符串b相同（多组输入输出）
思路：
注意每次操作后，a和b的不同的位数，要么是+2，-2要么不变，可以看出，要想a变成b，当且仅当a和b不同的位数是偶数
对于每次操作应当尽可能的使用花费少的操作，由于选择具有不确定性（可以随便选），为了达到固定少花费的情况，此题是简单版本，花费最少是y，所以我们就尽量的不选择相邻的来进行转换，为了更好的控制花费，此时需要a[1]和a[n]的作用，对于每个i（a[i] != b[i]）的话，若是使用a[1]和a[n]来进行不断的切换其中一个，使得所有的转换都是以最小花费进行
时间复杂度；O（1）
拓展：这个是可以通过找规律看出来的，这个是简单版本，还是有一个难的版本，更加标准的做法是使用记忆化dp（奈何dp学的太浅）这里推荐一个大佬的链接 [https://zhuanlan.zhihu.com/p/566175996]
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;
char s[N], p[N];
void solve() {
ll n, x, y;
cin >> n >> x >> y;
cin >> s + 1;
cin >> p + 1;
vector<int> vt;
for (int i = 1; i <= n; i ++ ) {
if(s[i] != p[i]) vt.push_back(i);
}
if(vt.size() == 0) {
cout << 0 << "\n";
return ;
}
if(vt.size() % 2 != 0) cout << -1 << "\n";
else {
if(vt.size() >= 4)
cout << y * (vt.size() / 2) << "\n";
else {
//容器中只有2个代表位置的元素
if(abs(vt[0] - vt[1]) != 1) cout << y << "\n";
else {
if(2 * y >= x) cout << x << "\n";
else cout << 2 * y << "\n";
}
}
}
}
int main() {
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
3、1733C Parity Shuffle Sorting
题意：
给予你一个长度时b，只包含非负整数元素的数组，你可以进行一下操作：
1、选择两个节点l和r（1 <= l <= r <= n）
2、如果a[l] + a[r]是偶数，则使得a[r] = a[l],否则的使得a[l] = a[r]
使用一些操作使得这个长度为n的数组a为非递减数组，被证明是肯定可以实现的，注意这里不是让你求出最小需要进行的操作次数
一个非递减数组的意思是，当且仅当a[1] <= a[2] <= a[3] <= a[4] ...<= a[n]。
思路：
这里强调了非递减数组，全等数组同样也是非递减数组，可以通过这个方向解决问题，先让1和n节点进行操作，使得两则相同，让后用着两个点来同化所以的点，知道整个数组中的元素都相同
时间复杂度：O（n）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int main() {
int t;
cin >> t;
while (t -- ) {
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
cout << n - 1 << endl;
if(n > 1) cout << 1 << ' ' << n << endl;
int x = (a[1] + a[n]) % 2 ? a[1] : a[n];
for (int i = 2; i < n; i ++ ) {
if((x + a[i]) % 2) cout << 1 << " " << i << endl;
else cout << i << " " << n << endl;
}
}
return 0;
}
4、1730C Minimum Notation
题意：
给予你一个只包含0-9的字符串，你可以进行一下操作任意次数
1、你可以选择一个位置i，并删除这个位置上的元素值d，然后插入一个值min(d + 1, 9）在任何位置（可以在开头，也可以在结尾，也可以在任意两个位置之间）
通过执行这些操作，你能得到的词典最小的字符串是什么？
（对于词典最小顺序得到的串进行了一些解释）
思路：
思路分析:我们先观察样例可知,设置一个后缀数组 past[N]记录对于位置 i ，是否在其后面的位置存在比 s[i]更小的数.若存在比 s[i]更小的数,我们应该将其取下后变成 char(s[i]+1),或者不变( s[i]=='9' )放置在新的字符串 s1 ,将 s1 排序后输出即可
时间复杂度：O（n）
代码：
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N = 2e5 + 5;
int a[N];
char s[N];
int vis[N];
int w[N];
void solve() {
scanf("%s", s + 1);
int len = strlen(s + 1);
vector<int> vt[10];
for (int i = 1; i <= len; i ++ ) {
vt[(s[i] - '0')].push_back(i);
}
int ans = 0;
int temp = -1;
for (int i = 0; i <= 9; i ++ ) {
// if(vt[i].size() == 0) continue;
for (int j = 0; j < vt[i].size(); j ++ ) {
if(vt[i][j] >= temp) {
a[ ++ ans] = i;
temp = vt[i][j];
}
else {
if(i == 9) a[ ++ ans] = i;
else a[ ++ ans] = i + 1;
}
}
}
sort (a + 1, a + 1 + ans);
for (int i = 1; i <= ans; i ++ ) {
cout << a[i];
}
printf("\n");
}
int main() {
int t;
scanf("%d", &t);
while (t -- ) {
solve();
}
return 0;
}
5、1729 Friends and the Restaurant
题意：
一群n个朋友决定去餐馆吃饭每一个朋友计划带你x[i]个菜，一共点y[i]个菜
朋友们决定把去餐馆的时间分成几天，每天至少有两个朋友为一组去餐馆，每个朋友都不超过一次光顾这家餐馆（也就是说，这些朋友不想交），这些小组必须满足这些条件，及每组的总预算不得低于朋友们在餐厅花的预计费用，换句话说就是，每个组的x[i]总和不得超过组中y[i]的总和，朋友最多停留几天在餐馆
思路：每个组中的x[i]的总值不得超过y[i]的总值，将每个人按照 y[i] - a[i]来进行排序，让最富裕的人来和最贫穷的人进行组队，互相中和以达到去餐厅的组数尽量的多，使用双指针算法来完成
时间复杂度：双指针算法O（n）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct node {
int a, b;
int cha;
}s[N];
bool cmp(node a, node b) {
return a.cha < b.cha;
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> s[i].a;
for (int i = 1; i <= n; i ++ ) cin >> s[i].b;
for (int i = 1; i <= n; i ++ ) {
s[i].cha = s[i].b - s[i].a;
// cout << s[i].cha << endl;
}
sort (s + 1, s + 1 + n, cmp);
int l = 1, r = n;
int sum = 0;
while (l < r) {
while (s[l].cha + s[r].cha < 0) {
l ++ ;
if(l >= r) break;
}
if(s[l].cha + s[r].cha >= 0 && l != r) sum ++ ;
r -- ;
l ++ ;
}
cout << sum << endl;
}
int main() {
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}