这套月赛题不是特别难
T1:离散化+单调队列,队列里出现数的种类不超过K+1,找最大的num[a[i]]
T2:一眼可以看出BFS+状压DP,还要SPFA预处理出各个块之间的dis
T3:线段树,没什么难度
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; ; int n,K,a[maxn],b[maxn],m,ans,head,tail,q[maxn],vis[maxn],cnt; int main(){ scanf("%d%d", &n, &K); ; i<=n; i++) scanf("%d", &b[i]),a[i]=b[i]; sort(b+,b++n); m=unique(b+,b++n)-b-; ; i<=n; i++) a[i]=lower_bound(b+,b++m,a[i])-b; //for (int i=1; i<=n; i++) printf("%d\n", a[i]); head=tail=cnt=; ; i<=n; i++){ if (!vis[a[i]]) cnt++; vis[a[i]]++; q[tail++]=i; ){ vis[a[q[head]]]--; ) cnt--; head++; } ans=max(ans,vis[a[q[tail-]]]); } printf("%d\n", ans); ; }
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; ; ]={,,,-}; ]={,-,,}; struct node{ int x,y; node(int _x, int _y):x(_x),y(_y){} }; <<][],dis[][],id[maxn][maxn],vis[maxn][maxn],cnt,stx[],sty[],N; char s[maxn][maxn]; bool check(int x, int y){ || y< || x>n || y>m) ; ; } void bfs(int sx, int sy, int num){ queue<node> Q; Q.push(node(sx,sy)); id[sx][sy]=num; vis[sx][sy]=; while (!Q.empty()){ int x=Q.front().x, y=Q.front().y; Q.pop(); ; k<; k++){ int tx=x+dx[k], ty=y+dy[k]; if (check(tx,ty) && !vis[tx][ty] && s[tx][ty]=='X'){ vis[tx][ty]=; id[tx][ty]=num; Q.push(node(tx,ty)); } } } } void find_land(){ cnt=; ; i<=n; i++) ; j<=m; j++) if (s[i][j]=='X' && !vis[i][j]){ bfs(i,j,++cnt); stx[cnt]=i; sty[cnt]=j; } // for (int i=1; i<=cnt; i++) printf(" %d %d\n", stx[i], sty[i]); } void spfa(int sx, int sy, int num){ queue<node> Q; int next,cost; memset(d,0x3f,sizeof(d)); memset(dis[num],0x3f,sizeof(dis[num])); Q.push(node(sx,sy)); d[sx][sy]=; vis[sx][sy]=; dis[num][num]=; while (!Q.empty()){ int x=Q.front().x, y=Q.front().y; Q.pop(); ; k<; k++){ int tx=x+dx[k], ty=y+dy[k]; if (!check(tx,ty) || s[tx][ty]=='.') continue; cost=(s[tx][ty]=='S'); if (d[tx][ty]>d[x][y]+cost){ d[tx][ty]=d[x][y]+cost; ){ vis[tx][ty]=; Q.push(node(tx,ty)); } } if ((s[tx][ty]=='X') && ((next=id[tx][ty])!=num)) dis[num][next]=min(dis[num][next],d[tx][ty]); } vis[x][y]=; } } void dp(){ N=(<<cnt); memset(f,0x3f,sizeof(f)); ; i<=cnt; i++) f[(<<(i-))][i]=; ; s<N; s++){ ; i<=cnt; i++) <<(i-))) ; j<=cnt; j++) <<(j-)))) f[s^(<<(j-))][j]=min(f[s^(<<(j-))][j],f[s][i]+dis[i][j]); } int ans=0x7fffffff; ; i<=cnt; i++) ans=min(ans,f[N-][i]); printf("%d\n", ans); } int main(){ scanf("%d%d", &n, &m); ; i<=n; i++){ scanf(); } find_land(); ; i<=cnt; i++) spfa(stx[i],sty[i],i); dp(); ; }
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; ; struct node{ int l,r,len,lz,lm,rm,mx; }t[maxn*],now; int n,m,x,y,ans; ]; void pushup(int x){ t[x].lm=t[x<<].lm; ].lm==t[x<<].len) t[x].lm=t[x<<].len+t[x<<|].lm; t[x].rm=t[x<<|].rm; |].rm==t[x<<|].len) t[x].rm=t[x<<|].len+t[x<<].rm; t[x].mx=max(t[x<<].rm+t[x<<|].lm,max(t[x<<].mx,t[x<<|].mx)); } void pushdown(int x){ ){ //涂色 t[x<<].lz=; t[x<<|].lz=; t[x<<].lm=t[x<<].rm=t[x<<].mx=; t[x<<|].lm=t[x<<|].rm=t[x<<|].mx=; } ){ //不涂色 t[x<<].lz=; t[x<<|].lz=; t[x<<].lm=t[x<<].rm=t[x<<].mx=t[x<<].len; t[x<<|].lm=t[x<<|].rm=t[x<<|].mx=t[x<<|].len; } t[x].lz=; } node query(int x, int p){ int l=t[x].l, r=t[x].r; pushdown(x); ].mx>=p) ,p); ].rm+t[x<<|].lm>=p){ node ret; ret.l=t[x<<].r-t[x<<].rm+; ret.r=ret.l+p-; return ret; }|,p); } void update(int a, int b, int x, int c){ int l=t[x].l, r=t[x].r; if (l==a && r==b){ ){ t[x].lz=; t[x].lm=t[x].rm=t[x].mx=; } ){ t[x].lz=; t[x].lm=t[x].rm=t[x].mx=t[x].len; } return; } ; pushdown(x); ,c); |,c); ,c),update(mid+,b,x<<|,c); pushup(x); } void build(int l, int r, int x){ t[x].l=l; t[x].r=r; t[x].len=r-l+; if (l==r){ t[x].lz=; t[x].lm=t[x].rm=t[x].mx=; return; } ; build(l,mid,x<<); build(mid+,r,x<<|); pushup(x); } int main(){ scanf("%d%d", &n, &m); build(,n,); //printf("%d\n", t[1].mx); while (m--){ scanf("%s", opt); ]=='A'){ scanf("%d", &x); ].mx<x) ans++; else{ now=query(,x); //printf(" %d %d\n", now.l, now.r); update(now.l,now.r,,); } }else{ scanf("%d%d", &x, &y); update(x,y,,); } } printf("%d\n", ans); ; }