把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF1607H Banquet Preparations
题目大意：每道菜有a克肉b克鱼，会被吃掉共m克，求每个m中有多少吃肉多少吃鱼，使得吃完后不同的菜最少，求吃法（当菜的肉和鱼重量分别相等就看作相同）。

解：

最近做过不少这样考虑选择之后的“范围”的题目，显然，两个菜要相同，首先a+b-m要相同，所以在进行处理之前，我们先把a+b-m相同的菜分到一起。
然后，m的存在实际告诉了我们吃完之后这个菜重量分布的范围，且由于一组内a+b-m相等，当吃完，也就是m为0时，知道了a就相当于知道了b。因此我们就假设这道菜吃完后的a的范围为[l,r]，这个范围很容易求出，于是题目的要求也就变成了在每组中，找到一些点，使得每个[l,r]都包含这些点中的至少一个，也就是“公共点”。
于是很容易想到先把l，r按l排序，由于尽量有包含顺序，所以l和r相等时把r按反顺序排序。从后往前遍历，如果当前的r小于上一个的l，那么无论如何这两段都不会有公共点了，于是建立一个新的公共点，设置为当前的l（因为当然越小越好），否则他们就能找到一个公共点。
为每个[l,r]找到该公共点，就成功解决了这道题目。
算是求n个线段最小的公共点数的模板题。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 300005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define pi 3.141592657
using namespace std;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}
ll getpos(int p, ll n) {
	return n / cpow(10, p - 1) % 10;
}
ll getwei(ll n) {
	int res = 0;
	while (n) {
		res++;
		n /= 10;
	}
	return res;
}
/*

---------------------------------------------------------------------
5 4
1 3 11 15 32
*/
struct tr {
	int a , b, m,num;
	friend bool operator<(tr t1, tr t2) {
		return t1.a < t2.a;
	}
}trs[maxn];
struct sg {
	int a, b,num;
	friend bool operator<(sg s1, sg s2) {
		if (s1.a == s2.a) {
			return s1.b > s2.b;
		}
		return s1.a < s2.a;
	}
};
vector<tr> sm[maxn];
vector<sg> sgs;
map<int,int> has;
int ansl[maxn], ansr[maxn];
int main() {
	cfast;
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		has.clear();
		int xb = 1;
		inc(i, 0, n) {
			cin >> trs[i].a >> trs[i].b >> trs[i].m;
			trs[i].num = i;
			int ad = trs[i].a + trs[i].b - trs[i].m;
			if (has[ad] == 0) {
				has[ad] = xb++;
			}
			sm[has[ad]].push_back(trs[i]);
		}
		ll ans = 0;
		for (int i = 1; i < xb; i++) {
			sgs.clear();
			int mi = 1e9;
			inc(j, 0, sm[i].size()) {
				sg s = { max(0,sm[i][j].a - sm[i][j].m),sm[i][j].a - max(0,sm[i][j].m - sm[i][j].b),sm[i][j].num };
				sgs.push_back(s);
			}
			sort(sgs.begin(), sgs.end());
			for (int j = sgs.size() - 1; j >= 0; j--) {
				if (sgs[j].b < mi) {
					ans++;
					mi = sgs[j].a;
				}
				ansl[sgs[j].num] = trs[sgs[j].num].a-mi;
				ansr[sgs[j].num] = trs[sgs[j].num].m-ansl[sgs[j].num];
			}
		}
		cout << ans << endl;
		inc(i, 0, n) {
			cout << ansl[i] << " "<<ansr[i] << endl;
		}
		inc(i, 1, xb+1)sm[i].clear();
	}
}
/*
2 3
1 4

*/