蓝桥杯第四场双周赛（1~6）

本文介绍: 相反，增加数求区间中位数就是一道对顶堆的板子题了。因此考虑逆着做题，先将所有会飘走的气球放弃，将其余气球加入对顶堆。区间合并：将所有区间按照左端点排序，遍历区间，若当前左端点与前一个区间右端点有重合部分，则将他们合并成一个区间，否则将前一个区间存下来，当前区间为一个新的区间。5、方法很多，大体思路为将类型一样的宝石放到一起，将他们的作用区间进行合并，然后对整个数组进行区间修改。3、模拟题，找规律，第一行和最后一行只有两个数，其余行都是三个数。，因此所在列就是r – 1 + s。的所有取值，复杂度为。

1、水题

2、模拟题，写个函数即可

#define pb push_back
#define x first
#define y second 
#define int long long
#define endl 'n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f;
const LL llinf = 5e18;

typedef pair&lt;int,int&gt;pl;
priority_queue<LL , vector<LL&gt;, greater<LL&gt; &gt;mi;//小根堆
priority_queue<LL&gt; ma;//大根堆
LL gcd(LL a, LL b){
	return b &gt; 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
int qc(int a, int b , int c){
	return (a + b + c)/2;
}
int alg(int a , int b , int c){
	int cc = qc(a , b , c);
	return (cc * (cc - a) * (cc - b) * (cc - c));
}
void solve() 
{
	int a , b , c;
	cin &gt;&gt; a >> b >> c;
  if(a + b <= c || a + c <= b || b + c <= a){
    cout << -1;
  }
  else
	  cout << alg(a , b , c);
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
//	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

3、模拟题，找规律，第一行和最后一行只有两个数，其余行都是三个数。

第一行特殊处理，其余行： $(x + 1) / 3 + 1$ 就是当前所在行 $r$ ， $x - ((r - 1) * 3 - 1)$ 就是所在行第s 个数 , 每行第一个数是 $r - 1$ ，因此所在列就是r – 1 + s。

#include <iostream>
using namespace std;
int main()
{
  long long n , m;
  cin >> n >> m;
  for(int i = 0 ; i < m ; i ++){
    long long x;
    cin >> x;
    if(x <= 1){
      cout << 1 << " " << x + 1 << endl;
    }
    else{
      long long r = (x + 1) / 3 + 1;
      long long st = x - ((r - 1) * 3 - 1);
      long long dc = r - 1 + st;
      cout << r << " " << dc << endl;
    }

  }
  return 0;
}

4、考虑找到 $x^a , y^b , z^c$ 的所有可能取值，取值上界应该为 $10^{12} * 10^5 = 10^{17}$ 。由于 $2^{64}>10^{18}$ ,因此每个肯定不超过64种取值。用三重循环找到所有 $x^a + y^b + z^c$ 的所有取值，复杂度为 $O(64^3)$ 。注意 $x^a*x<inf$ 判断可能会爆long long ，所以在判断是否到达上界需要用 $x^a < inf/x$ 。用数组或者set去存每种取值，然后从小到大排序。按照题目条件对每个询问搜索即可（二分/暴力）。整体复杂度 $O(q * 64^3)/O(q*log(64^3))$

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl 'n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f;
const LL llinf = 2e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
LL a , b , c;
set<LL>st;
void solve() 
{
	cin >> a >> b >> c;
	vector<LL>aa , bb , cc;
	aa.pb(1);
	bb.pb(1);
	cc.pb(1);
	LL x = 1;
	while(a != 1 &amp;&amp; x < llinf / a){
		x *= a;
		aa.pb(x);
	}
	LL y = 1;
	while(b != 1 && y < llinf / b){
		y *= b;
		bb.pb(y);
	}
	LL z = 1;
	while(c != 1 && z < llinf / c){
		z *= c;
		cc.pb(z);
	}
	for(int i = 0 ; i < aa.size() ; i ++){
		for(int j = 0 ; j < bb.size() ; j ++){
			for(int z = 0 ; z < cc.size() ; z ++){
				st.insert(aa[i] + bb[j] + cc[z]);
			}
		}
	}
	int m;
	cin >> m;
	for(int i = 0 ; i < m ; i ++){
		LL que;
		cin >> que;
		auto it = st.upper_bound(que);
		while(*it - que == 1){
			que = *it;
			it = st.upper_bound(que);
		}
		cout << que + 1 << " " << (*it - que - 1) << endl;
	}
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
//	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

5、方法很多，大体思路为将类型一样的宝石放到一起，将他们的作用区间进行合并，然后对整个数组进行区间修改。

区间合并：将所有区间按照左端点排序，遍历区间，若当前左端点与前一个区间右端点有重合部分，则将他们合并成一个区间，否则将前一个区间存下来，当前区间为一个新的区间。

区间修改：差分/树状数组/线段树。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl 'n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
struct BIT{//Binary indexed Tree(树状数组)
	int n;
	vector<int> tr;
	BIT(int n) : n(n) , tr(n + 1 , 0){
	}
	int lowbit(int x){
		return x & -x;
	}
	void modify(int x , int modify_number){
		for(int i = x ; i <= n ; i += lowbit(i)){
			tr[i] += modify_number;
		}
	}
	void modify(int l , int r , int modify_number){
		modify(l , modify_number);
		modify(r + 1 , -modify_number);
	}
	int query(int x){
		int res = 0;
		for(int i = x ; i ;  i -= lowbit(i))
			res += tr[i];
		return res;
	}
	int query(int x , int y){
		return query(y) - query(x);
	}
};
void solve() 
{
	int n , m , q;
	cin >> n >> m >> q;
	vector<int>len(m + 5);
	for(int i = 1 ; i <= m ; i++){
		cin >> len[i];
	}
	BIT bit(n);
	vector<pair<int,int>>que;
	for(int i = 0 ; i < q ; i ++){
		int x , y;
		cin >> x >> y;
		que.pb({x , y});
	}
	sort(que.begin() , que.end());
	int r = 0 , pos = 0;
	for(int i = 0 ;i < q ; i ++){
		if(que[i].x != pos){
			pos = que[i].x;
			r = 0;
		}
		bit.modify( max(r + 1, que[i].y) , min(que[i].y + len[pos] - 1 , n) , 1);
		r = min(que[i].y + len[pos] - 1 , n);
	}
	for(int i = 1 ; i <= n ; i ++){
		cout << bit.query(i)<<" ";
	}
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
//	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

6、删除区间求中位数比较困难。相反，增加数求区间中位数就是一道对顶堆的板子题了。因此考虑逆着做题，先将所有会飘走的气球放弃，将其余气球加入对顶堆。然后再从后往前依次添加气球，维护对顶堆找答案即可（对顶堆网上一大堆模板）。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl 'n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
void solve() 
{
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	cin >> m;
	double ans[m + 5];
	int que[m + 5];
	int vis[n + 5];
	memset(vis,0,sizeof vis);
	for(int i = 1 ; i <= m ; i ++){
		cin >> que[i];
		vis[que[i]] = 1;
	}
	for(int i = 1 ;i <= n ; i ++){
		if(!vis[i]){
			ma.push(a[i]);
		}
	}
	while(ma.size() > mi.size()){
		mi.push(ma.top());
		ma.pop();
	}
	for(int i = m ; i > 0 ; i --){
		if((mi.size() + ma.size()) % 2 == 0){//偶数
			int x = mi.top();
			int y = ma.top();
			ans[i] = (double)(1.0 * x + y) / 2;
		}
		else{
			double x = mi.top();
			ans[i] = (double)(1.0 * x);
		}
		int yy = mi.top();
		if(a[que[i]] > yy){
			mi.push(a[que[i]]);
		}
		else{
			ma.push(a[que[i]]);
		}
		while(mi.size() > ma.size() + 1){
			ma.push(mi.top());
			mi.pop();
		}
		while(ma.size() > mi.size()){
			mi.push(ma.top());
			ma.pop();
		}
	}
	for(int i = 1 ; i <= m ; i++){
		printf("%.1f " , ans[i]);
	}
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
//	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}