正文

题目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[1_{n]，然后dp[state[i]]++，这样dp[1}2^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;