对局匹配
直接贪心
![[Offer收割]编程练习赛42](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pbWdzLzQvOS8zLzUvMzgvOGY5MDBhODljNjM0N2M1NjFmZGYyMTIyZjEzYmU1NjIuanBl.jpe?w=700&webp=1 "[Offer收割]编程练习赛42")
![[Offer收割]编程练习赛42](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pbWdzLzMvMC80LzYvMTQvOTYxZGRlYmViMzIzYTEwZmUwNjIzYWY1MTQ5MjlmYzEuanBl.jpe?w=700&webp=1 "[Offer收割]编程练习赛42")
#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("\n");
}
return 0;
}