目录
写在前面
开始板刷1500了，主要是最近卡1300-1400上不去，发现cf很多思维题要不是想不到，要不就是签的慢，被读题卡了心态就巨难受，一下就不想写了，而且现在学知识点容易陷入递归，学到一个知识点发现需要用其他知识点，然后又去学其他知识点，然后学完还需要对这些一堆知识点做题练习不然只会板子根本没有什么对算法深刻的理解。感觉不如这样去板刷，遇到不会的只学这个不去学太多，在题目中理解知识点应该比单纯泛泛去学可能效果会更好。也记录一下，自己1500刷多少，才能有提升。
1. A. Did We Get Everything Covered?(构造、思维)
题目链接
A. Did We Get Everything Covered?
题意
给\(n，k\)以及长度为\(m\)的一个小写的字符串。
字符串的子序列是否包含用前\(k\)个小写字母构成的长度为n的字符串的所有情况
题解
- 首先判断有没有解：
要构成所有的字符串，我们可以把原串进行拆分，拆分成n个段，每段如果都包含前k个小写字母至少一次，则说明有解，反之说明无解。 - 无解的情况下，考虑如何构造答案。
用每一段最后一次出现的字符，加上不满足的段中没有出现的字符
正确性？每一段最后出现的字符一定在前面没出现过，只能在后面出现，这样构造出来的子序列是正确的
代码
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int mod=998244353;
void solve() {
int n,k,m;
string s;
cin>>n>>k>>m;
cin>>s;
set<char>cnt;
int cur=0;
string ans;
rep(i,0,m-1) {
cnt.insert(s[i]);
if(cnt.size()==k) {
ans+=s[i];
++cur;
cnt.clear();
}
if(cur>=n) {
cout<<"YES"<<endl;
return;
}
}
cout<<"NO"<<endl;
int len=ans.size();
rep(i,0,k-1) {
char c='a'+i;
if(cnt.count(c)==0) {
rep(j,1,n-len) ans+=c;
break;
}
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
总结
有判定正确性的思路，但是不会构造
wa了几发。最开始是构造的思路是错的
后面有一个小细节处理的不好，当要修改\(string\)时，就不能用\(string\)的\(size\)作为循环的控制条件，这样很容易寄。
很好的一道构造题目
2 F. Greetings（离散化+树状数组）
题目链接
题意
题解
由于两个人的速度是一样的，所以到达终点之前两个人是不会相遇的，考虑一下什么情况两个人会相遇，其中一个人到达终点时，另一个人，终点所在地的前面，并且它的终点在更右边。
将两个人的起点终点分别用\(S_a 、S_b、 E_a、 E_b\)表示，并假设\(a\)在前\(b\)在后（b在前是对称的），有下图
- \(a\)的终点\(<\) \(b\)的终点，这时两者同时出发，a到终点时，b已经经过的a的终点，两者不会相遇，对答案没有贡献
- \(a\)的终点\(>\) \(b\)的终点，这时b会先到终点，速度一样，a此时还没有到达\(E_b\)，此时两者一定会在\(E_b\)相遇
所以答案转化为对于当前区间计算有多少个区间被它所包含。
因为这道题目数据的实际大小是没有意义的，相对大小是有用的，并且值域比较大，我们考虑离散化，然后通过树状数组去查询。
具体的做法是，先按右端点从小打大排序，然后从前往后遍历区间，每次查询起点大于当前点起点的个数。就是这个区间对答案产生的贡献。
代码
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
void solve() {
int n;
cin>>n;
struct node{
int l,r;
bool operator<(const node &t)const{
return r<t.r;
}
};
vector<node>a(n);
vector<int>b(2*n);
int k=0;
rep(i,0,n-1){
cin>>a[i].l>>a[i].r;
b[k++]=a[i].l;
b[k++]=a[i].r;
}
sort(b.begin(),b.end());
rep(i,0,n-1){
a[i].l=lower_bound(b.begin(),b.end(),a[i].l)-b.begin()+1;
a[i].r=lower_bound(b.begin(),b.end(),a[i].r)-b.begin()+1;
}
sort(a.begin(),a.end());
// rep(i,0,n-1){
// cout<<a[i].l<<' '<<a[i].r<<endl;
// }
vector<int>c(2*n+1,0);
auto lowbit=[](int x){
return x&-x;
};
auto add=[&](int x,int k)->void{
for(int i=x;i<=2*n;i+=lowbit(i)){
c[i]+=k;
}
};
auto sum=[&](int x){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res+=c[i];
}
return res;
};
int ans=0;
rep(i,0,n-1){
int r=a[i].r,l=a[i].l;
ans+=sum(r)-sum(l-1);
add(l,1);
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
总结
- 离散化的板子记得不是很熟，这种东西应该很熟并且默写的很快的
- 树状数组用的还是比较少有些细节记得不太清，就比如树状数组的下标是从几开始的？
答案是1，这就导致离散化的时候也要从1开始。 - 看了一些题解，发现了这类问题被称为二维偏序问题
\(a_i<a_j、b_i>b_j\)