Axehco

1805

HignC

annaelsaaaa
epsilonu
mengzhi_0

abc0

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;
}


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;
}


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;
}