三道编程题都是竞赛题，难度很大。

1. 第k大斜率

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

在平面直角坐标系上，有 n 个不同的点。任意两个不同的点确定了一条直线。请求出所有斜率存在的直线按斜率从大到小排序后，第 k 条直线的斜率为多少。

为了避免精度误差，请输出斜率向下取整后的结果。

 

输入格式：

第一行，包含两个正整数 n 和 k 。

接下来 n 行，每行包含两个整数 xi​,yi​ ，表示每个点的横纵坐标。

输出格式：

输出一行，包含一个整数，表示第 k 小的斜率向下取整的结果。

 

数据规模：1≤n≤100000

数据规模是10^5，如果暴力遍历所有的两个点组合，只能过10%的测试数据。显然要用低于O(n^2)的方法去做，并且，注意到最后输出的是一个整数，那么考虑二分。

有一类题目，就是先使用二分法去猜测答案，然后再验证猜的数对不对。例如 875. 爱吃香蕉的珂珂， 1552. 两球之间的磁力， 410. 分割数组的最大值。

这一题要求第k大的斜率向下取整，那么意味着应该有k条直线的斜率 >= k。那么，对于猜测的斜率s，假设有A条直线的斜率 >= s。如果A < k，说明s猜大了，右边界调整为s - 1。如果 A >= k，说明s可能猜小了，也可能猜中了, 左边界调整为s。

下一个问题就是，怎么求出A。

这需要对问题进行转换：如果 (x1, y1) (x2, y2) 的斜率大于等于k，并且 x1 < x2，那么 y1 - sx1 <= y2 - sx2。那么问题就转换为，求出满足xi < xj, 并且 yi - sxi <= yj - sxj 的 (i, j)对个数。这就像是数组逆序对问题，可以用归并排序去做。

在生成原始数组 y - sx 之前，首先要对所有的坐标点按x从小到大排序，相同的x按照y从大到小排序，这是为了避免 x1 = x2时， 如果 y1 < y2，那么会被计入 y1 - sx1 <= y2 - sx2，但实际上这个斜率不存在，不应该被计入。

#include <bits/stdc++.h>
using namespace std;//题目要的是第k大斜率向下取整，用二分法去猜
//因为是向下取整的，也就是说有k条直线的斜率是大于等于s的，那么先猜测s，然后再计算有多少条直线的斜率大于等于s，记为A。
//如果 A < k, 说明s的值猜大了；如果 A >= k，s的值可能猜小了，也可能猜中了。
//如何计算A的值呢？
//如果两个点(x1, y1), (x2, y2)的斜率大于等于s，那么 y1 - sx1 <= y2 - sx2 (x1 < x2)
//那么A的值就是：满足 yi - sxi <= yj - sxj 并且 xi < xj 的二元组(i, j)的数目
//为了避免重复，限定 i < j，那么就需要首先对坐标对排序，
//按照x从小到大排序，当x相等时 y 按从大到小排序，这样相等的x就不会被计入 yi - sxi < yj - sxj 中
//这个问题就变成了类似于数组中的逆序对问题，这里的数组中的元素是v[i] = yi - sxi， 求满足 i < j, v[i] <= v[j] 的二元组(i, j)个数using ll = long long;
const int MAXN = 1e5 + 10;
int n;
ll k;
struct Node
{int x, y;bool operator < (const Node& other) const{return x != other.x ? x < other.x : y > other.y;}
}all[MAXN];ll v[MAXN], t[MAXN];
ll cnt = 0;void mergeSort(int l, int r)
{if(l == r) return;int m = l + (r - l) / 2;mergeSort(l, m);mergeSort(m+1, r);int i = l, j = m + 1, tk = l;while(i <= m && j <= r){if(v[i] <= v[j]){cnt += r - j + 1;t[tk++] = v[i++];}else t[tk++] = v[j++];}while(i <= m) t[tk++] = v[i++];while(j <= r) t[tk++] = v[j++];for(i = l; i <= r; i++) v[i] = t[i];
}bool check(ll s)
{for(int i = 0; i < n; i++) v[i] = all[i].y - s * all[i].x;cnt = 0;mergeSort(0, n - 1);return cnt >= k;
}int main()
{cin >> n >> k;for(int i = 0; i < n; i++) scanf("%d%d", &all[i].x, &all[i].y);sort(all, all + n);ll l = INT32_MIN, r = INT32_MAX;while(l < r){ll m = l + (r - l + 1) / 2;if(check(m)) l = m;else r = m - 1;}printf("%lld", l);return 0;
}

 2. 同余方程

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

求关于x的方程 ax % b = 1的最小正整数解。

 

输入格式

一行，包含两个正整数 a,b用一个空格隔开。

 

输出格式

一个正整数 x0​，即最小正整数解。输入数据保证一定有解。

 

数据规模：

 

2≤a,b≤2,000,000,000

数论问题。

ax % b = 1 有解，等价于 ax - kb = 1, 并且 gcd(a, b) = 1。因此问题转化为 ax - kb = gcd(a, b) 的解，然后使用扩展欧几里得算法。

#include <iostream>  
#include <cstdio> 
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b)
{if(b==0){x=1;y=0;return;}exgcd(b,a%b);k=x;x=y;y=k-a/b*y;return;
}
int main()
{cin>>a>>b;exgcd(a,b);cout<<(x+b)%b;
}

3. 传染病控制

https://vijos.org/p/1101

题目大意：有一个树形结构的感染人群，每一个传播周期，父节点会感染子节点。每一个传播周期，只能切断一条父子节点的连接。节点1是根节点，并且已经被感染。求出最少有多少人会被感染。

一开始用的是贪心，从上到下，每次选择子节点最多的一个节点的连接路径切断，但是只能过20%。贪心做法是不正确的，因为这个问题和子树的结构有密切的关系。

例如，考虑这样一种结构：

 如果按照贪心策略，最终会有5个节点被感染。如下图：

但是，如果按照下面的策略，最终只会有3个节点被感染。如下图

因此，这一题不能用贪心，只能用暴力搜索，每次枚举可能被删除的边，也就是在所有下一个可能被感染的节点中选一个删除。最后直到没有下一个节点时，统计有多少节点被感染。

另外要注意的是题目中输入的是联通的边，没有给出父子关系，所以需要首先建立出树，才能进行搜索。

#include <bits/stdc++.h>
using namespace std;const int MAXN = 310;
int n, p;
vector<int> tree[MAXN];
vector<int> connect[MAXN];
bool visited[MAXN] = {false};int helper(const vector<int>& nodes)
{if(nodes.empty()) return 0;int total = MAXN;vector<int> next;for(int i : nodes){for(int j : tree[i]){next.push_back(j);}}if(next.empty()){total = min(total, (int)nodes.size());}else{for(int i = 0; i < next.size(); i++){vector<int> t(next.begin(), next.end());t.erase(t.begin() + i);total = min(total, (int)nodes.size() + helper(t));}}return total;
}void buildTree(int u)
{visited[u] = true;for(int i : connect[u]){if(visited[i]) continue;tree[u].push_back(i);}for(int i : tree[u]){buildTree(i);}
}int main()
{scanf("%d%d", &n, &p);for(int i = 0; i < p; i++){int u, v;scanf("%d%d", &u, &v);connect[u].push_back(v);connect[v].push_back(u);}buildTree(1);int ans = helper({1});printf("%d\n", ans);return 0;
}