程序员进阶之算法练习（一百）
新年伊始，终到百篇，龙年大吉。
题目1
题目链接 题目大意： 给出一个整数，问该整数能否切分为两个数字a和b，满足： 1、a和b都不包括前导零，是一个正常的数字； 2、a和b都大于0； 3、b > a；
如果可以，则输出数字a和b；如果不可以则输出-1；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行，单个整数 (数字长度为2~8)
输出： 每个样例一行，如果可以，则输出数字a和b；如果不可以则输出-1；
Examples input 5 20002001 391125 200200 2001000 12
output 2000 2001 39 1125 -1 200 1000 1 2
题目解析： 按照题目的要求，a要尽可能小，b要尽可能大。 由于题目给出的数字本身就合法，那么将第一个数字开始分为a，往后找到第一个非零的数字就分给b，这样b一定是最大的。 从字符串上切分好a和b，接下来就是转成数字。 这里为了便于计算，从字符串a右边开始往左边枚举每一个位置上的数字，就可以得到数字a。（数字b同理，也可以字符串切割后，用sscanf取巧）
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
int k = 1, n = str.length();
while (k < n) {
if (str[k] != '0') break;
++k;
}
if (k >= n) {
cout << -1 << endl;
continue;;
}
int x = 0, y = 0;
int tmp = k - 1, val = 1;
while (tmp >= 0) {
x += val * (str[tmp] - '0');
--tmp;
val *= 10;
}
tmp = n - 1, val = 1;
while (tmp >= k) {
y += val * (str[tmp] - '0');
--tmp;
val *= 10;
}
if (x < y) cout << x << " " << y << endl;
else cout << -1 << endl;
}
}
}
ac;题目2
题目链接 题目大意： 给出一个01字符组成的字符串𝑠，现在可以对字符串进行任意次下面操作： 1、删除字符串中的某个一个字符，代价为1； 2、调换两个位置上的字符，代价为0；
现在要求，若干次操作后的字符串t，t上面每一个字符都与原来字符串s的字符相反，比如说： s=011 那么t=10，最小操作代价是1，移除一个字符1，然后交换一次0、1的位置；
s=111100 那么t=00，最小操作代价是4，移除所有字符1；
问生成满足要求的字符串t，最小的代价是多少。（注意移除所有字符也满足要求）
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行，字符串𝑠 (1≤ |𝑠| ≤2⋅1e5）
输出： 每个样例一行，输出满足题目要求的最小代价；
Examples input 4 0 011 0101110001 111100
output 1 1 0 4
题目解析： 按照题目的要求，直接看最终字符串t的样式，比如说s=111100，那么t=001111； 那么只需要累计原来0、1的数字数量，然后从左到右枚举t的位置，直到剩下的字符无法填充，那么就得到t的最大长度； 得到t的最大长度k，那么需要移除的字符串长度就是n--k。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
int n = str.length(), x = 0, y = 0;
for (int i = 0; i < n; ++i)
if (str[i] == '0') ++x;
else ++y;
int k = 0, cntX = x, cntY = y;
while (k < n) {
if (str[k] == '0') {
if (y > 0) --y;
else break;
}
else {
if (x > 0) --x;
else break;
}
++k;
}
if (x + y == 0) {
cout << 0 << endl;
}
else {
cout << n - k << endl;
}
}
}
}
ac;题目3
题目链接 题目大意： 给出一个空的数组，现在有两个操作： 操作1，往数组添加一个数字2^x； 操作2，询问数组中的若干个数字，数字和是否可以为w；
输入： 第一行，整数𝑡 表示m个操作 (1≤m≤100000) 每个操作一行 操作1，是输入1和x (0≤x≤29 ). 操作2，是输入2和w；(0≤w≤1e9 ).
输出： 每个操作2输出一行，存在则输出YES，不存在输出NO；
Examples input 5 1 0 1 0 1 0 2 3 2 4
output YES NO
题目解析： 题目的数据范围简化了题目，首先x比较小，数组中最多只有30个整数类型，那么可以按照这个规则聚类； 其次，在判断数组是否存在某个元素和时，可以从大到小遍历数组，对于某个元素y如果小于等于当前w，则优先取用，并且w=w-y，直到数组末尾；如果此时w=0，则有解，否则无解；
class Solution {
static const int M = 536870912; // 2^29
int a[30];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int k, x;
cin >> k >> x;
if (k == 1) a[x]++;
else {
int cur = M;
for (int i = 29; i >= 0; --i) {
if (a[i] > 0 && x >= cur) {
int left = 1, right = a[i] + 1;
int find = left;
while (left < right) {
int mid = (left + right) / 2;
lld sum = 1LL * mid * cur;
if (sum > x) {
right = mid;
}
else {
find = mid;
left = mid + 1;
}
}
x -= find * cur;
}
cur /= 2;
}
cout << (x == 0 ? "YES" : "NO") << endl;
}
}
}
}
ac;题目4
题目链接 题目大意： 有两个整数n和k，n表示字符串长度，k表示字符串由前k个小写字符； 现在需要构造一个字符串s，要求任何长度为n的字符串，都是字符串s的子序列；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤676) 每个样例一行，整数n和k (1≤𝑛≤26 ) and (1≤𝑘≤26 ).
输出： 每个样例一行，输出字符串s，如果有多个则输出最短长度的字符串；
Examples input 4 1 2 2 1 2 2 2 3
output ab aa baab abcbac
题目解析： 题目的要求，所有常读为n的字符串，在拼接的时候就可以看成是n个选择，每次从k个字符中选择一个； 那么在构造的时候，可以采用这样的策略： 我们重复abc/abc/abc这样的字符串，每一组都相当有k个不同字符的桶。 这样构造出来的结果就能满足要求。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) putchar('a' + j);
}
cout << endl;
}
}
}
ac;题目5
题目链接 题目大意： 有一个正整数x，现在需要把x分成n个正整数，这些正整数之和是x； 现在要求，n个正整数的最大公约数，尽可能的大；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例一行，整数𝑥和 𝑛 (1≤𝑥≤1e8) and (1≤𝑛≤𝑥).
输出： 每个样例一行，输出最大的公约数。
Examples input 3 10 3 5 5 420 69
output 2 1 6
题目解析： 按照题目的要求，全部拆分成数字1，必然可以拆出满足要求： k-1个整数1，剩下的整数是x-n-1，这些整数的最大公约数是1；
同理，假如最大公约数是2，可以这么拆： k-1个整数2，剩下的整数是x-2n-2，最大的公约数是2；
也就是说，假设最大公约数是k，也可以这么安排：n-1个整数k，剩下是x-kn-k；
由于题目的范围不大，那么枚举最大公约数的数字就好。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int x, n;
cin >> x >> n;
int k = sqrt(x) + 1;
int ans = 1;
for (int i = 1; i <= k; ++i) {
if (x % i == 0) {
if (i >= n) ans = max(ans, x / i);
if (x / i >= n) ans = max(ans, i);
}
}
cout << ans << endl;
}
}
}
ac;