腾讯笔试-04-24

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_map>
#include <unordered_set>

bool cmp(std::string &a, std::string &b) {
    if (a.size() != b.size()) {
        return a.size() < b.size();
    }

    return a < b;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n; 

    std::vector<std::string> b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
        m = b[i].size();
    }

    std::vector<std::string> v(m);
    for (int i = 0; i < m; i++) {
        std::string temp;
        bool ok = false;
        for (int j = 0; j < n; j++) {
            if (b[j][i] != '0') {
                ok = true;
            }
            if (ok) {
                temp += b[j][i];
            }
        }
        if (temp.size() == 0) {
            temp = "0";
        }
        v[i] = temp;
    }

    std::sort(v.begin(), v.end(), cmp);
    for (const auto &x : v) {
        std::cout << x << " ";
    }
    std::cout << "\n";

    return 0;
}

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_map>
#include <unordered_set>

const int MAX_N = 200010;

int primes[MAX_N], vis[MAX_N], cnt;

void init() {
    vis[1] = true;
    for (int i = 2; i < MAX_N; i++) {
        if (!vis[i]) {
            primes[cnt++] = i;
        }
        for (int j = 0; j < cnt && primes[j] * i < MAX_N; j++) {
            vis[primes[j] * i] = 1;
            if (i % primes[j] == 0) {
                break ;
            }
        }
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a int整型vector 
     * @return int整型
     */
    int getNumber(std::vector<int>& a) {
        // write code here
        init();


        while (true) {
            if (a.size() == 1) {
                break ;
            }
            std::vector<int> now;
            for (int i = 1; i <= a.size(); i++) {
                //std::cout << i << " " << vis[i] << "\n";
                if (!vis[i]) {
                    now.emplace_back(a[i - 1]);
                }
            }
            a = now;
        }


        return a[0];
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    Solution s;
    std::vector<int> v{3, 1, 1, 4, 5, 6};
    std::cout << s.getNumber(v) << "\n";

    return 0;
}

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_map>
#include <unordered_set>

const long long INF = 0x3f3f3f3f3f3f3f3f;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::string t;
    std::cin >> t;

    std::vector<long long> s1(n + 1), s0(n + 1);
    for (int i = 1; i <= t.size(); i++) {
        s1[i] = s1[i - 1];
        s0[i] = s0[i - 1];
        if (t[i - 1] == '1') {
            s1[i] += i;
        } else {
            s0[i] += i;
        }
    }

    long long ans = INF;
    ans = std::min(ans, s1[n]);
    for (int i = 1; i <= n; i++) {
        long long left = s0[i];
        long long right = s1[n] - s1[i];
        long long temp;
        if (left - right < 0) {
            temp = right - left;
        } else {
            temp = left - right;
        }
        ans = std::min(ans, temp);
    }

    std::cout << ans << "\n";

    return 0;
}

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_map>
#include <unordered_set>

struct ListNode {
    int val;
    struct ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

const int INF = 0x3f3f3f3f;

class Solution {
public:
    bool cmp(ListNode *l1, ListNode *l2) {
        for (auto i = l1, j = l2; i; i = i->next, j = j->next) {
            if (i->val < j->val) {
                return true;
            }
        }
        return false;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a ListNode类vector 指向每段碎片的开头
     * @return ListNode类
     */
    ListNode* solve(std::vector<ListNode*>& a) {
        // write code here
        if (a.empty()) {
            return nullptr;
        }

        std::unordered_map<int, int> pre;
        for (auto l : a) {
            auto last = l->val;
            l = l->next;
            while (l) {
                pre[l->val] = last;
                last = l->val;
                l = l->next;
            }
        }

        std::unordered_map<int, ListNode*> dict;
        for (const auto &it : pre) {
            dict[it.first] = new ListNode(it.first);
        }

        auto res = new ListNode(-1);
        auto ans = res;
        int minVal = INF;
        ListNode* begin = nullptr;

        for (const auto &it : dict) {
            if (it.first < minVal) {
                minVal = it.first;
                begin = it.second;
            }
        }

        for (const auto &it : pre) {
            dict[it.second]->next = dict[it.first];
        }

        auto cur = begin;
        res->next = new ListNode(cur->val);
        res = res->next;
        cur = cur->next;

        while (cur->val != minVal && cur) {
            res->next = new ListNode(cur->val);
            res = res->next;
            cur = cur->next;
        }

        // 逆时针
        std::unordered_map<int, int> pre1;
        for (auto l : a) {
            auto last = l->val;
            l = l->next;
            while (l) {
                pre1[last] = l->val;
                last = l->val;
                l = l->next;
            }
        }

        std::unordered_map<int, ListNode*> dict1;
        for (const auto &it : pre1) {
            dict1[it.first] = new ListNode(it.first);
        }

        auto res1 = new ListNode(-1);
        auto ans1 = res1;
        minVal = INF;
        ListNode* begin1 = nullptr;

        for (const auto &it : dict1) {
            if (it.first < minVal) {
                minVal = it.first;
                begin1 = it.second;
            }
        }

        for (const auto &it : pre1) {
            dict1[it.second]->next = dict1[it.first];
        }

        auto cur1 = begin1;
        res1->next = new ListNode(cur1->val);
        res1 = res1->next;
        cur1 = cur1->next;

        while (cur1->val != minVal && cur1) {
            res1->next = new ListNode(cur1->val);
            res1 = res1->next;
            cur1 = cur1->next;
        }
        
        //return ans1->next;
        
        auto l1 = ans->next, l2 = ans1->next;
        while (l1) {
            if (l1->val < l2->val) {
                return ans->next;
            } else if (l1->val > l2->val) {
                return ans1->next;
            }
            l1 = l1->next;
            l2 = l2->next;
        }

        return ans->next;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    return 0;
}

#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <array>

int n, m;
long long ans;

void dfs(int u, long long sum, std::vector<int> &v, int left) {
    if (u == n) {
        ans = std::max(ans, sum + 1ll * left * v[n - 1]);
        return ;
    }

    dfs(u + 1, sum, v, left);
    if (sum >= v[u]) {
        dfs(u + 1, sum - v[u], v, left + 1);
    }
    if (left) {
        dfs(u + 1, sum + v[u], v, left - 1);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n >> m;

    std::vector<int> v(n);
    for (int i = 0; i < n; i++) {
        std::cin >> v[i];
    }

    ans = m;
    dfs(0, m, v, 0);

    std::cout << ans << "\n";

    return 0;
}