noip模拟65 solutions
这个看到最后一题是他们的省选模拟题我整个人都傻了
不过好像之前也有过，但是这一回我是真的不会做
所以这一次我仅仅改了两道题
T1 网格图
这个就直接枚举就好了，直接一点一点的更新，\(\mathcal{O(n^3)}\)
就完事了。。。。
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=505;
char s[N];
int n,m,jz[N][N],ans;
int id[N][N],tot;
int fa[N*N],siz[N*N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
int fx=find(x),fy=find(y);
//cout<<fx<<" "<<x<<" "<<fy<<" "<<y<<endl;
if(fx==fy)return ;
fa[fx]=fy;siz[fy]+=siz[fx];
}
int ji[N*N],cnt,res;
bool vis[N*N];
signed main(){
#ifdef oj
freopen("grid.in","r",stdin);
freopen("grid.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
fo(i,1,n){
scanf("%s",s+1);
fo(j,1,n){
if(s[j]=='.')jz[i][j]=1;
else jz[i][j]=0;
id[i][j]=++tot;
fa[tot]=tot;siz[tot]=1;
}
}
fo(i,1,n){
fo(j,1,n){
if(!jz[i][j])continue;
if(i<n&&jz[i+1][j])merge(id[i][j],id[i+1][j]);
if(j<n&&jz[i][j+1])merge(id[i][j],id[i][j+1]);
}
}
//cout<<"sx"<<" "<<find(id[3][2])<<endl;
fo(i,m,n){
fo(j,m,n){
cnt=0;res=0;
if(j==m){
fo(x,i-m+1,i){
fo(y,j-m+1,j){
if(jz[x][y]){
int fx=find(id[x][y]);
siz[fx]--;
}
}
}
}
else {
fo(x,i-m+1,i){
if(jz[x][j-m]){
int fx=find(id[x][j-m]);
siz[fx]++;
}
if(jz[x][j]){
int fx=find(id[x][j]);
siz[fx]--;
}
}
}
//cout<<res<<endl;
fo(x,i-m+1,i){
if(j>m&&jz[x][j-m]){
int f=find(id[x][j-m]);
if(!vis[f])res+=siz[f],vis[f]=true,ji[++cnt]=f;
}
if(j<n&&jz[x][j+1]){
int f=find(id[x][j+1]);
if(!vis[f])res+=siz[f],vis[f]=true,ji[++cnt]=f;
}
}
fo(y,j-m+1,j){
if(i>m&&jz[i-m][y]){
int f=find(id[i-m][y]);
if(!vis[f])res+=siz[f],vis[f]=true,ji[++cnt]=f;
}
if(i<n&&jz[i+1][y]){
int f=find(id[i+1][y]);
if(!vis[f])res+=siz[f],vis[f]=true,ji[++cnt]=f;
}
}
ans=max(ans,res);
//cout<<i<<" "<<j<<" "<<res<<endl;
fo(k,1,cnt)vis[ji[k]]=false;
//fo(k,1,tot)if(vis[k])cout<<"Sb"<<endl;
if(j==n){
fo(x,i-m+1,i){
fo(y,j-m+1,j){
if(jz[x][y]){
int fx=find(id[x][y]);
siz[fx]++;
}
}
}
}
}
}
printf("%d",ans+m*m);
}
T2 序列问题
CDQ板子好吧
当然也可以直接最长上升子序列
AC_code
#include<bits/stdc++.h>
using namespace std;
#define oj
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=5e5+5;
int n,ans;
struct node{
int a,id,f;
node(){}
}sca[N];
bool comp1(node x,node y){return x.a<y.a;}
bool comp2(node x,node y){return x.id<y.id;}
int tr[N];
void ins(int x,int v){
if(x==0){tr[0]=max(tr[0],v);return ;}
for(int i=x;i<=n;i+=(i&(-i)))tr[i]=max(tr[i],v);
}
int ask(int x){
int ret=tr[0];
for(int i=x;i;i-=(i&(-i)))ret=max(ret,tr[i]);
return ret;
}
void clear(int x){
if(x==0){tr[0]=0;return ;}
for(int i=x;i<=n;i+=(i&(-i)))tr[i]=0;
}
void sol(int l,int r){
if(l==r)return ;
int mid=l+r>>1;
sol(l,mid);
sort(sca+l,sca+mid+1,comp1);
sort(sca+mid+1,sca+r+1,comp1);
for(int ir=mid+1,il=l;ir<=r;ir++){
while(il<=mid&&sca[il].a<sca[ir].a){
if(sca[il].id-sca[il].a>=0)ins(sca[il].id-sca[il].a,sca[il].f);il++;
}
if(sca[ir].id-sca[ir].a>=0)sca[ir].f=max(sca[ir].f,ask(sca[ir].id-sca[ir].a)+1);
}
for(int i=l;i<=mid;i++)if(sca[i].id-sca[i].a>=0)clear(sca[i].id-sca[i].a);
//sort(sca+l,sca+mid+1,comp2);
sort(sca+mid+1,sca+r+1,comp2);
sol(mid+1,r);
//sort(sca+l+1,sca+r+1,comp2);
}
signed main(){
#ifdef oj
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
#endif
scanf("%d",&n);
fo(i,1,n){
scanf("%d",&sca[i].a),sca[i].id=i;
if(sca[i].a<=sca[i].id)sca[i].f=1;
}
sol(1,n);
fo(i,1,n)ans=max(ans,sca[i].f);
printf("%d",ans);
}