头像

Axehco




离线:2天前


最近来访(17)
用户头像
HignC
用户头像
龙舟队队长
用户头像
annaelsaaaa
用户头像
epsilonu
用户头像
mengzhi_0
用户头像
生生_6
用户头像
努力搬砖滴打工人
用户头像
abc0
用户头像
想去hkust的Steward
用户头像
1213
用户头像
墨染空
用户头像
王礼涛


Axehco
12天前
#include <iostream>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    stack<char> stk;
    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        if (stk.empty() || stk.top() != s[i]) {
            stk.push(s[i]);
        } else {
            stk.pop();
            cnt++;
        }
    }
    if (cnt % 2 == 1) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Axehco
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {
    int n, x, num;
    cin >> n;
    int res = 0;

    cin >> x;
    while (--n) {
        cin >> num;
        res = max(res, abs(num - x));
        x = num;
    }
    cout << res << endl;
    return 0;
}



Axehco
4个月前
// 动态规划
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;
int w[N];
int dp[N][2];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);

    dp[0][0] = 0;
    dp[0][1] = -w[1];
    for (int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + w[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - w[i]);  // 这里可以进行多次买入买出
    }

    printf("%d\n", dp[n][0]);
    return 0;
}

// 贪心
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    int res = 0;
    int preprice, num;
    scanf("%d", &preprice);  // 前一天的价格
    while (--n) {
        scanf("%d", &num);
        res += max(0, num - preprice);
        preprice = num;
    }

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



Axehco
4个月前
// 动态规划
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n;
int dp[N][2], price[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &price[i]);

    dp[0][0] = 0;
    dp[0][1] = -price[1];
    for (int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + price[i]);
        dp[i][1] = max(dp[i -1][1], -price[i]);
    }

    printf("%d\n", dp[n][0]);
    return 0;
}

// 贪心
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    int res = 0;
    int minprice, num;
    scanf("%d", &minprice);  // 第一天的
    while (--n) {
        scanf("%d", &num);
        res = max(res, num - minprice);
        minprice = min(minprice, num);
    }

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



Axehco
4个月前
// 动态规划
class Solution {
public:
    int dp[510][2];
    int maxDiff(vector<int>& nums) {
        if (nums.empty()) return 0;
        dp[0][0] = 0;
        dp[0][1] = -nums[0];
        for (int i = 1; i <= nums.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]);
            dp[i][1] = max(dp[i -1][1], -nums[i - 1]);  // 注意下标是从1开始的
        }
        return dp[nums.size()][0];
    }
};

// 贪心
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int res = 0;
        int minprice = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            minprice = nums[i] < minprice ? nums[i] : minprice;
            res = max(res, nums[i] - minprice);
        }
        return res;
    }
};

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if (nums.empty()) return 0;
        int res = 0;
        for (int i = 1, minprice = nums[0]; i < nums.size(); i++) {
            minprice = min(nums[i], minprice);
            res = max(res, nums[i] - minprice);
        }
        return res;
    }
};



Axehco
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int dp[N][N];
char a[N], b[N];

int main() {
    int n, m;
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = min(dp[i - 1][j] + 1, 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", dp[n][m]);
    return 0;
}


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

Axehco
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int dp[N][N];
char a[N], b[N];

int main() {
    int n, m;
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = min(dp[i - 1][j] + 1, 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", dp[n][m]);
    return 0;
}


活动打卡代码 AcWing 899. 编辑距离

Axehco
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15, M = 1010;
int dp[N][N];
int n, m;
char str[M][N];

int edit_distance(char a[], char b[]) {
    // 注意是从1开始读的
    int la = strlen(a + 1), lb = strlen(b + 1);

    for (int i = 1; i <= lb; i++) dp[0][i] = i;
    for (int i = 1; i <= la; i++) dp[i][0] = i;

    for (int i = 1; i <= la; i++) {
        for (int j = 1; j <= lb; j++) {
            dp[i][j] = min(dp[i - 1][j] + 1, 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);
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (a[i] != b[j]));  // 简写
        }
    }
    return dp[la][lb];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", str[i] + 1);

    while (m--) {
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (edit_distance(str[i], s) <= limit) 
                res++;
        }
        printf("%d\n", res);
    }

    return 0;
}



Axehco
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15, M = 1010;
int dp[N][N];
int n, m;
char str[M][N];

int edit_distance(char a[], char b[]) {
    // 注意是从1开始读的
    int la = strlen(a + 1), lb = strlen(b + 1);

    for (int i = 1; i <= lb; i++) dp[0][i] = i;
    for (int i = 1; i <= la; i++) dp[i][0] = i;

    for (int i = 1; i <= la; i++) {
        for (int j = 1; j <= lb; j++) {
            dp[i][j] = min(dp[i - 1][j] + 1, 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);
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (a[i] != b[j]));  // 简写
        }
    }
    return dp[la][lb];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", str[i] + 1);

    while (m--) {
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (edit_distance(str[i], s) <= limit) 
                res++;
        }
        printf("%d\n", res);
    }

    return 0;
}



Axehco
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
char a[N], b[N];
int dp[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    cin >> a + 1 >> b + 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}