洛谷
P1878 舞蹈课 - 洛谷
这题有个很妙的思路
用链表实现
注意：
bool operator<(const node &x) const这种要写结构体里面
r[i] = i + 1; l[i] = i - 1;链表初始化
l[x],r[y]，这里x和y要分清楚
字符串这里有下标越界问题，要注意
字符串下标是从0开始，所以遇到字符串处理时要-1
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
struct node{int w, c, d;bool operator<(const node &x) const//这种要写在结构体里面{if (w != x.w)return w > x.w;//差异最小的return c > x.c;//最左边}
};
priority_queue<node> q;
int a[N], r[N], l[N], cnt;
bool is[N];
int res1[N], res2[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;string s;cin >> s;for (int i = 1; i <= n;i++){cin >> a[i];}s += 'H'; // 防止下标越界// 考虑 s[r[y]-1],若 y=n,r[y]=n+1for (int i = 1; i < n;i++){if(s[i-1]!=s[i]){q.push({abs(a[i] - a[i + 1]), i, i + 1});}}for (int i = 1; i <= n;i++){r[i] = i + 1;l[i] = i - 1;}while(!q.empty()){node t = q.top();q.pop();int x = t.c, y = t.d;if(is[x]==0&&is[y]==0){r[l[x]] = r[y];l[r[y]] = l[x];cnt++;res1[cnt] = x, res2[cnt] = y;is[x] = 1, is[y] = 1;if(is[l[x]]==0&&is[r[y]]==0)if(s[l[x]-1]+s[r[y]-1]=='G'+'B')q.push({abs(a[l[x]] - a[r[y]]), l[x], r[y]});//加入满足条件的}}cout << cnt << endl;for (int i = 1; i <= cnt;i++){cout << res1[i] << " " << res2[i] << endl;}
}
P2251 质量检测 - 洛谷
之前做的时候没有好好理解呀，突然发现单调队列就是滑动窗口
注意：
if,while判断
初始时int hh=0,tt=-1;
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
int a[N],q[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, k;cin >> n >> k;for (int i = 0; i < n;i++){cin >> a[i];}int hh = 0, tt = -1;for (int i = 0; i < n;i++){if(hh<=tt&&i-k+1>q[hh])hh++;while(hh<=tt&&a[q[tt]]>=a[i])tt--;q[++tt] = i;if(i>=k-1)cout << a[q[hh]] << endl;}
}
P1908 逆序对 - 洛谷
因为数字大小在1e9，所以直接求会RE（这里是会数组下标越界）
所以要进行离散化操作
for (int i = 1; i <= n;i++){//离散化
ranks[a[i].num] = i;
}//把第 a[i].num小的数变成 i
然后相当于对ranks[i]数组求解，当成a[i]就行啦
注意，这里排序是先排值，然后再对先后排序，先出现的算小的
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=5e5+10;
int n;
int c[N], ranks[N];struct point{int val, num;bool operator<(const point &x)const {//排序if(val!=x.val)return val < x.val;return num < x.num;}
}a[N];int lowbit(int x){return x & (-x);
}
void add(int x,int k){while(x<=n){c[x] += k;x += lowbit(x);}
}LL summ(int x){LL res = 0;while(x){res += c[x];x -= lowbit(x);}return res;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n;i++){cin >> a[i].val;a[i].num = i;}sort(a + 1, a + 1 + n);for (int i = 1; i <= n;i++){//离散化ranks[a[i].num] = i;}//把第 a[i].num个数变成 iLL ans = 0;for (int i = 1; i <= n;i++){add(ranks[i], 1);ans += i - summ(ranks[i]);}cout << ans << endl;
}
CF（goodbye2025补题）
Problem - D - Codeforces（构造）
构造题
题意：构造一个攻击序列，对于\((x,y)\) , \(x\)打 \(y\) ，于是 \(a_x-a_y,a_y-a_x\)，注意，攻击的大小a_x,a_y不变，要使得最后剩下\(m\)个elves，要使得 \(m\)个精灵都攻击过
首先，必须满足\(2\times m\leq n\) ，因为
It is guaranteed that all a_i are distinct.，每次攻击一定会有一个精灵失去生命值，又要保证\(m\)个精灵都进行攻击过，所以\(m\)的最大可能即为\(m=2\times n\) ，此时\(m\)个打\(n-m\)个精灵。
先对生命值（也是攻击值）排序
接下来分类讨论
- \(m==0\) ：从第\(n-1\)个精灵开始攻击第\(n\)个精灵，然后最大的精灵能被到第\(i\)个精灵打败的话，即可满足\(m=0\) 的条件。先从小到大，依次\(a_j\)打\(a_{j+1}\) ，一直打到\(a_{i-1}\)打\(a_i\)，然后从残血\(a_i\)开始，依次打\(a_n\) 。
- 先处理前面小的部分，然后\(a_n\)到\(a_{n-m+1}\) ，打前\(m\)个，其他相互打即可
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
struct node{int x, id;bool operator<(const node &aa)const{return x < aa.x;}
} a[N];void solve()
{int n, m;cin >> n >> m;for (int i = 1; i <= n;i++){cin >> a[i].x;a[i].id = i;}if(m*2>n){cout << -1 << endl;return;}sort(a + 1, a + 1 + n);vector<pair<int, int>> ans;if(m==0){for (int i = n - 1; i>0;i--){ans.push_back({a[i].id, a[n].id});a[n].x -= a[i].x;if(a[n].x<=0){cout << ans.size() + i - 1 << endl;for (int j = 1; j < i;j++){cout << a[j].id << " " << a[j + 1].id << endl;}for (int j = 0; j < ans.size();j++){cout << ans[j].first << " " << ans[j].second << endl;}return;}}cout << -1 << endl;}else{for (int i = 1; i <= n - 2 * m;i++){ans.push_back({a[i].id, a[i + 1].id});}for (int i = n - m + 1; i <= n;i++){//大打小ans.push_back({a[i].id, a[i-m].id});}cout << ans.size() << endl;for(auto x:ans){cout << x.first << " " << x.second << endl;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - E - Codeforces（二分+交互）
恐怖的二分，卡了好久
需要发现对于\(2^k\) （区间最大值），分成两半，变成\(2^{k-1}+2^{k-1}\)，所以对于整个分完的数组，一定能找到一个mid，使得从
L-mid和mid-R，都为\(2^{k-1}\)，每次找区间小的那部分，就能找到最大值了
时间复杂度：\(O(log^2n)\)
为什么卡这么久，因为发现代码里的三个//注意，发现一个，改了之后不对，又重新改回来，导致三个//注意，明明都发现了，却没有一起改。。。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;LL qry(LL l,LL r){LL x;cout << "? " << l << " " << r << endl;cin >> x;return x;
}void solve()
{int n;cin >> n;int L = 1, R = n,l,r,mid,p;LL sum = qry(1, n);while (L!=R)//注意！！！{l = L, r = R;while (l + 1 < r){mid = (l + r) / 2;if (qry(L, mid)<=sum/2)l = mid;elser = mid;}if(l-L<=R-l-1)//注意！！！R = l;elseL = l+1;//注意！！！sum /= 2;}cout << "! " << sum << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}