暑假集训CSP提高模拟2
\(T1\) T2745. 活动投票 \(30pts\)
-
懒得再复制一遍了，直接挂当时的 题解 得了。
点击查看代码
int main() { ll n,a,sum=0,ans=-0x7f7f7f7f,i; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a); if(ans==a) { sum++; } else { sum--; if(sum<=0) { sum=1; ans=a; } } } printf("%lld\n",ans); return 0; }
\(T2\) T2741. 序列 \(0pts\)
- 原题： UVA1608 不无聊的序列 Non-boring sequences
- 部分分
-
\(10pts\) ：莫队处理出所有区间，询问即可。
点击查看代码
int a[200010],b[200010],cnt[200010],sum[200010],L[200010],R[200010],pos[200010],klen,ksum; struct ask { int l,r,id; }q[10000010]; bool q_cmp(ask a,ask b) { return (pos[a.l]==pos[b.l])?((pos[a.l]%2==1)?(a.r<b.r):(a.r>b.r)):(a.l<b.l); } void init(int n,int m) { klen=n/sqrt(m)+1; ksum=n/klen; for(int i=1;i<=ksum;i++) { L[i]=R[i-1]+1; R[i]=R[i-1]+klen; } if(R[ksum]<n) { ksum++; L[ksum]=R[ksum-1]+1; R[ksum]=n; } for(int i=1;i<=ksum;i++) { for(int j=L[i];j<=R[i];j++) { pos[j]=i; } } } void add(int x) { cnt[x]++; if(cnt[x]==1) { sum[pos[x]]++; } if(cnt[x]==2) { sum[pos[x]]--; } } void del(int x) { cnt[x]--; if(cnt[x]==1) { sum[pos[x]]++; } if(cnt[x]==0) { sum[pos[x]]--; } } int query() { for(int i=1;i<=ksum;i++) { if(sum[i]>=1) { return 1; } } return 0; } int main() { int t,n,m,l,r,flag,i,j; scanf("%d",&t); for(j=1;j<=t;j++) { scanf("%d",&n); m=flag=0; memset(cnt,0,sizeof(cnt)); memset(sum,0,sizeof(sum)); for(i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+1+n); b[0]=unique(b+1,b+1+n)-(b+1); for(i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+1+b[0],a[i])-b; } for(l=1;l<=n;l++) { for(r=l;r<=n;r++) { m++; q[m].l=l; q[m].r=r; q[m].id=m; } } init(n,m); sort(q+1,q+1+m,q_cmp); l=1; r=0; for(i=1;i<=m;i++) { while(l>q[i].l) { l--; add(a[l]); } while(r<q[i].r) { r++; add(a[r]); } while(l<q[i].l) { del(a[l]); l++; } while(r>q[i].r) { del(a[r]); r--; } if(query()==0) { flag=1; break; } } if(flag==0) { printf("non-boring\n"); } else { printf("boring\n"); } } return 0; }
-
- 正解
-
线段树优化 \(DP\) 。
-
设 \(f_{l,r}\) 表示 \([l,r]\) 中仅出现 \(1\) 次的数的个数。
-
从 \(r-1\) 到 \(r\) 的过程，实际上是多加了一个 \(a_{r}\) 。若 \(a_{r}\) 以前没有出现过，则 \(f_{k,r}=f_{k,r-1}+1 (k \in [1,r])\) ；否则有 \(\begin{cases} f_{k,r}=f_{k-1,r}(k \in [1,lastlast_{a_{r}}]) \\ f_{k,r}=f_{k,r-1}-1 (k \in (lastlast_{a_{r}},last_{a_{r}}]) \\ f_{k,r}=f_{k,r-1}+1 (k \in (last_{a_{r}},r]) \end{cases}\) 。序列合法当且仅当 \(\forall r \in [1,n],\min\limits_{l=1}^{r} \{ f_{l,r} \} \ge 1\) 。
-
区间修改、区间查询的线段树维护即可。
点击查看代码
int a[200010],b[200010],f[200010],pos[200010]; pair<int,int>last[200010]; struct SMT { struct SegmentTree { int l,r,minn,lazy; }tree[1600010]; int lson(int x) { return x*2; } int rson(int x) { return x*2+1; } void pushup(int rt) { tree[rt].minn=min(tree[lson(rt)].minn,tree[rson(rt)].minn); } void build(int rt,int l,int r,int a[]) { tree[rt].l=l; tree[rt].r=r; tree[rt].lazy=0; if(l==r) { tree[rt].minn=a[l]; return; } int mid=(l+r)/2; build(lson(rt),l,mid,a); build(rson(rt),mid+1,r,a); pushup(rt); } void pushdown(int rt) { if(tree[rt].lazy!=0) { tree[lson(rt)].lazy+=tree[rt].lazy; tree[rson(rt)].lazy+=tree[rt].lazy; tree[lson(rt)].minn+=tree[rt].lazy; tree[rson(rt)].minn+=tree[rt].lazy; tree[rt].lazy=0; } } void update(int rt,int x,int y,int val) { if(x<=tree[rt].l&&tree[rt].r<=y) { tree[rt].lazy+=val; tree[rt].minn+=val; return; } pushdown(rt); int mid=(tree[rt].l+tree[rt].r)/2; if(x<=mid) { update(lson(rt),x,y,val); } if(y>mid) { update(rson(rt),x,y,val); } pushup(rt); } int query(int rt,int x,int y) { if(x<=tree[rt].l&&tree[rt].r<=y) { return tree[rt].minn; } pushdown(rt); int mid=(tree[rt].l+tree[rt].r)/2,ans=0x7f7f7f7f; if(x<=mid) { ans=min(ans,query(lson(rt),x,y)); } if(y>mid) { ans=min(ans,query(rson(rt),x,y)); } return ans; } }T; int main() { int t,n,flag=0,i,j; scanf("%d",&t); for(j=1;j<=t;j++) { scanf("%d",&n); flag=0; for(i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; last[i]=make_pair(0,0); pos[i]=0; } sort(b+1,b+1+n); b[0]=unique(b+1,b+1+n)-(b+1); for(i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+1+b[0],a[i])-b; } T.build(1,1,n,f); for(i=1;i<=n;i++) { last[i].first=pos[a[i]]; last[i].second=last[last[i].first].first; pos[a[i]]=i; if(last[i].first==0) { T.update(1,1,i,1); } else { T.update(1,last[i].second+1,last[i].first,-1); T.update(1,last[i].first+1,i,1); } if(T.query(1,1,i)<=0) { flag=1; break; } } if(flag==1) { printf("boring\n"); } else { printf("non-boring\n"); } } return 0; }
-
-
官方题解
也可以分治递归求解，代码看 luogu 题解吧。
-
\(T3\) T6201. Legacy \(100pts\)
-
原题： CF786B Legacy
-
部分分
-
正解
-
直接挂学习笔记的 题解 了。
点击查看区间连区间代码
struct SegmentTree { ll l,r; }tree[2000010]; vector<pair<ll,ll> >e[2000010]; ll dis[2000010],id[2000010],vis[2000010],cnt=0; ll lson(ll x) { return x*2; } ll rson(ll x) { return x*2+1; } void build(ll rt,ll l,ll r,ll n) { tree[rt].l=l; tree[rt].r=r; e[rt+n*4].push_back(make_pair(rt,0)); if(l==r) { id[l]=rt; return; } e[lson(rt)].push_back(make_pair(rt,0)); e[rson(rt)].push_back(make_pair(rt,0)); e[rt+n*4].push_back(make_pair(lson(rt)+n*4,0)); e[rt+n*4].push_back(make_pair(rson(rt)+n*4,0)); ll mid=(l+r)/2; build(lson(rt),l,mid,n); build(rson(rt),mid+1,r,n); } void update(ll rt,ll x,ll y,ll pd,ll n,ll t,ll w) { if(x<=tree[rt].l&&tree[rt].r<=y) { if(pd==0) { e[rt].push_back(make_pair(n*8+t,0)); } else { e[n*8+t].push_back(make_pair(rt+n*4,w)); } return; } ll mid=(tree[rt].l+tree[rt].r)/2; if(x<=mid) { update(lson(rt),x,y,pd,n,t,w); } if(y>mid) { update(rson(rt),x,y,pd,n,t,w); } } void dij(ll p) { ll x,i; priority_queue<pair<ll,ll> >q; memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[p]=0; q.push(make_pair(-dis[p],-p)); while(q.empty()==0) { x=-q.top().second; q.pop(); if(vis[x]==0) { vis[x]=1; for(i=0;i<e[x].size();i++) { if(dis[e[x][i].first]>dis[x]+e[x][i].second) { dis[e[x][i].first]=dis[x]+e[x][i].second; q.push(make_pair(-dis[e[x][i].first],-e[x][i].first)); } } } } } void add(ll a,ll b,ll c,ll d,ll w,ll n) { cnt++; update(1,a,b,0,n,cnt,w); update(1,c,d,1,n,cnt,w); } int main() { ll n,m,p,pd,w,a,b,c,d,i; scanf("%lld%lld%lld",&n,&m,&p); build(1,1,n,n); for(i=1;i<=m;i++) { scanf("%lld",&pd); if(pd==1) { scanf("%lld%lld%lld",&a,&c,&w); b=a; d=c; } if(pd==2) { scanf("%lld%lld%lld%lld",&a,&c,&d,&w); b=a; } if(pd==3) { scanf("%lld%lld%lld%lld",&c,&a,&b,&w); d=c; } add(a,b,c,d,w,n); } dij(id[p]); for(i=1;i<=n;i++) { if(i==p) { printf("0 "); } else { printf("%lld ",(dis[id[i]+n*4]==0x3f3f3f3f3f3f3f3f)?-1:dis[id[i]+n*4]); } } return 0; }
-
\(T4\) T2731. DP搬运工1 \(22pts\)
- 部分分
-
\(22pts\) ：生成所有全排列，依次判断。
点击查看代码
const ll p=998244353; ll a[100]; int main() { ll n,k,sum,ans=0,i; cin>>n>>k; for(i=1;i<=n;i++) { a[i]=i; } do { sum=0; for(i=2;i<=n;i++) { sum+=max(a[i],a[i-1]); } ans=(ans+(sum<=k))%p; }while(next_permutation(a+1,a+1+n)); cout<<ans<<endl; return 0; }
-
- 正解
总结
- \(T1\) 看到是原题后，马上就写了，结果把将
sum=1写成sum++;了，迷之自信让我没再去测别的样例，挂了 \(70pts\) 。 - \(T2\) 两次大样例有点弱，都把乱搞做法放过去了。
- \(T3\) 赛时在想 \(Dijkstra\) 怎么写，真就应了前几天听牛客的课时授课老师说的“要把广搜，\(Dijkstra,SPFA\)，堆优化 \(Prim\) 这几个容易搞混的代码之间的不同点搞清楚，别整的最后场上一直在纠结某个地方应该怎么写”。