题面:https://codeforces.com/problemset/problem/1408/B

大致题意：给定数组${a_{n}}$,将其分解成m个数组${b_{n}}$,满足$a_{i}=b_{1,i}+b_{2,i}+...+b_{m,i}$，且$b_{i}$中不同的数字最多有k种,给定k,求m最小为多少?

题解:若$a_{i+1}!=a_{i}$，则会有一个b数组在i+1出产生变化，其他不变，故我们统计a数组发生变化次数cnt，将cnt个变化平均分给m个b，cnt/m<=k-1,m>=cnt/k-1，而k=1时，进行特判

代码摆了

我好菜QAQ

题面:https://codeforces.com/problemset/problem/1517/C

题面:https://codeforces.com/problemset/problem/1540/A

大概题意:有一个有向、有负边、无负环的图，再给定node1到各个node的最短距离dis[i]，求图中边权的总和最小值

题解:从node[a]到node[b]之间的边入手,val>=dis[b]-dis[a]，即若dis[b]<=dis[a],可构造一个非正边;若dis[b]>dis[a],则a到b只能构造正边

我们将所有非负边构造出后，接下来只能构造正边，如何构造尽量少的正边使题设成立？易知只能构造node[1]到dis最大的node的边(此为必须,非负边情况下,其他node没有到该node的边，而该node有到所有node的边)

故我们只需排序后，算出所有node对ans的贡献即可。

附code:

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

#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<stack>
#include<deque>
#include<unordered_set>
using namespace std;
using ll = long long;
ll T,n,m,k;
ll tmp;
ll a[200005];
int main()
{
    cin >> T;
    while(T--)
    {
        ll ans = 0;
        cin >> n;
        for (ll i = 1; i <= n;i++)
        {
            cin >> a[i];
        }
        sort(a + 1, a + 1 + n);
        ans += a[n];
        for (ll i = 1; i <= n;i++)
        {
            ans += (n - i) * a[i];
            ans -= (i - 1) * a[i];
        }
        cout << ans << '\n';
    }
    return 0;
}

裸题题面：给定n个点及其x、y坐标，统计每个点有多少点x、y坐标均小于该点

易想到树状数组统计逆序数对，故我们根据x坐标大小对点进行排序，以y坐标作为树状数组下标，一边读入一边统计(即二维偏序)

二维数点的应用:

https://www.luogu.com.cn/problem/P2163

大致题意：给定n颗树的x、y坐标，给定m个询问，询问给出一个矩形区域，求矩形内有多少树

根据容斥定理，我们可以预先处理出每个x、y坐标所对应的二维前缀和，可以达到O(1)查询

问题：坐标范围过大，若对每个坐标进行遍历是$O(n^{2})$的复杂度，而就算对x、y坐标进行离散化仍无法通过

注意到我们不需要每个点的前缀和，故跟上题类似，我们对树的坐标、查询的坐标都根据x坐标进行排序(注意查询需要拆成4个点，且包含正负属性)，我们对查询进行遍历，若当前统计的x坐标小于查询的x坐标，则继续统计直至当前统计的x坐标等于查询的x坐标，树状数组下标为y坐标，复杂度为O(nlogn)，注意y坐标可能需要离散化

其实就是二维数点+容斥定理

延伸:CDQ分治—前置：归并排序，将事件(查询、修改)进行归并排序，在排序时统计前面事件的影响，用于数点问题，即将点按照x坐标排序，然后对y坐标进行归并排序

单调队列，即队列内元素单调递增or递减的队列

顾名思义，单调栈即栈内元素单调递增或单调递减的栈

以前在cf做的一些题目

久仰大名的莫队算法

3.13的cfdiv2

题面:https://codeforces.com/problemset/problem/1065/B

大致题意：给定n个点、m条无向边，求最多、最少会有多孤立点(孤立点即无边与其相连的点)

题解：最少会有多少点：较易贪心思路，一条边最多使两个孤立点转为连接点，故取n-2*m

最多会有多少点：同样采取贪心，这次贪用最少的点，消耗尽量多的边，由于不存在自连、重边，故i个点最多形成$i*(i-1)/2$条边，故我们找到最大的i满足$m>=i*(i-1)/2$,将这i个点、$i*(i-1)/2$条边剔除后，剩n-i个点，$m-i*(i-1)/2$条边，用剩下的每个点向之前的互联点集团中的每个点连一条边，因为剩下的边数肯定<n,故直接n-=1，剩下的点数即为答案。

擦，最多点的想法有点绕，好像直接依次-1、-2、-3直至m为0就可，我是傻逼

附code：

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

#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<stack>
#include<deque>;
#include<unordered_set>
using namespace std;
using ll = long long;
ll T;
ll n;
ll m, k;
ll a[200005];
const ll INF = 1e12;
int main()
{
	cin >> n >> m;
	ll MIN, MAX;
	MIN = max(n -2*m, 0LL);
	for (ll i = n; i >= 2; i--)
	{
		if (m >= i * (i - 1) / 2)
		{
			m -= i * (i - 1) / 2;//0
			n -= i;
			if (m > 0) n -= 1;
			break;
		 }
	}/*
	ll i = 0;
	if (m != 0) n--;
	while (m > 0&&n>0)
	{
		m -= ++i;
		n--;
	}*/
	cout << MIN << " " << n << "\n";
	return 0;
}