OJ笔试强训_1至24天

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{int a = 0, b = 0;cin >> a >> b;if (a > b)swap(a, b);int c = __gcd(a, b); // 9 6 -> 3 -> 18cout << a * b / c << endl; // !!!!!两者乘积除以最大公约数// if(c == 1)// {// cout << a * b << endl;// return 0;// }// else if(c == a)// {// cout << b << endl;// return 0;// }// else// {// if(c * b % a == 0)// {// cout << b * c << endl;// return 0;// }// else if(c * a % b == 0)// {// cout << c * a << endl;// return 0;// }// }// for (int i = b; i <= a * b; i += c)// {// 	if (i % a == 0 && i % b == 0)// 	{// 		cout << i << endl;// 		break;// 	}// }return 0;
}

#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** max increasing subsequence* @param arr int整型vector the array* @return int整型*/int MLS(vector<int>& arr) {set<int> s(arr.begin(), arr.end());vector<int> nums(s.begin(), s.end());sort(nums.begin(), nums.end()); // 排序+遍历一遍int sz = nums.size();int ret = 1;for (int i = 1; i < sz; ++i){int len = 1;while (nums[i] - nums[i - 1] == 1){++len;++i;}cout << ret << " " << len << endl;ret = max(ret, len);}return ret;}
};

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param numbers int整型vector* @return bool布尔型*/bool IsContinuous(vector<int>& numbers) {vector<int> arr(13, 0);int cnt = 0; // 非0的个数for (auto& e : numbers){arr[e]++;if (e != 0)++cnt;}if (arr[0] == 4) // 保证下面有两个不同的边界{cout << "line 21" << endl;return true;}int left = 0, right = 0;for (int i = 1; i <= 13; ++i){if (arr[i] > 1) // 保证去重{// cout << "有重复";return false;}}for (int i = 1; i <= 13; ++i) // 找左边界{if (arr[i] != 0){left = i;break;}}for (int i = 13; i > left; --i) // 找右边界{if (arr[i] != 0){right = i;break;}}// cout << left << " " << right << endl;// 0 0 2 4 6 left = 2, right = 6;int sum = right - left - 1; // 中间应该有的个数sum -= cnt - 2; // 减去中间已经有的个数// cout << "sum " << sum << " arr[0]" << arr[0] << endl;if (sum <= arr[0])return true;elsereturn false;}
};

#include <climits>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param numbers int整型vector* @return bool布尔型*/bool IsContinuous(vector<int>& numbers) {// 找规律->不会出现重复元素 && max - min >= 4vector<int> arr(13, 0);int minLeft = INT_MAX, maxRight = INT_MIN; // 找最大最小值for (auto& e : numbers){if(e == 0)continue;minLeft = min(minLeft, e);maxRight = max(maxRight, e);arr[e]++;if(arr[e] > 1)return false;}return maxRight - minLeft <= 4;}
};

#include <iostream>
#include <ostream>
#include <vector>
using namespace std;
#define int long long // 66666666666666666666666666666666666666666666
signed main()
{// 把马吃了是不是后面的点就能走了？emmmint n = 0, m = 0, x = 0, y = 0;cin >> n >> m >> x >> y;// if (n == 1 || m == 1) // 边界处理// {// 	cout << 1 << endl;// 	return 0;// }// if (abs(m - x) + abs(n - y) == 3 && m != x && n != y)// {// 	cout << 0 << endl;// 	return 0;// }// vector<vector<int>> borad(n, vector<int>(m));vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));for (int i = 0; i <= n; ++i){if (abs(i - x) + abs(0 - y) == 3 && i != x && 0 != y)break;if (x == i && y == 0) // 马也不能走！！！真服了break;dp[i][0] = 1;}for (int j = 0; j <= m; ++j){if (abs(0 - x) + abs(j - y) == 3 && 0 != x && j != y)break;if (x == 0 && y == j) // 马也不能走！！！真服了break;dp[0][j] = 1;}for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){if (abs(i - x) + abs(j - y) == 3 && i != x && j != y)continue;if (x == i && y == j) // 马也不能走！！！真服了continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}// for(int i = 0; i <= n; ++i) // DeBug：打印dp矩阵// {// for(int j = 0; j <= m; ++j)// {// cout << dp[i][j] << " ";// }// cout << endl;// }cout << dp[n][m] << endl;return 0;
}

#include <iostream>
#include <ostream>
#include <vector>
using namespace std;
#define int long long // 66666666666666666666666666666666666666666666
signed main()
{// 把马吃了是不是后面的点就能走了？emmmint n = 0, m = 0, x = 0, y = 0;cin >> n >> m >> x >> y;// if (n == 1 || m == 1) // 边界处理// {// 	cout << 1 << endl;// 	return 0;// }// if (abs(m - x) + abs(n - y) == 3 && m != x && n != y)// {// 	cout << 0 << endl;// 	return 0;// }// vector<vector<int>> borad(n, vector<int>(m));vector<vector<int>> dp(n + 2, vector<int>(m + 2, 0));// for (int i = 0; i <= n; ++i)// {// 	if (abs(i - x) + abs(0 - y) == 3 && i != x && 0 != y)// 		break;// 	if (x == i && y == 0) // 马也不能走！！！真服了// 		break;// 	dp[i][0] = 1;// }// for (int j = 0; j <= m; ++j)// {// 	if (abs(0 - x) + abs(j - y) == 3 && 0 != x && j != y)// 		break;// 	if (x == 0 && y == j) // 马也不能走！！！真服了// 		break;// 	dp[0][j] = 1;// }dp[0][1] = 1;x += 1, y += 1;for (int i = 1; i <= n + 1; ++i){for (int j = 1; j <= m + 1; ++j){if (abs(i - x) + abs(j - y) == 3 && i != x && j != y)continue;if (x == i && y == j) // 马也不能走！！！真服了continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}// for(int i = 0; i <= n; ++i) // DeBug：打印dp矩阵// {// for(int j = 0; j <= m; ++j)// {// cout << dp[i][j] << " ";// }// cout << endl;// }cout << dp[n + 1][m + 1] << endl;return 0;
}

#include <iostream>
using namespace std;
int main()
{int n = 0, m = 0, a = 0, b = 0;cin >> n >> m >> a >> b;int res = 0;if (a > b) // 先组成a{if (n >= 2 && m >= 1){res += min(n / 2, m) * a;if (res / a == n / 2){m -= n / 2;n %= 2;}else{n -= m;m = 0;}}if (n >= 1 && m >= 2){res += min(n, m / 2) * b;}}else // 先组成b{if (n >= 1 && m >= 2){res += min(n, m / 2) * b;// cout << res << " " << n << " " << m << " " << endl;if (res / b == m / 2){n -= m / 2;m %= 2;}else{m -= n;n = 0;}}// cout << n << " " << m << endl;if (n >= 2 && m >= 1){res += min(n / 2, m) * a;}}cout << res << endl;return 0;
}

#include <iostream>
using namespace std;
#define int long long
signed main()
{int n = 0, m = 0, a = 0, b = 0;cin >> n >> m >> a >> b;int res = 0;// 2x + 3y = ? 条件太少就枚举for(int x = 0; x <= min(n / 2, m); ++x) // 枚举x{int y = min(n - 2 * x, (m - x) / 2);res = max(res, a * x + b * y);}cout << res << endl;return 0;
}

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;int main()
{string str1, str2;getline(cin, str1);getline(cin, str2);unordered_map<char, int> hash; // str2的字母和个数for(auto& e : str2){hash[e]++;}string res;for(auto& e : str1){if(!hash.count(e))res += e;}cout << res << endl;return 0;
}

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {ListNode* cur1 = pHead1;int cnt1 = 0, cnt2 = 0;while(cur1 != nullptr){cnt1++;cur1 = cur1->next;}ListNode* cur2 = pHead2;while(cur2 != nullptr){cnt2++;cur2 = cur2->next;}// cout << pHead1->val << " " << pHead2->val << endl;if(cnt1 < cnt2)swap(pHead1, pHead2);cur1 = pHead1, cur2 = pHead2;// cout << pHead1->val << " " << pHead2->val << endl;int diff = abs(cnt1 - cnt2);while(diff--){cur1 = cur1->next;}while(cur1 != nullptr && cur2 != nullptr){// cout <<cur1->val  << " " <<  cur2->val << endl;if(cur1->val == cur2->val)return cur1;cur1 = cur1->next;cur2 = cur2->next;}return nullptr;}
};

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {auto cur1 = pHead1, cur2 = pHead2; // 解法二-等量关系while(cur1 != cur2){cur1 = cur1 != nullptr ? cur1->next : pHead2; // 为空就到另个链表重新走cur2 = cur2 != nullptr ? cur2->next : pHead1;}return cur1;}
};

#include <iostream>
#include <vector>
using namespace std;#define int long longsigned main()
{int n = 0;string str;cin >> n >> str;vector<int> s(n), h(n), y(n);s[0] = str[0] == 's' ? 1 : 0;for(int i = 1; i < n; ++i){s[i] = s[i - 1];if(str[i] == 's')s[i] += 1;h[i] = h[i - 1];if(str[i] == 'h')h[i] += s[i - 1];y[i] = y[i - 1];if(str[i] == 'y')y[i] += h[i - 1];}cout << y[n - 1] << endl;return 0;
}

#include <iostream>
#include <vector>
using namespace std;#define int long longsigned main()
{int n = 0;string str;cin >> n >> str;// vector<int> s(n), h(n), y(n); // 用变量进行空间优化int s = 0, h = 0, y = 0;s = str[0] == 's' ? 1 : 0;for(int i = 1; i < n; ++i){if(str[i] == 's')s += 1;if(str[i] == 'h')h += s;if(str[i] == 'y')y += h;}cout << y << endl;return 0;
}

#include <iostream>
#include <vector>using namespace std;
int main()
{int T = 0;cin >> T;while (T--){int n = 0, k = 0;string str;cin >> n >> k >> str;int res = 0;for (int i = 0; i < n; ++i){if (i >= 2 && str[i - 2] == 'W' && str[i - 1] == 'W' && str[i] == 'W') {res += k;}else if (str[i] == 'W') {++res;}else {--res;}}cout << res << endl;}return 0;
}

#include <ostream>
#include <unordered_set>
#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param arr int整型vector the array* @return int整型*/int maxLength(vector<int>& arr) {int res = 1, sz = arr.size();for (int i = 0; i < sz; ++i)    // 暴力{int len = 1;vector<bool> hash(100001, false);hash[arr[i]] = true;for (int j = i + 1; j < sz && hash[arr[j]] == false; ++j){++len;hash[arr[j]] = true;}res = max(res, len);}   // for (int i = 0; i < sz; )    // 笔试时写的，8/11// {// 	int len = 1;// 	vector<bool> hash(100001, false);// 	hash[arr[i++]] = true;// 	while (i < sz && hash[arr[i]] == false)// 	{// 		++len;// 		hash[arr[i]] = true;// 		++i;// 	}// 	res = max(res, len);// }return res;}
};

#include <ostream>
#include <unordered_set>
#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param arr int整型vector the array* @return int整型*/int maxLength(vector<int>& arr) {int res = 1, sz = arr.size();for (int i = 0; i < sz; ++i)    // 暴力{int len = 1;vector<bool> hash(100001, false);hash[arr[i]] = true;for (int j = i + 1; j < sz && hash[arr[j]] == false; ++j){++len;hash[arr[j]] = true;}res = max(res, len);}   // for (int i = 0; i < sz; )    // 笔试时写的，8/11// {// 	int len = 1;// 	vector<bool> hash(100001, false);// 	hash[arr[i++]] = true;// 	while (i < sz && hash[arr[i]] == false)// 	{// 		++len;// 		hash[arr[i]] = true;// 		++i;// 	}// 	res = max(res, len);// }return res;}
};

#include <ostream>
#include <unordered_set>
#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param arr int整型vector the array* @return int整型*/int hash[100001] = { 0 };int maxLength(vector<int>& arr) {int res = 1, sz = arr.size();for (int left = 0, right = 0; right < sz; ++right)     // 滑动窗口{hash[arr[right]]++; // 进窗口while (left < sz && hash[arr[right]] > 1) // 判断{hash[arr[left++]]--; // 出窗口}res = max(res, right - left + 1);}   // for (int i = 0; i < sz; ++i)    // 暴力// {// 	int len = 1;// 	vector<bool> hash(100001, false);// 	hash[arr[i]] = true;// 	for (int j = i + 1; j < sz && hash[arr[j]] == false; ++j)// 	{// 		++len;// 		hash[arr[j]] = true;// 	}// 	res = max(res, len);// }   // for (int i = 0; i < sz; )    // 笔试时写的，8/11// {// 	int len = 1;// 	vector<bool> hash(100001, false);// 	hash[arr[i++]] = true;// 	while (i < sz && hash[arr[i]] == false)// 	{// 		++len;// 		hash[arr[i]] = true;// 		++i;// 	}// 	res = max(res, len);// }return res;}
};

#include <climits>
#include <iostream>
#include <vector>
using namespace std;
int main()
{int n = 0;string str;cin >> n >> str;vector<int> hash(26, 0);int sz = str.size();for (int i = 0; i < sz; ++i){hash[str[i] - 'a']++;}int maxCnt = 0, maxIndex = 0;int secCnt = 0, secIndex = 0;for (int i = 0; i < 26; ++i) // 要放第一大然后放第二大？跟着下标排序{if (hash[i] > maxCnt){maxCnt = hash[i];maxIndex = i;}}for (int i = 0; i < 26; ++i) // 要放第一大然后放第二大？跟着下标排序{if (i != maxIndex && hash[i] > secCnt){secCnt = hash[i];secIndex = i;}}if (maxCnt > sz / 2)cout << "no";else{cout << "yes" << endl;vector<char> res(n, '1');int i = 0;while (maxCnt--){res[i] = (maxIndex + 'a');i += 2;}if (i > n - 1)i = 1;// while(secCnt--)// {// res[i] = (secIndex + 'a');// i += 2;// }// if(i > n - 1)// i = 1;int j = 0;while (res[n - 1] == '1' || res[n - 2] == '1'){if (j != maxIndex && hash[j] != 0) // 找到一个后往后找{res[i] = (j + 'a'); // 不等于0就放入一个然后往hash后面找// cout << i << " res[i] : " << res[i] << " hash[j] " << hash[j] << endl;i += 2;if (i > n - 1)i = 1;hash[j]--;}if (j == 25)j = 0;else++j;}for (auto& e : res){cout << e;}}return 0;
}

#include <climits>
#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0;string str;cin >> n >> str;vector<int> hash(26, 0);int sz = str.size();for (int i = 0; i < sz; ++i){hash[str[i] - 'a']++;}int maxCnt = 0, maxIndex = 0;for (int i = 0; i < 26; ++i) // 先放第一大{if (hash[i] > maxCnt){maxCnt = hash[i];maxIndex = i;}}if (maxCnt > (sz + 1) / 2)cout << "no";else{cout << "yes" << endl;vector<char> res(n);int i = 0;while (maxCnt--){res[i] = (maxIndex + 'a');i += 2;}// cout << maxIndex << endl;for (int j = 0; j < 26; ++j){if (j != maxIndex && hash[j] != 0) // 找到一个后往后找{while(hash[j]--){if(i >= n)i = 1;res[i] = j + 'a';i += 2;}}}for (auto& e : res){cout << e;}cout << endl;}return 0;
}

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
// 偷房子那题？dp
#define int long long
signed main()
{int n = 0;cin >> n;unordered_map<int, int> hash;vector<int> v(n);for(int i = 0; i < n; ++i){cin >> v[i];hash[v[i]] += v[i];}vector<int> arr;for(auto [a, b] : hash){arr.push_back(a);// cout << a << " " << b << endl;}sort(arr.begin(), arr.end());// dp[0][i]表示从第0个元素开始选到第i个元素结束// dp[1][i]表示从第1个元素开始选到第i个元素结束int res1 = 0, res2 = 0;for(int i = 0; i < n; i += 2){res1 += hash[arr[i]];}for(int i = 1; i < n; i += 2){res2 += hash[arr[i]];}cout << max(res1, res2) << endl;// dp[i][j]表示选择第n个元素开始，到第j个元素结束// 选j -> dp[i][j] = dp[i][j - 2] + v[j]// 不选j-> dp[i][j] = max(dp[i][j - 1], dp[i][j - 2]);return 0;
}/*  Day14_2，组队竞赛
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
/*
2
5 2 8 5 1 5 -> 1 5 8 ,2 5 5用例说明错了吧
1 2 5 5 5 8 （最小，第二大，第一大）
5 2 8 5 1 5 9 9 9 
1 9 9 ,2 8 9 , 5 5 5#define int long long
signed main()
{int n = 0;cin >> n;n *= 3;priority_queue<int> q;int x = 0;for(int i = 0; i < n; ++i){cin >> x;q.push(x);}int res = 0;for(int i = n / 3; i < n - n / 3; ++i){q.pop();// cout << q.top() << " ";res += q.top();q.pop();}cout << res << endl;return 0;
}
*//*  // Day14_1，乒乓球框
#include <iostream>
#include <vector>
using namespace std;int main()
{string str1, str2;cin >> str1 >> str2;vector<int> hash1(26, 0), hash2(26, 0);for(auto& e : str1){hash1[e - 'A']++;}for(auto& e : str2){hash2[e - 'A']++;}for(int i = 0; i < 26; ++i){if(hash1[i] < hash2[i]){cout << "No";return 0;}}cout << "Yes";return 0;
}
*/

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
// 偷房子那题？dp
const int N = 1e4 + 7;
int main()
{int n = 0;cin >> n;vector<int> hash(N);int x = 0;for(int i = 0; i < n; ++i){cin >> x;hash[x] += x;}vector<int> f(N), g(N); // f是选，g是不选for(int i = 1; i < N; ++i){f[i] = g[i - 1] + hash[i];g[i] = max(f[i - 1], g[i - 1]);}cout <<  max(f[N - 1], g[N - 1]);return 0;/*unordered_map<int, int> hash;vector<int> v(n);for(int i = 0; i < n; ++i){cin >> v[i];hash[v[i]] += v[i];}vector<int> arr;for(auto [a, b] : hash){arr.push_back(a);// cout << a << " " << b << endl;}sort(arr.begin(), arr.end());// dp[0][i]表示从第0个元素开始选到第i个元素结束// dp[1][i]表示从第1个元素开始选到第i个元素结束int res1 = 0, res2 = 0;for(int i = 0; i < n; i += 2){res1 += hash[arr[i]];}for(int i = 1; i < n; i += 2){res2 += hash[arr[i]];}cout << max(res1, res2) << endl;// dp[i][j]表示选择第n个元素开始，到第j个元素结束// 选j -> dp[i][j] = dp[i][j - 2] + v[j]// 不选j-> dp[i][j] = max(dp[i][j - 1], dp[i][j - 2]);return 0;*/
}

#include <climits>
#include <iostream>
#include <vector>
using namespace std;#define int long long
signed main()
{int x = 0;cin >> x;// vector<int> v; // 用两个变量优化int i = 1;int prev = 0, next = 0;do{// v.push_back(i * i);prev = next;next = i * i;++i;} while (next < x);if (next == x)cout << x << endl;else if (next - x < x - prev)cout << next << endl;elsecout << prev << endl;// if(v.back() == x)// cout << x << endl;// else if(v.back() - x < x - v[v.size() - 2])// cout << v.back() << endl;// else// cout << v[v.size() - 2] << endl;return 0;
}

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
signed main()
{int x = 0;cin >> x;int n = sqrt(x);int prev = n * n, next = (n + 1) * (n + 1);if(x - prev < next - x){cout << prev << endl;}else{cout << next << endl;}return 0;
}

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 2 * 1e5 + 1;
int main()
{int n = 0, m = 0;cin >> n >> m;int x = 0, y = 0;unordered_map<int, vector<int>> Edge;vector<int> in(N);while (cin >> x >> y) // x 指向 y{Edge[x].push_back(y);in[y]++;}// for(auto& [a, b] : Edge)// {// cout << a << " -> ";// for(auto& e : b)// {// cout << e << " ";// }// cout << endl;// }// for(auto& e : in)// {// if(e != 0)// cout << e << " ";// }// cout << endl;priority_queue<int> q;for (int i = 1; i <= n; ++i){if (in[i] == 0){q.push(i);// cout << "begin" << i;}}vector<int> res;while (q.size()){int tmp = q.top();q.pop();res.push_back(tmp);for (auto& e : Edge[tmp]) // tmp指向的边的入度减一{in[e]--;if (in[e] == 0) // 减为0了就进队列q.push(e);}// // Edge.erase(tmp); // 加这步?// for(auto& [a, b] : Edge)// {// cout << a << " -> ";// for(auto& e : b)// {// cout << e << " ";// }// cout << endl;// }// for(int i = 1; i <= n; ++i)// {// cout << in[i] << " ";// }// cout << endl;}if(res.size() != n){cout << -1;}else{for (int i = 0; i < n - 1; ++i){cout << res[i] << " ";}cout << res[n - 1]; // 666666666666666}return 0;
}

#include <climits>
#include <iostream>
using namespace std;int main() // Day16_3 双指针?
{string str;int n = 0;cin >> str >> n;int sz = str.size();int cnt = 0; // 统计C和G数量int begin = 0, cur = 0, maxCnt = INT_MIN;while(cur < sz - n){cnt = 0;for(int i = cur; i < cur + n; ++i){if(str[i] == 'C' || str[i] == 'G')++cnt;}if(cnt > maxCnt){begin = cur;maxCnt = cnt;}++cur;}string res(str.begin() + begin, str.begin() + begin + n);cout << res << endl;return 0;
}/*
#include <cmath> // Day16_2
#include <iostream>
#include <string>
using namespace std;bool isPrime(int x) // 判断是否是质数
{for(int i = 2; i <= sqrt(x); ++i){if(x % i == 0)return false;}return true;
}bool isTrue(int x) // 判断是否是神奇数
{string str = to_string(x);int sz = str.size();for(int i = 0; i < sz; ++i) // 枚举十位数{if(str[i] == '0')continue;for(int j = 0; j < sz; ++j) // 枚举个位数{if(j != i && isPrime((str[i] - '0') * 10 + (str[j] - '0')))return true;}}return false;
}int main()
{int a = 0, b = 0;cin >> a >> b;int cnt = 0;for(int i = a; i <= b; ++i){if(isTrue(i))++cnt;}cout << cnt << endl;return 0;
}
*//*
#include <cctype> // Day16_1
class Solution {
public:string formatString(string str, vector<char>& arg) {string ret;int sz1 = str.size(), sz2 = arg.size();int j = 0;for(int i = 0; i < sz1; ++i){if(isupper(str[i]) || islower(str[i])){if(i != 0 && str[i - 1] == '%')continue;ret += str[i];}if(str[i] == '%')ret += arg[j++];}while(j < sz2){ret += arg[j++];}return ret;}
};
*/

#include <algorithm>
#include <cstdlib>
#include <iostream>
using namespace std;
int main() // Day17_1_简单模拟
{int n = 0;cin >> n;string tmp;while (n){int val = n % 10;if (val % 2 == 0)tmp += "0";elsetmp += "1";n /= 10;}reverse(tmp.begin(), tmp.end());int res = atoi(tmp.c_str());cout << res;return 0;
}

#include <iostream>
#include <vector>
using namespace std;
#define int long long
signed main() // Day17_2_时间O（N^2），前缀和？-> 每一行和每一列的和，
{int n = 0, m = 0;cin >> n >> m;vector<vector<int>> vv(n, vector<int>(m));for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j){scanf("%lld", &vv[i][j]);}}vector<int> sum1(n); // 每一行的和for (int i = 0; i < n; ++i) // 每一行{for (int j = 0; j < m; ++j) // 每一列{sum1[i] += vv[i][j];}}// for(int i = 0; i < n; ++i)// {// cout << sum1[i] << " ";// }// cout << endl << endl;vector<int> sum2(m); // 每一列的和for (int j = 0; j < m; ++j) // 每一列{for (int i = 0; i < n; ++i) // 每一行{sum2[j] += vv[i][j]; // j i}}// for(int i = 0; i < n; ++i)// {// cout << sum2[i] << " ";// }// cout << endl << endl;vector<vector<int>> res(n, vector<int>(m));for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j){// res[i][j] = sum1[i] + sum2[j];// cout << sum1[i] + sum2[j] - vv[i][j] << " ";printf("%lld ", sum1[i] + sum2[j] - vv[i][j]);}printf("\n");}return 0;
}

#include <climits>
#include <ios>
#include <iostream>
#include <vector>
using namespace std;
#define int long long
signed main() // Day17_3_dp? 滑动窗口选快乐值->选不了多段？->两次。
// n和k还有限制太难了，放弃? n好像不是限制。。。。
{int n = 0, k = 0;cin >> n >> k;vector<int> a(n), b(n);for (int i = 0; i < n; ++i)cin >> a[i];for (int i = 0; i < n; ++i)cin >> b[i];int maxHappy = INT_MIN;int tmp = 0;for (int left = 0, right = 0; right < n; ++right){if (right - left <= k)tmp += a[right]; // 进窗口while (tmp > maxHappy) // 判断{if (right - left >= k)tmp -= a[left++]; // 出窗口if (tmp > maxHappy)maxHappy = tmp; // 更新结果}// cout << "tmp2 " << tmp << " left " << left << " right " << right << endl;}// cout << maxHappy << endl << endl;vector<int> index; // 存储最大快乐数区间的左下标int maxHappyTmp = INT_MIN + 2;tmp = 0;for (int left = 0, right = 0; right < n; ++right){if (right - left <= k)tmp += a[right]; // 进窗口while (tmp > maxHappyTmp) // 判断{if (right - left >= k)tmp -= a[left++]; // 出窗口if (tmp >= maxHappyTmp){maxHappyTmp = tmp; // 更新结果if (maxHappyTmp == maxHappy)index.push_back(left);}}}int b_min = INT_MAX, res = 0;for (auto& e : index){// cout << e << " ";tmp = 0;for (int i = e; i < k + e; ++i){tmp += b[i];// cout << i << " ";}if (tmp < b_min){res = e;b_min = tmp;}}cout << res + 1 << endl;return 0;
}

#include <climits>
#include <ios>
#include <iostream>
#include <vector>
using namespace std;
#define int long long
signed main() // Day17_3_dp? 滑动窗口选快乐值->选不了多段？->两次。
// n和k还有限制太难了，放弃? n好像不是限制。。。。
{int n = 0, k = 0;    // 看了题解后，k是滑动窗口的大小。。。。。cin >> n >> k;vector<int> a(n), b(n);for (int i = 0; i < n; ++i)cin >> a[i];for (int i = 0; i < n; ++i)cin >> b[i];int aSum = 0, bSum = 0, res = 0;int aMax = INT_MIN, bMin = INT_MAX;for (int left = 0, right = 0; right < n; ++right){aSum += a[right]; // 进窗口bSum += b[right]; // 进窗口while(right - left + 1 > k) // 判断{aSum -= a[left];bSum -= b[left];++left; // 出窗口}if(aSum > aMax || (aSum == aMax && bSum < bMin)) // 更新结果{res = left;aMax = aSum;bMin = bSum;}}cout << res + 1 << endl;return 0;
}

#include <string>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param param string字符串* @return string字符串*/string compressString(string param) {int left = 0, right = 1, sz = param.size();string ret;while (right < sz){int cnt = 1;while (param[left] == param[right]){++cnt;++right;}ret += param[left];if (cnt != 1)ret += to_string(cnt);// ret += cnt + '0'; // !!!!!!!!!!!!left = right;++right;}if (left == sz - 1)ret += param[left];// cout << left << " " << right << " " << sz << endl;return ret;}
};

#include <iostream>
#include <ostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
struct cmp
{bool operator()(pair<int, int> p1, pair<int, int> p2) // 堆的比较和逻辑相反{if (p1.first > p2.first)return false;else if (p1.first == p2.first)return p1.second > p2.second;elsereturn true;}
};
#define int long long
signed main()
{int n = 0, k = 0;cin >> n >> k;// vector<int> a(n), b(n);priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> qb;vector<int> a(n);for (int i = 0; i < n; ++i){cin >> a[i];}int x = 0;for (int i = 0; i < n; ++i){cin >> x;qb.push({ x, a[i] });}// while(qb.size())// {// cout << qb.top().first << " " << qb.top().second << endl;// qb.pop();// }// cout << "-------------" << endl;int sum1 = 0, sum2 = 0;while (qb.size() && k--){sum2 += qb.top().first;sum1 += qb.top().second;qb.pop();}cout << sum1 << " " << sum2 << endl;return 0;
}

#include <vector>
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 计算01背包问题的结果* @param V int整型 背包的体积* @param n int整型 物品的个数* @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi* @return int整型*/int knapsack(int V, int n, vector<vector<int> >& vw) {// vector<vector<int>> dp(n + 7, vector<int>(V + 7)); // 0到i最大重量，体积不超过j// // 不选，dp[i][j] = dp[i - 1][j]// 选，dp[i][j] = dp[i - 1][j - vw[i - 1][2]] + vw[i - 1][1]//for (int i = 1; i <= n; ++i)//{//	for (int j = 0; j <= V; ++j)//	{//		dp[i][j] = dp[i - 1][j];//		if (j - vw[i - 1][0] >= 0)//		{//			// cout << j << " " << vw[i - 1][0] << endl;//			dp[i][j] = max(dp[i][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);//		}//	}//}//return dp[n][V];vector<int> dp(V + 7); // 滚动数组优化for (int i = 1; i <= n; ++i){for (int j = V; j >= 0 && j - vw[i - 1][0] >= 0; --j){dp[j] = max(dp[j], dp[j - vw[i - 1][0]] + vw[i - 1][1]);}}return dp[V];}
};

#include <iostream> // day19_1
#include <numeric>
using namespace std;int mygcd(int a, int b)
{return b == 0 ? a : mygcd(b, a % b);
}int main()
{long long n = 0, x = 0;while(cin >> n >> x){int tmp = 0;for(int i = 0; i < n; ++i){cin >> tmp;if(tmp <= x)x += tmp;else// x += gcd(x, tmp); // 库里有这个函数或者__gcdx += mygcd(x, tmp);}cout << x << endl;}return 0;
}

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param grid int整型vector<vector<>> * @return int整型**/int maxValue(vector<vector<int> >& grid) { // Day19_2int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for(int i = 1; i <= m; ++i){for(int j = 1; j <= n; ++j){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];}}return dp[m][n];}
};

#include <iostream>
#include <string>
#include <vector>
using namespace std;int main()
{int T = 0;cin >> T;while(T--){int n = 0;cin >> n;vector<string> vStr(n);for(int i = 0; i < n; ++i)  {cin >> vStr[i];}// 枚举最左边的每一个字符，和最右边的每一个字符相比，有一样的就是trueint left = 0, right = n - 1;while(left < right){bool flag = false;for(auto& e1 : vStr[left]){for(auto& e2 : vStr[right]){if(e1 == e2){flag = true;break;}}if(flag)break;}if(!flag){cout << "No" << endl;break;}++left;--right;}if(left >= right)cout << "Yes" << endl;}return 0;
}

#include <iostream> // Day20_1
using namespace std;int main()
{int a = 0, h = 0, b = 0, k = 0;cin >> a >> h >> b >> k;long long res = 0;while(h > 0 && k > 0){res += a + b;h -= b;k -= a;}res += h > 0 ? a * 10 : 0;res += k > 0 ? b * 10 : 0;cout << res << endl;return 0;
}

#include <iostream> // Day20_1
#include <cmath>
using namespace std;int main()
{long long a = 0, h = 0, b = 0, k = 0;cin >> a >> h >> b >> k;long long res = 0, n = min(h / b, k / a); // 结果和回合数res += n * (a + b);h -= n * b; // 计算剩余血量k -= n * a;if(h > 0 && k > 0) // 判断是否都还活着{h -= b;k -= a;res += a + b;}if(h > 0 || k > 0)res += (h > 0 ? a * 10 : b * 10);cout << res << endl;return 0;
}

#include <iostream> // Day20_2
#include <vector>
using namespace std;int main()
{int n = 0;cin >> n;vector<int> a(n);for(int i = 0; i < n; ++i){cin >> a[i];}vector<int> dp(n);int res = a[0];dp[0] = a[0];for(int i = 1; i < n; ++i){dp[i] = max(dp[i - 1] + a[i], a[i]);res = max(res, dp[i]);}cout << res << endl;return 0;
}

#include <iostream>
using namespace std;int main()    // （判断是否全同->0，否则是n-1（回文减去1）或n）
{string str;cin >> str;int sz = str.size();bool flag = true;for(int i = 0; i < sz; ++i){   if(str[i] != str[0]) // 判断是否全同{flag = false;}}if(flag){cout << 0 << endl;return 0;}int left = 0, right = sz - 1;flag = true;    // 判断整个串是否是回文串while(left < right){if(str[left] != str[right]){flag = false;break;}++left;--right;}if(flag)cout << sz - 1<< endl;elsecout << sz << endl;return 0;  /*string str;cin >> str;int sz = str.size(), res = 1;for(int i = 0; i < sz; ++i){   int left = i, right = sz - 1;while(left < right){if(str[left] != str[right])break;--right;}// cout << right - left + 1 << endl;res = max(res, right - left + 1);}cout << res;// eeeeemeeeee处理不了return 0;   */ 
}

#include <iostream>
#include <vector>
using namespace std;int main()
{string str;cin >> str;int n = str.size();vector<vector<int>> dp(n, vector<int>(n));// dp[i][j] 表示i到j区间的最长回文子序列for(int i = n - 1; i >= 0; --i){dp[i][i] = 1;for(int j = i + 1; j < n; ++j){if(str[i] == str[j])dp[i][j] = dp[i + 1][j - 1] + 2;elsedp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}cout << dp[0][n - 1];return 0;
}

#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;int main()  // Day22_1
{string str1, str2;cin >> str1 >> str2;int n1 = str1.size(), n2 = str2.size();int res = INT_MAX;for(int i = 0; i < n2 - n1 + 1; ++i) // 枚举str2每一位{int cnt = 0;for(int j = 0; j < n1; ++j) // 枚举str1每一位{if(str2[i + j] != str1[j])++cnt;}// cout << "i " << i << endl;// cout << "cnt " << cnt << endl;res = min(res, cnt);}cout << res << endl;return 0;// string str1, str2;// cin >> str1 >> str2;// vector<int> hash(26);    // 错的，用str1依次和str2中间的比？// for(auto& e : str2)// {//     hash[e - 'a']++;// }// int res = 0;// for(auto& e : str1)// {//     if(hash[e - 'a'] == 0)//         ++res;//     else//         --hash[e - 'a'];// }// cout << res << endl;// return 0;
}

#include <iostream>
#include <vector>
using namespace std;int main()  // Day22_2
{int n = 0, aMax = 0;cin >> n;vector<int> a(n);for(int i = 0 ; i < n; ++i){cin >> a[i];aMax = max(aMax, a[i]);}for(int i = 0 ; i < n; ++i){while(a[i] < aMax){a[i] *= 2;}if(a[i] > aMax){cout << "NO" << endl;return 0;}}cout << "YES" << endl;return 0;
}

#include <iostream>
#include <vector>
using namespace std;int main()  // Day22_2
{int n = 0, aMax = 0;cin >> n;vector<int> a(n);for(int i = 0; i < n; ++i){cin >> a[i];aMax = max(aMax, a[i]);}for(int i = 0 ; i < n; ++i){// while(a[i] < aMax)// {//     a[i] *= 2;// }// if(a[i] > aMax)if((aMax % a[i]) || a[i] != 1 && a[i] < aMax && a[i] & (a[i] - 1) != 0){cout << "NO" << endl;return 0;}}cout << "YES" << endl;return 0;
}

#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main()
{int V = 0, n = 0;cin >> V >> n;vector<int> arr(n);for(int i = 0; i < n; ++i){cin >> arr[i];}vector<vector<int>> dp(n + 1, vector<int>(V + 1));// dp[i][j] 表示0到i个箱子所选择到的最大体积j// 选i if(j + arr[i] < V)dp[i][j] = dp[i - 1][j + arr[i]] + arr[i]// 不选i dp[i][j] = dp[i - 1][j]// 注意找原数组下标-1for(int i = 1; i <= n; ++i){for(int j = V; j >= 0; --j){dp[i][j] = dp[i - 1][j];if(j + arr[i - 1] <= V)dp[i][j] = max(dp[i][j], dp[i - 1][j + arr[i - 1]] + arr[i - 1]);// cout << dp[i][j] << endl;// res = min(res, V - dp[i][j]);}}cout << V - dp[n][0] << endl;return 0;
}

#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main()
{int V = 0, n = 0;cin >> V >> n;vector<int> arr(n);    // 下面找原数组不-1的话就多开一个位置占位，输入[1,n]for(int i = 0; i < n; ++i){cin >> arr[i];}vector<vector<int>> dp(n + 1, vector<int>(V + 1));for(int i = 1; i <= n; ++i){for(int j = 0; j <= V; ++j){dp[i][j] = dp[i - 1][j];if(j >= arr[i - 1])dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1]] + arr[i - 1]);}}cout << V - dp[n][V] << endl;return 0;
}

#include <iostream> // Day23_1，示例感觉都错了，还是没看懂，后面看懂了
using namespace std;
int main()
{int t = 0;cin >> t;while(t--){int h = 0, a = 0, H = 0, A = 0;cin >> h >> a >> H >> A; // 血量攻击力 血量攻击力int res = 0;int tmp = H;while(h > 0){// cout << h << " " << a << " " << tmp << " " << A << " res " << res << endl;if(A <= 0 || H <= a){res = -1;break;}if(a <= 0){res = 0;break;}tmp -= a;if(tmp <= 0){++res;tmp = H;continue;}h -= A;}cout << res << endl;}return 0;
}

#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;int main()
{int n = 0;cin >> n;string str;unordered_set<string> res;while(n--){cin >> str;sort(str.begin(), str.end());res.insert(str);}cout << res.size() << endl;return 0;
}

class Solution {    // Day_24_1
public:bool IsBalanced_Solution(TreeNode* pRoot) {return dfs2(pRoot) != -1;}int dfs(TreeNode* pRoot) // 返回-1代表不是平衡二叉树，不返回-1的话返回的是树高{if(pRoot == nullptr)return 0;if(pRoot->left == nullptr && pRoot->right == nullptr)return 1;if(abs(dfs(pRoot->left) - dfs(pRoot->right)) > 1)return -1;if(dfs(pRoot->left) != -1 && dfs(pRoot->right) != -1)return max(dfs(pRoot->left), dfs(pRoot->right)) + 1;return -1;}int dfs2(TreeNode* pRoot) // 题解代码。返回-1代表不是平衡二叉树，不返回-1的话返回的是树高{if(pRoot == nullptr)return 0;int left = dfs(pRoot->left);if(left == -1) // 剪枝return -1;int right = dfs(pRoot->right);if(right == -1)return -1;return abs(left - right) <= 1 ? max(left, right) + 1 : -1;}
};
/*
class Solution {    // Day_24_1
public:bool IsBalanced_Solution(TreeNode* pRoot) {if(pRoot == nullptr)return true;if(abs(rootHight(pRoot->left) - rootHight(pRoot->right)) > 1)return false;return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);}int rootHight(TreeNode* pRoot){if(pRoot == nullptr)return 0;if(pRoot->left == nullptr && pRoot->right == nullptr)return 1;return max(rootHight(pRoot->left), rootHight(pRoot->right)) + 1;}
};
*/

#include <climits>
#include <iostream>
#include <vector>
using namespace std;#define int long longsigned main()  // Day24_2 前缀和，然后枚举两个点
{int n = 0;cin >> n;vector<vector<int>> vv(n, vector<int>(n));int res = INT_MIN;for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){cin >> vv[i][j];res = max(res, vv[i][j]);}}vector<vector<int>> preSum(n + 1, vector<int>(n + 1));for(int i = 1; i <= n; ++i){for(int j = 1; j <= n; ++j){preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + vv[i - 1][j - 1];}}// for(int i = 1; i <= n; ++i)// {//     for(int j = 1; j <= n; ++j)//     {//         cout << preSum[i][j] << " ";//     }//     cout << endl;// }for(int i = 1; i <= n; ++i) // 下次用x1,y1, x2,y2{for(int j = 1; j <= n; ++j){for(int ii = 1; ii <= i; ++ii){for(int jj = 1; jj <= j; ++jj){res = max(res, preSum[i][j] - preSum[i][jj - 1] - preSum[ii - 1][j] + preSum[ii - 1][jj - 1]); // 注意-1// cout << i << j << " " << ii << jj << endl;}}}}cout << res << endl;return 0;
}/*
0 -2 -7 0 
9  9 -4 -2 
-4 6 -2 -3 
-1 13 11 6 
90 -2 -9 -9 
9 9  -4 -2 
5 6 -11 -8 
4 13 -4 -3 
15*/

#include <iostream>
using namespace std;int main()  // Day24_3_在连续区间中找个数为一半1的1和一半0的0？的区间的数目
{int n = 0, res = 0;string str;cin >> n >> str;int cnt0 = 0, cnt1 = 0;for(int i = 0; i < n; ++i){if(str[i] == '0')++cnt0;else++cnt1;}if(cnt0 % 2 != 0 || cnt1 % 2 != 0){cout << 0 << endl;return 0;}cnt0 /= 2, cnt1 /= 2;int left = 0, right = 0;int tmp0 = 0, tmp1 = 0;while(right < n - 1){if(str[right] == '0')++tmp0;else++tmp1;while(right - left + 1 > n / 2) // 下面注释的出窗口逻辑错了{if(str[left++] == '0')--tmp0;else--tmp1;}if(right - left + 1 == n / 2) // 注释掉也行，但有点怪{if(tmp0 == cnt0 && tmp1 == cnt1)res += 2;}++right;}/*while(right < n - 1){if(str[right] == '0')++tmp0;else++tmp1;while(left < n && right - left + 1 == n / 2 && tmp0 == cnt0 && tmp1 == cnt1){//cout << tmp0 << " " << tmp1 << endl;//cout << left << " " << right << endl;res += 2;if(str[left++] == '0')--tmp0;else--tmp1;}++right;}*/cout << res << endl;return 0;
}