头像

春春打飞舞




离线:1小时前


最近来访(369)
用户头像
ㅤ煜
用户头像
茈.
用户头像
何其明
用户头像
夕暮
用户头像
kzyz
用户头像
顽童
用户头像
Spare
用户头像
重生带我走
用户头像
全球化
用户头像
肉多多
用户头像
AuroraY
用户头像
papapiu
用户头像
守仁
用户头像
柒月栗子
用户头像
yxc的小迷妹
用户头像
天依
用户头像
sdsdsdsdds
用户头像
H小轩
用户头像
Goku74
用户头像
雪落之声


#define eb emplace_back
#define all(x) x.begin(), x.end()

class Solution {
public:
    vector<string> alertNames(vector<string>& names, vector<string>& times) {
        int n = names.size();
        map<string, vector<int>> ts;
        for (int i = 0, h, m; i < n; i ++ ) {
            auto s = names[i];
            sscanf(times[i].c_str(), "%d:%d", &h, &m);
            ts[s].eb(h * 60 + m);
        }
        vector<string> res;
        for (auto &[k, v]: ts) {
            sort(all(v));
            int m = v.size();
            if (m <= 2) continue;
            for (int i = 0; i + 2 < m; i ++ )
                if (v[i + 2] - v[i] <= 60) {
                    res.eb(k);
                    break;
                }
        }
        sort(all(res));
        return res;
    }
};


活动打卡代码 AcWing 167. 木棒

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <numeric>

#define endl '\n'

#define all(x) x.begin(), x.end()

using namespace std;

int main()
{
    int n, sum, len;
    vector<int> a, st;

    function<bool(int, int, int)> dfs = [&](int u, int s, int last) {
        if (u * len == sum) return true;
        if (s == len) return dfs(u + 1, 0, 0);

        for (int i = last; i < n; i ++ ) {
            if (st[i] or s + a[i] > len) continue;

            st[i] = 1;
            if (dfs(u, s + a[i], i + 1)) return true;
            st[i] = 0;

            if (!s or s + a[i] == len) return false;

            int j = i;
            while (j < n and a[j] == a[i]) j ++ ;
            i = j - 1;
        }
        return false;
    };

    function<void()> solve = [&]() {
        a = vector<int>(n);
        for (int i = 0; i < n; i ++ ) cin >> a[i];

        sort(all(a), greater<>());
        sum = accumulate(all(a), 0);

        st = vector<int>(n);

        len = 1;
        while (true)
        {
            if (sum % len == 0 and dfs(0, 0, 0))
            {
                cout << len << endl;
                return;
            }
            len ++ ;
        }
    };

    while (cin >> n, n) solve();

    return 0;
}

洛谷 AC

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <numeric>

#define endl '\n'

using namespace std;

const int N = 66;

int n, sum, len;
int a[N], st[N];

bool dfs(int u, int s, int last)
{
    if (u * len == sum) 
    {
        printf("%d\n", len);
        exit(0);
    }
    if (s == len) return dfs(u + 1, 0, 0);

    for (int i = last; i < n; i ++ ) 
    {
        if (st[i] or s + a[i] > len) continue;

        st[i] = 1;
        if (dfs(u, s + a[i], i + 1)) return true;
        st[i] = 0;

        if (!s or s + a[i] == len) return false;

        while (i + 1 < n and a[i] == a[i + 1]) i ++ ;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) 
    {
        scanf("%d", a + i);
        sum += a[i];
    }

    sort(a, a + n, greater<>());

    len = a[0];
    while (len * 2 <= sum)
    {
        if (sum % len == 0 and dfs(0, 0, 0)) return 0;
        len ++ ;
    }

    printf("%d\n", sum);

    return 0;
}



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if (!root->left and !root->right) return root->val;
        int l, r;
        if (root->left) l = evaluateTree(root->left);
        if (root->right) r = evaluateTree(root->right);
        if (root->val == 2) return l or r;
        return l and r;
    }
};


活动打卡代码 LeetCode 2561. 重排水果

#define eb emplace_back
#define all(x) x.begin(), x.end()

typedef long long LL;

class Solution {
public:
    LL minCost(vector<int>& b1, vector<int>& b2) {
        map<int, int> cnt, s[2];
        for (auto x: b1) cnt[x] ++ , s[0][x] ++ ;
        for (auto x: b2) cnt[x] ++ , s[1][x] ++ ;

        for (auto &[k, v]: cnt)
            if (v & 1)
                return -1;

        int t = 2e9;
        vector<int> a, b;
        for (auto &[k, v]: cnt) {
            t = min(t, k * 2);
            int x = s[0][k], y = s[1][k];
            while (x < v / 2) x ++ , a.eb(k);
            while (y < v / 2) y ++ , b.eb(k);
        }

        sort(all(a));
        sort(all(b), greater<>());

        LL res = 0;
        for (int i = 0; i < a.size(); i ++ ) res += min({a[i], b[i], t});

        return res;
    }
};


活动打卡代码 LeetCode 2560. 打家劫舍 IV

class Solution {
public:
    int minCapability(vector<int>& a, int k) {
        int n = a.size();

        function<bool(int)> check = [&](int x) {
            int cnt = 0, mx = 0;
            vector<int> st(n);
            for (int i = 0; i < n; i ++ ) {
                if (i and st[i - 1]) continue;
                if (a[i] <= x) {
                    mx = max(mx, x);
                    cnt ++ ;
                    st[i] = 1;
                }
            }
            int cnt2 = 0, mx2 = 0;
            st = vector<int>(n);
            for (int i = n - 1; ~i; i -- ) {
                if (i < n - 1 and st[i + 1]) continue;
                if (a[i] <= x) {
                    mx2 = max(mx2, x);
                    cnt2 ++ ;
                    st[i] = 1;
                }
            }
            return cnt >= k or cnt2 >= k;
        };

        int l = 1, r = 1e9;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};



class Solution {
public:
    vector<int> vowelStrings(vector<string>& ws, vector<vector<int>>& qs) {
        set<char> S{'a', 'e', 'i', 'o', 'u'};

        int n = ws.size();
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i ++ ) {
            auto t = ws[i - 1];
            s[i] = s[i - 1];
            if (S.count(t[0]) and S.count(t.back())) s[i] ++ ;
        }

        int m = qs.size();
        vector<int> res(m);
        for (int i = 0; i < m; i ++ ) {
            auto q = qs[i];
            int l = q[0], r = q[1] + 1;
            res[i] = s[r] - s[l];
        }

        return res;
    }
};



#define ep emplace
#define pq priority_queue

typedef long long LL;

class Solution {
public:
    LL pickGifts(vector<int>& gs, int k) {
        LL sum = 0;
        for (auto x: gs) sum += x;

        pq<int> q;
        for (auto x: gs) q.ep(x);

        while (k -- ) {
            auto t = q.top(); q.pop();
            sum -= t;
            t = sqrt(t);
            sum += t;
            q.ep(t);
        }

        return sum;
    }
};



灵神的上下轮廓

class Solution {
public:
    bool isPossibleToCutPath(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();

        function<bool(int, int)> dfs = [&](int x, int y) {
            if (x == n - 1 and y == m - 1) return true;
            g[x][y] = 0;
            return x + 1 < n and g[x + 1][y] and dfs(x + 1, y) 
                or y + 1 < m and g[x][y + 1] and dfs(x, y + 1);
        };

        return !dfs(0, 0) or !dfs(0, 0);
    }
};

两次搜索

#define x first
#define y second

#define ep emplace

typedef pair<int, int> PII;

class Solution {
public:
    bool isPossibleToCutPath(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        vector st(n, vector<int>(m));

        queue<PII> q;
        q.ep(0, 0);
        while (q.size()) {
            auto [x, y] = q.front(); q.pop();
            if (st[x][y]) continue;
            st[x][y] = 1;
            if (x + 1 < n and g[x + 1][y]) q.ep(x + 1, y);
            if (y + 1 < m and g[x][y + 1]) q.ep(x, y + 1);
        }

        q.ep(n - 1, m - 1);
        while (q.size()) {
            auto [x, y] = q.front(); q.pop();
            if (st[x][y] & 2) continue;
            st[x][y] |= 2;
            if (x >= 1 and g[x - 1][y]) q.ep(x - 1, y);
            if (y >= 1 and g[x][y - 1]) q.ep(x, y - 1);
        }

        vector<int> cnt(n + m);
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (st[i][j] == 3)
                    cnt[i + j] ++ ;

        for (int i = 1; i < n + m - 2; i ++ )
            if (cnt[i] <= 1)
                return true;

        return false;
    }
};

下面是被 hack 的代码

hack 数据:

[[1,1,1,0],[1,1,1,1],[1,0,1,1],[1,0,1,1]]

output: false

answer: true

错误代码

class Solution {
public:
    bool isPossibleToCutPath(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        vector<int> cnt(n + m);

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ ) 
                if (g[i][j])
                    cnt[i + j] ++ ;

        for (int i = 1; i < n + m - 2; i ++ ) 
            if (cnt[i] <= 1)
                return true;

        return false;
    }
};

过不去的暴力找路径(悲),纪念一下

class Solution {
public:
    bool isPossibleToCutPath(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        vector<int> pre(n * m);

        vector st(n, vector<int>(m));
        st[0][0] = 1;

        vector cnt(n, vector<int>(m));

        int S = 0, T = n * m - 1, tot = 0;

        function<void(int, int, int)> dfs = [&](int u, int x, int y) {
            if (u == T) {
                for (int i = T; i != S; i = pre[i]) {
                    int a = i / m, b = i % m;
                    if (i != T) cnt[a][b] ++ ;
                }
                tot ++ ;
                return;
            }
            if (x + 1 < n and !st[x + 1][y] and g[x + 1][y] == 1) {
                st[x + 1][y] = 1;
                int t = (x + 1) * m + y;
                pre[t] = u;
                dfs(t, x + 1, y);
                st[x + 1][y] = 0;
            }
            if (y + 1 < m and !st[x][y + 1] and g[x][y + 1] == 1) {
                st[x][y + 1] = 1;
                int t = x * m + y + 1;
                pre[t] = u;
                dfs(t, x, y + 1);
                st[x][y + 1] = 0;
            }
        };

        dfs(0, 0, 0);

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (cnt[i][j] == tot)
                    return true;

        return false;
    }
};



#define all(x) x.begin(), x.end()

class Solution {
public:
    int maximizeWin(vector<int>& pos, int k) {
        int n = pos.size();
        vector<int> f(n + 2), g(n + 2);

        for (int i = 1; i <= n; i ++ ) {
            auto it = lower_bound(all(pos), pos[i - 1] - k);
            if (it == pos.end()) {
                f[i] = i;
                continue;
            }
            int j = it - pos.begin();
            f[i] = i - j;
        }

        for (int i = n; i; i -- ) {
            auto it = upper_bound(all(pos), pos[i - 1] + k);
            if (it == pos.end()) {
                g[i] = n - i + 1;
                continue;
            }
            int j = it - pos.begin() + 1;
            g[i] = j - i;
        }

        for (int i = 1; i <= n; i ++ ) f[i] = max(f[i], f[i - 1]);
        for (int i = n; i; i -- ) g[i] = max(g[i], g[i + 1]);

        int res = 0;
        for (int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i + 1]);

        return res;
    }
};



class Solution {
public:
    int maxCount(vector<int>& b, int n, int mxs) {
        set<int> S;
        for (auto x: b) S.insert(x);

        int sum = 0, last = 0, cnt = 0;
        for (int i = 1; i <= n; i ++ ) {
            if (S.count(i)) continue;
            if (sum + i > mxs) return cnt;
            sum += i, cnt ++ ;
        }

        return cnt;
    }
};