P1机房聚餐

直接枚举可能性应该会炸，我们考虑利用二分，二分OIer的人数，然后尝试能否买下即可！

这些写出check的策略！

int check(int num) {	for(int i = 1; i <= n; i ++) 
	food[i] = hug[i] + gre[i] * (num - 1);  //算出每个人吃的
	sort(food + 1, food + 1 + n);  //优先选吃的少（因为穷）
	int cra = 0;  //统计一下人数!
	for(int i = 1; i <= num; i ++)
		cra += food[i];
	return (cra <= ttf);
}

P2数字游戏v2

本题应该是本次模拟赛中最简单的一题，考虑利用前缀和+桶维护，然后利用组合数，即可

s=a[1]*a[4]+a[2]*a[3]+a[0]*(a[0]-1)/2;  注意这个a[0]的情况即可，因为它是任选两个合并而来，其他的都是两两配对

P3翻转字符

前缀和和后缀和的应用

从前向后遍历的过程中，记录字符A对应的 Pi 前缀和  PA，以及字符 B 对应的 Pi 前缀和 PB 。即 PAi 是所有位置 <=i 的字符 A 的能量之和，同理 PBi 是字符 B 的能量之和。

我们考虑枚举最终前缀翻转的位置  ，当这两个差值达到最大时（ PAi-PBi ），我们翻转这个前缀， B 能够获得最多的能量。

同理我们倒序遍历，可以求出获得能量最多的后缀翻转。记录这两个最大值中更大的那个就是答案，时间复杂度 O(n) 。

这里面有一个小技巧就是只需要枚举一个即可，另外一个可以通过相减得出

    for(int i = 1; i <= n; i++) {
        cin >> num[i];
        sum[i] = sum[i - 1] + num[i];
    }
    cin >> s;
    for(int i = 0; i < n; i++) {
        sumB[i + 1] = sumB[i];
        if(s[i] == 'B')
            sumB[i + 1] += num[i + 1];
    }
 
    long long res = sumB[n];
    for(int i = 1; i <= n; i++) {
        res = max(res, sumB[n] + sum[i] - 2 * sumB[i]);
        res = max(res, sumB[i] * 2 + sum[n] - sumB[n] - sum[i]);
    }

P4友好匹配

考虑利用LCA，然后利用树上前缀（和树根的权值），然后利用公式计算一下即可！本题没有卡倍增，如果加强一下数据，可以考虑卡O（n）LCA的算法

for(int i=0;i<3;i++){
    int z=w[x][i]+w[y][i]-w[lf][i]-w[father[lf]][i];
    ans+=z*(z-1)/2;
}

P5保留火种

其实就是修建道路
一开始只能想到枚举g去跑最小生成树
是m^2的算法（50pts）
但是其实每次加入的边只有一条
而且之前都不在最小生成树上的边以后也肯定不会在
所以可以建一个新的边的集合存当前生成树的边
这个集合的边最多只有n条
这样复杂度就降为n*m
可以通过本题

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n, m, top, st[1010100];
long long wG, wS, ans=1e18;
struct node
{
	long long x, y, g, s;
}a[1010100];
long long fa[1010100];
long long find(long long x){
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
bool cmp(node x, node y){
	return x.g<y.g;
}
int main()
{
	scanf("%lld%lld%lld%lld", &n, &m, &wG, &wS);
	for(long long i=1; i<=m; i++)
		scanf("%lld%lld%lld%lld", &a[i].x, &a[i].y, &a[i].g, &a[i].s);
	sort(a+1, a+1+m, cmp);
	for(long long i=1; i<=m; i++)
	{
		long long j;
		for(j=1; j<=n; j++)
			fa[j]=j;
		for(j=top; j>=1; j--)
			if(a[st[j]].s>a[i].s)
				st[j+1]=st[j];
			else break;
		top++;
		st[j+1]=i;
		long long maxg=0, maxs=0, sum=0;
		for(j=1; j<=top; j++)
		{
			long long fx=find(a[st[j]].x), fy=find(a[st[j]].y);
			if(fx!=fy)
			{
				fa[fy]=fx;
				maxg=max(a[st[j]].g, maxg);
				maxs=max(a[st[j]].s, maxs);
				st[++sum]=st[j];
			}
		}
		if(sum==n-1)
			ans=min(ans, wG*maxg+wS*maxs);
		top=sum;
	}
	if(ans==1e18)
		printf("-1");
	else
		printf("%lld", ans);
	return 0;
}

P6最佳买入

直接把个数拆成二次幂的和，然后做01背包

代码就不给了！