NOIp2018集训test-9-16(联考二day2)

T1旋转子段

一开始脑袋抽了花了近一个小时写了个跟这题毫无关系的莫名其妙的代码，一急代码就各种bug,最后t1就花了一个半小时多，然后后面时间不太够了，考得稀烂。

因为每个数存在唯一的中心使得绕这个中心翻转后成为”不动点“，容易想到枚举对称中心。因为把关于这个中心对称的所有点都翻转不一定最优(然而王巨直接全翻过了，数据大概是用脚造的)，那么按到对称中心的距离排序后一一枚举翻到哪个位置的答案，不翻的部分用前缀和数组维护即可，每个点只会在它的对称中心被枚举到，所以复杂度是nlogn(set or 排序)的。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,a[N],sa[N],sum[N],f[N],ans;

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 struct node {

     int i,ai;

     node(int i,int ai):i(i),ai(ai){}

     friend bool operator <(const node&A,const node&B) {

         return max(A.i,A.ai)<max(B.i,B.ai);

     }

 };

 multiset<node>vc[N];

 #define ANS

 int main() {

 #ifdef ANS

     freopen("rotate.in","r",stdin);

     freopen("rotate.out","w",stdout);

 #endif

     read(n);

     For(i,,n) {

         read(a[i]);

         sa[a[i]]=i;

         sum[i]=sum[i-]+(a[i]==i);

         vc[i+a[i]].insert(node(i,a[i]));

     }

     For(i,,n) {

         int r=max(i,a[i]),l=min(i,a[i]);

         f[i]=sum[l-];

     }

     For(i,,*n) if(vc[i].size()) {

         int tp=;

         while(vc[i].size()){

             node x=*vc[i].begin();

             vc[i].erase(vc[i].begin());

             tp++;

             ans=max(ans,f[x.i]+tp+sum[n]-sum[max(x.i,x.ai)]);

         }

     }

     printf("%d\n",ans);

     Formylove;

 }

 /*

 20

 12 2 6 16 3 17 19 15 13 4 11 20 8 10 18 1 9 5 7 14

 */

T2跳房子

这是一个很sb的dijkstra，但是机房大多数人(除了yicongli)都没考虑清楚，总是在同一个地方打两次传送门来传送，会被这样的数据卡掉

#####
#...#
#...#
#.C.#
#...#
#...#
#.F.#
#####

题解说的是，先跑一遍dijkstra找到每个点最近的墙，我看到这个数据的时候也是这样想的，但是ycl吊打标解。

如图，从一个点到离它最近的墙和它要去的目标点的交点的路径上是一定没有墙的，否则就不是最近的墙了，所以一定可以直接走到那个交点，然后从交点打出两个传送门进行传送，所以把每个点向它四周能到达的第一个墙连距离为四个距离的最小值的边就可以了。

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,m,sx,sy,tx,ty,xx[]={,,-,},yy[]={-,,,};

 char s[N][N];

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 struct node {

     int x,y,dis;

     node(int x,int y,int dis):x(x),y(y),dis(dis){}

     friend bool operator <(const node&A,const node&B) {

         return A.dis>B.dis;

     }

 };

 int ok(int x,int y) { return x>=&&x<=n&&y>=&&y<=m; }

 #define pr pair<int,int>

 #define fi first

 #define se second

 pr tt[N][N][];

 int td[N][N];

 void pre() {

     memset(td,/,sizeof(td));

     For(i,,n) {

         For(j,,m) {

             if(s[i][j]!='#'&&s[i][j-]!='#') {

                 tt[i][j][].fi=tt[i][j-][].fi;

                 tt[i][j][].se=tt[i][j-][].se;

             }

             else tt[i][j][].fi=i,tt[i][j][].se=j;

             td[i][j]=min(td[i][j],j-tt[i][j][].se);

         }

         Rep(j,m,) {

             if(s[i][j]!='#'&&s[i][j+]!='#') {

                 tt[i][j][].fi=tt[i][j+][].fi;

                 tt[i][j][].se=tt[i][j+][].se;

             }

             else tt[i][j][].fi=i,tt[i][j][].se=j;

             td[i][j]=min(td[i][j],tt[i][j][].se-j);

         }

     }

     For(j,,m) {

         For(i,,n) {

             if(s[i][j]!='#'&&s[i-][j]!='#') {

                 tt[i][j][].fi=tt[i-][j][].fi;

                 tt[i][j][].se=tt[i-][j][].se;

             }

             else tt[i][j][].fi=i,tt[i][j][].se=j;

             td[i][j]=min(td[i][j],i-tt[i][j][].fi);

         }

         Rep(i,n,) {

             if(s[i][j]!='#'&&s[i+][j]!='#') {

                 tt[i][j][].fi=tt[i+][j][].fi;

                 tt[i][j][].se=tt[i+][j][].se;

             }

             else tt[i][j][].fi=i,tt[i][j][].se=j;

             td[i][j]=min(td[i][j],tt[i][j][].fi-i);

         }

     }

 }

 int dis[N][N],vis[N][N];

 priority_queue<node>que;

 void dijkstra() {

     que.push(node(sx,sy,));

     while(!que.empty()) {

         node tp=que.top();

         que.pop();

         if(dis[tp.x][tp.y]!=tp.dis||vis[tp.x][tp.y]) continue;

         vis[tp.x][tp.y]=;

         For(i,,) {

             int nx=tp.x+xx[i],ny=tp.y+yy[i];

             if(ok(nx,ny)&&s[nx][ny]!='#') {

                 if(dis[nx][ny]>tp.dis+) {

                     dis[nx][ny]=tp.dis+;

                     que.push(node(nx,ny,tp.dis+));

                 }

             }

             pr t=tt[tp.x][tp.y][i];

             if(t.fi==tp.x&&t.se==tp.y) continue;

             if(dis[t.fi][t.se]>tp.dis++td[tp.x][tp.y]) {

                 dis[t.fi][t.se]=tp.dis++td[tp.x][tp.y];

                 que.push(node(t.fi,t.se,tp.dis++td[tp.x][tp.y]));

             }

         }

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("cell.in","r",stdin);

     freopen("cell.out","w",stdout);

 #endif

     read(n); read(m);

     For(i,,n) {

         scanf("%s",s[i]+);

         For(j,,m) {

             if(s[i][j]=='C') sx=i,sy=j;

             else if(s[i][j]=='F') tx=i,ty=j;

         }

     }

     pre();

     memset(dis,/,sizeof(dis));

     int inf=dis[][];

     dis[sx][sy]=;

     dijkstra();

     if(dis[tx][ty]==inf) puts("no");

     else printf("%d\n",dis[tx][ty]);

     Formylove;

 }

 /*

 4 5

 #####

 #C#.#

 ###F#

 #####

 */

T3column

我的树状数组还是当年ppz教的，一直不是很会搞树状数组，知道标解但是树状数组半天弄不陈展，然后最后放弃了直接打了个暴力，下来后想着要写树状数组还是头疼，就写了线段树，于是很快就过了。。

枚举每个点i作为最高点，然后二分高度，如果此时aj<hj的多于aj>hj的就r--否则l++

aj和hj的关系，对于i左边的点看 hi+(i-j)-aj正负，右边看hi+(j-i)-aj的正负，展开之后用数据结构维护就好了。

因为树状数组的时候我总是搞不清楚查的上下界什么的，写线段树的时候虽然写得比较丑，但是直接传进v让它去帮我找小于v或大于v的东西，这样我自己就很容易理清楚

 //Achen

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 #include<set>

 #include<map>

 #define Formylove return 0

 #define For(i,a,b) for(int i=(a);i<=(b);i++)

 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)

 const int N=;

 typedef long long LL;

 typedef double db;

 using namespace std;

 int n,a[N],b[N],sz,a1[N],a2[N];

 LL ans=1e18;

 template<typename T>void read(T &x)  {

     char ch=getchar(); x=; T f=;

     while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

     if(ch=='-') f=-,ch=getchar();

     for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

 }

 #define pr pair<int,LL>

 #define fi first

 #define se second

 #define lc (x<<1)

 #define rc ((x<<1)|1)

 #define mid ((l+r)>>1)

 struct sgtree{

     pr sg[N<<];

     void update(int x,int l,int r,int pos,int f) {

         if(l==r) {

             sg[x].fi+=f;

             sg[x].se+=b[l]*f;

             return;

         }

         if(pos<=mid) update(lc,l,mid,pos,f);

         else update(rc,mid+,r,pos,f);

         sg[x].fi=sg[lc].fi+sg[rc].fi;

         sg[x].se=sg[lc].se+sg[rc].se;

     }

     pr qryx(int x,int l,int r,int v) {

         if(b[r]<v) return sg[x];

         if(b[l]>=v) return make_pair(,);

         pr rs,tp;

         if(b[mid]>=v) return qryx(lc,l,mid,v);

         rs=sg[lc];

         tp=qryx(rc,mid+,r,v);

         rs.fi+=tp.fi,rs.se+=tp.se;

         return rs;

     }

     pr qryd(int x,int l,int r,int v) {

         if(b[l]>v) return sg[x];

         if(b[r]<=v) return make_pair(,);

         pr rs,tp;

         if(b[mid]<=v) return qryd(rc,mid+,r,v);

         rs=sg[rc];

         tp=qryd(lc,l,mid,v);

         rs.fi+=tp.fi,rs.se+=tp.se;

         return rs;

     }

 }t1,t2;

 void solve() {

     For(i,,n) {

         b[++b[]]=i+a[i];

         b[++b[]]=i-a[i];

     }

     sort(b+,b+b[]+);

     sz=unique(b+,b+b[]+)-(b+);

     For(i,,n) {

         a1[i]=lower_bound(b+,b+sz+,i+a[i])-b;

         a2[i]=lower_bound(b+,b+sz+,i-a[i])-b;

         t1.update(,,sz,a1[i],);

     }

     For(i,,n) {

         t1.update(,,sz,a1[i],-);

         int l=max(i,n-i+),r=1e9+n,rs=;

         while(l<=r) {

             pr tp1=t2.qryd(,,sz,i-mid);

             pr tp2=t2.qryx(,,sz,i-mid);

             pr tp3=t1.qryx(,,sz,mid+i);

             pr tp4=t1.qryd(,,sz,mid+i);

             LL tpans=((LL)tp1.fi*(mid-i)+tp1.se)-((LL)tp2.fi*(mid-i)+tp2.se)+

             ((LL)tp3.fi*(mid+i)-tp3.se)-((LL)tp4.fi*(mid+i)-tp4.se)+abs(mid-a[i]);

             ans=min(ans,tpans);

             if(tp1.fi+tp3.fi>tp2.fi+tp4.fi) r=mid-;

             else l=mid+;

         }

         t2.update(,,sz,a2[i],);

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

     freopen("column.in","r",stdin);

     freopen("column.out","w",stdout);

 #endif

     read(n);

     For(i,,n) read(a[i]);

     solve();

     printf("%lld\n",ans);

     Formylove;

 }

 /*

 4

 1 1 2 3

 */

巴特西

NOIp2018集训test-9-16(联考二day2)

最新文章

热门文章