Loading... 主要在刷这个题单： [2020,2021 年 CF 简单题精选 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/training/2018#problems) 以及偶尔可能穿插一些1800分题。 # CF1292B Aroma's Search ## 题意 二维平面上一堆点，每个点的坐标都是上一个点的线性函数——$x_i=w_ix_{i-1}+b_i$且$w\geq2$，求从某个坐标出发走曼哈顿距离最多走多少个点。 ## 分析 整个过程可以分为： 1. 走到某个点上 2. 向左走 3. 向右走 由于有$w\geq2$，所以很显然向左走再回头是更优的（因为$d(i,i+1)\leq d(i,0)$），那么我们**枚举进入点**即可。 ## 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define pb(x) push_back(x) #define FOR(x, y, z) for (auto x = y; x <= z; x++) #define endl '\n' #define ends ' ' #define umax(x, y) x = max(x, y) #define umin(x, y) x = min(x, y) typedef long long ll; typedef pair<int, int> pii; #define N 200005 #define M ll(1e16) ll x00, y00, wx, wy, bx, by; ll xa, ya, t; vector<ll> x, y; ll dis(ll x1, ll y1, ll x2, ll y2) { return abs(x1 - x2) + abs(y1 - y2); } int main() { cin >> x00 >> y00 >> wx >> wy >> bx >> by; cin >> xa >> ya >> t; x.push_back(x00), y.push_back(y00); while (x.back() <= M && y.back() <= M) x.push_back(wx * x.back() + bx), y.push_back(wy * y.back() + by); int ans = 0; FOR(p, 0, x.size() - 1)//进入点 { ll tt = t; tt -= dis(x[p], y[p], xa, ya); //cout<<x[p]<<ends<<y[p]<<ends<<tt<<endl; if (tt < 0) continue; int nans = 1; int l = 0; // 左端点 for (; l < p; l++) if (dis(x[l], y[l], x[p], y[p]) <= tt) break; nans += p - l; tt -= 2 * dis(x[l], y[l], x[p], y[p]); for (l = p + 1; tt > 0 && l < x.size(); l++) { tt -= dis(x[l], y[l], x[l - 1], y[l - 1]); if (tt >= 0) nans++; } umax(ans, nans); //cout<<"p="<<p<<", ans="<<nans<<endl; } cout << ans; return 0; } ``` # CF1304C Air Conditioner  ## 做法 这个就比较常规了吧，维护一个可能达到的区间$[up,down]$就好。 ## 代码 ```cpp #include<bits/stdc++.h> #include<ranges> using namespace std; #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define FOR(x,y,z) for (auto x=y; x<=z;x++) #define endl '\n' #define ends ' ' #define umax(x,y) x=max(x,y) #define umin(x,y) x=min(x,y) typedef long long ll; typedef pair<int,int> pii; #define N 200005 int t; struct T{ int low, high, tm; T() = default; T(int l, int h, int t):low(l), high(h), tm(t){} }; vector<T> arr; int main() { cin>>t; while (t--) { int n, tmp0; cin>>n>>tmp0; arr.clear(); FOR(i,1,n) { int l,h,p; cin>>p>>l>>h; arr.emplace_back(l,h,p); } ranges::sort(arr, [](const T &lhs, const T &rhs){ return lhs.tm < rhs.tm; }); int u = tmp0, d = tmp0, tm = 0; bool flg = true; for (auto v : arr) { int l = v.tm - tm; u += l; d -= l; if (d > v.high || u < v.low) { flg = false; break; } umax(d, v.low); umin(u, v.high); tm = v.tm; } if (flg) cout<<"YES\n"; else cout<<"NO\n"; } return 0; } ``` # CF1442B Identify the Operations ## 题意 给定数列$a$和$b$，其中$a$是$n$排列。每次可以从$a$中删除一个位置$a_i$，然后将$a_{i-1}$或者$a_{i+1}$append到$b$的末尾。问有多少种可能的方案。 ## 做法 容易想到给$a$中所有数打上时间戳标记，那么依次枚举$b$中的每个数字，在$a$中找到它，然后分三种情况即可。一个重要的观察是**当你删掉一个数，那么它旁边用来添加的那个数时间戳失效，可以看做直接替代了被删掉的数字**，从而无时间戳的数字是永远不会减少的，也就保证了概率乘法的时候删除数字对之后的选择无后效性。去掉时间戳这一点我们可以用set维护，也可以写双向链表，这样时间复杂度最低。维护也很方便。 ## 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define FOR(x,y,z) for (auto x = y; x <= z; x++) #define endl '\n' #define ends ' ' #define N 200005 #define M 998244353 int t; int n, k; int a[N], b[N], pos[N]; int l[N], r[N]; int main() { cin>>t; while (t--) { cin>>n>>k; //pre set<int> s; s.clear(); FOR(i,1,n) pos[i] = 0, l[i] = i-1, r[i] = i+1; //read FOR(i,1,n) { cin>>a[i]; pos[a[i]] = i; } FOR(i,1,k) { cin>>b[i]; s.insert(pos[b[i]]); } //calc int ans = 1; FOR(i,1,k) { int now = pos[b[i]];//now pos int cnt = 0; if (l[now]>0 && l[now]<=n && s.find(l[now]) == s.end()) cnt++; if (r[now]>0 && r[now]<=n && s.find(r[now]) == s.end()) cnt++; if (!cnt) { ans = 0; break; } else ans = ans * cnt % M; r[now-1] = r[now]; l[now+1] = l[now]; s.erase(now); } cout<<ans<<endl; } return 0; } ``` # CF1250B The Feast and the Bus ## 题意 若干队伍$k(k\leq 8000)$出行，总人数$n\leq 5*10^5$，只能租一辆车多次运载。设车容量为$s$，运载趟数为$r$，那么总开销为$s*r$。每趟只能载最多两个队伍。求最小开销。 ## 做法 单次check显然双指针，非常典。 但是有两个变量，如何二分呢？注意到$k$非常小，$s\leq k$，所以我们可以枚举$s$然后二分$r$是否可行。 ## 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define FOR(x,y,z) for(auto (x)=y;(x)<=(z);(x)++) #define endl '\n' #define ends ' ' typedef long long ll; int n, k; #define N 8003 int arr[N];//tmp vector<int> a; bool check(int capa, int t) { int ans = 0; int l = 0, r = a.size()-1; while (l < r) { if (a[l] + a[r]<=capa) l++,r--; else r--; ans++; } if (l == r) ans++; return ans <= t; } int main() { cin.sync_with_stdio(false); cin.tie(nullptr); cin>>n>>k; FOR(i,1,n) { int x; cin>>x; arr[x]++; } FOR(i,1,k) if (arr[i]) a.push_back(arr[i]); ranges::sort(a); ll ans = INT_MAX; FOR(t,1,k)//枚举趟数 { int l = a.back(), r = 500000; ll ok = INT_MAX;//二分容量 while (l <= r) { int mid = (l+r)/2; if (check(mid, t)) ok = mid, r = mid-1; else l = mid+1; } ans = min(ans, ok*t); } cout<<ans; return 0; } ``` © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏