程序员进阶之算法练习（六十八）
题目1
题目链接 题目大意： 有n个球，序号分别是1、2、3、、、、n，每个球上面有一个数字a[1]、a[2]、a[3]、、、a[n]，这组数字是不递减的，即是 a[i]≤a[i+1]， 1≤i<𝑛； 现在需要给n个球染色，需要满足： 1、每个球只有一个颜色； 2、将某个颜色的球挑选出来，按照序号从小到大放好，上面的数字是严格递增；
问，最少需要几个颜色。
输入： 第一行是𝑡，表示样例数 (1≤𝑡≤100) 每个样例两行，第一行是整数𝑛 (1≤𝑛≤100) 第二行是n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛)
输出： 每个样例一行，输出最少需要的颜色数量。
Examples input 5 6 1 1 1 2 3 4 5 1 1 2 2 3 4 2 2 2 2 3 1 2 3 1 1
output 3 2 4 1 1
题目解析： 由于本身数字就是不递减，要满足严格递增，只需要关注数字相同的部分； 相同数字的最大连续长度，就是需要的颜色数量。
int a[N];
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = 1, cur = 1;
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (i > 0) {
if (a[i] == a[i - 1]) {
++cur;
ans = max(ans, cur);
}
else {
cur = 1;
}
}
}
cout << ans << endl;
}
return 0;
}题目2
题目链接 题目大意： 小明喜欢0到9中的一个数字d，如果某个整数的十进制表示中，数字d只出现一次则称这个整数是lucky数； 比如说d=7的时候，17就是lucky数，77就不是lucky数； 现在给出q个整数，问给出的整数是否都能拆分为若干个lucky数之和；
输入： 第一行是样例数𝑡 (1≤𝑡≤9) 每个样例两行，第一行𝑞 and 𝑑 (1≤𝑞≤1e4, 1≤𝑑≤9). 第二行是𝑞个整数 𝑎1,𝑎2,…,𝑎𝑞 (1≤𝑎𝑖≤1e9). 输出： 每个样例有q行，每一行对应a[i]是否可以拆分为若干个lucky数之和；
Examples input 2 3 7 24 25 27 10 7 51 52 53 54 55 56 57 58 59 60
output YES NO YES YES YES NO YES YES YES YES YES YES NO
题目解析： 以7为例，如果数字大于77，那么必然有解：可以拆分为7x+若干个7的组合； 比如说77=70+7，100=7+7+7+7+72；
那么小于100的数字可以枚举，更大的数字必然有解。
int a[100][10]; // a[i][j]表示数字为i，幸运数字是j，是否有解
int main(int argc, const char * argv[]) {
// insert code here...
for (int i = 1; i < 100; ++i) {
for (int lucky = 1; lucky <= 9; ++lucky) {
bool ok = 0;
int tmp = i;
while (tmp) {
if (tmp % 10 == lucky) {
ok = 1;
break;
}
tmp /= 10;
}
a[i][lucky] = ok;
for (int k = 1; k <= i; ++k) {
if (a[k][lucky] && k + lucky < 100) {
a[k+lucky][lucky] = 1;
}
}
}
}
int t;
cin >> t;
while (t--) {
int q, d;
cin >> q >> d;
while (q--) {
int k;
cin >> k;
if (k >= 100) {
cout << "YES" << endl;
}
else {
cout << (a[k][d] ? "YES" : "NO") << endl;
}
}
}
return 0;
}题目3
题目链接 题目大意： n个数字的数组a，可以执行最多k次操作，每次操作是找两个数字，其中一个+1，另外一个-1； 想知道经过最多k次操作之后，数组最小的字典序是什么；
输入： 第一行是样例数𝑡 (1≤𝑡≤20) 每个样例两行，第一行是整数𝑛 and 𝑘 (2≤𝑛≤100, 1≤𝑘≤10000) 第二行是n个整数 𝑎1 , 𝑎2, …, 𝑎𝑛 (0≤𝑎𝑖≤100) 输出： 每个样例一行，要求所有数字非负，且 字典序最小；
Examples input 2 3 1 3 1 4 2 10 1 0
output 2 1 5 0 1
题目解析： 容易知道，要让字典序最小，那么就是让前面的数字尽可能小； 所以从左到右开始选择数字，让前面的数字优先-1，收益最大； 同理，当我们需要+1的时候，为了字典序最小，全部加到最末尾的整数即可；
class Solution {
static const int N = 100010;
public:
int n, m;
int a[N], b[N], c[N], ans[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n - 1; ++i) {
if (m >= a[i]) {
a[n - 1] += a[i];
m -= a[i];
a[i] = 0;
}
else {
a[n - 1] += m;
a[i] -= m;
m = 0;
}
}
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
cout << endl;
}
}
}
ac;题目4
题目链接 题目大意： 有n个整数的数组a，现在将数组分成两个集合，如果两个集合内的整数之和相等，则是不美好的； 现在希望去掉若干个数字，要求n个数字无法拆成两个集合，这两个集合的和是相等的。
输入： 第一行是整数𝑛 (2≤𝑛≤100) 第二行是n个整数𝑎1 , 𝑎2, …, 𝑎𝑛 (1≤𝑎𝑖≤2000) 输出： 第一行是需要移除的整数个数m，第二行是m个需要移除整数的下标；
Examples input 4 6 3 9 12 output 1 2
题目解析： 假设n个数字分成集合a[x]和b[y]，并且sum(a) = sum(b)，那么sum(a)=sum(n)/2。 最开始的想法是，如果sum(a)=sum(b)，那么只要去掉一个集合a或者b中的奇数，那么必然会出现sum(a)!=sum(b)； （因为奇数和偶数必定不相同） 问题就变成题目中是否存在一个解，使得sum(a)==sum(b) ： 如果有存在，则去掉n个数字中的奇数； 如果不存在，则不需要去掉任何数字；
注意，这里很容易产生误解：觉得去掉最小/最大的整数也是可行的。 例子： 4 4 6 6 8 8 去掉4之后可以拆分为 4 + 6 + 6 = 8 + 8 去掉8之后可以拆分为 4 + 4 + 6 = 6 + 8 直接找一个数字最小、最大都无法直接确定。
我们回到最初判断，我们会首先认为，如果sum(n)是奇数，则无解； 那么假如数组中存在一个奇数，我们只要去掉这个奇数即可。 那如果数组中一个奇数都没有呢？ 假如数组都是偶数，假设最终分出来的两个集合a和b，我们对两边的集合除以2，不影响sum(a)=sum(b)； 如果还是没有奇数，我们可以继续这样操作。容易知道，这样是一定可以找到一个奇数。 根据上面的思路，我们把每一个数字看成二进制，最右边1出现之后，就是奇数了。那么即是寻找n个数字中，最右边1最早出现的位置。
如果要判断n个数字中，能不能凑出来sum(n)/2的数字，这个不就是背包嘛。
class Solution {
static const int N = 101, M = 101*2000;
public:
int n, m;
int a[N], dp[M], ans[N];
int bitpos(int n) {
int pos = 0;
while (n % 2 == 0) {
n /= 2;
pos++;
}
return pos;
}
public:
void solve() {
cin >> n;
int sum = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum += a[i];
}
bool ok = 1;
if (sum % 2) {
ok = 0;
}
else {
sum /= 2;
dp[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = sum; j > 0; --j) {
if (j >= a[i]) {
dp[j] |= dp[j-a[i]];
}
}
}
ok = dp[sum];
}
if (ok) {
int minIndex = 0, minPos = bitpos(a[0]);
for (int i = 1; i < n; ++i) {
if (bitpos(a[i]) < minPos) {
minPos = bitpos(a[i]);
minIndex = i;
}
}
cout << 1 << " " << minIndex + 1 << endl;
}
else {
cout << 0 << endl;
}
}
}题目5
题目链接 题目大意： 有n * k个整数分别为 1、2、3、4、、、n * k，现在需要将这些整数分成n行，并且对于每一行都满足： 任意选择区间[l, r]，区间的平均数是整数； 问，是否存在这样的分配方式；
输入： 第一行，整数𝑡 表示t个样例 (1≤𝑡≤500) 每个样例一行，整数𝑛 and 𝑘 (1≤𝑛,𝑘≤500)
输出： 每个样例，如果无解则输出NO； 如果有解则输出YES，接下来n行分别输出k个数字；
Examples input 4 1 1 2 2 3 3 3 1
output YES 1 YES 1 3 2 4 NO YES 1 2 3
题目解析： 按照题目的要求，对于n行数字，每行数字的任意区间的平均数都是整数； 当区间长度为2时，（a[i][j] + a[i][j+1]）/ 2能够整除，那么必须是两个奇数或者两个偶数； 由此我们知道，当k>1的时候，肯定每一行数字都是奇数，或者都是偶数；（n=1或者k=1结果较为简单，这里不做讨论）
那么可以推断出， 如果nk是奇数，那么最终肯定会出现奇数个数字，无法满足要求； 当nk是偶数时，如果n是奇数，则k是偶数，那么在平均分配奇偶数的时候，必然会在第(n+1)/2行出现奇偶数混杂的情况，无法满足要求； 如果n是偶数，那么就可以按照1、3、5、7、、这样分配所有奇数，2、4、6、8这样分配所有偶数； 任意区间的平均数，都是中间两个数的平均值；
class Solution {
static const int N = 201010;
char str[N];
int dp[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
if (k == 1) {
cout << "YES" << endl;
for (int i = 0; i < n; ++i) {
cout << i + 1 << endl;
}
}
else if (n % 2) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
for (int i = 0; i < n / 2; ++i) {
int tmp = i * k * 2 + 1;
for (int j = 0; j < k; ++j) {
cout << tmp + j * 2 << " ";
}
cout << endl;
for (int j = 0; j < k; ++j) {
cout << tmp + 1 + j * 2 << " ";
}
cout << endl;
}
}
}
}
}腾讯云开发者
