头像

IFKY

UESTC




离线:22小时前


最近来访(38)
用户头像
小肥牛
用户头像
Codemon
用户头像
griezman
用户头像
陈先森_3
用户头像
Fatin
用户头像
Ymg2020
用户头像
伊蕾娜我的伊蕾娜
用户头像
Cccc
用户头像
露西亚
用户头像
Erliu886
用户头像
.isEmpty
用户头像
计算机数学小助手
用户头像
simonhan
用户头像
Whynot.
用户头像
ZDC
用户头像
namelessstory
用户头像
Natsuzora
用户头像
撒野_9
用户头像
柳下舟
用户头像
名字长才会有人跟着念


IFKY
4天前

参考: DP

#include <iostream>
#include <algorithm>
#include <cstring>

const int N = 210, M = 20010;

int n, m;
int w[N], s[N];
int dp[M];

struct Node{
    int ans, W;
}q[M];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
    scanf("%d", &m);
    memset(dp, 0x3f3f3f3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < w[i]; j ++ ) { // j为模w[i]后的余数
            int head = 1, tail = 0;
            for (int k = j, cnt = 0; k <= m; cnt ++ , k += w[i]) {
                if (tail - head == s[i]) head ++ ;
                int ans = dp[k] - cnt;
                while (head <= tail && ans < q[tail].ans) tail -- ;
                q[++ tail].ans = ans, q[tail].W = k; 
                dp[k] = q[head].ans + cnt; //转移当前的最新状态
            }
        }
    printf("%d\n", dp[m]);
    return 0;
}


活动打卡代码 AcWing 902. 最短编辑距离

IFKY
7天前

$ dp[i][j] $
集合:a[1~i]变成b[1~j]的所有操作方式
属性:最小值

#include <iostream>
#include <vector>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int dp[N][N];

int main() {
    scanf("%d%s", &n, a + 1); // 从1号位置开始存储字符串
    scanf("%d%s", &m, b + 1);

    for (int i = 0; i <= n; i ++ ) dp[i][0] = i;
    for (int i = 0; i <= m; i ++ ) dp[0][i] = i;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;  // 增,删
            if (a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]); // 不操作
            else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1); // 改
        }
    printf("%d\n", dp[n][m]);
    return 0;
}



IFKY
23天前

识宝发现冰原上的一个位置有一个宝箱,她很想拿到这个宝箱,当她在宝箱相邻格子停下时,她就可以拿到宝箱。
识宝在冰原上滑行时会选择一个坐标轴方向直线前进,直到触碰到地图边界或障碍物时才会停下(宝箱也属于障碍物,触碰到障碍物必须停下,无法穿过障碍物)。
现在,识宝在地图左上角,她想知道她至少需要滑行几次才可以拿到宝箱。

输入描述

第一行输入两个整数n, m($ 1 \leq n, m \leq 300 $) 表示地图大小。
接下来 $n$ 行,每行一个字符串表示地图, 其中 #表示障碍物, .表示冰面, @ 表示宝箱,数据保证地图上有且只有一个宝箱,保证宝箱和其他障碍物不会在地图左上角。

输出描述

一个整数表示拿到宝箱最少滑行次数,若无法拿到宝箱,则输出-1。

样例

输入1
4 4
...#
.@..
....
#...

输出1
4

输入2
4 4
....
.@..
....
...#

输出2
-1

参考代码

分析:难点在如何处理“滑行”。在bfs基础上加一个判断, 满足“停止点”才入队。

#include <bits/stdc++.h>

using namespace std;

string mp[310];
int n, m;
int vis[310][310] ={0};
int way[5] = {1, 0, -1, 0, 1};

struct node {
    int x, y, step; // step记录滑行次数
};

int ans = INT_MAX;

bool Canvis(int i, int j) {
    if (i < 0 || j < 0 || i >= n || j >= m || mp[i][j] == '#' || mp[i][j] == '@')
        return false;
    return true;
}

bool check(int i, int j) { // 判断是否到达终点
    for (int w = 0; w < 4; w ++ ) {
        int nx = i + way[w], ny = j + way[w + 1];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (mp[nx][ny] == '@') return true;
    }
    return false;
}

void bfs() {
    queue<node> q;
    q.push(node{0, 0, 0});
    while (q.size()) {
        node n1 = q.front();
        q.pop();
        vis[n1.x][n1.y] = 1;
        for (int i = 0; i < 4; i ++ ) {
            int step = n1.step;
            int new_x = n1.x, new_y = n1.y;

            if (check(new_x, new_y)) ans = min(ans, step);

            // 能走就接着走
            while (Canvis(new_x + way[i], new_y + way[i + 1])) {
                new_x += way[i];
                new_y += way[i + 1];
            }
            // 入队的点都是"停止点"
            if (vis[new_x][new_y] == 0) q.push(node{new_x, new_y, step + 1});
        }
    }
}

int main() {
    cin >> n >> m;
    string s;
    for (int i = 0; i < n; i ++ ) {
        cin >> s;
        mp[i] = s;
    }
    bfs();
    if (ans != INT_MAX) cout << ans;
    else cout << -1;

    return 0;
}




IFKY
1个月前

给定一个长度为n的正整数序列,求共有多少个三元组(i, j, k) 满足 $a[i] = a[k] > a[j]$,其中$0 <= i < j < k < n$。

数据范围记不太清了,n 是$2e5$级别的话,好像要用到树状数组来做。具体可以参照求逆序对数变种的做法。
n如果比较小,1000级别的话,可以用vector数组 + 二分来做。
时间复杂度大概是 $O(1000 * n \log n)$

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N];
vector<int> pos[N];

int main() {
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ ) {
        for (int val = a[i] + 1; val <= 1000; val ++ ) {
            if (!pos[val].size()) continue;
            if (pos[val][0] < i && pos[val].back() > i) {
                int left = 0, right = pos[val].size() - 1;
                while (right - left > 1) {
                    int mid = left + right >> 1;
                    if (pos[val][mid] < i) left = mid;
                    else right = mid; // 否则,pos[val][mid]一定大于i,不可能等,因为val > a[i]
                }
                // 二分找到最大的left, 使得pos[val][left] < i, 这样left + 1就是a[i]左边的val个数
                res += (left + 1) * (pos[val].size() - (left + 1));
            }
        }
    }
    cout << res << endl;
    return 0;
}




IFKY
1个月前

给定一个 $4 \times 4$ 的网格,0表示可走,1表示不可走,8表示礼物(唯一)。迷宫入口可能有多个,问按什么路线走,能最快找到礼物。返回路线坐标对。

样例

输入:
0 1 1 1
0 0 0 1
1 0 8 1
1 0 1 1

输出:
(3, 1), (2, 1), (2, 2)

思路

从礼物出发找到最近的出口,就可以看成单源最短路问题。

代码实现

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

int matrix[4][4];
PII pre[4][4];  //记录前驱
vector<PII> res;
int d[4][4];

PII bfs(int x, int y) {
    memset(d, -1, sizeof d);
    queue<PII> q;
    q.push({x,y});
    d[x][y] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for (int i = 0; i < 4; i ++ ) {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a >= 0 && a < 4 && b >= 0 && b < 4 && matrix[a][b] == 0 && d[a][b] == -1) {
                d[a][b] = d[t.first][t.second] + 1;
                q.push({a, b});
                pre[a][b] = {t.first, t.second};
                if (a == 0 || a == 3 || b == 0 || b == 3) return {a, b};
            }
        }
    }
    return {x, y};
}

int main() {
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            scanf("%d", &matrix[i][j]);

    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            if (matrix[i][j] == 8) {
                PII end = bfs(i, j);

                int a = end.first, b = end.second;
                while (a != i && b != j) {
                    res.push_back(end);
                    a = end.first, b = end.second;
                    end = pre[a][b];
                }
                res.push_back({i, j}); // 礼物位置
                for (auto& x : res) cout << x.first << ',' << x.second << endl;

                return 0;
            }

    return 0;
}


活动打卡代码 LeetCode 1282. 用户分组

IFKY
1个月前

C++代码

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res;
        int n = groupSizes.size();
        unordered_map<int, vector<int>> hash;

        for (int i = 0; i < n; i ++ ) {
            int t = groupSizes[i];
            hash[t].push_back(i);
            if (hash[t].size() == t) {
                res.push_back(hash[t]);
                hash[t].clear();
            }
        }
        return res;
    }
};

Java代码

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> res = new ArrayList<>();
        Map<Integer, List<Integer>> hash = new HashMap<>();
        for (int i = 0; i < groupSizes.length; i ++ ) {
            int x = groupSizes[i];
            if (hash.get(x) == null) hash.put(x, new ArrayList());
            hash.get(x).add(i);
            if (hash.get(x).size() == x) {
                res.add(hash.get(x));
                hash.put(x, null);
            }
        }
        return res;
    }
}

Python代码

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        res = []
        hash = {}
        for i in range(len(groupSizes)):
            x = groupSizes[i]
            if x not in hash:
                hash[x] = []
            hash[x].append(i)
            if len(hash[x]) == x:
                res.append(hash[x])
                hash[x] = []
        return res


活动打卡代码 LeetCode 1282. 用户分组

IFKY
1个月前

Hash 边挂边分! 太优雅了!

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res;
        unordered_map<int, vector<int>> hash;

        for (int i = 0; i < groupSizes.size(); i ++ ) {
            int x = groupSizes[i];
            hash[x].push_back(i);
            if (hash[x].size() == x) {
                res.push_back(hash[x]);
                hash[x].clear();
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 640. 求解方程

IFKY
1个月前
class Solution {
public:
    pair<int, int> work(string str) {
        int a = 0, b = 0;
        if (str[0] != '+' && str[0] != '-') str = '+' + str;

        for (int i = 0; i < str.size(); i ++ ) {  // 别忘,最后还有i ++  
            int j = i + 1, t = 0;
            while (j < str.size() && isdigit(str[j])) t = t * 10 + str[j ++ ] - '0';

            if (i + 1 == j) t = 1; // x的系数为1
            if (str[i] == '-') t = -t;
            if (j < str.size() && str[j] == 'x') a += t, i = j;
            else b += t, i = j - 1;
        }
        return {a, b};
    }

    string solveEquation(string equation) {
        int k = equation.find('=');
        auto left = work(equation.substr(0, k)), right = work(equation.substr(k + 1));
        int a = left.first - right.first, b = right.second - left.second;
        if (!a) {
            if (!b) return "Infinite solutions";
            else return "No solution";
        }
        return "x=" + to_string(b / a);
    }
};



IFKY
1个月前

DFS

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        return dfs(root)[0];
    }

    vector<int> dfs(TreeNode* root) {
        // 计算每个子树的最大值、最小值
        vector<int> res({1, root->val, root->val}); // 初始化默认当前值

        if (root->left) {
            auto t = dfs(root->left);
            if (!t[0] || t[1] >= root->val) res[0] = 0;
            res[1] = max(res[1], t[1]);
            res[2] = min(res[2], t[2]);
        }
        if (root->right) {
            auto t = dfs(root->right);
            if (!t[0] || t[2] <= root->val) res[0] = 0;
            res[1] = max(res[1], t[1]);
            res[2] = min(res[2], t[2]);
        }

        return res;
    }
};



IFKY
1个月前
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
PII s[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &s[i].first, &s[i].second);

    sort(s, s + n); // 按左端点排序

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
    {
        if (s[i].first > ed) res ++ , ed = s[i].second;
        else ed = min(ed, s[i].second); // 前缀min, 贪心策略,前缀尽量小,才可能选取更多区间。
        // s[i].second < ed时,其实将上一个区间换了,只不过res没有改变。
    }

    printf("%d\n", res);
    return 0;
}