A、thanks,mom
签到题
print("thanks,mom")
B、 霓虹
暴力出奇迹！ 肉眼观察，然后暴力打表。例如mp["06"]就是数码管从0跳变到6变化的灯管数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
map<string, int> mp;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
mp["01"] = 4; mp["02"] = 3; mp["03"] = 3; mp["04"] = 4; mp["05"] = 3;
mp["06"] = 2; mp["07"] = 3; mp["08"] = 1; mp["09"] = 2;
mp["10"] = 4; mp["12"] = 5; mp["13"] = 3; mp["14"] = 2; mp["15"] = 5;
mp["16"] = 6; mp["17"] = 1; mp["18"] = 5; mp["19"] = 4;
mp["20"] = 3; mp["21"] = 5; mp["23"] = 2; mp["24"] = 5; mp["25"] = 4;
mp["26"] = 3; mp["27"] = 4; mp["28"] = 2; mp["29"] = 3;
mp["30"] = 3; mp["31"] = 3; mp["32"] = 2; mp["34"] = 3; mp["35"] = 2;
mp["36"] = 3; mp["37"] = 2; mp["38"] = 2; mp["39"] = 1;
mp["40"] = 4; mp["41"] = 2; mp["42"] = 5; mp["43"] = 3; mp["45"] = 3;
mp["46"] = 4; mp["47"] = 3; mp["48"] = 3; mp["49"] = 2;
mp["50"] = 3; mp["51"] = 5; mp["52"] = 4; mp["53"] = 2; mp["54"] = 3;
mp["56"] = 1; mp["57"] = 4; mp["58"] = 2; mp["59"] = 1;
mp["60"] = 2; mp["61"] = 6; mp["62"] = 3; mp["63"] = 3; mp["64"] = 4;
mp["65"] = 1; mp["67"] = 5; mp["68"] = 1; mp["69"] = 2;
mp["70"] = 3; mp["71"] = 1; mp["72"] = 4; mp["73"] = 2; mp["74"] = 3;
mp["75"] = 4; mp["76"] = 5; mp["78"] = 4; mp["79"] = 3;
mp["80"] = 1; mp["81"] = 5; mp["82"] = 2; mp["83"] = 2; mp["84"] = 3;
mp["85"] = 2; mp["86"] = 1; mp["87"] = 4; mp["89"] = 1;
mp["90"] = 2; mp["91"] = 4; mp["92"] = 3; mp["93"] = 1; mp["94"] = 2;
mp["95"] = 1; mp["96"] = 2; mp["97"] = 3; mp["98"] = 1;
string a, b; cin >> a >> b;
ll ans = 0;
for (int i = 0; i < a.size(); i++) {
if (a[i] == b[i]) continue;
string tmp = "";
tmp = tmp + a[i] + b[i];
ans += mp[tmp];
}
cout << ans << endl;
return 0;
}
C、奇偶排序
根据题意，排序规则偶数比奇数大，要求原数组从小到大排列后的数组。开两个vector类型的a,b数组分别存储偶数和奇数，分别对a，b进行排序，先遍历输出b（奇数），再遍历输出a（偶数）即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin >> n;
vector<int> a, b;
for (int i = 0; i < n; i++) {
int x; cin >> x;
if (x & 1) b.push_back(x);
else a.push_back(x);
}
sort(b.begin(), b.end());
for (auto i : b) cout << i << " ";
sort(a.begin(), a.end());
for (auto i : a) cout << i << " ";
return 0;
}
D、 可结合的元素对
前置知识：lowbit(x)=x&(-x)，可以取出一个二进制中最后一个1。
可以分析得出，lowbit(x)一定是2的k次幂。根据题意，要求lowbit(a i+a j)=a i +a j，所以a i+a j=2^k，a i=2^k-a j，可以通过枚举每个a[j]，来判断对应的a[i]是否合法（题目中要求ai>=1）记录每个值的数量即可。这里用了map来记录数量。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n; cin>>n;
ll ans=0;
map<int,int> res;
while(n--){
int x; cin>>x;
for(int i=0;i<=30;i++){
int a=(1<<i)-x;
if(a>=1) ans+=res[a];
}
res[x]++;
}
cout<<ans<<endl;
return 0;
}
E、 兽之泪
优先队列。
分类讨论打boss和不打boss的情况：
1、不打boss：就将前n-1个怪兽的a[i]压入最小堆，做m次操作，每次累加最小堆的堆顶元素a[i]，然后弹出堆顶元素，同时压入a[i]对应的b[i]，直到做完m次操作。
2、打boss: 将前n个元素的a[i]直接累加，然后取所有b[i]中的最小值mi，让mi乘（n-m）,再加上之前a[i]累加的和。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 10;
typedef pair<int, int> PII;
int a[N], b[N];
ll ans1, ans2;
priority_queue<PII, vector<PII>, greater<PII>> pq;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
for (int i = 1; i <= n - 1; i++) pq.push({
a[i],i });
for (int i = 1; i <= m; i++) {
ans1 += pq.top().first;
int t = pq.top().second;
pq.pop();
pq.push({
b[t],t });
}
int mi = 1e9;
for (int i = 1; i <= n; i++) {
ans2 += a[i];
mi = min({
mi, b[i] });
}
ans2 += (m - n) * mi;
cout << min(ans1, ans2) << endl;
return 0;
}
F、矩阵X
求一个矩阵所有元素的和，用二维前缀和。求一个矩阵的极差（也就是矩阵元素最大值-矩阵元素最小值）用滑动窗口/单调队列。先枚举列，用滑动窗口求每一列相应区域的最大值和最小值；再枚举行，用滑动窗口求之前列中相应的最大值和最小值，并且维护。最后将二维前缀和*极差即可。
补这题时参考了别的大佬的代码~大佬说这题是缝补典。个人感觉非常繁琐......
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n, m, h, w;
vector<vector<int>> g, s, v, lmn, lmx, hmn, hmx;
int sum(int x, int y) {
return v[x][y] - v[x - h][y] - v[x][y - w] + v[x - h][y - w];
}
void solve() {
cin >> n >> m >> h >> w;
g = vector<vector<int>>(n + 1, vector<int>(m + 1));
s = g, v = g;
lmn = lmx = hmn = hmx = g;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> g[i][j];
s[i][j] = s[i][j - 1] + g[i][j];
v[i][j] = v[i - 1][j] + s[i][j];
}
}
for(int j = 1; j <= m; j++) {
deque<int> q;
for(int i = 1; i <= n; i++) {
while(q.size() && g[q.back()][j] > g[i][j]) {
q.pop_back();
}
q.push_back(i);
while(q.size() && q.front() <= i - h) {
q.pop_front();
}
if(i >= h) {
lmn[i][j] = g[q.front()][j];
}
}
q.clear();
for(int i = 1; i <= n; i++) {
while(q.size() && g[q.back()][j] < g[i][j]) {
q.pop_back();
}
q.push_back(i);
while(q.size() && q.front() <= i - h) {
q.pop_front();
}
if(i >= h) {
lmx[i][j] = g[q.front()][j];
}
}
}
for(int i = h; i <= n; i++) {
deque<int> q;
for(int j = 1; j <= m; j++) {
while(q.size() && lmn[i][q.back()] > lmn[i][j]) {
q.pop_back();
}
q.push_back(j);
while(q.size() && q.front() <= j - w) {
q.pop_front();
}
if(j >= w) {
hmn[i][j] = lmn[i][q.front()];
}
}
q.clear();
for(int j = 1; j <= m; j++) {
while(q.size() && lmx[i][q.back()] < lmx[i][j]) {
q.pop_back();
}
q.push_back(j);
while(q.size() && q.front() <= j - w) {
q.pop_front();
}
if(j >= w) {
hmx[i][j] = lmx[i][q.front()];
}
}
}
int ans = 0;
for(int i = h; i <= n; i++) {
for(int j = w; j <= m; j++) {
int sub = hmx[i][j] - hmn[i][j];
ans = max(ans, sub * sum(i, j));
}
}
cout << ans << endl;
}
signed main () {
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
solve();
return 0;
}
