吹风不与周郎便,铜雀春生锁二乔
第一题 简单模拟
题目意思:问一个字符串分成若干个长为 p 或 q 的字符串,不能就输出 -1,否则输出分成了
几个字符串以及分成的字符串。
解题思路:暴力枚举一个长度的数量,注意从0开始模拟就好
时间复杂度:o(简单)
void solve()
{
int a,b; cin>>n>>a>>b;
string s; cin>>s; s=' '+s;
for(int i=0;i<=n/a;i++){
int x=n-i*a;
int num=i;
if(x%b==0){
int y=x/b;
cout<<i+y<<endl;
int st=1;
for(int x=1;x<=num;x++){
for(int cnt=1;cnt<=a;cnt++,st++) cout<<s[st];
cout<<endl;
}
for(int x=1;x<=y;x++){
for(int cnt=1;cnt<=b;cnt++,st++) cout<<s[st];
cout<<endl;
}
return ;
}
}
cout<<-1<<endl;
return ;
}
第二题 简单模拟
题目意思:给定排列从数列$a_i$里面的数开始,从1走到n,每一次的贡献为$a_i$-$a_{next}$
解题思路:记录位置模拟即可
时间复杂度度:o(n)
int a[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++){
int x; cin>>x;
a[x]=i;
}
int ans=0;
for(int i=2;i<=n;i++) ans+=abs(a[i]-a[i-1]);
cout<<ans<<endl;
return ;
}
第三题 简单括号模拟
题目意思:给定一个括号字符串,四种类型的括号,左括号可以替换为左括号,右括号同理,每次花
费代价为1求是否能变成合法括号序,已经代价
解题思路:括号一般采用栈来维护,直接模拟即可
时间复杂度:o(n)
stack<char> q;
void solve()
{
string s; cin>>s;
bool ok=false;
int ans=0;
for(int i=0;s[i];i++){
if(q.empty()){
if(s[i]==')'||s[i]=='>'||s[i]=='}'||s[i]==']') ok=true;
q.push(s[i]);
}
else{
if(s[i]=='<'||s[i]=='{'||s[i]=='('||s[i]=='[') q.push(s[i]);
else{
if(s[i]=='>'){
if(q.top()=='<') q.pop();
else{
q.pop();
ans++;
}
}
if(s[i]==')'){
if(q.top()=='(') q.pop();
else{
q.pop();
ans++;
}
}
if(s[i]=='}'){
if(q.top()=='{') q.pop();
else{
q.pop();
ans++;
}
}
if(s[i]==']'){
if(q.top()=='[') q.pop();
else{
q.pop();
ans++;
}
}
}
}
}
if(!q.empty()) ok=true;
if(ok) cout<<"Impossible"<<endl;
else cout<<ans<<endl;
return ;
}
第四题 线段覆盖问题
题目意思:给定你m个线段,求被m条线段覆盖的的点的集合
解题思路:首先对于线段问题考虑是否需要离散化,接着我们考虑左右边界,
也就是这个不是整点的线段也就是[0,2]和[3,5]是不能合并的(2,3)之间也有点
我们考虑直接放大2倍然后把中间的过度点也标记出来,然后使用差分的思路
接着用前缀和来求一下满足要求的线段是哪些
时间复杂度:O(nlogn)
vector<int> alls;
vector<PII> seg;
int a[N];
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
int a,b; cin>>a>>b;
a*=2,b*=2;
seg.push_back({a,b});
alls.push_back(a);
alls.push_back(b);
alls.push_back(a-1);
alls.push_back(b+1);//前缀和需要的点
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
auto find = [&] (int x){
return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;
};
// 前缀和思路
for(auto&[l,r]:seg){
a[find(l)]++;
a[find(r)+1]--;
}
for(int i=1;i<N;i++) a[i]+=a[i-1];
vector<PII> ans;
for(int i=1;i<N;i++){
if(a[i]>=m){//一直找满足要求的点加入其中
int j=i;
while(j+1<N&&a[j+1]>=m) j++;
ans.push_back({alls[i-1]/2,alls[j-1]/2});
i=j;
}
}
cout<<ans.size()<<endl;
for(auto&[l,r]:ans) cout<<l<<' '<<r<<endl;
return ;
}