菜狗现在才开始备战蓝桥杯QAQ

【蓝桥杯专题】 （C++ | 洛谷 | acwing | 蓝桥）

• 贪心题 建议 整理同类型 然后背过！

1055. 股票买卖 II

链接 链接

• 思路 ： 能卖就卖 累加和
• 可证明

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\\n"
#define endl "\\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1e5 + 10;int a[N];void solve () {int n;cin >> n;rep(i, 0, n - 1) {cin >> a[i];}int now = a[0] ;ll ans = 0;rep(i, 0, n - 2) {int dt = a[i + 1] - a[i];if(dt > 0) ans += dt;} cout << ans << endl;}int main(void){freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 3;// cin >> T;while(T --) solve();return 0;
}

AcWing 104. 货仓选址

区间选点 ， 注意单数 还是 复数个节点
链接 链接

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\\n"
#define endl "\\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1e5 + 10;int a[N];void solve () {int n;cin >> n;rep(i, 0, n - 1) {cin >> a[i];}int mid = 0;if(n % 2 == 1) {mid =  n / 2;} else {mid = n / 2 - 1;}ll res = 0;rep(i, 0, n - 1) {res += abs(a[mid] - a[i]);}cout << res << endl;
}int main(void){freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

传递糖果

链接 链接

建议 ： https://www.acwing.com/solution/content/28451/

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\\n"
#define endl "\\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1e6 + 10;ll a[N], c[N];void solve () {int n ;ll sum = 0;cin >> n;rep (i, 1, n ) {cin >> a[i];sum += a[i];}// cout << sum << endl;int a_ = sum / n;// cout << a_ << endl;for(int i = n; i > 1; i --) { // dijianc[i] = c[i + 1] + a_ - a[i];}c[1] = 0;sort(c + 1, c + n + 1);ll res = 0;rep(i, 1, n) {res += abs(c[i] - c[(i + 1) / 2]);}cout << res << endl;
}int main(void){freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

AcWing 112. 雷达设备

链接 链接

• 思路 ： 重载sort函数 ，对每个节点 映射到对应区间， 最后对所以区间就行判断， 重复就不选 ， 选就cnt ++

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\\n"
#define endl "\\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 1e3 + 10;struct segement {double l, r;bool operator < (const segement & t) {return r < t.r;}
}seg[N];void solve () {int n , d;bool flag = false;cin >> n >> d;rep(i, 1, n) {int x, y;cin >> x >> y;if (y > d) {flag = true;} else {double len = sqrt(d * d - y * y);seg[i].l = x - len, seg[i].r = x + len;}}if (flag) {cout << "-1" << endl;return;} else {sort(seg + 1, seg + n + 1);int cnt = 0;double last = -1e20;rep(i, 1, n) {if(last < seg[i].l) {cnt ++ ;last = seg[i].r;}}cout << cnt << endl;}
}int main(void){freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

付账问题

题目链接

• 存在问题 ： 如果要使用 scanf printf就别使用 cin cout
  
  
  

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
// typedef long long ll;
// typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\\n"
#define endl "\\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
// const int N = 5* 1e5 + 10;int a[5000010];
int n;void solve () {
//   int n;long double s;scanf("%d%LF", &n, &s);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);sort(a, a + n);long double res = 0, avg = s / n;for (int i = 0; i < n; i ++ ){double cur = s / (n - i);if (a[i] < cur) cur = a[i];res += (cur - avg) * (cur - avg);s -= cur;}printf("%.4Lf\\n", sqrt(res / n));// cout << sqrt(res / n) << endl;
}int main(void){
// 	freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

乘积最大

• 取模的数 正负不会 影响结果的
• 在 C++ 直接取模即可
• 分情况讨论 : 除了负数那个 其他情况全为正（因为如果最大数都为负数的话，那么就代表全为负数） 直接取就可以

链接 链接

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\\n"
#define endl "\\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+9;
const int N = 1e5 + 10;int a[N];void solve () {int n, k;cin >> n >> k;rep(i, 0, n - 1) {cin >> a[i];}  sort(a, a + n);int l = 0 ,r = n - 1;int sign = 1;int res = 1;if(k % 2) {res *= a[r --];k --;if(res < 0) sign = -1;}while(k) {ll x = (ll) a[l] * a[l + 1], y = (ll)a[r] * a[r - 1];if(x * sign > y * sign) {res =  x % mod * res % mod; l += 2;} else{res = y % mod * res % mod;r -= 2;}k -=2;}cout << res << endl;
}int main(void){
// 	freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

AcWing 1247. 后缀表达式

链接 链接

#include <bits/stdc++.h>
// #include <iostream>
using namespace std;
typedef long long ll;
typedef double db;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, a, n) for(int i = n; i <= a; i --)
#define pb push_back;
#define fs first;
#define sz second;
#include <stdlib.h> // atoi
#define debug cout<<"debug"<<"\\n"
#define endl "\\n";
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N = 2 * 1e5 + 10;int a[N];void solve () {int n, m;cin >> n >> m;int k = n + m + 1;rep(i, 0, k - 1) {cin >> a[i];}ll res = 0;if(!m) {rep(i,0,k - 1)res += a[i];} else {sort(a, a + k );res += a[k - 1] - a[0];rep(i, 1, k - 2) {res += abs(a[i]);}}cout << res << endl;
}int main(void){
// 	freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

P

链接 链接