Hallo！大家好！今天有全排列+贪心+深搜+二分（已按顺序），考的是算法，有一点难度，大家独立思考后不会做可以借鉴一下博主的代码。

目录

A 算式900

解析：

代码：

B 谈判

解析：

代码：

        sort：

        优先队列：

C 幸运数

解析：

代码：

D 123

解析：

代码：

---

A 算式900

解析：

        这是一道模拟题，当我们看到“10个数包含0~9所有数字”时，就会想到全排列。这题注意没有前导0，所以要特判一下，输出格式像例子那样就行了

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[]= {0,1,2,3,4,5,6,7,8,9};

bool judge() {
	if(a[0]==0 || a[4]==0 || a[8]==0) return false;
	if(((a[0]*1000+a[1]*100+a[2]*10+a[3])-(a[4]*1000+a[5]*100+a[6]*10+a[7]))*(a[8]*10+a[9]) == 900)
		return true;
	else return false;
}

int main() {
	do {
		if(judge()) {
			int x=a[0]*1000+a[1]*100+a[2]*10+a[3];
			int y=a[4]*1000+a[5]*100+a[6]*10+a[7];
			int z=a[8]*10+a[9];
			if(x==5012&&y==4987&&z==36) continue;
			printf("(%d-%d)*%d=900",x,y,z);
		}
	}	while(next_permutation(a,a+10));
	return 0;
}

B 谈判

解析：

        这是一道贪心题，因为局部最优解合并起来就是全局解，即答案。每次合成部落都合成当前人数最少的两个部落，这样花费就会最少。这个题有两种解法，第一种就是用sort，每个循环都sort（数据量是1000，很小，不会超）；第二种是用优先队列（博主打校赛时就用sort交上去，结果超时了，当时数据量是50000，一时没想到用优先队列）。下面这两种方法的代码实现。

代码：

        sort：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
int a[1005];

int main() {
	LL s=0;//虽然int也不会溢出
	cin>>n;
	for(int i=0; i<n; i++)
	cin>>a[i];
	sort(a,a+n);
	for(int i=1; i<n; i++) {
		a[i]=a[i]+a[i-1];
		s+=a[i];
		sort(a+i,a+n);//贪心
	}
	cout<<s;
	return 0;
}

        优先队列：

#include <bits/stdc++.h>
#include <queue>
using namespace std;
typedef long long LL;
int n;
priority_queue <int,vector<int>,greater<int> > q;//从小到大（greater改less就是从大到小）

int main() {
	LL s=0;
	cin>>n;
	for(int i=0; i<n; i++) {
		int x;
        cin>>x;
		q.push(x);
	}
	for(int i=1; i<n; i++) {
		int a=q.top();
		q.pop();
		int b=q.top();
		q.pop();
		int c=a+b;
		s+=c;
		q.push(c);
	}
	cout<<s;
	return 0;
}

C 幸运数

解析：

        这是一道深搜题，当然也可以通过模拟做出来，先用一个数组存从1到n的奇数（已经将位置为2的数弹出），由题得，可以将需弹出的该数的所在位置让后面的数往上补齐，就好像我们军训时补齐一样（赋值就好了），到最后遍历一遍n到m就ok了。

代码：

#include <bits/stdc++.h>
#include <queue>
using namespace std;
typedef long long LL;
int m,n,len;
int a[1000005];
//cnt表示第cnt个幸运数(第一个：2；第二个：3；第三个：7；第四个：9……)
//处于a[cnt]的倍数的位置应该弹出
void dfs(int cnt) {
	int sum=a[cnt];
	if(cnt > n) return; //比n大的话，弹不弹都不影响答案
	//这里剪不剪枝都行(从i=1开始遍历也能A)(博主是害怕会T，所以剪枝，这样剪枝是该题运行得最快的)
	//为什么是i=cnt？因为这里的幸运数是递增的，所以第a[cnt]之前的数是不需要移动的 
	for(int i=a[cnt]; i<=n; i++) {
		if(i % a[cnt])
			a[sum++]=a[i];//将后一个值给到前面，（假如该数不会弹出，则照旧赋值；要弹出的话就跳过这步）
	}
	dfs(cnt+1); //下一个幸运数
}


int main() {
	int cou=0;
	cin>>m>>n;
	for(int i=1; i<=n; i++) a[i]=2*i-1; //存奇数（已完成弹出“位置为2的倍数”的数）
	dfs(2);
	int sum=0;
	for(int i=1; a[i]<n; i++) {
		if(a[i]>m) {
			sum++;
			//cout<<a[i]<<endl;
		}
	}

	cout<<sum;
	return 0;
}

D 123

解析：

        这道题我做了一个小时，45min写出来70分答案（TLE），一开始是用for循环找位置，后来用二分查找来查位置，不得不说，二分真的快（用for的话是10^6*10^6=10^12,肯定T的；而二分的话是10^6*log10^6=3*10^7,丝毫不慌）。

        这道题可以用前缀和+差分+二分，前缀和可以分两个数组求，一个用来存1 2 3……的和(将整个数列分割成1，1 2，1 2 3……然后求每一份)，一个用来求第r个位置前的前缀和（当然不是具体位置，10^12肯定T，是每一份的右边界的位置的前缀和，也就是说sum1=1, sum2=1+1+2=4, sum3=1+1+2+1+2+3=10……以此类推），而差分就是用于精确定位到具体的l，r的位置，那么应该怎么定位呢？

        假如l=3,r=9，那么输出的答案应该是14，让我们画个图来理解吧！

        二分的话是用来查找对应位置。因为是用n*(n+1)/2>=1e12来定义数组大小，所以也用这个公式来确定l，r在s数组的对应段位置。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL l,r;
//n*(n+1)/2>=1e12 n大概是150w
LL s[1500010],sum[1500010];//s存1……n的和，sum存前缀和

//查找该位置在哪一个s里面，定义到对应的前缀和
LL cha(LL x) {
    LL ll=1,rr=1500000,ans;
    //二分模板
    while(ll<=rr) {
        LL mid=(ll+rr)/2;
        if(mid*(mid+1)/2 >= x) {
            rr=mid-1;
            ans=mid;
        } else ll=mid+1;
    }
    return ans;
}

int main() {
    for(int i=1; i<=1500000; i++) {
        s[i]=s[i-1]+i;
        sum[i]=sum[i-1]+s[i];
    }
    int T;
    cin>>T;
    while(T--) {
        cin>>l>>r;
        LL f1=cha(l);
        LL f2=cha(r);
        LL s1=l-(f1*(f1-1)/2); 
        LL s2=r-(f2*(f2-1)/2);
        //cout<<f1<<" "<<f2<<" "<<s1<<" "<<s2;
        cout<<(LL)(sum[f2-1]-sum[f1-1]-s[s1-1]+s[s2])<<endl;
        //sum[f2-1]-sum[f1-1]是定位到大概的位置，左边界有可能比l大，也可能刚好，而右边界肯定是比r小的
        //所以s[s1-1]是当前计算的左边界比l多了几个位置的数字之和，s[s2]是补足r比右边界大的几个数字之和
    }
    return 0;
}