2018.10.15模拟赛

2024-01-03 14:18

文章标签 15 模拟 2018.10

本文主要是介绍2018.10.15模拟赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

T1

水题

T2

有很多种方法能 $A$ ，比如说树状数组或者线段树

觉得 $w z h$ 的方法很好，就是将采矿点排序，然后对于每个矿石区间，二分查找能覆盖到的第一个采矿点和最后一个采矿点，用类似差分的思想在这两个点上做个标记，然后遍历每一个采矿点，如果说这个点被一些区间覆盖了，但是这些区间之中有一些还可以覆盖前面采矿点，此时如果用 $2^n$ 这种方法算的话会算重，那么只需要把单独选前面那些区间的方案去掉就好了，就是 $2^n-2^m$ 这种

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 200005
#define LL long long
using namespace std;
int n,m,a[maxn],l[maxn],r[maxn],cntr[maxn],cntl[maxn];
LL ans,bin[maxn];
bool isp[maxn];
const int mod=998244353;inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f;
}inline void prework(){bin[0]=1;for(int i=1;i<=n;i++) bin[i]=(bin[i-1]<<1)%mod;
}inline int find(int x,bool typ){int ll=1,rr=m,res=0;while(ll<=rr){int mid=(ll+rr)>>1;if(!typ){//找第一个大于等于左端点的 if(a[mid]>=x) rr=mid-1,res=mid;else ll=mid+1;}else{//找第一个小于等于右端点的 if(a[mid]<=x) ll=mid+1,res=mid;else rr=mid-1;}} return res;
}inline void solve(){sort(a+1,a+m+1);for(int i=1;i<=n;i++){int lf=find(l[i],0);if(!lf || a[lf]>r[i]) continue;cntl[lf]++; int rg=find(r[i],1);cntr[rg]++;}int cnt=0;for(int i=1;i<=m;i++){if(cntl[i])(ans+=bin[cnt+cntl[i]]-bin[cnt]+mod)%=mod;cnt+=cntl[i]-cntr[i];}
}int main(){freopen("B.in","r",stdin);freopen("B.out","w",stdout);n=rd(); m=rd(); prework();for(int i=1;i<=n;i++) l[i]=rd(),r[i]=rd();for(int i=1;i<=m;i++) a[i]=rd();solve();printf("%lld\n",ans);return 0;
}

T3

看似很难其实很简单的题

一开始想暴力，可以维护一个栈，如果下一个元素和栈顶元素相同就弹出，他们可以匹配成一对括号，栈为空就是一个合法的序列，正解和暴力的思想差不多，就是用哈希维护栈的形态，，用 $m a p$ 存当前形态出现次数，如果当前栈的形态和之前某次栈的形态相同，那么说明中间的一段一定是合法的，就让 $a n s + = m p [n o w]$ ，哈希要用双哈希，就是把两个哈希拼到一起，看别人的博客学习了一下双哈希姿势

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#define maxn 1000005
#define LL long long
using namespace std;
int n,stk[maxn],top;
char s[maxn];
LL ans;
const int bas=29, mod1=1e9+7,mod2=1e9+9;struct qwq{int x,y;LL get(){return 1LL*x*mod2+y;}bool operator <(const qwq &b) const{return x<b.x||(x==b.x&&y<b.y);}
}has[maxn];map<LL,int> mp;int main(){freopen("C.in","r",stdin);freopen("C.out","w",stdout);scanf("%s",s+1); n=strlen(s+1);has[0].x=0,has[0].y=0; mp[has[0].get()]++;for(int i=1;i<=n;i++){if(top && stk[top]==s[i]-'a'+1) top--;else{stk[++top]=s[i]-'a'+1;has[top]=has[top-1];has[top].x=(1LL*has[top].x*bas+s[i]-'a'+1)%mod1;has[top].y=(1LL*has[top].y*bas+s[i]-'a'+1)%mod2;}LL tmp=has[top].get();ans+=mp[tmp]; mp[tmp]++;}printf("%lld\n",ans);return 0;
}