getres

作者： 作者的头像   komoreb1 ,  2024-07-13 17:05:48 ,  所有人可见 ,  阅读 2

0


// // // // week1 计算矩阵边缘元素之和

// // // // #include [HTML_REMOVED]
// // // // using namespace std;
// // // // int n, m;
// // // // int main()
// // // // {
// // // // cin >> m >> n;
// // // // int res = 0;
// // // // int t;
// // // // for (int i = 1; i <= m; i)
// // // // {
// // // // for (int j = 1; j <= n; j)
// // // // {
// // // // cin >> t;
// // // // if (i == 1 || j == 1 || i == m || j == n)
// // // // {
// // // // res += t;
// // // // }
// // // // }
// // // // }
// // // // cout << res;
// // // // }

// // // // wwek1 sort
// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // using namespace std;
// // // // int n, m;

// // // // int main()
// // // // {
// // // // // 注意是多组测试用例
// // // // while (scanf(“%d%d”, &n, &m) != EOF)
// // // // {
// // // // priority_queue[HTML_REMOVED] pq;
// // // // int t;
// // // // for (int i = 1; i <= n; i++)
// // // // {
// // // // scanf(“%d”, &t);
// // // // pq.push(t);
// // // // }

// // // // for (int i = 1; i <= m; i++)
// // // // {
// // // // printf(“%d”, pq.top());
// // // // pq.pop();
// // // // if (i != m)
// // // // printf(” “);
// // // // }
// // // // }
// // // // }

// // // // week1 大理石问题

// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // using namespace std;
// // // // int N, Q;
// // // // int caseNum = 0;

// // // // int main()
// // // // {
// // // // while (cin >> N >> Q && N && Q)
// // // // {
// // // // caseNum++;
// // // // cout << “CASE# ” << caseNum << “:” << endl;
// // // // // binary-search
// // // // vector[HTML_REMOVED] a;
// // // // while (N–)
// // // // {
// // // // int t;
// // // // cin >> t;
// // // // a.push_back(t);
// // // // // get num
// // // // }
// // // // sort(a.begin(), a.end());

// // // // while (Q–)
// // // // {
// // // // int t;
// // // // cin >> t;
// // // // // 二分查找
// // // // int loc = lower_bound(a.begin(), a.end(), t) - a.begin();
// // // // if (a[loc] == t)
// // // // {
// // // // cout << t << ” found at ” << loc + 1 << endl;
// // // // }
// // // // else
// // // // {
// // // // cout << t << ” not found” << endl;
// // // // }
// // // // }
// // // // a.clear();
// // // // }
// // // // }

// // // // week1 EXCEL排序

// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // using namespace std;

// // // // struct Student
// // // // {
// // // // string num;
// // // // string name;
// // // // int score;
// // // // };

// // // // int C;
// // // // bool compare(Student a, Student b)
// // // // {
// // // // if (C == 1)
// // // // {
// // // // return a.num < b.num;
// // // // }
// // // // else if (C == 2)
// // // // {
// // // // if (a.name == b.name)
// // // // {
// // // // return a.num < b.num;
// // // // }
// // // // else
// // // // return a.name < b.name;
// // // // }
// // // // else if (C == 3)
// // // // {
// // // // if (a.score == b.score)
// // // // {
// // // // return a.num < b.num;
// // // // }
// // // // else
// // // // return a.score < b.score;
// // // // }
// // // // return false;
// // // // }

// // // // int main()
// // // // {
// // // // int casenum = 0;
// // // // int N;
// // // // while (cin >> N >> C && N && C)
// // // // {
// // // // casenum;
// // // // vector[HTML_REMOVED] students;
// // // // for (int i = 0; i < N; i)
// // // // {
// // // // Student temple;
// // // // cin >> temple.num >> temple.name >> temple.score;
// // // // students.push_back(temple);
// // // // }
// // // // sort(students.begin(), students.end(), compare);
// // // // cout << “Case ” << casenum << “:\n”;
// // // // for (int i = 0; i < N; i++)
// // // // {
// // // // cout << students[i].num << ” ” << students[i].name << ” ” << students[i].score << endl;
// // // // }
// // // // }
// // // // }

// // // // week1 安迪的第一个字典

// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]
// // // // #include [HTML_REMOVED]

// // // // using namespace std;
// // // // int main()
// // // // {
// // // // // 利用set的排序和去重功能
// // // // set[HTML_REMOVED] a;
// // // // string temple;
// // // // while (cin >> temple)
// // // // {
// // // // string buf = “”;
// // // // // 获取到的一个单词和一些附属
// // // // for (int i = 0; i < temple.length(); i++)
// // // // {
// // // // if (isalpha(temple[i]))
// // // // {
// // // // // 该位置是个字母
// // // // temple[i] = tolower(temple[i]);
// // // // buf += temple[i];
// // // // }
// // // // else
// // // // {
// // // // // 该位置不是个字母
// // // // if (!buf.empty())
// // // // {
// // // // // buf不为空 需要插入 并进行更新
// // // // a.insert(buf);
// // // // buf = “”;
// // // // }
// // // // }
// // // // }

// // // // // 字符串的结尾再进行判断
// // // // if (!buf.empty())
// // // // {
// // // // a.insert(buf);
// // // // }
// // // // }

// // // // for (string s : a)
// // // // {
// // // // cout << s << endl;
// // // // }
// // // // }

// // // // week2 单调栈
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // using namespace std;

// // // const int N = 3e6 + 10;
// // // int a[N], res[N];
// // // int n;
// // // int main()
// // // {
// // // cin >> n;

// // // for (int i = 1; i <= n; i)
// // // cin >> a[i];
// // // stack[HTML_REMOVED] st;
// // // st.push(1);
// // // for (int i = 2; i <= n; i)
// // // {
// // // while (!st.empty() && a[st.top()] < a[i])
// // // {
// // // res[st.top()] = i;
// // // st.pop();
// // // }
// // // st.push(i);
// // // }
// // // for (int i = 1; i <= n; i++)
// // // {
// // // cout << res[i];
// // // if (i != n)
// // // cout << ” “;
// // // }
// // // }

// // // // week2 看病要排队
// // // // 优先级队列 采用多种方式进行排序
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // using namespace std;

// // // struct Patient
// // // {
// // // int id;
// // // int priority;
// // // Patient(int a, int b)
// // // {
// // // id = a;
// // // priority = b;
// // // }

// // // friend bool operator<(Patient x, Patient y)
// // // {
// // // if (x.priority == y.priority)
// // // {
// // // return x.id > y.id; // 当优先级相同，编号小的先出队
// // // }
// // // return x.priority < y.priority; // 优先级大的先出队
// // // }

// // // // bool operator<(const Patient &other) const
// // // // {
// // // // if (priority == other.priority)
// // // // {
// // // // return id > other.id; // 当优先级相同，编号小的先出队
// // // // }
// // // // return priority < other.priority; // 优先级大的先出队
// // // // }
// // // };

// // // int main()
// // // {
// // // int N, A, B;
// // // while (cin >> N)
// // // {
// // // priority_queue[HTML_REMOVED] q[4];
// // // int count = 0;
// // // while (N–)
// // // {
// // // string t;
// // // cin >> t;
// // // if (t == “IN”)
// // // {
// // // cin >> A >> B;
// // // count++; // IN 发生第k次时 进来的病人的id为k
// // // q[A].push(Patient(count, B));
// // // }
// // // else
// // // {
// // // cin >> A;
// // // if (q[A].empty())
// // // {
// // // cout << “EMPTY” << endl;
// // // }
// // // else
// // // {
// // // auto t = q[A].top();
// // // q[A].pop();
// // // cout << t.id << endl;
// // // }
// // // }
// // // }
// // // }
// // // return 0;
// // // }

// // // // week2 字符串哈希
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // using namespace std;
// // // int N;

// // // int myHashFunc(string s)
// // // {
// // // int base = 75;
// // // int hashValue = 0;
// // // for (int i = 0; i < s.size(); i++)
// // // {
// // // hashValue = hashValue * i + s[i] - ‘a’;
// // // }
// // // return hashValue;
// // // }

// // // int main()
// // // {

// // // cin >> N;
// // // set[HTML_REMOVED] se;
// // // while (N–)
// // // {
// // // string tmp;
// // // cin >> tmp;
// // // se.insert(myHashFunc(tmp));
// // // }
// // // cout << se.size();
// // // }

// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]

// // // using namespace std;
// // // int main()
// // // {
// // // int N;
// // // cin >> N;
// // // unordered_set[HTML_REMOVED] us;
// // // while (N–)
// // // {
// // // string t;
// // // cin >> t;
// // // us.insert(t);
// // // }
// // // cout << us.size() << endl;
// // // }

// // // // 魔咒词典
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // #include [HTML_REMOVED]
// // // using namespace std;

// // // int gethash(string s)
// // // {
// // // long long res = 0;
// // // int base = 65487;
// // // int mod = 123456789;
// // // for (int i = 0; i < s.size(); i++)
// // // {
// // // res = (res * base + s[i] - ‘a’) % mod;
// // // }
// // // return res;
// // // }

// // // int main()
// // // {
// // // ios::sync_with_stdio(false);
// // // unordered_map[HTML_REMOVED] hash_to_mo;
// // // unordered_map[HTML_REMOVED] hash_to_fun;
// // // string s;
// // // // 词典最后一行以”@END@”结束
// // // while (getline(cin, s) && s != “@END@”)
// // // {
// // // auto pos = s.find(‘]’);
// // // string left = s.substr(1, pos - 1);
// // // string right = s.substr(pos + 2);
// // // hash_to_fun[gethash(left)] = right;
// // // hash_to_mo[gethash(right)] = left;
// // // }

// // // int N;
// // // cin >> N;
// // // cin.ignore();

// // // while (N–)
// // // {
// // // string t;
// // // getline(cin, t);
// // // if (t[0] == ‘[‘)
// // // {
// // // t = t.substr(1, t.size() - 2);
// // // if (hash_to_fun.count(gethash(t)) > 0)
// // // {
// // // cout << hash_to_fun[gethash(t)] << endl;
// // // }
// // // else
// // // {
// // // cout << “what?” << endl;
// // // }
// // // }
// // // else
// // // {
// // // if (hash_to_mo.count(gethash(t)) > 0)
// // // {
// // // cout << hash_to_mo[gethash(t)] << endl;
// // // }
// // // else
// // // {
// // // cout << “what?” << endl;
// // // }
// // // }
// // // }
// // // return 0;
// // // }

// // // 表达式括号匹配
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // using namespace std;
// // int main()
// // {
// // string s;
// // cin >> s;
// // stack[HTML_REMOVED] st;
// // bool flag = false;
// // for (int i = 0; i < s.size() - 1; i++)
// // {
// // if (s[i] == ‘(‘)
// // {
// // st.push(1);
// // }
// // else if (s[i] == ‘)’)
// // {
// // if (st.empty())
// // {
// // flag = true;
// // break;
// // }
// // st.pop();
// // }
// // }
// // if (!flag && st.empty())
// // cout << “YES”;
// // else
// // cout << “NO”;
// // }

// // // link/cut Tree
// // #include [HTML_REMOVED]
// // using namespace std;

// // long long l, r, k;

// // int main()
// // {
// // cin >> l >> r >> k;
// // // boundary case
// // bool hasSolution = false;
// // // get result
// // long long tmp = 1;
// // while (1)
// // {
// // if (tmp >= l && tmp <= r)
// // {
// // // set flag -> has sloution
// // hasSolution = true;
// // cout << tmp << ” “;
// // // tmp = tmp * k;
// // }
// // // tmp*k>r -> tmp>r/k avoid overflow in advance
// // if (tmp > r / k)
// // {
// // break;
// // }
// // tmp = tmp * k;
// // }
// // if (!hasSolution)
// // { // flag is no set
// // cout << -1 << endl;
// // }
// // }

// // // 简单枚举
// // #include [HTML_REMOVED]
// // using namespace std;
// // bool isLegal(int num1, int num2)
// // {
// // int a[10] = {0};
// // while (num1)
// // {
// // a[num1 % 10]; // log last location number
// // num1 = num1 / 10;
// // }
// // while (num2)
// // {
// // a[num2 % 10];
// // num2 = num2 / 10;
// // }
// // for (int i = 1; i < 10; i++)
// // {
// // // notice the judge condition
// // // if has the complicated number
// // if (a[i] != 1)
// // {
// // return false;
// // }
// // }
// // return true;
// // }

// // int main()
// // {
// // // xxxxx/xxxxx
// // int target;
// // int nCase = 0;
// // while (cin >> target && target)
// // {
// // bool hasSolution = false;
// // int right = 1234;
// // if (nCase++)
// // {
// // cout << endl;
// // }
// // // notice the cureculum condition
// // // only judge the left is OK
// // while (right * target < 99999) // actually can set <=98765
// // {
// // if (isLegal(right * target, right))
// // {
// // hasSolution = true;
// // // format output ->printf
// // printf(“%05d / %05d = %d\n”, right * target, right, target);
// // // cout << setw(5) << setfill(0) << right * target << ” /ßß ” << right << ” = ” << target << endl;
// // }

// // right += 1;
// // }
// // if (!hasSolution)
// // {
// // cout << “There are no solutions for ” << target << “.” << endl;
// // }
// // }
// // }

// // // 暴力——Maximum Product
// // #include [HTML_REMOVED]
// // using namespace std;
// // int main()
// // {
// // int n;
// // int casenum = 0;
// // while (cin >> n)
// // {
// // casenum;
// // long long res = 0;
// // long long data[100];
// // for (int i = 0; i < n; i)
// // {
// // cin >> data[i];
// // }
// // for (int i = 0; i < n; i)
// // {
// // for (int j = i; j < n; j)
// // {
// // long long temple = 1;
// // for (int k = i; k <= j; k++)
// // {
// // temple *= data[k];
// // }
// // if (temple > res)
// // {
// // res = temple;
// // }
// // }
// // }
// // if (res < 0)
// // res = 0;
// // printf(“Case #%d: The maximum product is %lld.\n\n”, casenum, res);
// // }
// // }

// // // Ignatius and the Princess II (第m个组合数)
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // using namespace std;
// // int main()
// // {
// // int num[1001];
// // int n;
// // int m;
// // while (cin >> n >> m)
// // {
// // for (int i = 1; i <= n; i)
// // {
// // num[i] = i;
// // }
// // int count = 1;
// // do
// // {
// // if (count == m)
// // {
// // break;
// // }
// // count;
// // } while (next_permutation(num + 1, num + n + 1));
// // for (int i = 1; i < n; i++)
// // {
// // cout << num[i] << ” “;
// // }
// // cout << num[n] << endl;
// // }
// // }

// // // 组合的输出
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // using namespace std;

// // bool compare(vector[HTML_REMOVED] a, vector[HTML_REMOVED] b)
// // {
// // for (int i = 0; i < a.size(); i++)
// // {
// // if (a[i] != b[i])
// // {
// // return a[i] < b[i];
// // }
// // }
// // }

// // int main()
// // {
// // int n, r;
// // while (cin >> n >> r)
// // {
// // vector[HTML_REMOVED]> res;
// // for (int i = 0; i < (1 << n); i)
// // {
// // int count = 0;
// // for (int j = 0; j <= n; j)
// // {
// // if (i & (1 << j))
// // count;
// // }
// // if (count == r)
// // {
// // vector[HTML_REMOVED] res1;
// // for (int j = 0; j <= n; j)
// // {
// // if (i & (1 << j))
// // {
// // res1.push_back(j + 1);
// // }
// // }
// // res.push_back(res1);
// // }
// // }
// // sort(res.begin(), res.end(), compare);
// // for (int i = 0; i < res.size(); i)
// // {
// // for (int j = 0; j < res[i].size(); j)
// // {
// // cout << setw(3) << res[i][j];
// // }
// // cout << endl;
// // }
// // }
// // }

// // // 逆序对
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // using namespace std;
// // long long res;
// // void merge(vector[HTML_REMOVED] &arr, int low, int high)
// // {
// // int mid = low + (high - low) / 2;
// // int n1 = mid + 1 - low;
// // int n2 = high - mid;
// // vector[HTML_REMOVED] L(n1), R(n2);
// // for (int i = 0; i < n1; i)
// // {
// // L[i] = arr[low + i];
// // }
// // for (int i = 0; i < n2; i)
// // {
// // R[i] = arr[mid + 1 + i];
// // }
// // int i = 0, j = 0;
// // int index = low;
// // while (i < n1 && j < n2)
// // {
// // if (L[i] <= R[j])
// // {
// // arr[index] = L[i];
// // }
// // else
// // {
// // arr[index] = R[j];
// // res += n1 - i;
// // }
// // }
// // while (i < n1)
// // {
// // arr[index] = L[i];
// // }
// // while (j < n2)
// // {
// // arr[index] = R[j];
// // }
// // }
// // void mergesort(vector[HTML_REMOVED] &arr, int low, int high)
// // {
// // if (low < high)
// // {
// // int mid = low + (high - low) / 2;
// // mergesort(arr, low, mid);
// // mergesort(arr, mid + 1, high);
// // merge(arr, low, high);
// // }
// // }

// // int main()
// // {
// // int n;
// // cin >> n;
// // vector[HTML_REMOVED] arr(n);
// // res = 0;
// // for (int i = 0; i < n; i++)
// // cin >> arr[i];
// // mergesort(arr, 0, n - 1);
// // cout << res;
// // }

// // // Max Sum 分治优化
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // using namespace std;
// // int arr[100010];
// // struct casenode
// // {
// // int sum, i, j;
// // casenode(int a, int b, int c)
// // {
// // sum = a;
// // i = b;
// // j = c;
// // }
// // };

// // casenode midmaxSubarray(int arr[], int mid, int left, int right)
// // {
// // casenode res(0, 0, 0);
// // int max_left = -10000;
// // int max_right = -10000;
// // int sum = 0;
// // // 向左寻找
// // for (int i = mid; i >= left; i–)
// // {
// // sum += arr[i];
// // if (sum >= max_left)
// // {
// // max_left = sum;
// // res.i = i;
// // }
// // }
// // sum = 0;
// // // 向右寻找
// // for (int j = mid + 1; j <= right; j++)
// // {
// // sum += arr[j];
// // if (sum > max_right)
// // {
// // max_right = sum;
// // res.j = j;
// // }
// // }
// // res.sum = max_left + max_right;
// // return res;
// // }

// // casenode maxSubarray(int arr[], int left, int right)
// // {
// // if (left == right)
// // return casenode(arr[left], left, right);
// // int mid = (left + right) / 2;
// // casenode s_left = maxSubarray(arr, left, mid);
// // casenode s_right = maxSubarray(arr, mid + 1, right);
// // casenode s_mid = midmaxSubarray(arr, mid, left, right);
// // if (s_left.sum >= s_right.sum && s_left.sum >= s_mid.sum)
// // {
// // return s_left;
// // }
// // else if (s_right.sum >= s_left.sum && s_right.sum >= s_mid.sum)
// // {
// // return s_right;
// // }
// // else
// // {
// // return s_mid;
// // }
// // }

// // int main()
// // {
// // int N;
// // int n;
// // int casenum = 1;
// // cin >> N;
// // while (N–)
// // {
// // cin >> n;
// // memset(arr, 0, sizeof(arr));
// // for (int i = 0; i < n; i)
// // cin >> arr[i];
// // casenode temple = maxSubarray(arr, 0, n - 1);
// // cout << “Case ” << casenum << “:” << endl;
// // cout << temple.sum << ” ” << temple.i + 1 << ” ” << temple.j + 1 << endl;
// // cout << endl;
// // casenum;
// // }
// // }

// // // 棋盘覆盖 分治
// // #include [HTML_REMOVED]
// // using namespace std;
// // int num = 0;
// // int board[1000][1000];
// // void chessBoard(int c, int r, int x, int y, int size)
// // {
// // if (size == 1)
// // return;
// // int flag = ++num;
// // // c开始是最左下角

// // int _size = size / 2; // 拆分

// // int mid_x = c + _size - 1; // 左下棋盘的最右上角
// // int mid_y = r + _size - 1;

// // if (x <= mid_x && y <= mid_y)
// // {
// // // 左下棋盘有特殊点
// // chessBoard(c, r, x, y, _size);
// // }
// // else
// // {
// // // 左下棋盘没有特殊点
// // // 放置标志 相当于重设特殊点
// // board[mid_x][mid_y] = flag;
// // chessBoard(c, r, mid_x, mid_y, _size);
// // }

// // if (x <= mid_x && y > mid_y)
// // {
// // // 左上棋盘有特殊点
// // chessBoard(c, r + _size, x, y, _size);
// // }
// // else
// // {
// // // 左上棋盘没有特殊点
// // // 放置标志 相当于重设特殊点
// // board[mid_x][mid_y + 1] = flag;
// // chessBoard(c, r + _size, mid_x, mid_y + 1, _size);
// // }

// // if (x > mid_x && y <= mid_y)
// // {
// // // 右下棋盘有特殊点
// // chessBoard(c + _size, r, x, y, _size);
// // }
// // else
// // {
// // // 右下棋盘没有特殊点
// // // 放置标志 相当于重设特殊点
// // board[mid_x + 1][mid_y] = flag;
// // chessBoard(c + _size, r, mid_x + 1, mid_y, _size);
// // }

// // if (x > mid_x && y > mid_y)
// // {
// // // 右上棋盘有特殊点
// // chessBoard(c + _size, r + _size, x, y, _size);
// // }
// // else
// // {
// // // 右上棋盘没有特殊点
// // // 放置标志 相当于重设特殊点
// // board[mid_x + 1][mid_y + 1] = flag;
// // chessBoard(c + _size, r + _size, mid_x + 1, mid_y + 1, _size);
// // }
// // }

// // int main()
// // {
// // int k, x, y;
// // cin >> k >> x >> y; // 棋盘大小和特殊方格的位置
// // board[x][y] = 0; // 特殊位置
// // int size = 1 << k;
// // // 调用函数
// // chessBoard(1, 1, x, y, size);
// // for (int i = 1; i <= size; i)
// // {
// // for (int j = 1; j <= size; j)
// // {
// // cout << board[i][j] << ” “;
// // }
// // cout << endl;
// // }
// // }
// // // a- good string
// // #include [HTML_REMOVED]
// // using namespace std;
// // string s;
// // int solve(int left, int right, char c)
// // {
// // if (left == right)
// // {
// // if (c == s[left])
// // return 0;
// // else
// // return 1;
// // }
// // int mid = (left + right) / 2;
// // int res1 = 0, res2 = 0;
// // for (int i = left; i <= mid; i)
// // {
// // if (c != s[i])
// // res1;
// // }
// // for (int i = mid + 1; i <= right; i)
// // {
// // if (c != s[i])
// // res2;
// // }
// // return min(res1 + solve(mid + 1, right, c + 1), res2 + solve(left, mid, c + 1));
// // }

// // int main()
// // {
// // int N;
// // cin >> N;
// // int n;
// // while (N–)
// // {
// // cin >> n >> s;
// // cout << solve(0, n - 1, ‘a’) << endl;
// // }
// // }

// // // 合并果子
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // using namespace std;

// // int main()
// // {
// // priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> pq;
// // int n; // 果子种类数
// // cin >> n;
// // int t;
// // int res = 0;
// // for (int i = 0; i < n; i++)
// // {
// // cin >> t;
// // pq.push(t); // 放入堆中
// // }

// // while (pq.size() > 1)
// // {
// // int t1 = pq.top();
// // pq.pop();
// // int t2 = pq.top();
// // pq.pop();
// // int t3 = t1 + t2;
// // res += t3;
// // pq.push(t3);
// // }
// // cout << res;
// // }

// // // 线段覆盖——区间数量问题 最早截至时间优先
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // using namespace std;

// // bool cmp(pair[HTML_REMOVED] &a, pair[HTML_REMOVED] &b)
// // {
// // return a.second < b.second;
// // }

// // vector[HTML_REMOVED]> vec;

// // int main()
// // {
// // int n;
// // while (cin >> n && n)
// // {
// // vec.clear();
// // int res = 1;
// // for (int i = 0; i < n; i++)
// // {
// // int start;
// // int end;
// // cin >> start >> end;
// // vec.push_back(make_pair(start, end)); // 放入vector中
// // } // 获取数据
// // sort(vec.begin(), vec.end(), cmp);
// // int cur_end_time = vec[0].second;

// // for (int i = 1; i < n; i)
// // {
// // if (vec[i].first >= cur_end_time)
// // {
// // cur_end_time = vec[i].second; // 更换结束时间
// // res; // 增加一个符合条件的节目
// // }
// // }

// // cout << res << endl;
// // }
// // }

// // // Stall Reservations —— 时间安排问题 最早开始时间优先
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // using namespace std;

// // struct cow
// // {
// // int start;
// // int end;
// // int index;
// // };

// // struct cmp
// // { // 优先级队列的优先级
// // bool operator()(pair[HTML_REMOVED] a, pair[HTML_REMOVED] b) const
// // {
// // // 定义优先级
// // return a.second > b.second;
// // }
// // };

// // // 定义牛牛的优先级
// // bool compare(cow a, cow b)
// // {
// // return a.start < b.start;
// // }
// // int res[50001];
// // int main()
// // {
// // vector[HTML_REMOVED] cows;
// // int n;
// // cin >> n;
// // // vector[HTML_REMOVED] res(n); // 为输出每个牛牛对应的牛棚的索引
// // for (int i = 0; i < n; i++)
// // {
// // cow temple;
// // int start, end;
// // cin >> start >> end;
// // temple.start = start;
// // temple.end = end;
// // temple.index = i;
// // cows.push_back(temple);
// // }
// // // 给vector中的牛牛进行排序
// // sort(cows.begin(), cows.end(), compare);

// // priority_queue[HTML_REMOVED], vector[HTML_REMOVED]>, cmp> pq; // 用来表示牛棚的数量

// // for (int i = 0; i < n; i)
// // {
// // // 从排序后的进行选择 排在前面的是最先开始的
// // cow cur_cow = cows[i]; // 当前被选择的牛
// // if (pq.empty() || pq.top().second >= cur_cow.start)
// // {
// // // 需要新开一个牛棚
// // // pair 存储 牛棚index和终止时间
// // pq.push(make_pair(pq.size() + 1, cur_cow.end));
// // res[cows[i].index] = pq.size(); // 存储牛牛的结果
// // }
// // else
// // {
// // // 更换堆顶牛棚的状态即可
// // pair[HTML_REMOVED] t = pq.top();
// // pq.pop();
// // // 更换终止时间
// // t.second = cur_cow.end;
// // res[cows[i].index] = t.first; // 牛棚的位置
// // pq.push(t);
// // }
// // }
// // cout << pq.size() << endl;
// // for (int i = 0; i < n; i)
// // {
// // cout << res[i] << endl;
// // }
// // // for (auto t : res)
// // // {
// // // cout << t << endl;
// // // }
// // }

// // // 均分纸牌
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]

// // using namespace std;

// // int main()
// // {
// // int n;
// // cin >> n;
// // vector[HTML_REMOVED] card_num(n);
// // int sum = 0;
// // for (int i = 0; i < n; i++)
// // {

// // cin >> card_num[i]; // 获取牌的
// // sum += card_num[i];
// // }
// // // 计算最终达到的平均值
// // int avg = sum / n;
// // // 将原始的每个位置减去avg
// // for (int i = 0; i < n; i)
// // {
// // card_num[i] -= avg;
// // }
// // // 找到首尾不是0 的位置
// // int i = 0;
// // while (card_num[i] == 0 && i < n)
// // {
// // i;
// // }
// // int j = n - 1;
// // while (card_num[j] == 0 && j > 0)
// // {
// // j–;
// // }
// // // 开始进行计数
// // int res = 0;
// // while (i < j)
// // {
// // card_num[i + 1] += card_num[i];
// // card_num[i] = 0;
// // res;
// // // 可能又存在连续的0
// // while (card_num[i] == 0 && i < n)
// // {
// // i;
// // }
// // }
// // cout << res;
// // }

// // // 删数问题——删除递增区间的最后一个数字
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]
// // #include [HTML_REMOVED]

// // using namespace std;

// // int main()
// // {
// // string n;
// // cin >> n; // 高精度正整数
// // int k;
// // cin >> k; // 想要删的个数
// // for (int i; i = 0, k–; n.erase(i, 1)) // 删除k个数字
// // {
// // while (i < n.length() && n[i] <= n[i + 1])
// // {
// // i++;
// // }
// // }
// // while (n.size() > 1 && n[0] == ‘0’)
// // {
// // n.erase(0, 1); // 去除前面 可能多余的0
// // }
// // cout << n;
// // }

// // 有向图的拓扑排序
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// const int N = 1e5 + 10, M = 1e5 + 10;
// int n, m;
// vector[HTML_REMOVED] edges[N];
// int indegree[N];
// vector[HTML_REMOVED] res;

// void Topu()
// {
// queue[HTML_REMOVED] q;
// for (int i = 1; i <= n; i++)
// {
// if (indegree[i] == 0)
// {
// q.push(i);
// }
// }
// while (!q.empty())
// {
// int fr = q.front();
// res.push_back(fr);
// q.pop();
// for (int v : edges[fr])
// {
// if (–indegree[v] == 0)
// {
// q.push(v);
// }
// }
// }
// }

// int main()
// {
// cin >> n >> m;
// res.clear();
// for (int i = 1; i <= m; i)
// {
// int x, y;
// cin >> x >> y;
// edges[x].push_back(y);
// indegree[y];
// }

// Topu();

// if (res.size() != n)
// {
// cout << -1;
// }
// else
// for (int r : res)
// cout << r << ” “;

// return 0;
// }

// // 数楼梯
// n = int(input())

// if n <= 1:
// print(1)
// else:
// a, b = 1, 1
// for i in range(2, n + 1):
// a, b = b, a + b
// print(b)

// // 采药 —— 01背包
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// int c[101];
// int p[101];
// int dp[101][1001] = {0};
// int main()
// {
// int T, M;
// cin >> T >> M;
// for (int i = 1; i <= M; i)
// {
// cin >> c[i] >> p[i];
// }
// for (int i = 1; i <= M; i)
// {
// for (int j = 1; j <= T; j)
// {
// if (j >= c[i])
// {
// dp[i][j] = max(dp[i - 1][j - c[i]] + p[i], dp[i - 1][j]);
// }
// else
// {
// dp[i][j] = dp[i - 1][j];
// }
// }
// }
// cout << dp[M][T];
// }
// // 装箱问题 —— 01背包
// #include [HTML_REMOVED]
// using namespace std;
// int p[31];
// int dp[31][20001] = {0};
// int main()
// {
// int V, n;
// cin >> V >> n;
// for (int i = 1; i <= n; i)
// {
// cin >> p[i];
// }
// for (int i = 1; i <= n; i)
// {
// for (int j = 1; j <= V; j)
// {
// if (p[i] <= j)
// {
// dp[i][j] = max(dp[i - 1][j - p[i]] + p[i], dp[i - 1][j]);
// }
// else
// {
// dp[i][j] = dp[i - 1][j];
// }
// }
// }
// cout << V - dp[n][V];
// }
// // Milking Time —— 带权区间问题 dp
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// struct node
// {
// int start;
// int end;
// int eff;
// } tem[1001]; // 存储区间

// bool compare(node a, node b)
// {
// return a.end < b.end; // 按活动时间升序
// }

// int p[1001];
// int dp[1001] = {0};
// int main()
// {
// int N, M, R;
// cin >> N >> M >> R;
// for (int i = 1; i <= M; i)
// {
// cin >> tem[i].start >> tem[i].end >> tem[i].eff;
// tem[i].end += R; // 休息R小时
// }
// sort(tem + 1, tem + 1 + M, compare); // 进行排序
// // 求解p[i]:在tem[i]开始前最后结束的活动
// for (int i = M; i >= 1; i–)
// {
// for (int j = i - 1; j > 0; j–)
// {
// if (tem[j].end <= tem[i].start)
// {
// p[i] = j;
// break; // 成功找到
// }
// }
// }
// for (int i = 1; i <= M; i)
// {
// dp[i] = max(dp[p[i]] + tem[i].eff, dp[i - 1]);
// }
// cout << dp[M];
// }
// // 最大子段和
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// int n;
// int a[200001];
// int D[200001];
// int main()
// {
// cin >> n;
// for (int i = 1; i <= n; i)
// {
// cin >> a[i];
// }
// int res = -100000;
// D[n] = a[n];
// for (int i = n - 1; i >= 1; i–)
// {
// if (D[i + 1] > 0)
// {
// D[i] = a[i] + D[i + 1];
// }
// else
// {
// D[i] = a[i];
// }
// res = max(res, D[i]); // 获取最大值
// }
// cout << res;
// }
// // Common Subsequence
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// int main()
// {
// string s1, s2;
// while (cin >> s1 >> s2)
// {
// int m = s1.length();
// int n = s2.length();
// vector[HTML_REMOVED]> dp(m + 1, vector[HTML_REMOVED](n + 1, 0));
// for (int i = 1; i <= m; i)
// {
// for (int j = 1; j <= n; j++)
// {
// if (s1[i - 1] == s2[j - 1])
// {
// dp[i][j] = dp[i - 1][j - 1] + 1;
// }
// else
// {
// dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
// }
// }
// }
// cout << dp[m][n] << endl;
// }
// }

// // 最长公共子序列
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]

// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// const int mod = 1e8;
// int main()
// {
// string s1;
// string s2;
// cin >> s1 >> s2;
// int m = s1.length();
// int n = s2.length();
// vector[HTML_REMOVED]> dp(2, vector[HTML_REMOVED](n + 1, 0));
// vector[HTML_REMOVED]> num(2, vector[HTML_REMOVED](n + 1, 0));
// for (int j = 0; j <= n; j)
// {
// num[0][j] = 1;
// }
// num[1][0] = 1;
// int t = 0; // 状态跳转
// for (int i = 1; i < m; i, t ^= 1) // 状态转换
// {

// for (int j = 1; j < n; j++)
// {
// num[t ^ 1][j] = 0;
// if (s1[i - 1] == s2[j - 1])
// {

// dp[t ^ 1][j] = dp[t][j - 1] + 1;
// num[t ^ 1][j] += num[t][j - 1] % mod;
// }
// else
// {
// dp[t ^ 1][j] = max(dp[t][j], dp[t ^ 1][j - 1]);
// }
// if (dp[t ^ 1][j] == dp[t][j])
// {
// num[t ^ 1][j] += num[t][j] % mod;
// }
// if (dp[t ^ 1][j] == dp[t ^ 1][j - 1])
// {
// num[t ^ 1][j] += num[t ^ 1][j - 1] % mod;
// }
// if (dp[t ^ 1][j] == dp[t][j - 1])
// {
// num[t ^ 1][j] -= num[t][j - 1];
// }
// }
// }
// cout << dp[t][n - 1] << endl;
// cout << num[t][n - 1] << endl;
// }

// // Red and Black
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// int W, H;
// char mat[21][21];
// int a, b;
// char temple;
// int res = 0;
// void dfs(int x, int y)
// {
// mat[x][y] = ‘#’;
// res;
// if (x - 1 >= 1 && mat[x - 1][y] == ‘.’)
// {
// dfs(x - 1, y);
// }
// if (x + 1 <= H && mat[x + 1][y] == ‘.’)
// {
// dfs(x + 1, y);
// }
// if (y - 1 >= 1 && mat[x][y - 1] == ‘.’)
// {
// dfs(x, y - 1);
// }
// if (y + 1 <= W && mat[x][y + 1] == ‘.’)
// {
// dfs(x, y + 1);
// }
// }
// int main()
// {
// while (cin >> W >> H)
// {
// if (W == 0 && H == 0)
// {
// break;
// }
// for (int i = 1; i <= H; i)
// {
// for (int j = 1; j <= W; j++)
// {
// cin >> temple;
// if (temple == ‘@’)
// {
// a = i;
// b = j;
// }
// mat[i][j] = temple;
// }
// }
// // 进行深搜 从(a,b)开始
// dfs(a, b);
// cout << res << endl;
// res = 0;
// };
// }

// // 考前临时抱佛脚
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// int s[5];
// int times[21][5];

// int main()
// {
// cin >> s[1] >> s[2] >> s[3] >> s[4];
// int res_res = 0;
// for (int i = 1; i <= 4; i)
// {
// int sum = 0;
// for (int j = 1; j <= s[i]; j)
// {
// int temple;
// cin >> temple;
// times[j][i] = temple;
// sum += temple;
// }
// // 一个个科目进行解决
// // 转换为01背包问题
// int dp[1001] = {0};
// for (int k = 1; k <= s[i]; k)
// {
// for (int w = sum / 2; w >= times[k][i]; w–)
// {
// dp[w] = max(dp[w], dp[w - times[k][i]] + times[k][i]);
// }
// }
// int result = 0;
// for (int i = 1; i <= sum / 2; i)
// {
// if (dp[i] > result)
// result = dp[i];
// }
// res_res += max(result, sum - result);
// }
// cout << res_res;
// }
// // 马的遍历
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// #include [HTML_REMOVED]
// typedef pair[HTML_REMOVED] PI;
// int n, m, x, y;
// int dx[8] = {1, 1, -2, -2, -1, -1, 2, 2};
// int dy[8] = {-2, 2, 1, -1, 2, -2, -1, 1};
// int res[401][401];
// bool visited[401][401] = {false};
// queue[HTML_REMOVED] q;
// void bfs(int x, int y)
// {
// q.push(make_pair(x, y)); // 压入队列中
// visited[x][y] = true; // 标记为已经见过
// int temple = 0;
// res[x][y] = 0;
// while (!q.empty())
// {
// PI top = q.front();
// q.pop(); // 获取队列首元素
// temple = res[top.first][top.second] + 1; // 存储步骤数量
// for (int i = 0; i < 8; i)
// {
// int xi = top.first + dx[i];
// int yi = top.second + dy[i];
// if (!visited[xi][yi] && xi <= n && xi >= 1 && yi <= m && yi >= 1)
// {
// q.push(make_pair(xi, yi));
// visited[xi][yi] = true; // 标记为已经见过
// res[xi][yi] = temple; // 更新步骤数量
// }
// }
// }
// }
// int main()
// {
// cin >> n >> m >> x >> y;
// memset(res, -1, sizeof(res));
// bfs(x, y);
// for (int i = 1; i <= n; i)
// {
// for (int j = 1; j <= m; j++)
// {
// cout << res[i][j] << ” “;
// }
// cout << endl;
// }
// }

// // 八数码问题
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;

// string d = “durl”;
// int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// struct node
// {
// string state;
// int cantor;
// int pos;
// node(string s, int c, int pp) : state(s), cantor(c), pos(pp) {}
// };
// int visited[362888] = {0};
// int factory[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

// bool legal(int x, int y)
// {
// if (x >= 0 && x <= 2 && y >= 0 && y <= 2)
// return true;
// return false;
// }

// int getCanter(string str)
// {
// int res = 0;
// for (int i = 0; i < 9; i)
// {
// int cnt = 0;
// for (int j = i + 1; j < 9; j)
// if (str[i] > str[j])
// cnt++;
// res += cnt * factory[9 - i - 1];
// }
// return res;
// }

// struct path
// {
// int from;
// char dir;
// } pa[362888];

// void bfs(string init)
// {
// queue[HTML_REMOVED] que;
// int num = getCanter(init);
// que.push(node(init, num, 8));
// visited[num] = 1;
// pa[num].from = -1;
// while (!que.empty())
// {
// node top = que.front();
// que.pop();
// int x = top.pos / 3;
// int y = top.pos % 3;
// for (int i = 0; i < 4; i)
// {
// int xx = x + dir[i][0];
// int yy = y + dir[i][1];
// if (!legal(xx, yy))
// continue;
// int move = 3 * xx + yy;
// string next_state = top.state;
// swap(next_state[top.pos], next_state[move]);
// num = getCanter(next_state);
// if (visited[num])
// continue;
// visited[num] = 1;
// que.push(node(next_state, num, move));
// pa[num].from = top.cantor;
// pa[num].dir = d[i];
// }
// }
// }
// int main()
// {
// bfs(“12345678x”);
// string tmp;
// while (getline(cin, tmp))
// {
// string puzzle;
// for (int i = 0; i < tmp.size(); i)
// {
// if (tmp[i] != ‘ ‘)
// {
// puzzle.push_back(tmp[i]);
// }
// }
// int num = getCanter(puzzle);
// if (visited[num] == 0)
// {
// cout << “unsolvable” << endl;
// continue;
// }
// while (true)
// {
// if (pa[num].from == -1)
// break;
// cout << pa[num].dir;
// num = pa[num].from;
// }
// cout << endl;
// }
// }

// // 走迷宫 广搜
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// typedef pair[HTML_REMOVED] P;
// char m_map[41][41];
// int R, C;
// int dx[4] = {0, 0, 1, -1};
// int dy[4] = {1, -1, 0, 0}; // 确定行走方向
// int res;
// queue[HTML_REMOVED] q1, q2;
// int state[41][41]; // 记录当前状态 从前往后为1 从后往前为2

// int dis[41][41]; // 需要走的步数

// bool check(int x, int y)
// {
// if (m_map[x][y] == ‘.’ && x >= 1 && x <= R && y >= 1 && y <= C)
// {
// return true;
// }
// return false;
// }

// void double_bfs()
// {
// int flag; // 确定是从哪边开始搜
// // 初始化
// q1.push(make_pair(1, 1));
// dis[1][1] = 1;
// state[1][1] = 1;
// q2.push(make_pair(R, C));
// dis[R][C] = 1;
// state[R][C] = 2;
// while (!q1.empty() && !q2.empty())
// {
// P temple;
// if (q1.size() > q2.size())
// {
// // 从q2开始搜
// temple = q2.front();
// q2.pop();
// flag = 1;
// }
// else
// {
// // 从q1开始搜
// temple = q1.front();
// q1.pop();
// flag = 2;
// }

// for (int i = 0; i < 4; i++)
// {
// // 更新坐标
// int xi = temple.first + dx[i];
// int yi = temple.second + dy[i];
// if (check(xi, yi))
// { // 满足条件
// if (!dis[xi][yi]) // 没有被搜索到
// {
// dis[xi][yi] = dis[temple.first][temple.second] + 1;
// state[xi][yi] = state[temple.first][temple.second];
// if (flag == 1)
// q2.push(make_pair(xi, yi));
// else
// q1.push(make_pair(xi, yi));
// }
// else
// {
// if (state[xi][yi] + state[temple.first][temple.second] == 3) // 在此处相遇
// {
// res = dis[xi][yi] + dis[temple.first][temple.second];
// return; // 结束
// }
// }
// }
// }
// }
// }

// int main()
// {
// cin >> R >> C;
// for (int i = 1; i <= R; i)
// {
// for (int j = 1; j <= C; j)
// {
// cin >> m_map[i][j];
// }
// }
// double_bfs();
// cout << res << endl;
// }

// // 胜利大逃亡 —— 状压 + BFS广搜
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// int n, m, t;

// char m_map[21][21];
// bool visited[21][21][1 << 11];
// int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// struct node
// {
// int x, y, key, time;
// node(){};
// node(int u, int v, int z, int w)
// {
// x = u;
// y = v;
// key = z;
// time = w;
// }
// };
// queue[HTML_REMOVED] q;

// int bfs(int stx, int sty)
// {
// int x, y, key;
// node now;
// q.push(node(stx, sty, 0, 0));
// visited[stx][sty][0] = 1;
// while (!q.empty())
// {
// now = q.front();
// q.pop();
// if (now.time >= t)
// return -1;
// if (m_map[now.x][now.y] == ‘^’)
// return now.time;
// for (int i = 0; i < 4; i++)
// {
// x = now.x + dir[i][0];
// y = now.y + dir[i][1];
// key = 0;
// if (x >= 0 && x <= n - 1 && y >= 0 && y <= m - 1 && m_map[x][y] != ‘*’ && !visited[x][y][now.key])
// {
// if (m_map[x][y] >= ‘a’ && m_map[x][y] <= ‘j’)
// key |= (1 << (m_map[x][y] - ‘a’));
// else if (m_map[x][y] >= ‘A’ && m_map[x][y] <= ‘J’)
// {
// if (!(now.key & (1 << (m_map[x][y] - ‘A’))))
// continue;
// }
// q.push(node(x, y, now.key | key, now.time + 1));
// visited[x][y][now.key] = 1;
// }
// }
// }
// return -1;
// }

// int main(void)
// {
// int res, stx, sty;
// while (cin >> n >> m >> t)
// {
// memset(visited, 0, sizeof(visited));
// while (!q.empty())
// {
// q.pop();
// }
// for (int i = 0; i < n; i)
// {
// for (int j = 0; j < m; j)
// {
// cin >> m_map[i][j];
// if (m_map[i][j] == ‘@’)
// {
// stx = i;
// sty = j;
// }
// }
// }
// res = bfs(stx, sty);
// cout << res << endl;
// }
// }

// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// int main()
// {
// string s;
// getline(cin, s);
// reverse(s.begin(), s.end());

// for (int i = 0; i < s.size(); i)
// {
// int j = i;
// if (isalpha(s[j]))
// {
// while (j < s.size() && isalpha(s[j]))
// {
// if (islower(s[j]))
// s[j] = toupper(s[j]);
// else if (isupper(s[j]))
// s[j] = towlower(s[j]);
// j;
// }
// reverse(s.begin() + i, s.begin() + j);
// i = j - 1;
// }
// }

// for (int i = 0; i < s.size(); i++)
// {
// cout << s[i];
// }
// return 0;
// }

// // 亲戚 —— 并查集
// #include [HTML_REMOVED]
// using namespace std;
// const int maxn = 5001;
// int s[maxn];

// int height[maxn];
// void init_set()
// {
// for (int i = 1; i <= maxn; i++)
// {
// s[i] = i;
// height[i] = 0;
// }
// }
// int find_set(int x)
// {
// if (x != s[x])
// s[x] = find_set(s[x]); // 查找优化
// return s[x];
// }
// void union_set(int x, int y)
// {
// x = find_set(x);
// y = find_set(y);
// if (height[x] == height[y])
// {
// height[x] = height[x] + 1; // 树高度相等 +1
// s[x] = y;
// }
// else
// {
// if (height[x] < height[y]) // 高树高度保持不变
// s[x] = y;
// else
// s[y] = x;
// }
// }

// int main()
// {
// int n, m, p;
// cin >> n >> m >> p;
// init_set(); // 初始化并查集
// int temple1, temple2;
// while (m–)
// {
// cin >> temple1 >> temple2;
// // 获取亲戚关系 放到并查集中
// union_set(temple1, temple2);
// }
// while (p–)
// {
// cin >> temple1 >> temple2;
// if (find_set(temple1) == find_set(temple2))
// {
// cout << “Yes” << endl;
// }
// else
// {
// cout << “No” << endl;
// }
// }
// }
// // 食物链 —— 并查集的扩展域
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// const int maxn = 50001;

// int s[maxn * 3];
// int find_set(int x)
// {
// if (x != s[x])
// {
// s[x] = find_set(s[x]); // 查找优化
// }
// return s[x];
// }
// int n, k;
// int res = 0;
// void init_set()
// {
// for (int i = 1; i <= 3 * n; i)
// {
// s[i] = i; // 初始化并查集。
// }
// }
// int main()
// {
// // cin >> n >> k;
// scanf(“%d%d”, &n, &k);
// init_set(); // 初始化
// while (k–)
// {
// int D, x, y;
// // cin >> D >> x >> y;
// scanf(“%d%d%d”, &D, &x, &y);
// if (x > n || y > n)
// {
// res;
// continue;
// }
// if (D == 1)
// {
// // x和y是同类
// if (find_set(x) == find_set(y + n) || find_set(x) == find_set(y + 2 * n))
// { // 不能有猎物和天敌关系
// res;
// continue;
// }
// s[find_set(y)] = find_set(x); // 本身同类
// s[find_set(y + n)] = find_set(x + n); // 猎物域同类
// s[find_set(y + 2 * n)] = find_set(x + 2 * n); // 天敌域同类
// }
// if (D == 2)
// { // x吃y
// // 不能有同类和天敌反关系
// if (find_set(x) == find_set(y) || find_set(x) == find_set(y + 2 * n))
// {
// res;
// continue;
// }
// s[find_set(x)] = find_set(y + n);
// s[find_set(x + n)] = find_set(y + 2 * n);
// s[find_set(x + 2 * n)] = find_set(y);
// }
// }
// printf(“%d”, res);
// }
// // 二叉树的遍历
// #include [HTML_REMOVED]
// using namespace std;
// struct node
// {
// int left;
// int right;
// int father;
// } tree[1000001];

// void preorder(int t)
// {
// cout << t << ” “;
// if (tree[t].left)
// {
// preorder(tree[t].left);
// }
// if (tree[t].right)
// {
// preorder(tree[t].right);
// }
// }

// void inorder(int t)
// {
// if (tree[t].left)
// {
// inorder(tree[t].left);
// }
// cout << t << ” “;
// if (tree[t].right)
// {
// inorder(tree[t].right);
// }
// }

// void lastorder(int t)
// {
// if (tree[t].left)
// {
// lastorder(tree[t].left);
// }
// if (tree[t].right)
// {
// lastorder(tree[t].right);
// }
// cout << t << ” “;
// }

// int main()
// {
// int n;
// cin >> n;
// int temple1, temple2;
// for (int i = 1; i <= n; i++)
// {
// cin >> temple1 >> temple2;
// if (temple1)
// {
// tree[i].left = temple1;
// tree[temple1].father = i;
// }
// if (temple2)
// {
// tree[i].right = temple2;
// tree[temple2].father = i;
// }
// }
// preorder(1);
// cout << endl;
// inorder(1);
// cout << endl;
// lastorder(1);
// }

// // 中位数 —— 动态版
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// priority_queue[HTML_REMOVED] q1; // 大根堆
// priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> q2; // 小根堆
// int main()
// {
// // 中位数左边是大根堆
// int N;
// int mid;
// cin >> N;
// cin >> mid;
// cout << mid << endl; // 输出第一个数
// q1.push(mid);
// for (int i = 1; i <= (N - 1) / 2; i++)
// {
// int x, y;
// cin >> x >> y;
// mid = q1.top();
// if (x < mid)
// {
// q1.push(x);
// }
// else
// {
// q2.push(x);
// }
// if (y < mid)
// {
// q1.push(y);
// }
// else
// {
// q2.push(y);
// }
// // 两个数xy都放入了大根堆q1中
// if (q1.size() - q2.size() == 3)
// {
// q2.push(q1.top());
// q1.pop();
// }
// // 两个数都放入了小根堆q2中
// else if (q2.size() - q1.size() == 1)
// {
// q1.push(q2.top());
// q2.pop();
// }
// // 选择大根堆的size比小根堆的size大1
// cout << q1.top() << endl;
// }
// }

// // Shaolin
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// map[HTML_REMOVED] mp; // map按照key进行排序
// int main()
// {
// // ios::sync_with_stdio(false);
// int n;
// // while (cin >> n && n)
// while (scanf(“%d”, &n) && n)
// {
// mp.clear(); // 注意清空之前的数据
// mp[1e9] = 1; // 方丈 战斗力–id
// while (n–)
// {
// int id, g, res;
// // cin >> id >> g;
// scanf(“%d %d”, &id, &g);
// mp[g] = id;
// map[HTML_REMOVED]::iterator it = mp.find(g); // 进行位置查找
// if (it == mp.begin())
// { // 战斗力较高位于第一
// res = (it)->second;
// }
// else
// {
// map[HTML_REMOVED]::iterator it_2 = it;
// it_2–;
// it;
// // 选择最接近的对应id
// if (it->first - g >= g - it_2->first)
// res = it_2->second;
// else
// res = it->second;
// }
// // cout << id << ” ” << res << endl;
// printf(“%d %d\n”, id, res);
// }
// }
// }
// // 统计难题 —— 字典树
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// const int maxn = 5e5 + 1;
// const int charsize = 26;
// int nxt[maxn + 1][charsize];
// int total[maxn + 1];
// int coun = 0;

// void insert(char s[], int len)
// {
// int current = 0;
// for (int i = 0; i < len; i)
// {
// int x = s[i] - ‘a’;
// if (!nxt[current][x])
// nxt[current][x] = coun;
// current = nxt[current][x];
// total[current]++;
// }
// }

// int search(char s[], int len)
// {
// int current = 0;
// for (int i = 0; i < len; i++)
// {
// int x = s[i] - ‘a’;
// if (!nxt[current][x])
// {
// return 0; // 没找到
// }
// current = nxt[current][x];
// }
// return total[current];
// }

// int main()
// {
// char str[11];
// while (gets(str))
// {
// int len = strlen(str);
// if (!len)
// break;
// insert(str, len);
// }
// while (gets(str))
// {
// printf(“%d\n”, search(str, strlen(str)));
// }
// }

// // KMP算法
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// const int maxlen = 1e6 + 1;
// int _next[maxlen]; // next数组
// int main()
// {
// string up, down;
// cin >> up;
// cin >> down; // 模式串
// _next[0] = _next[1] = 0;
// // 获取next数组
// int j = 0;
// for (int i = 1; i < down.size(); i)
// {
// while (j && down[i] != down[j])
// j = _next[j];
// _next[i + 1] = (down[i] == down[j] ? j : 0);
// }
// j = 0; // j是下面要匹配字符串当前索引
// for (int i = 0; i < up.size(); i)
// {
// while (j && up[i] != down[j])
// {
// j = _next[j]; // 从next数组中寻找
// }
// if (up[i] == down[j])
// {
// j;
// }
// if (j == down.size())
// {
// printf(“%d\n”, i - down.size() + 2);
// }
// }
// for (int i = 1; i <= down.size(); i++)
// {
// printf(“%d “, _next[i]);
// }
// }

// // 确定比赛名次 —— 拓扑排序
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// const int MAXN = 501;
// int M, N;
// // link
// vector[HTML_REMOVED] edge[MAXN];
// // indegree
// int indegree[MAXN];
// // small treap
// priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> pq;
// // res
// int res[MAXN];
// void toposort()
// {
// // get indegree==0
// int idx = 0;
// for (int i = 1; i <= N; i)
// {
// if (indegree[i] == 0)
// {
// pq.push(i);
// // res[idx] = i;
// }
// }
// while (!pq.empty())
// {
// int _top = pq.top();
// pq.pop();
// res[idx] = _top; // 这里才设置拓扑序
// for (int nxt : edge[_top])
// {
// // 减去删掉的入度边
// if (–indegree[nxt] == 0)
// {
// pq.push(nxt);
// }
// }
// }
// cout << res[1];
// for (int i = 2; i <= N; i)
// {
// cout << ” ” << res[i];
// }
// }
// int main()
// {
// while (cin >> N >> M)
// {
// // clear
// for (int i = 0; i < MAXN; i)
// {
// edge[i].clear();
// }
// int u, v;
// while (M–)
// {
// cin >> u >> v;
// // M行的输入数据
// edge[u].push_back(v);
// indegree[v]; // in
// }
// toposort();
// }
// }
// // 欧拉路径
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// #include [HTML_REMOVED]
// int n, m;
// const int MAXN = 100001;
// // 邻接链表矩阵
// vector[HTML_REMOVED] edge[MAXN];
// // 入度
// int indegree[MAXN];
// // 出度
// int outdegree[MAXN];

// int judge_oula()
// {
// // 默认返回的深搜的起点
// int start = 1;
// bool allequal = true;
// int sum1 = 0;
// int sum2 = 0;
// for (int i = 1; i <= n; i++)
// {
// if (indegree[i] != outdegree[i])
// {
// allequal = false;
// }

// if (indegree[i] - outdegree[i] == 1)
// {
// // in - out ==1
// sum1;
// }
// if (indegree[i] - outdegree[i] == -1)
// {
// // out - in ==1
// sum2;
// start = i; // 可以选做起点 出度更大
// }
// if (indegree[i] - outdegree[i] > 1)
// {
// // 入度比出度不止>1
// return -1; // 没有Oula路
// }
// }
// if (!(allequal || ((sum1 == sum2) && sum1 == 1)))
// {
// // 不满足第二个条件
// return -1;
// }
// // if (!allequal)
// // {
// // return -1;
// // // 不满足第三个条件
// // }
// return start; // 返回深搜起点
// }
// // PATH
// #include [HTML_REMOVED]
// stack[HTML_REMOVED] res;

// int cont[MAXN]; // 对应下标为i的节点已经访问了几条边

// void dfs(int st)
// {
// while (cont[st] < edge[st].size())
// {
// int idx = cont[st];
// cont[st]++; // 下一条边
// // 继续深搜
// dfs(edge[st][idx]);
// }
// // 出深搜
// res.push(st);
// }
// int main()
// {

// cin >> n >> m;
// int u, v;
// while (m–)
// {
// // M行的输入数据
// cin >> u >> v;
// edge[u].push_back(v);
// indegree[v]; // in
// outdegree[u]; // out
// }
// // 需要字典序最小的欧拉路径 此处进行排序
// for (int i = 1; i <= n; i++)
// {
// sort(edge[i].begin(), edge[i].end());
// }
// // 判断是否有欧拉路 同时返回深搜起点
// int start = judge_oula();
// if (start == -1)
// {
// cout << “No” << endl;
// }
// else
// {
// // 深搜
// dfs(start);
// while (!res.empty())
// {
// cout << res.top() << ” “;
// res.pop();
// }
// }
// }
// // 迷宫城堡 —— 强连通分量
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// const int MAXN = 10001;
// int M, N, k;
// // link
// vector[HTML_REMOVED] edge[MAXN];
// vector[HTML_REMOVED] reedge[MAXN];
// bool visited[MAXN];
// // 记录第一次dfs的序列
// int first_s[MAXN];

// // 深搜过程需要确认是否访问过
// void dfs1(int st)
// {
// visited[st] = true;
// for (int i = 0; i < reedge[st].size(); i)
// {
// if (!visited[reedge[st][i]])
// {
// dfs1(reedge[st][i]);
// }
// }
// first_s[k] = st;
// }
// // 深搜过程需要确认是否访问过
// void dfs2(int st)
// {
// visited[st] = false; // 标记访问 反过来
// for (int i = 0; i < edge[st].size(); i)
// {
// if (visited[edge[st][i]])
// {
// dfs2(edge[st][i]);
// }
// }
// }
// void init()
// {
// k = 0;
// for (int i = 0; i <= N; i)
// {
// edge[i].clear();
// reedge[i].clear();
// }
// memset(visited, 0, sizeof(visited));
// memset(first_s, 0, sizeof(first_s));
// }
// int main()
// {
// while (cin >> N >> M && N) // M可能是0
// {
// // k = 0;
// // clear and init
// // for (int i = 0; i <= N; i)
// // {
// // edge[i].clear();
// // reedge[i].clear();
// // }
// // memset(visited, 0, sizeof(visited));
// // memset(first_s, 0, sizeof(first_s));
// init();
// int u, v;
// while (M–)
// {
// cin >> u >> v;
// // M行的输入数据
// edge[u].push_back(v);
// reedge[v].push_back(u); // 反向
// }
// // 正向遍历
// for (int i = 1; i <= N; i)
// {
// // 未被访问过
// if (!visited[i])
// {
// // 进深搜
// dfs1(i);
// }
// }
// // 已经获取到了first_s
// int linkcount = 0; // 强连通分量的数量
// // 反向遍历
// for (int i = N; i >= 1; i–)
// {
// // 反向也是未访问过
// if (visited[first_s[i]])
// {
// linkcount++;
// // 进深搜
// dfs2(first_s[i]);
// }
// }
// // 只有一个强连通分量 说明任意两个房间都相互连通
// if (linkcount == 1)
// {
// cout << “Yes” << endl;
// }
// else
// {
// cout << “No” << endl;
// }
// }
// }

// // 单源最短路径
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// // 堆优化的dijkstra算法
// typedef pair[HTML_REMOVED] PI;
// const int N = 10001;
// priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> pq; // 寻找距离最小的边
// long long dist[N]; // 到每个点的最短距离
// bool visited[N] = {false}; // 判断该点是否见过
// vector[HTML_REMOVED] edges[N]; // 邻接链表类型
// int n, m, s; // 点的个数、有向边的个数、出发点的编号

// void Dijkstra()
// {
// // 初始化
// for (int i = 1; i <= n; i)
// {
// dist[i] = (1 << 31) - 1;
// }
// dist[s] = 0; // 起始点
// pq.push({0, s}); // 加入该起始点
// while (!pq.empty())
// {
// PI top = pq.top();
// pq.pop();
// // int distance = top.first; // 到达这个起始点的权重
// int u = top.second; // 起始点
// // 见过该点则跳过
// if (visited[u])
// {
// continue;
// }
// // 将该点进行标记
// visited[u] = true;
// // 对于当前起始点能够到达的节点 的边
// for (unsigned i = 0; i < edges[u].size(); i)
// {
// int v = edges[u][i].first; // 目标点
// int w = edges[u][i].second; // u->v的权重
// // 松弛操作
// if (dist[v] > dist[u] + w)
// {
// // disu[u]也可以替换成之前的distance
// dist[v] = dist[u] + w;
// // 将变化的点加入堆
// pq.push({dist[v], v});
// }
// }
// }
// }

// int main()
// {
// scanf(“%d%d%d”, &n, &m, &s); // 点的个数、有向边的个数、出发点的编号
// int u, v, w;
// while (m–)
// {
// scanf(“%d%d%d”, &u, &v, &w); // u->v 权重为w
// edges[u].push_back({v, w});
// }
// Dijkstra();
// for (int i = 1; i <= n; i++)
// {
// printf(“%d “, dist[i]);
// }
// }
// // Floyd
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// const int N = 101;
// typedef pair[HTML_REMOVED] PI;
// int n, m; // 点的个数和边的个数
// // vector[HTML_REMOVED] edges[N]; // 邻接链表类型
// int dist[N][N]; // 邻接矩阵类型

// void floyd()
// {
// for (int k = 1; k <= n; k)
// {
// for (int i = 1; i <= n; i)
// {
// for (int j = 1; j <= n; j++)
// {
// dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
// }
// }
// }
// }

// int main()
// {
// scanf(“%d%d”, &n, &m); // 点的个数 无向边的个数
// // 初始化 小优化 防止爆掉 设置为Int最大的一半
// memset(dist, 0x3f, sizeof dist);
// int u, v, w;
// for (int i = 1; i <= n; i)
// {
// for (int j = 1; j <= n; j)
// {
// if (i == j)
// dist[i][j] = 0;
// }
// }
// while (m–)
// {
// scanf(“%d%d%d”, &u, &v, &w); // u->v 权重为w
// // 无向图
// dist[u][v] = w;
// dist[v][u] = w;
// }
// floyd();
// for (int i = 1; i <= n; i)
// {
// for (int j = 1; j <= n; j)
// {
// printf(“%d “, dist[i][j]);
// }
// printf(“\n”);
// }
// }

// // 最小生成树
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// using namespace std;
// using namespace std;
// const int maxM = 200001;
// const int maxN = 5001;

// struct Edge
// {
// // 存储边
// int u, v, w;
// bool operator<(const Edge &E) const
// {
// return w < E.w;
// }
// } edges[maxM];

// int N, M; // N个节点 M条无向边
// int p[maxN]; // 并查集 父节点数组

// // 使用并查集
// // 并查集初始化
// void init_set()
// {
// for (int i = 1; i <= N; i++)
// {
// p[i] = i;
// }
// }

// // 并查集的查找
// int find_set(int x)
// {
// if (x != p[x])
// p[x] = find_set(p[x]); // 查找优化
// return p[x];
// }

// int Kruskal()
// {
// // 排序 由大到小
// sort(edges, edges + M); // M条边
// init_set();

// int sum = 0; // 边权和
// int cnt = 0; // 判断是否存在最小生成树

// // 权重由小到大 遍历全部边
// for (int i = 0; i < M; i)
// {
// int u = edges[i].u;
// int v = edges[i].v;
// int w = edges[i].w;
// // 该边两个点不同 才可以被算进 即不连通
// u = find_set(u); // u的老大
// v = find_set(v); // v的老大
// if (u != v)
// {
// p[u] = v; // 进行老大的合并s
// sum = sum + w; // 记录边权和
// cnt;
// }
// }
// if (cnt < N - 1) // 最小生成树 应该是N-1条边
// {
// return -1;
// }
// return sum;
// }

// int main()
// {
// scanf(“%d%d”, &N, &M);
// for (int i = 0; i < M; i++)
// {
// int u, v, w;
// scanf(“%d%d%d”, &u, &v, &w);
// edges[i] = {u, v, w};
// }
// int result = Kruskal();
// if (result > 0)
// {
// printf(“%d\n”, result);
// }
// else
// {
// printf(“orz\n”);
// }
// }

// // 二分图的最大匹配
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// const int N = 1010;
// using namespace std;

// int n, m, e; // 二分图左部点个数n 右部点个数m 边数e
// vector[HTML_REMOVED] edges[N];
// bool visited[N]; // 对象是否被测试
// int aim[N]; // 选择的对象

// bool find(int x)
// {
// for (auto y : edges[x])
// {
// // 遍历x可连接到的对象
// if (!visited[y])
// {
// // 在当前轮中 这个对象没有被测试
// visited[y] = true;
// // y没有队友 或者y 原先的对象可以找别人组队
// if (aim[y] == 0 || find(aim[y]))
// {
// aim[y] = x; // x可以找她组队
// return true;
// }
// }
// }
// return false;
// }
// int res = 0;
// void match()
// {
// memset(aim, 0, sizeof aim);
// for (int i = 1; i <= n; i)
// {
// // 每轮都进行对象的尝试 对vis进行初始化
// memset(visited, false, sizeof visited);
// if (find(i))
// { // 可以进行两两组队
// res; // 记录匹配数
// }
// }
// }

// int main()
// {
// scanf(“%d%d%d”, &n, &m, &e);
// // 接下来e行
// int u, v;
// while (e–)
// {
// scanf(“%d%d”, &u, &v);
// edges[u].push_back(v);
// }
// match();
// cout << res << endl;
// }

include [HTML_REMOVED]

using namespace std;
int n, m;
int main()
{
cin >> m >> n;
int res = 0;
int t;
for (int i = 1; i <= m; i)
{
for (int j = 1; j <= n; j)
{
cin >> t;
if (i == 1 || j == 1 || i == m || j == n)
{
res += t;
}
}
}
cout << res;
}

0 评论