zzu天梯赛选拔

C. NANA去上课 — 简单数学

需要记录上一步处在哪个位置
然后判断如果是同一侧移动距离就是abs（x1 - x2）
如果不同就是x1 + x2

#include <iostream>
#include <cmath>
using namespace std;
#define int long long
signed main()
{int n; cin >> n;char s, pres; int x, prex; cin >> pres >> prex;int res = prex;for(int i = 2; i <= n; i ++){cin >> s >> x;if(pres != s) res += x + prex;else res += abs(prex - x);pres = s, prex = x;}res += prex;cout << res << '\n';
}

D. NANA在夜市 — bfs

倒着思考，从终点往周围扩展，判断能否到达，把能到达的点放入队列，接着扩展
这里判断时需要注意从能到达的点往外扩展时 方向是反着的，判断能否到达需要反着判断

#include <iostream>
#include <queue>
using namespace std;
const int N = 1010;
char g[N][N];
bool st[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};signed main()
{int n, m; cin >> n >> m;for(int i = 0; i < n; i ++) cin >> g[i];int sx, sy;// 找到终点位置 for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++)if(g[i][j] == 'O')sx = i, sy = j;queue<pair<int,int>> q;q.push({sx, sy});st[sx][sy] = true;int res = 1;while(q.size()){int x = q.front().first;int y = q.front().second;q.pop();for(int i = 0; i < 4; i ++){int ax = x + dx[i];int ay = y + dy[i];if(ax < 0 || ax >= n || ay < 0 || ay >= m || st[ax][ay]) continue;if((i == 0 && g[ax][ay] == 'D') || (i == 1 && g[ax][ay] == 'U') || (i == 2 && g[ax][ay] == 'L') || (i == 3 && g[ax][ay] == 'R')) {q.push({ax, ay});st[ax][ay] = true;res ++;}}}cout << res << '\n';}

F. NANA 的排名 — 二分+排序

先按照每个人的最低分加入到总成绩，用两个数组记录，一个原始数组，一个按总成绩从大到小排序的数组
遍历每一个人，用二分在在已经排序的数组里找到比它的数的数量就是排名
这里不需要考虑原来加入的自己，因为按最高分加入一定比最低分加入高

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node
{int l, r;int sum;
};
bool cmp(Node a, Node b)
{return a.sum > b.sum;
}
signed main()
{int n; scanf("%d", &n);vector<Node> vec, pre;	for(int i = 0, l, r, x, sum; i < n; i ++){scanf("%d %d", &l, &r);sum = 0;for(int j = 0; j < 5; j ++){scanf("%d", &x);sum += x;}sum += l;vec.push_back({l, r, sum});pre.push_back({l, r, sum});}sort(vec.begin(), vec.end(), cmp);vector<int> res;for(int i = 0; i < n; i ++){int sum = pre[i].sum + pre[i].r - pre[i].l;int l = 0, r = n;while(l < r){int mid = l + r >> 1;if(vec[mid].sum <= sum) r = mid;else l = mid + 1;}cout << l + 1 << '\n';}
}

G. NANA看天鹅舞会 — 贪心

最小的天鹅数黑白配对
剩下的相同2只配对
如果剩下的是奇数 减去c
#include
using namespace std;
#define int long long
signed main()
{
int n, m, a, b, c;
cin >> n >> m >> a >> b >> c;
if(n > m) swap(n, m);
int res = n * a;
m -= n;
res += (m / 2) * b;
if(m & 1) res -= c;
cout << res << ‘\n’;
}

I. NANA做胡辣汤 — 滑动窗口

先把处理好的全加起来
用hh记录长度为k窗口的左端点，遍历右端点每次求出长度为k的区间中的没处理好的调料数量
每次更新res

#include <iostream>
using namespace std;
const int N = 100010;
#define int long long
int a[N], b[N];
signed main()
{int n, k; cin >> n >> k;for(int i = 0; i < n; i ++) cin >> a[i];for(int i = 0; i < n; i ++) cin >> b[i];int hh = 0, sum = 0;for(int i = 0; i < n; i ++)if(b[i]) sum += a[i];// 先处理第一个窗口 for(int i = 0; i < k; i ++)if(!b[i]) sum += a[i];int res = sum;for(int i = k; i < n; i ++){if(!b[i - k]) sum -= a[i - k];if(!b[i]) sum += a[i];res = max(sum, res);}cout << res << '\n';
}

J. NANA与她的朋友们 — 双指针

k和ai很大，但是数只有1e5个，很容易想到离散化
因为每次影响的只有最大值和最小值，就可以直接看 最大值 和 最小值分别对应的数量哪个小
每次用k减去 那个小的，维护一个双指针，直到k小于0，或者双指针相遇

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define int long long
map<int,int> mp;
signed main()
{int n, k, x; scanf("%lld %lld",&n, &k);vector<int> vec;for(int i = 0; i < n; i ++){scanf("%lld", &x);if(!mp.count(x)) vec.push_back(x);mp[x] ++;}sort(vec.begin(), vec.end());int hh = 0, tt = vec.size() - 1;while(hh < tt){int l = mp[vec[hh]];int r = mp[vec[tt]];if(l < r){int num = vec[hh + 1] - vec[hh];int cnt = l;if(k >= cnt * num){k -= cnt * num;mp[vec[hh + 1]] += mp[vec[hh]];hh ++;	} else{int t = k / cnt;k -= t * cnt;int res = vec[tt] - vec[hh] - t;cout << res << '\n';return 0;}}else{int num = vec[tt] - vec[tt - 1];int cnt = r;if(k >= cnt * num){k -= cnt * num;mp[vec[tt - 1]] += mp[vec[tt]];tt --;}else{int t = k / cnt;k -= t * cnt;int res = vec[tt] - t - vec[hh];cout << res << '\n';return 0;}}}cout << 0 << '\n';
}

K. NANA在郑州 — 小模拟

#include <iostream>
using namespace std;
#define int long long
int val[] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 4};
signed main()
{int n;cin >> n;// kong geint res = n - 1;while(n --){string s; cin >> s;for(int i = 0; i < s.size(); i ++) res += val[s[i] - 'a'];}cout << res << '\n';
}