4-18腾讯笔试

#include <cstdio>
#include <climits>

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

using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
};

class Solution {
public:
    ListNode* solve(ListNode* list) {
        if (!list) return list;
        using ListPair = pair<ListNode**, ListNode**>;
        ListNode **t;
        vector<ListPair> min_list;
        for (t = &list; *t; t = &(*t)->next) {
            ListNode **next = &(*t)->next;
            min_list.emplace_back(next, next);
        }
        *t = list;  /* 循环 */
        int list_size = min_list.size();
        while (min_list.size() != 1) {
            vector<ListPair> tmp;
            int min_val = INT_MAX;
            int min_cnt = 0;
            for (unsigned i = 0; i < min_list.size(); ++i) {
                auto lp = min_list[i];
                int v = (*lp.second)->val;
                if (v < min_val) {
                    min_val = v;
                    min_cnt = 1;
                    tmp.clear();
                    tmp.emplace_back(lp.first, &(*lp.second)->next);
                } else if (v == min_val) {
                    ++min_cnt;
                    tmp.emplace_back(lp.first, &(*lp.second)->next);
                }
            }

            /* 全部一样 */
            if (min_cnt == list_size) {
                *t = nullptr;
                return list;
            }
            min_list.swap(tmp);
        }
        list = *min_list.back().first;
        *min_list.back().first = nullptr;
        return list;
    }
};

ListNode* create_list(vector<int>& arr)
{
    ListNode* list = nullptr;
    for (int i = arr.size()-1; i >= 0; --i) {
        ListNode* node = new ListNode;
        node->val = arr[i];
        node->next = list;
        list = node;
    }
    return list;
}

void print_list(ListNode* list)
{
    for (; list; list = list->next)
        printf("%d ", list->val);
    printf("\n");
}

void free_list(ListNode* list)
{
    ListNode* next;
    for (; list; list = next) {
        next = list->next;
        delete list;
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
    Solution slv;
    auto list = create_list(arr);
    print_list(list);
    list = slv.solve(list);
    print_list(list);
    free_list(list);
    return 0;
}

struct User {
    User(int id, int gap, int t) : id_(id), gap_(gap), t_(t) {
    }
    int id_;
    int gap_;
    int t_;
};

struct user_greater {
    bool operator()(User const& lhr, User const& rhs) {
        return lhr.t_ > rhs.t_ || (lhr.t_ == rhs.t_ && lhr.id_ > rhs.id_);
    }
};

int main()
{
    int n, k;
    cin >> n >> k;
    priority_queue<User, vector<User>, user_greater> pq;
    int gap;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &gap);
        pq.emplace(i, gap, gap);
    }

    while (k--) {
        auto pr = pq.top();
        pq.pop();
        printf("%d\n", pr.id_);
        pq.emplace(pr.id_, pr.gap_, pr.t_ + pr.gap_);
    }

    return 0;
}

#define STR_MAX (int)(1e5+5)

bool str_equal(char* str1, int len1, char* str2, int len2)
{
    if ((len1&1) && (len2&1) && (len1 == len2) && (0 == strncmp(str1, str2, len1)))
        return true;
    if (!(len1&1) && !(len2&1)) {
        len1 /= 2;
        len2 /= 2;
        return (str_equal(str1, len1, str2, len2) && str_equal(str1+len1, len1, str2+len2, len2))
            || (str_equal(str1, len1, str2+len2, len2) && str_equal(str1+len1, len1, str2, len2));
    }
    return false;
}

int main()
{
    int t;
    cin >> t;
    char str1[STR_MAX], str2[STR_MAX];
    while (t--) {
        scanf("%s", str1);
        scanf("%s", str2);
        printf("%s\n", str_equal(str1, strlen(str1), str2, strlen(str2))?  "YES": "NO");
    }
    return 0;
}

int n, m, tm;
vector<vector<int>> mp;
int rst = 0;

void dfs(int r0, int c0, int r, int c, int t, int g)
{
    //printf("(%d %d) (%d %d) %d %d\n", r0, c0, r, c, t, g);
    int dir[4][2] = {
        {0, 1}, {1, 0}, {-1, 0}, {0, -1},
    };
    if (r == n-1 && c == m-1 && tm == t) {
        rst = max(g, rst);
        return;
    }
    if (tm == t) return;
    t += 1;
    for (int i = 0; i < 4; ++i) {
        int rr = r+dir[i][0];
        int cc = c+dir[i][1];
        if (0 <= rr && rr < n && 0 <= cc && cc < m && (rr != r0 || cc != c0)
                && (n-rr-1 + m-cc-1 <= tm-t) && (tm-t+g > rst))
            dfs(r, c, rr, cc, t, g + (t%mp[rr][cc] == 0));
    }
}

int main()
{
    cin >> n >> m >> tm;
    mp = vector<vector<int>>(n, vector<int>(m));
    for (int r = 0; r < n; r++)
        for (int c = 0; c < m; c++)
            scanf("%d", &mp[r][c]);
    dfs(0, 0, 0, 0, 0, 0);
    printf("%d\n", rst);
    return 0;
}