程序员进阶之算法练习（六十五）
正文
题目1
题目链接 题目大意： 给出n个整数和整数x，问能否找到一个顺序： 按照这个顺序累加数字，中间不会出现数字和等于x； 已知n个整数互不相同。
输入： 第一行，整数 𝑡 表示样例数(1≤𝑡≤1000) 每个样例有2行，第一行 整数 𝑛 and 𝑥 (1≤𝑛≤100; 1≤𝑥≤1e4) 第二行 n个整数𝑤𝑖 (1≤𝑤𝑖≤100) 输出： 如果无解，直接输出NO； 如果有解，则输出YES，接下来一行输出n个整数，从左到右为累加顺序；
Examples input 3 3 2 3 2 1 5 3 1 2 3 4 8 1 5 5 output YES 3 2 1 YES 8 1 2 3 4 NO
题目解析： 如果最终结果等于x，那么不管如何调整，最终会有x出现，无解； 如果最终结果不等于x，那么就一定构造出来合理的顺序： 比如说[1, i]的和等于x，由于a[i]!=a[i+1]，那么将i和i+1的数字进行调换即可。
那么只需要从左到右遍历数组，不断累加中间的数字和sum； 假如sum==x，则判断数字是否用完，否则将后面的数字与当前任意一个位置交换，由于整数各不相同，交换之后必然sum!=x； 如果后面没有数字了，则无解。
class Solution {
static const int N = 100010;
public:
int n, x;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n >> x;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ok = 1, sum = 0;
for (int i = 0; i < n; ++i) {
sum += a[i];
if (sum == x) {
if (i == n - 1) {
ok = 0;
}
else {
swap(a[i], a[i + 1]);
break;
}
}
}
if (ok) {
cout << "YES" << endl;
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
cout << endl;
}
else {
cout << "NO" << endl;
}
}
}
}
ac;题目2
题目链接 题目大意： 给出n个等边直角三角形，问 能不能拼出来正方形。
输入： 第一行整数𝑡，表示样例数 (1≤𝑡≤1e4) 每个样例一行，整数𝑛 (1≤𝑛≤1e9) 输出： 每个样例一行，可以则输出YES，否则输出NO；
Examples input 3 2 4 6
output YES YES NO
样例解释： n=2时，可以拼出来正方形
n=4时，可以拼出来正方形
题目解析：
一个三角形面积是0.5，n个三角形的面积是n/2，假设最终能拼成三角形，则边长是 √(n/2)。
只要最终的边长 是三角形的边是1和√2的整数倍，则题目有解。
简化计算，我们已知
√(n/2) = 1*x
或者 √(n/2) = √2 * y
两边平方，有n/2=x*x 或者 n/2=2*y*y
所以只要求一下√(n/2)，看看最终能否找到x或者y即可。
class Solution {
static const int N = 100010;
public:
int n, x;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
if (n % 2) {
cout << "NO" << endl;
}
else {
n /= 2;
int t = sqrt(n), k = sqrt(n / 2);
if (t * t == n || k * k * 2 == n) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
}
}
}
ac;题目3
题目链接 题目大意： 有n个整数a[i]，需要将n个整数分成m组，要求每组数字和之差不超过x；
输入： 第一行整数𝑡，表示样例数 (1≤𝑡≤1000) 每个样例两行，第一行 整数𝑛, 𝑚, and 𝑥 (1≤𝑚≤𝑛≤1e5; 1≤𝑥≤1e4) 第二行n个整数ℎ𝑖 (1≤ℎ𝑖≤𝑥) 输出： 每个样例一行，如果有解则输出YES，接下来一行输出n个整数y[i]，表示每个数字归属y[i]组； 如果无解则输出NO；
Examples input 2 5 2 3 1 2 3 1 2 4 3 3 1 1 2 3 output YES 1 1 1 2 2 YES 1 2 2 3
题目解析： 有一个很重要的点，是所有的数字都比x小，那么必然可以满足题目要求，比如说下面这种方式： 从左到右放数字，每次从m组数字中，挑出数字和最小的一组，放入该数字； 由于放入之前数字和之差小于等于x，那么往最小数字和的分组放入数字，并且该数字小于等于x，可以知道最终仍满足数字和之差小于等于x； 用数学的方式来描述： 已知A<=B且A+x>=B，然后我们有数字t（t<=x） 那么必然有A+t <= B+x，也就是A+t和B之差仍不会超过x；
思考🤔： 从直觉来分析，每次选择m个分组中，数字和最小的分组，优先放入数字，这种是比较直接的策略，但是如果没有h[i]<X的限制呢？
class Solution {
static const int N = 100010;
public:
int n, m, x, tmp;
priority_queue<pair<lld, int> > top;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n >> m >> x;
while (!top.empty()) {
top.pop();
}
for (int i = 0; i < m; ++i) {
top.push(make_pair(0, i + 1));
}
cout << "YES" << endl;
for (int i = 0; i < n; ++i) {
cin >> tmp;
pair<lld, int> cur = top.top();
top.pop();
cur.first -= tmp;
top.push(cur);
printf("%d ", cur.second);
}
cout << endl;
}
}
}
ac;题目4
题目链接 题目大意： 商店里有n只袜子，每只袜子的颜色是c[i]；（这只袜子可能是左脚，也可能是右脚） 现在可以执行若干次操作，每次操作从下面3个选项中选择： 1、将某只袜子染色成任意颜色； 2、将一只左袜子改造成右袜子； 3、将一只右袜子改造成左袜子；
现在想知道最少执行多次操作，才能拼出n/2双袜子（一双袜子是左脚+右脚，并且颜色相同）；
输入： 第一行整数 𝑡 ，表示样例数 (1≤𝑡≤1000) 每个样例两行，第一行整数𝑛, 𝑙, and 𝑟 (2≤𝑛≤2⋅1e5; 𝑛 是偶数; 0≤𝑙,𝑟≤𝑛; 𝑙+𝑟=𝑛) 第二行是n个整数𝑐𝑖 (1≤𝑐𝑖≤𝑛)，前l个是左脚，后r个是右脚； 输出： 每个样例一行，输出最少的操作次数。
Examples input 4 6 3 3 1 2 3 2 2 2 6 2 4 1 1 2 2 2 2 6 5 1 6 5 4 3 2 1 4 0 4 4 4 4 3 output 2 3 5 3
题目解析： 先将左右袜子颜色一样的挑出来； 接着将相同颜色的left/right 组成一对，每对的代价是1；（将多的那一组，分给少的那一组）
假设剩下x只left，y只right，并且x和y没有相同的颜色，则剩下有两个花费： 1、花费abs(x-y)/2的差额，将left和right数量对齐； 2、花费（x+y)/2的费用，将一半的颜色和另外一半对齐；
题目5
题目链接 题目大意： 小明和n个朋友一起选课，一共有m门课，小明知道每个朋友喜欢的课程，并且每个人喜欢的课程数不会超过p； 现在想知道怎么选修课程，才能满足 至少有N/2（向上取整）个同学都喜欢他选择的课程；
输入： 第一行是整数 𝑛,𝑚 and 𝑝 (1≤𝑛≤2⋅1e5, 1≤𝑝≤𝑚≤60, 1≤𝑝≤15) 接下来n行，每行是m个0/1整数，1表示喜欢这个课程；
输出： 结果输出一行，m个0/1整数，1表示对这个课程的细化。
Examples input 5 5 4 11001 10101 10010 01110 11011 output 10001
题目解析： dp[i]表示小明选择了课程状态为i的喜欢人数，i表示为二进制，1则表示选中该课程。 那么把所有的选修与小明的喜欢状态进行与操作，得到state[1n]，然后dp[state[i]]++，这样dp[12^k]就可以表示为小明与所有人喜欢的最大交集的数量。 然后接下来就有dp[(100)2]+=dp[(101)2]等状态递归，原来是因为我们统计了和小明喜欢状态为101的人，自然可以累加到dp[100]上面，同时也可以累加到dp[001]上面。
另外只需要把小明喜欢的课程直接拿出来，离散化处理即可，非小明喜欢的直接去掉。 注意，状态压缩的时候，要考虑重复的情况，比如说111=>110,101 但是110和101都可以转移到100，所以如果先枚举状态，再枚举转移的状态位，会出现数据重复。
class Solution {
static const int N = 200010, M = 65, P = 16;
int bit_count(int k) {
int ret = 0;
while (k) {
ret += k%2;
k /= 2;
}
return ret;
}
public:
int n, m, p;
char str[N][M];
int ans;
bool ans_out[M];
int dp[1<<P];
int look(int k) { // 随机选择k
int ret = 0, cnt = 0;
for (int i = 0; i < m; ++i) {
cnt += str[k][i] == '1';
}
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; ++i) {
if (i != k) {
int state = 0;
for (int j = 0; j < m; ++j) {
if (str[k][j] == '1') { // 离散化处理，将i与k的交集，用state来表示
state = state * 2 + (str[i][j] == str[k][j]);
}
}
++dp[state];
}
}
int max_state = (1<<cnt) - 1;
++dp[max_state]; // 最大的状态，就是所有的数字都选中，k是所有子集都有
int tmp = 1;
while (tmp <= max_state) { // tmp是每次转移的书籍，从最小的状态1开始，到2、4、8等，每次只能转移一个，避免重复
int cur_state = max_state;
while (cur_state > 0) {
if (dp[cur_state] >= (n+1)/2) {
int cnt = bit_count(cur_state);
if (cnt > ans) { // 记录答案
ans = cnt;
int bit = 1;
for (int i = m - 1; i >= 0; --i) { // 注意这里是要逆序
if (str[k][i] == '0') {
ans_out[i] = false;
}
else {
ans_out[i] = bit & cur_state;
bit = bit * 2;
}
}
}
}
if (tmp & cur_state) {
dp[cur_state - tmp] += dp[cur_state];
}
--cur_state;
}
tmp = tmp * 2;
}
return ret;
}
public:
void solve() {
cin >> n >> m >> p;
for (int i = 0; i < n; ++i) {
scanf("%s", str[i]);
}
ans = 0;
// srand((unsigned long long)new char);
for (int i = 0; i < 100; ++i) {
look(rand()%n);
}
for (int i = 0; i < m; ++i) {
cout << (ans_out[i]?"1":"0");
}
cout << endl;
}
}
ac;腾讯云开发者
