P2

题目1

现需要将一根长为正整数n的竹子砍为若干段 每段长度均为正整数 请返回每段竹子长度的最大乘积是多少 答案需要对1000000007取模 前置知识：模下快速幂

观察得到：

n = 4 -> 2 * 2 -> 4 % 3 = 1
n = 5 -> 3 * 2 -> 5 % 3 = 2
n = 6 -> 2 * 2 -> 6 % 3 = 0
n = 7 -> 3 * 2 * 2 -> 7 % 3 = 1
n = 8 -> 3 * 3 * 2 -> 8 % 3 = 2
n = 9 -> 3 * 3 * 3 -> 9 % 3 = 0
 
进而
n <= 3 特判
n > 3 时
if (n % 3 == 0)
{
	return quickmod(3, n / 3, mod) % mod;
}
if (n % 3 == 1)
{
	n -= 4;
	return 4 * quickmod(3, n / 3, mod) % mod;
}
if (n % 3 == 2)
{
	n -= 2;
	return 2 * quickmod(3, n / 3, mod) % mod;
}
 
也可以这么写：
auto tail = n % 3 == 0 ? 1 : (n % 3 == 1 ? 4 : 2);
auto power = tail == 1 ? n : (n - tail) / 3;
return quickmod(3, power, mod) * tail % mod;

题目2

一个数字n一定要分成k份 得到的乘积最大是多少 数字n 和 k 有可能到达${10}^{12}$ 结果需要对 $1e9+7$ 取模

先计算平均值 再算多多少
int n, k, mod = 1e9 + 7;
cin >> n >> k;
auto a = n / k;
auto b = n % k;
auto ans1 = quickmod(a + 1, b, mod);
auto ans2 = quickmod(a, k - b, mod);
return ans1 * ans2 % mod;

题目3

给若干会议的开始，结束时间 参加某个会议的期间 不能参加其他会议 返回能参加的最大会议数量

int n;
cin >> n;
vector<pair<int, int>> v(n);
for (auto &&[v1, v2] : v)
{
	cin >> v1 >> v2;
}
 
// 贪心策略 结束时间早的早排
ranges::sort(v, [](auto &v1, auto &v2) { return v1.second < v1.second; });
int ans = 1;
auto [beg, en] = v[0];
for (int i = 1; i < n; i++)
{
	auto [curbe, curen] = v[i];
	if (curbe >= en)
	{
		en = curen;
		ans++;
	}
}
return ans;

题目4

给定若干会议的开始，结束时间 任何会议的召开期间 你只需要抽出一天来参加 但是 同一天只能参加一个会议 返回你能参加的最大会议数量

思路： 等价于牛客寒假H 两种做法 一种是维护一个小根堆 一种是集合 + 二分

二分做法

int n, ans = 0, last = -1;
cin >> n;
vector<pair<int, int>> v(n);
for (auto &&[a, b] : v) cin >> a >> b; last = max(last, b);
ranges::sort(v, [](auto &&v1, auto &&v2)
{
	auto [a, b] = v1, [c, d] = v2;
	return a == c ? b < d : a < c;	
});
set<int> st;
for (int i = 1; i <= last; i++) st.insert(i);
 
for (auto &&[a, b] : v)
{
	auto it = st.lower_bound(a);
	if (it != st.end() and *it <= r)
	{
		ans++;
		st.erase(*it);
	}
}
 
cout << ans;

小根堆做法：

int n, ans = 0;
cin >> n;
vector<pair<int, int>> v(n);
map<int, vector<int>> mp;
for (auto &&[a, b] : v) 
{
	cin >> a >> b;
	mp[a].emplace_back(b);
}
 
priority_queue<int, vector<int>, greater<int>> pq;
int index = 1;
for (auto &&i : mp[index]) pq.push(i);
while (pq.size())
{
	while (pq.size() and pq.top() < index) pq.pop();
	if (!pq.empty()) 
	{
		pq.pop();
		ans++;
		index++;
		for (auto &&i : mp[index]) pq.push(i);
	}
}
cout << ans;

题目5

给你n个项目，对于每一个项目i 有一个纯利润prefits[i] 和启动该项目需要的最小资本 capital[i] 最初你的资本是w 完成一个项目的时候你将获得纯利润 添加到你的总资本中 从给定项目中选择最多k个不同项目的列表 最大化你的最终资本ans

int n, w, k; 
cin >> n >> w >> k; 
vector<pair<int, int>> projects(n); // pair<capital, profit> 
for (int i = 0; i < n; i++) 
{ 
	cin >> projects[i].second; // profit 
} 
for (int i = 0; i < n; i++) 
{
	cin >> projects[i].first; // capital 
} 
// 按启动资本排序
ranges::sort(projects);
// 优先队列保存利润，默认是大顶堆 
priority_queue<int> pq; 
int index = 0; 
for (int i = 0; i < k; i++) 
{ 
	// 将所有启动资本小于等于当前资金的项目加入优先队列 
	while (index < n && projects[index].first <= w) 
	{ 
		pq.push(projects[index].second); 
		index++; 
	} 
	// 如果没有可做的项目，则退出 
	if (pq.empty()) break; 
	// 选择当前利润最大的项目 
	w += pq.top(); 
	pq.pop(); 
} 
cout << w;

题目6

给定一个非负数组v 计算任何两个数差值的绝对值 如果v中没有 将绝对值加入到v里 但是只加入一次 直到arr大小固定 返回最终长度

结论：求出这个数组中所有数字的gcd 记为num 这个数组中所有数字的最大值 记为max 那么

for (int i = num; i <= max; i += num) // 所有的i都会在这个数组中

代码：

int n;
cin >> n;
map<int, int> mp;
vector<int> v(n);
for (int i = 0; i < n;i ++) 
{
	cin >> v[i];
	mp[v[i]]++;
}
int ans = n, num = gcd(v[0], v[1]);
for (int i = 2; i < n; i++) num = gcd(num, v[i]);
// 现在num是所有数字的最大公约数
int maxnum = ranges::max(v);
for (int i = num; i <= max; i += num) ans += (mp.count(i) == 0);
cout << ans;

P3