又一次用题目说明了线段树的重要性
T1：
就是升级版的lineup
给了n个数，现在可以删掉k种数，问在这种情况下最多能达成的连续的相等的数字之总长度
思路：用一个单调队列进行维护，维护到了每个点时的最长长度
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node{ int x,y; }a[2000100]; int n,m,ans=-1,cnt=1,c[2010000]; int read(){ char c=getchar();int re=0,flag=1; while((c<'0'||c>'9')&&c!='-') c=getchar(); if(c=='-'){ flag=-1;c=getchar(); } while(c>='0'&&c<='9') re=re*10+int(c-48),c=getchar(); return re*flag; } bool cmp1(node l,node r){ return l.x<r.x; } bool cmp2(node l,node r){ return l.y<r.y; } int main(){ freopen("lineup.in","r",stdin); freopen("lineup.out","w",stdout); int i,l=1,len=0,now; n=read();m=read(); for(i=1;i<=n;i++) a[i].x=read(),a[i].y=i; sort(a+1,a+n+1,cmp1); now=a[1].x; for(i=1;i<=n;i++){ if(now==a[i].x) a[i].x=cnt; else{ now=a[i].x;a[i].x=++cnt; } } sort(a+1,a+n+1,cmp2); for(i=1;i<=n;i++){ if(!c[a[i].x]&&len<=m){ len++;c[a[i].x]++; ans=max(ans,c[a[i].x]); } else if(!c[a[i].x]&&len>m){ c[a[i].x]++; c[a[l].x]--; while(c[a[l].x]) l++,c[a[l].x]--; l++; ans=max(ans,c[a[i].x]); } else{ c[a[i].x]++; ans=max(ans,c[a[i].x]); } } printf("%d",ans); }
T2：
题意：有一张50*50的地图，图中连续的X为岛屿，S为浅水，.为深水
问题来了：在给定的小于等于二十个岛中，从任意一个点出发，最多经过多少个潜水方块，能够走到所有岛？
思路：bfs和spfa处理每两个岛之间的最短距离，状压dp：f[i][j]中，i表示现在走过的岛屿的集合，j表示最后一个岛（现在的落脚点）
代码量大啊......
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #define mp make_pair using namespace std; const int dx[5]={0,-1,0,1,0},dy[5]={0,0,-1,0,1}; int n,m,a[151][151],nb[151][151],cnt=0; int dis[120][120]; bool vis[151][151]; vector<pair<int,int> >island[120]; int dp[200100][16]; void bfs(int stx,int sty){ int i,j,x,y,tx,ty,xx,yy,flag; pair<int,int>tmp; queue<pair<int,int> >q; q.push(mp(stx,sty));vis[stx][sty]=1; nb[stx][sty]=++cnt,island[cnt].push_back(mp(stx,sty)); while(!q.empty()){ tmp=q.front();q.pop(); x=tmp.first;y=tmp.second; for(i=1;i<=4;i++){ tx=x+dx[i];ty=y+dy[i]; if(tx>0&&tx<=n&&ty>0&&ty<=m&&!vis[tx][ty]&&a[tx][ty]==2){ q.push(mp(tx,ty));vis[tx][ty]=1;nb[tx][ty]=cnt; island[cnt].push_back(mp(tx,ty)); } } } } void spfa(int k){ queue<pair<int,int> >q; int i,x,y,tx,ty; pair<int,int>tmp; int len[150][150]; dis[k][k]=0;memset(len,127,sizeof(len)); for(i=0;i<island[k].size();i++){ q.push(island[k][i]); vis[island[k][i].first][island[k][i].second]=1; len[island[k][i].first][island[k][i].second]=0; } while(!q.empty()){ tmp=q.front();q.pop(); x=tmp.first;y=tmp.second; vis[x][y]=0; for(i=1;i<=4;i++){ tx=x+dx[i];ty=y+dy[i]; if(0<tx&&tx<=n&&ty>0&&ty<=m&&a[tx][ty]&&((a[tx][ty]==2)?(len[tx][ty]>len[x][y]):(len[tx][ty]>len[x][y]+1))){ if(a[tx][ty]==2&&dis[k][nb[tx][ty]]>len[x][y]){ dis[k][nb[tx][ty]]=len[x][y]; } len[tx][ty]=((a[tx][ty]==2)?len[x][y]:(len[x][y]+1)); if(!vis[tx][ty]){ vis[tx][ty]=1;q.push(mp(tx,ty)); } } } } } int main(){ int i,j,k;char str[51]; scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%s",str); for(j=0;j<m;j++){ if(str[j]=='.') a[i][j+1]=0; if(str[j]=='S') a[i][j+1]=1; if(str[j]=='X') a[i][j+1]=2; } } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(a[i][j]==2&&!nb[i][j]) bfs(i,j); } } memset(dis,127,sizeof(dis)); for(i=1;i<=cnt;i++){ memset(vis,0,sizeof(vis)); spfa(i); } memset(dp,127,sizeof(dp)); int tot=0,ans=0x7fffffff; for(i=1;i<=cnt;i++){ dp[1<<(i-1)][i]=0;tot+=(1<<(i-1)); } for(i=1;i<=tot;i++){ for(j=1;j<=cnt;j++){ if(i&(1<<(j-1))){ for(k=1;k<=cnt;k++){ if((i-(1<<(j-1)))&(1<<(k-1))) dp[i][j]=min(dp[i][j],dp[i-(1<<(j-1))][k]+dis[k][j]); } } } } for(i=1;i<=cnt;i++) ans=min(ans,dp[tot][i]); printf("%d",ans); }
T3：
题意：等同于9.10的T3，一模一样hhhhhh
T4：
给出n(n<500)个正方形的中心点，和每一个都相等的边长，问有没有互相覆盖的正方形存在？
如果没有输出0，有一对的话输出重叠的面积，有两对以上输出-1
思路：把正方形按照x坐标排序，对于每一个正方形，对于在数组中排在自己后面，而且x坐标和自己相差不到边长的正方形检测y坐标即可
理论最大时间是O(nlonn+n2)，但是实际上后面只有不到nlogn
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; struct node{ int x,y; }a[50010]; long long n,k,i,j,ans=0,tmp; bool cmp(node l,node r){ return l.x<r.x; } int read(){ char c=getchar();int re=0,flag=1; while((c<'0'||c>'9')&&c!='-') c=getchar(); if(c=='-'){ flag=-1;c=getchar(); } while(c>='0'&&c<='9') re=re*10+int(c-48),c=getchar(); return re*flag; } int main(){ freopen("squares.in","r",stdin); freopen("squares.out","w",stdout); n=read();k=read(); for(i=1;i<=n;i++) a[i].x=read(),a[i].y=read(); sort(a+1,a+n+1,cmp); for(i=1;i<=n;i++){ for(j=i+1;a[j].x<a[i].x+k&&j<=n;j++){ if((abs(a[j].y-a[i].y)<k)&&(abs(a[j].y-a[i].y)<k)){ if(ans==1){ printf("-1");return 0; } else{ ans++;tmp=abs((k-abs(a[i].x-a[j].x))*(k-abs(a[i].y-a[j].y))); } } } } if(ans) printf("%lld",tmp); else printf("0"); }