对局匹配
直接贪心
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; void makedata() { freopen("input.txt", "w", stdout); cout << 200000 << endl; for(int i = 0; i < 200000; i++) cout << 1000000000 << ' '; fclose(stdout); } int a[110000]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); int n, k; cin >> n >> k; for(int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); int ptr = 0, ans = 0; while(ptr < n) { if(ptr + 2 < n && a[ptr + 2] - a[ptr] <= k) { ans++; ptr += 3; } else ptr++; } cout << ans << endl; return 0; }
稀疏矩阵乘积
对应关系别搞乱就行了
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> #include<set> #include <list> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; int x[3000], y[3000], w[3000], b[3000][3000], c[3000][3000]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif std::ios::sync_with_stdio(0), cin.tie(0); int n, p, q; int xx, yy, ww; cin >> n >> p >> q; for (int i = 0; i < p; i++)cin >> x[i] >> y[i] >> w[i]; memset(b, 0, sizeof(b)); for (int i = 0; i < q; i++) { cin >> xx >> yy >> ww; b[xx][yy] = ww; } memset(c, 0, sizeof(c)); for (int i = 0; i < p; i++) { for (int j = 1; j <= n; j++) { c[x[i]][j] += w[i] * b[y[i]][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (c[i][j] != 0) cout << i << ' ' << j << ' ' << c[i][j] << endl; } } return 0; }
树上的等差数列
首先随便以某一个节点为根把树建起来。树上的一条路径可以看成是从某一个节点出发，在树结构上上升到某一个祖先节点，再下降到一个后代节点。记录father[x]为x节点的父节点，dep[x]为前两项为a[father[x]],a[x]的等差数列沿树结构向下最多能走的深度。枚举这个最高点r，把它的子节点按权值分类，枚举所有能构成等差数列的组合a1，a[r]，a2，找到权值分别为a1和a2的子节点中dep值最大的点（且这两个点不为同一个点），那么产生了一个局部的最长等差数列l(a1)+1+l(a2)，选出其中最大的输出。
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> #include<set> #include <list> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; map<int, VI> mp[110000]; int a[110000], father[110000], dep[110000]; VI G[110000]; void build(int x, int fa) { father[x] = fa; for (int i = 0; i < G[x].size(); i++) { int u = G[x][i]; if (u == fa) continue; auto it = mp[x].find(a[u]); if (it == mp[x].end()) mp[x][a[u]] = VI(); mp[x][a[u]].push_back(u); build(u, x); } } void calc(int x) { if (dep[x] != 0) return; int d = a[father[x]] - a[x]; int aa = a[x] - d; auto it = mp[x].find(aa); if (it == mp[x].end()) { dep[x] = 1; return; } int tmp = 1; for (int i = 0; i < (*it).second.size(); i++) { int u = (*it).second[i]; calc(u); if (dep[u] + 1 > tmp) tmp = dep[u] + 1; } dep[x] = tmp; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif std::ios::sync_with_stdio(0), cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } build(1, 0); memset(dep, 0, sizeof(dep)); for (int i = 2; i <= n; i++) calc(i); int ans = 0; for (int i = 1; i <= n; i++) { for (auto itl = mp[i].begin(); itl != mp[i].end(); itl++) { int lval = (*itl).first, ldep = 0, ldot = 0; for (int j = 0; j < (*itl).second.size(); j++) { if (dep[(*itl).second[j]] > ldep) { ldep = dep[(*itl).second[j]]; ldot = (*itl).second[j]; } } int rval = 2 * a[i] - lval, rdep = 0, rdot = 0; auto itr = mp[i].find(rval); if (itr == mp[i].end()) { if (ldep + 1 > ans) ans = ldep + 1; continue; } for (int j = 0; j < (*itr).second.size(); j++) { if (dep[(*itr).second[j]] > rdep && (*itr).second[j] != ldot) { rdep = dep[(*itr).second[j]]; rdot = (*itr).second[j]; } } if (ldep + 1 + rdep > ans) ans = ldep + 1 + rdep; } } cout << ans << endl; return 0; }
翻转字符串
可以用Splay树实现反转操作。首先根据整个字符串建树，对于每次操作(l,r)，首先把l左边的字符旋转到根节点上，此时(l,r)位于根节点的右子树上；然后把r右边的字符旋转到根节点的右子树的树根，这样一来，就得到了只由(l,r)构成的一棵子树：根节点的右子树的左子树，对其添加一个lazy标记，最后对树进行一个前序遍历即可。
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; const int maxLength = 100002; class Node{ public: Node *child[2]; char value; int size; bool flip; Node(char c) :value(c), size(1), flip(false){ child[0] = child[1] = NULL; } int getPosition()const{ return child[0] ? child[0]->size + 1 : 1; } void maintain(); void pushDown(); }; void Node::maintain(){ size = 1; if (child[0]){ size += child[0]->size; } if (child[1]){ size += child[1]->size; } } void Node::pushDown(){ if (flip){ swap(child[0], child[1]); for (int i = 0; i < 2; i++){ if (child[i]){ child[i]->flip ^= 1; } } flip = false; } } class SplayTree{ public: Node *root; SplayTree(char *a, int n); void build(Node *&node, char *begin, char *end); void rotate(Node *&node, int direction); void splay(Node *&node, int position); void reverse(int begin, int end); void traverse(Node *u); void traverse(); }; SplayTree::SplayTree(char *a, int n){ build(root, a, a + n - 1); } void SplayTree::build(Node *&node, char *begin, char *end){ if (begin > end){ return; } char *middle = begin + (end - begin >> 1); node = new Node(*middle); build(node->child[0], begin, middle - 1); build(node->child[1], middle + 1, end); node->maintain(); } void SplayTree::rotate(Node *&node, int direction){ Node *child = node->child[direction ^ 1]; node->child[direction ^ 1] = child->child[direction]; child->child[direction] = node; node->maintain(); child->maintain(); node = child; } void SplayTree::splay(Node *&node, int position){ node->pushDown(); if (node->getPosition() != position){ int d = node->getPosition() < position; Node *node2 = node->child[d]; position -= d ? node->getPosition() : 0; node2->pushDown(); if (node2->getPosition() != position){ int d2 = node2->getPosition() < position; position -= d2 ? node2->getPosition() : 0; splay(node2->child[d2], position); if (d == d2){ rotate(node, d ^ 1); } else{ rotate(node->child[d], d); } } rotate(node, d ^ 1); } } void SplayTree::reverse(int begin, int end){ splay(root, begin); splay(root->child[1], end - begin + 2); root->child[1]->child[0]->flip ^= 1; } void SplayTree::traverse(Node *u){ if (!u){ return; } u->pushDown(); traverse(u->child[0]); if (u->value){ printf("%c", u->value); } traverse(u->child[1]); } void SplayTree::traverse(){ traverse(root); } int main(){ char s[maxLength] = ""; while (~scanf("%s", s + 1)){ int n = strlen(s + 1); SplayTree splay(s, n + 2); int k; scanf("%d", &k); for (int i = 0; i < k; i++){ int begin, end; scanf("%d%d", &begin, &end); splay.reverse(begin + 1, end + 1); } splay.traverse(); printf(" "); } return 0; }