概况
排名:9/5411
过题数:5
Rating:(color{green}{+185})((color{orange}{2159}))
(上(color{orange}{橙})啦!)
题目
A. Stickers and Toys
AC时间:3min
题解:
有(n-t)个蛋里没有玩具,(n-s)个蛋里没有贴纸。
也就是说,买(n-t+1)个蛋必然得到玩具,买(n-s+1)个蛋必然得到贴纸。
上面两个数取(max)即是答案。
code:
#include<bits/stdc++.h>
using namespace std;
int T,a,b,c;
int main(){
scanf("%d",&T);
while(T--)scanf("%d%d%d",&a,&b,&c),printf("%d
",max(a-b+1,a-c+1));
return 0;
}
B.Letters Shop
AC时间:9min
题解:
记录(lt_{i,j})表示第(i)种小写字母出现(j)个的前缀,最小结尾的下标。
对于一个名字,统计其中每种小写字母的数量,设第(i)种小写字母出现的次数为(tt_i),则答案就是所有(lt_{i,tt_i})的最大值。
code:
#include<bits/stdc++.h>
using namespace std;
int n,m,len,lt[26][200010],tt[26],ans;
char c[200010],na[200010];
int main(){
scanf("%d%s",&n,c+1);
for(int i=1;i<=n;++i)lt[c[i]-'a'][++tt[c[i]-'a']]=i;
scanf("%d",&m);
while(m--){
scanf("%s",na+1),len=strlen(na+1),ans=0,memset(tt,0,sizeof(tt));
for(int i=1;i<=len;++i)++tt[na[i]-'a'];
for(int i=0;i<26;++i)ans=max(ans,lt[i][tt[i]]);
printf("%d
",ans);
}
return 0;
}
C.Vasya And Array
AC时间:25min
题解:
首先,一个序列中所有数相等是满足序列不降的要求的。
对于一个要求满足([l,r])不降的序列,可以化简为要求满足([l+1,r])中的元素与它的前一个元素相等这样,我们就把限制从一个区间转移到了每一个点上。
于是,我们只需要令(a_0=n+1),然后从前往后,对于有限制的点(i)令(a_i=a_{i-1}),否则令(a_i=a_{i-1}-1),最后对于每一个要求([l,r])不满足不降的序列判断合法性即可。
首先考虑构造序列,此时只考虑要求([l,r])中的所有元素与前一个相等的限制。
我们将所有限制按左端点从小到大排序,然后从前往后考虑,每次考虑左端点小于等于当前位置的区间的右端点最大值,如果大于等于当前位置就令当前位置的值为前一个位置,否则为前一个位置-1。
然后考虑判断合法,暴力判断即可(代码里是这么写的)。
但其实可以更简单快速地判断:由于序列是不增的,所以直接判断左右两端点是否相等即可。
也就是说整个可以做到(O(n+mlog m)),但由于(n,mle1000),直接暴力判断也是可过的。
code:
这份是(O(nm))的。
#include<bits/stdc++.h>
using namespace std;
struct Q{
int l,r;
}s[1010],ns[1010];
int n,m,t,ss,sn,nws=1,nwn=1,ans[1010],st,v;
bool cmp(Q x,Q y){
return x.l<y.l;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)scanf("%d",&t),t?++ss,scanf("%d%d",&s[ss].l,&s[ss].r),++s[ss].l:(++sn,scanf("%d%d",&ns[sn].l,&ns[sn].r));
sort(s+1,s+ss+1,cmp);
ans[0]=n+1;
for(int i=1;i<=n;++i){
while(nws<=ss&&s[nws].l<=i)st=max(st,s[nws++].r);
if(st>=i)ans[i]=ans[i-1];
else ans[i]=ans[i-1]-1;
}
for(int i=1;i<=sn;++i){
v=ans[ns[i].l];
for(int j=ns[i].l;j<=ns[i].r;++j)if(ans[j]!=v)goto PASS;
return puts("NO"),0;
PASS:
;
}
puts("YES");
for(int i=1;i<=n;++i)printf("%d ",ans[i]);
return 0;
}
D.Subarray Sorting
AC时间:51min
题解:
我们从小到大考虑每一位(b_i),找到最小的(j),满足(ile j,b_i=a_j),然后将(a_j)移到(i)的位置上。
首先,它能移到的条件是(a_j)是序列(a)的区间([i,j])中最小的数。
那么我们直接对区间(i,j)排序吗?
其实是错的。
由于操作的过程是不可逆的,所以我们每次要在将(a_j)移到位置(i)的前提下,尽量保证其他元素的相对位置不变。
所以我们令(k)从(j)到(i+1),依次对(a_k,a_{k-1})进行操作。由于(a_j)是区间([i,j])中最小的数,因此最终(a_j)会被移动到(i)位置,而且其他数相对位置不变。
感觉做完了?
等等!要如何实现呢?
其实也很简单。我们考虑记录若干个vector,其中(p_i)表示数值为(i)的数在(a)中从前往后的出现位置注意这个(a)序列在之后不会改变。
这样一来,我们记(ue_i)表示数(i)已经用了多少个,对于每个(b_i),必然取(j=p_{b_i,ue_{b_i}})。
然后我们就可以线段树维护区间最小值了。注意在将(a_i)移动到指定位置后,在线段树上将对应位置的值赋为无限大。
剩下的就是一些处理多组测试的问题了。
code:
#include<bits/stdc++.h>
#define ci const int&
#define Upd(x) (t[x].mn=min(t[x<<1].mn,t[x<<1|1].mn))
using namespace std;
const int INF=1e9;
struct node{
int l,r,mn;
}t[1200010];
int q,n,a[300010],g[300010],ap[300010],ue[300010];
vector<int>p[300010];
void Build(ci x,ci l,ci r){
t[x].l=l,t[x].r=r;
if(l==r)return(void)(t[x].mn=a[l]);
int mid=l+r>>1;
Build(x<<1,l,mid),Build(x<<1|1,mid+1,r),Upd(x);
}
void Change(ci x,ci id,ci v){
if(t[x].l==t[x].r)return(void)(t[x].mn=v);
int mid=t[x].l+t[x].r>>1;
id<=mid?Change(x<<1,id,v):Change(x<<1|1,id,v),Upd(x);
}
int Query(ci x,ci l,ci r){
if(l>r)return INF;
if(t[x].l==l&&t[x].r==r)return t[x].mn;
int mid=t[x].l+t[x].r>>1;
return l>mid?Query(x<<1|1,l,r):(r<=mid?Query(x<<1,l,r):min(Query(x<<1,l,mid),Query(x<<1|1,mid+1,r)));
}
int main(){
scanf("%d",&q);
for(int fr=1;fr<=q;++fr){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]),ap[a[i]]<fr?p[a[i]].clear(),ue[a[i]]=0,ap[a[i]]=fr:0,p[a[i]].push_back(i);
Build(1,1,n);
for(int i=1;i<=n;++i)scanf("%d",&g[i]);
for(int i=1;i<=n;++i){
if(ap[g[i]]<fr||ue[g[i]]>=p[g[i]].size()){
puts("NO");
goto END;
}
if(Query(1,1,p[g[i]][ue[g[i]]]-1)<g[i]){
puts("NO");
goto END;
}
Change(1,p[g[i]][ue[g[i]]],INF),++ue[g[i]];
}
puts("YES");
END:
;
}
return 0;
}
E.Tree Painting
AC时间:1h30min
题解:
实际上相当于给一棵无根树选定一个根,求每个点子树大小和的最大值。
考虑换根。
记(sz_x)表示节点(x)在1为根时的子树大小,(fsz_x=n-sz_x)。
然后从1开始换根。
如果我们要把根从(i)换到(j),(j)是在1为根时,(i)的一个孩子。那么事实上,除了(i,j)以外的节点对答案的贡献不变。
而点(i)的贡献减少了(sz_j),点(j)的贡献增加了(n-sz_j)。
直接取(max)即可。
code:
#include<bits/stdc++.h>
#define ci const int&
using namespace std;
struct edge{
int t,nxt;
}e[400010];
int n,u,v,cnt,be[200010],sz[200010],fsz[200010],vis[200010];
long long ans;
void add(ci x,ci y){
e[++cnt].t=y,e[cnt].nxt=be[x],be[x]=cnt;
}
void Get(ci x){
vis[x]=sz[x]=1;
for(int i=be[x];i;i=e[i].nxt)!vis[e[i].t]?Get(e[i].t),sz[x]+=sz[e[i].t]:0;
fsz[x]=n-sz[x],ans+=sz[x];
}
void dfs(ci x,long long nw){
ans=max(ans,nw),vis[x]=0;
for(int i=be[x];i;i=e[i].nxt)vis[e[i].t]?dfs(e[i].t,nw-sz[e[i].t]+(fsz[x]+sz[x]-sz[e[i].t])),0:0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
Get(1),dfs(1,ans);
printf("%I64d",ans);
return 0;
}
总结
莫名其妙Rank9,似乎是因为D题fst了一大堆?
然后就上橙了。。。
幸福来得太突然