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

    1、水题

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

    1. #define pb push_back
    2. #define x first
    3. #define y second 
    4. #define int long long
    5. #define endl '\n'
    6. const LL maxn = 4e05+7;
    7. const LL N = 5e05+10;
    8. const LL mod = 1e09+7;
    9. const int inf = 0x3f3f;
    10. const LL llinf = 5e18;
    11.  
    12. typedef pair<int,int>pl;
    13. priority_queue, greater >mi;//小根堆
    14. priority_queue ma;//大根堆
    15. LL gcd(LL a, LL b){
    16. 	return b > 0 ? gcd(b , a % b) : a;
    17. }
    18.  
    19. LL lcm(LL a , LL b){
    20. 	return a / gcd(a , b) * b;
    21. }
    22. int n , m;
    23. int a[N];
    24. void init(int n){
    25. 	for(int i = 0 ; i <= n ; i ++){
    26. 		a[i] = 0;
    27. 	}
    28. }
    29. int qc(int a, int b , int c){
    30. 	return (a + b + c)/2;
    31. }
    32. int alg(int a , int b , int c){
    33. 	int cc = qc(a , b , c);
    34. 	return (cc * (cc - a) * (cc - b) * (cc - c));
    35. }
    36. void solve() 
    37. {
    38. 	int a , b , c;
    39. 	cin >> a >> b >> c;
    40.   if(a + b <= c || a + c <= b || b + c <= a){
    41.     cout << -1;
    42.   }
    43.   else
    44. 	  cout << alg(a , b , c);
    45. }            
    46. signed main() 
    47. {
    48.     ios::sync_with_stdio(false);
    49.     cin.tie(0);
    50.     cout.tie(0);
    51.     cout.precision(10);
    52.     int t=1;
    53. //	cin>>t;
    54.     while(t--)
    55.     {
    56.     	solve();
    57.     }
    58.     return 0;
    59. }

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

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

            

    1. #include 
    2. using namespace std;
    3. int main()
    4. {
    5.   long long n , m;
    6.   cin >> n >> m;
    7.   for(int i = 0 ; i < m ; i ++){
    8.     long long x;
    9.     cin >> x;
    10.     if(x <= 1){
    11.       cout << 1 << " " << x + 1 << endl;
    12.     }
    13.     else{
    14.       long long r = (x + 1) / 3 + 1;
    15.       long long st = x - ((r - 1) * 3 - 1);
    16.       long long dc = r - 1 + st;
    17.       cout << r << " " << dc << endl;
    18.     }
    19.  
    20.   }
    21.   return 0;
    22. }

    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))

    1. #include 
    2. using namespace std;
    3. #define LL long long
    4. #define pb push_back
    5. #define x first
    6. #define y second 
    7. #define endl '\n'
    8. const LL maxn = 4e05+7;
    9. const LL N = 5e05+10;
    10. const LL mod = 1e09+7;
    11. const int inf = 0x3f3f;
    12. const LL llinf = 2e18;
    13. typedef pair<int,int>pl;
    14. priority_queue, greater >mi;//小根堆
    15. priority_queue ma;//大根堆
    16. LL gcd(LL a, LL b){
    17. 	return b > 0 ? gcd(b , a % b) : a;
    18. }
    19.  
    20. LL lcm(LL a , LL b){
    21. 	return a / gcd(a , b) * b;
    22. }
    23. int n , m;
    24. LL a , b , c;
    25. setst;
    26. void solve() 
    27. {
    28. 	cin >> a >> b >> c;
    29. 	vectoraa , bb , cc;
    30. 	aa.pb(1);
    31. 	bb.pb(1);
    32. 	cc.pb(1);
    33. 	LL x = 1;
    34. 	while(a != 1 && x < llinf / a){
    35. 		x *= a;
    36. 		aa.pb(x);
    37. 	}
    38. 	LL y = 1;
    39. 	while(b != 1 && y < llinf / b){
    40. 		y *= b;
    41. 		bb.pb(y);
    42. 	}
    43. 	LL z = 1;
    44. 	while(c != 1 && z < llinf / c){
    45. 		z *= c;
    46. 		cc.pb(z);
    47. 	}
    48. 	for(int i = 0 ; i < aa.size() ; i ++){
    49. 		for(int j = 0 ; j < bb.size() ; j ++){
    50. 			for(int z = 0 ; z < cc.size() ; z ++){
    51. 				st.insert(aa[i] + bb[j] + cc[z]);
    52. 			}
    53. 		}
    54. 	}
    55. 	int m;
    56. 	cin >> m;
    57. 	for(int i = 0 ; i < m ; i ++){
    58. 		LL que;
    59. 		cin >> que;
    60. 		auto it = st.upper_bound(que);
    61. 		while(*it - que == 1){
    62. 			que = *it;
    63. 			it = st.upper_bound(que);
    64. 		}
    65. 		cout << que + 1 << " " << (*it - que - 1) << endl;
    66. 	}
    67. }            
    68. int main() 
    69. {
    70.     ios::sync_with_stdio(false);
    71.     cin.tie(0);
    72.     cout.tie(0);
    73.     cout.precision(10);
    74.     int t=1;
    75. //	cin>>t;
    76.     while(t--)
    77.     {
    78.     	solve();
    79.     }
    80.     return 0;
    81. }

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

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

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

            

    1. #include 
    2. using namespace std;
    3. #define LL long long
    4. #define pb push_back
    5. #define x first
    6. #define y second 
    7. #define endl '\n'
    8. const LL maxn = 4e05+7;
    9. const LL N = 5e05+10;
    10. const LL mod = 1e09+7;
    11. const int inf = 0x3f3f;
    12. const LL llinf = 5e18;
    13. typedef pair<int,int>pl;
    14. priority_queue, greater >mi;//小根堆
    15. priority_queue ma;//大根堆
    16. LL gcd(LL a, LL b){
    17. 	return b > 0 ? gcd(b , a % b) : a;
    18. }
    19.  
    20. LL lcm(LL a , LL b){
    21. 	return a / gcd(a , b) * b;
    22. }
    23. int n , m;
    24. int a[N];
    25. void init(int n){
    26. 	for(int i = 0 ; i <= n ; i ++){
    27. 		a[i] = 0;
    28. 	}
    29. }
    30. struct BIT{//Binary indexed Tree(树状数组)
    31. 	int n;
    32. 	vector<int> tr;
    33. 	BIT(int n) : n(n) , tr(n + 1 , 0){
    34. 	}
    35. 	int lowbit(int x){
    36. 		return x & -x;
    37. 	}
    38. 	void modify(int x , int modify_number){
    39. 		for(int i = x ; i <= n ; i += lowbit(i)){
    40. 			tr[i] += modify_number;
    41. 		}
    42. 	}
    43. 	void modify(int l , int r , int modify_number){
    44. 		modify(l , modify_number);
    45. 		modify(r + 1 , -modify_number);
    46. 	}
    47. 	int query(int x){
    48. 		int res = 0;
    49. 		for(int i = x ; i ;  i -= lowbit(i))
    50. 			res += tr[i];
    51. 		return res;
    52. 	}
    53. 	int query(int x , int y){
    54. 		return query(y) - query(x);
    55. 	}
    56. };
    57. void solve() 
    58. {
    59. 	int n , m , q;
    60. 	cin >> n >> m >> q;
    61. 	vector<int>len(m + 5);
    62. 	for(int i = 1 ; i <= m ; i++){
    63. 		cin >> len[i];
    64. 	}
    65. 	BIT bit(n);
    66. 	vectorint,int>>que;
    67. 	for(int i = 0 ; i < q ; i ++){
    68. 		int x , y;
    69. 		cin >> x >> y;
    70. 		que.pb({x , y});
    71. 	}
    72. 	sort(que.begin() , que.end());
    73. 	int r = 0 , pos = 0;
    74. 	for(int i = 0 ;i < q ; i ++){
    75. 		if(que[i].x != pos){
    76. 			pos = que[i].x;
    77. 			r = 0;
    78. 		}
    79. 		bit.modify( max(r + 1, que[i].y) , min(que[i].y + len[pos] - 1 , n) , 1);
    80. 		r = min(que[i].y + len[pos] - 1 , n);
    81. 	}
    82. 	for(int i = 1 ; i <= n ; i ++){
    83. 		cout << bit.query(i)<<" ";
    84. 	}
    85. }            
    86. int main() 
    87. {
    88.     ios::sync_with_stdio(false);
    89.     cin.tie(0);
    90.     cout.tie(0);
    91.     cout.precision(10);
    92.     int t=1;
    93. //	cin>>t;
    94.     while(t--)
    95.     {
    96.     	solve();
    97.     }
    98.     return 0;
    99. }

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

            

    1. #include 
    2. using namespace std;
    3. #define LL long long
    4. #define pb push_back
    5. #define x first
    6. #define y second 
    7. #define endl '\n'
    8. const LL maxn = 4e05+7;
    9. const LL N = 5e05+10;
    10. const LL mod = 1e09+7;
    11. const int inf = 0x3f3f;
    12. const LL llinf = 5e18;
    13. typedef pair<int,int>pl;
    14. priority_queue, greater >mi;//小根堆
    15. priority_queue ma;//大根堆
    16. LL gcd(LL a, LL b){
    17. 	return b > 0 ? gcd(b , a % b) : a;
    18. }
    19.  
    20. LL lcm(LL a , LL b){
    21. 	return a / gcd(a , b) * b;
    22. }
    23. int n , m;
    24. int a[N];
    25. void init(int n){
    26. 	for(int i = 0 ; i <= n ; i ++){
    27. 		a[i] = 0;
    28. 	}
    29. }
    30. void solve() 
    31. {
    32. 	cin >> n;
    33. 	for(int i = 1 ; i <= n ; i ++){
    34. 		cin >> a[i];
    35. 	}
    36. 	cin >> m;
    37. 	double ans[m + 5];
    38. 	int que[m + 5];
    39. 	int vis[n + 5];
    40. 	memset(vis,0,sizeof vis);
    41. 	for(int i = 1 ; i <= m ; i ++){
    42. 		cin >> que[i];
    43. 		vis[que[i]] = 1;
    44. 	}
    45. 	for(int i = 1 ;i <= n ; i ++){
    46. 		if(!vis[i]){
    47. 			ma.push(a[i]);
    48. 		}
    49. 	}
    50. 	while(ma.size() > mi.size()){
    51. 		mi.push(ma.top());
    52. 		ma.pop();
    53. 	}
    54. 	for(int i = m ; i > 0 ; i --){
    55. 		if((mi.size() + ma.size()) % 2 == 0){//偶数
    56. 			int x = mi.top();
    57. 			int y = ma.top();
    58. 			ans[i] = (double)(1.0 * x + y) / 2;
    59. 		}
    60. 		else{
    61. 			double x = mi.top();
    62. 			ans[i] = (double)(1.0 * x);
    63. 		}
    64. 		int yy = mi.top();
    65. 		if(a[que[i]] > yy){
    66. 			mi.push(a[que[i]]);
    67. 		}
    68. 		else{
    69. 			ma.push(a[que[i]]);
    70. 		}
    71. 		while(mi.size() > ma.size() + 1){
    72. 			ma.push(mi.top());
    73. 			mi.pop();
    74. 		}
    75. 		while(ma.size() > mi.size()){
    76. 			mi.push(ma.top());
    77. 			ma.pop();
    78. 		}
    79. 	}
    80. 	for(int i = 1 ; i <= m ; i++){
    81. 		printf("%.1f " , ans[i]);
    82. 	}
    83. }            
    84. int main() 
    85. {
    86.     ios::sync_with_stdio(false);
    87.     cin.tie(0);
    88.     cout.tie(0);
    89.     cout.precision(10);
    90.     int t=1;
    91. //	cin>>t;
    92.     while(t--)
    93.     {
    94.     	solve();
    95.     }
    96.     return 0;
    97. }

            

    7、边数据较小，网络流问题。

  • 相关阅读:
    2022年中级经济师《工商管理》考试大纲
    使用STM32F103C8T自制freejoy控制板
    ch4-3 音频信号的频域特征
    NDVI时间序列分析之Sen+MK分析全过程梳理
    在Column中嵌入横向滚动的ListView
    国家/行业标准查询及下载全流程
    图像处理：图像清晰度评价
    《统计学习方法》第十九章 马尔可夫链蒙特卡罗法
    【英雄哥七月集训】第 20天：搜索二叉树
    Docker Desktop for Windows 安装过程整理
  • 原文地址：https://blog.csdn.net/weixin_61825750/article/details/134624528