NOIp2018集训test-9-23

这个NOI模拟题怕是比你们的NOIp模拟题要简单哦。。

友好的生物

应该是一道简单题，但是机房只有辉神一个人想到正解似乎。

被我kd-tree水过去了（这不是kd-tree的裸题吗？？？（不是））

 //Achen

 #include<bits/stdc++.h>

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

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

 #define Formylove return 0

 #define inf 1e18

 const int N=;

 using namespace std;

 typedef long long LL;

 typedef double db;

 int n,K,D;

 LL C[],ans;

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

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

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

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

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

 }

 struct node {

     int d[];

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

         return A.d[D]<B.d[D];

     }

 }p[N],q[N],T;

 void get_min(int &x,int y) { if(x>y) x=y; }

 void get_max(int &x,int y) { if(x<y) x=y; }

 int rt,ch[N][],dt[N][][];

 #define lc ch[x][0]

 #define rc ch[x][1]

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

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

     For(i,,K-) dt[x][i][]=dt[x][i][]=p[x].d[i];

     if(lc) For(i,,K-) {

         get_min(dt[x][i][],dt[lc][i][]);

         get_max(dt[x][i][],dt[lc][i][]);

     }

     if(rc) For(i,,K-) {

         get_min(dt[x][i][],dt[rc][i][]);

         get_max(dt[x][i][],dt[rc][i][]);

     }

 }

 int build(int l,int r,int k) {

     if(l>r) return ;

     D=k;

     sort(p+l,p+r+);

     int x=((l+r)>>);

     lc=build(l,x-,(k+)%K);

     rc=build(x+,r,(k+)%K);

     update(x,l,r);

     return x;

 }

 void get_ans(int x) {

     LL rs=;

     For(i,,K-) rs+=abs(p[x].d[i]-T.d[i])*C[i];

     rs-=abs(p[x].d[K-]-T.d[K-])*C[K-];

     ans=max(ans,rs);

 }

 LL guess_min(int x) {

     LL rs=;

     For(i,,K-) {

         if(dt[x][i][]<=T.d[i]&&dt[x][i][]>=T.d[i]) continue;

         if(T.d[i]<dt[x][i][]) rs+=(dt[x][i][]-T.d[i])*C[i];

         else rs+=(T.d[i]-dt[x][i][])*C[i];

     }

     rs-=max(abs(T.d[K-]-dt[x][K-][]),abs(T.d[K-]-dt[x][K-][]))*C[K-];

     return rs;

 }

 LL guess_max(int x) {

     if(!x) return -inf;

     LL rs=;

     For(i,,K-) {

         rs+=max(abs(T.d[i]-dt[x][i][]),abs(T.d[i]-dt[x][i][]))*C[i];

     }

     if(T.d[K-]<dt[x][K-][]) rs-=(dt[x][K-][]-T.d[K-])*C[K-];

     else if(T.d[K-]>dt[x][K-][]) rs-=(T.d[K-]-dt[x][K-][])*C[K-];

     return rs;

 }

 void qry(int x,int l,int r,int k) {

     if(!x||l>r) return ;

     get_ans(x);

     LL lg=guess_max(lc);

     LL rg=guess_max(rc);

     if(lg<=ans&&rg<=ans) return ;

     if(lg>=rg) {

         qry(lc,l,mid-,(k+)%K);

         if(rg>ans) qry(rc,mid+,r,(k+)%K);

     }

     else {

         qry(rc,mid+,r,(k+)%K);

         if(lg>ans) qry(lc,l,mid-,(k+)%K);

     }

 }

 #define ANS

 int main() {

 #ifdef ANS

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

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

 #endif

     read(n); read(K);

     For(i,,K-) read(C[i]);

     For(i,,n) {

         For(j,,K-) read(p[i].d[j]);

         q[i]=p[i];

     }

     ans=-inf;

     rt=build(,n,);

     For(i,,n) {

         T=q[i];

         qry(rt,,n,);

     }

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

     //cerr<<clock()<<endl;

     Formylove;

 }

kd-tree

正解：

这个题其实是三道题中最简单的一道。先来看这个问题的一个简化版，假设所有的属性都是差值越大越友好的话：

那么，这个题目会变得简单很多，我们依次枚举在最有情况下，每一种属性值是编号小的动物大，还是编号大的动物大。假设，对于第i种属性，编号小的动物大这种情况用t[i]=-1表示，编号大的动物属性值大这种情况用t[i]=1表示。那么，动物i和动物j的属性值

并且，我们总有一个时刻可以枚举对每一种属性的情况，使等号成立。所以，我们可以通过寻找右侧式子的最大值来确定左侧式子的最大值。

回到本题，题目中的最后一个属性和前面的是反过来的，即差值越小越友好，在这种情况下，我们可以先将动物们按照最后一个属性值来排序，之后按照上面给出的做法实现就可以了。

正解当然优美很多了

 //Achen

 #include<bits/stdc++.h>

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

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

 #define Formylove return 0

 #define inf 1e18

 const int N=;

 using namespace std;

 typedef long long LL;

 typedef double db;

 int n,K,D;

 LL C[],ans;

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

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

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

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

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

 }

 struct node {

     int d[];

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

         return A.d[K-]>B.d[K-];

     }

 }p[N];

 #define ANS

 int main() {

 #ifdef ANS

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

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

 #endif

     read(n); read(K);

     For(i,,K-) read(C[i]);

     For(i,,n) {

         For(j,,K-) read(p[i].d[j]);

     }

     sort(p+,p+n+);

     LL pr=inf;

     ans=-inf;

     int up=(<<K-)-;

     For(t,,up) {

         pr=inf;

         For(i,,n) {

             LL tp=;

             For(d,,K-) if(t&(<<d-)) tp-=C[d-]*p[i].d[d-];

             else tp+=C[d-]*p[i].d[d-];

             ans=max(ans,tp+C[K-]*p[i].d[K-]-pr);

             pr=min(pr,tp+C[K-]*p[i].d[K-]);

         }

     }

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

     //cerr<<clock()<<endl;

     Formylove;

 }

基因重组

这是个真水题，n^2dp随便怎么做，我做的时候脑子有点抽写得有点奇怪，还用了short卡空间。。但是这个dp随便怎么写都能过吧。

 //Achen

 #include<bits/stdc++.h>

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

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

 #define Formylove return 0

 const int N=;

 using namespace std;

 typedef long long LL;

 typedef double db;

 int n,m,up=,c1,c2,c3;

 short s1[N][N],f[N][N],mi[N],ans;

 LL x;

 char a[N],b[N],a2[N];

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

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

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

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

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

 }

 void get_min(short &x,int y) { if(x>y) x=y; }

 #define ANS

 int main() {

 #ifdef ANS

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

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

 #endif

     read(x); if(x>up) c1=up+; else c1=x;

     read(x); if(x>up) c2=up+; else c2=x;

     read(x); if(x>up) c3=up+; else c3=x;

     scanf("%s",a); n=strlen(a);

     For(i,,n-) {

         if(a[i]=='A') a2[i]='T';

         else if(a[i]=='T') a2[i]='A';

         else if(a[i]=='C') a2[i]='G';

         else if(a[i]=='G') a2[i]='C';

     }

     scanf("%s",b); m=strlen(b);

     Rep(i,n,) Rep(j,m,) {

         if(a[i-]==b[j-]) s1[i][j]=s1[i+][j+]+;

         else s1[i][j]=;

         if(a2[i-]==b[j-]) f[i][j]=f[i+][j+]+;

         else f[i][j]=;

     }

     For(i,,n) For(j,,m) s1[i][j]=max(s1[i][j],f[i][j]);

     memset(f,,sizeof(f));

     memset(mi,,sizeof(mi));

     mi[]=;

     f[][]=; ans=up;

     For(i,,n) {

         For(j,,m) {

             get_min(f[i][j],(int)mi[j]+c2);

             mi[j]=min(mi[j],f[i][j]);

             int t=s1[i+][j+];

             get_min(f[i+t][j+t],(int)f[i][j]+c1);

             if(j==m) get_min(ans,(int)f[i][j]);

             else get_min(f[i][j+],(int)f[i][j]+c3);

         }

     }

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

     //cerr<<clock()<<endl;

     Formylove;

 }

危险的迷宫

好多人切这题啊。。。全机房就我一个人不知道这题是费用流？？？

这不是一道插头dp的裸题吗？？？？

人类，你们对插头dp一无所知！

作死写了百行转移，结果大样例都没过，交上去还水过了50pt.

然后de了一晚上。。。

一个是有个地方n和m写反了，另外两个是两段轮廓线上一个是1一个是2的时候，如果这个格子本身是1或者2那么是不合法的，不能直接合并清0了！两句话价值一晚上+50pt。

 //Achen

 #include<bits/stdc++.h>

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

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

 #define Formylove return 0

 const int N=;

 using namespace std;

 typedef long long LL;

 typedef double db;

 int n,m,K,C,f[][][N],inf,pr[];

 int a[][],is[][],rr[][],dn[][];

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

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

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

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

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

 }

 void GM(int &x,int y) { if(x>y) x=y; }

 int get(int s,int k) {

     return s/pr[k-]%;

 }

 #define ANS

 int main() {

 #ifdef ANS

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

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

 #endif

     read(n); read(m);

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

     read(K);

     For(i,,K) {

         int x1,y1,x2,y2;

         read(x1); read(y1);

         read(x2); read(y2);

         if(x1>x2) swap(x1,x2),swap(y1,y2);

         if(x1<x2) dn[x1][y1]=;

         else {

             if(y1>y2) swap(y1,y2);

             rr[x1][y1]=;

         }

     }

     read(C);

     For(i,,C) {

         int x,y;

         read(x); read(y);

         is[x][y]=;

     }

     For(i,,C) {

         int x,y;

         read(x); read(y);

         is[x][y]=;

     }

     /*For(i,1,n) {

         For(j,1,m) {

             printf("%d ",rr[i][j]);

         } puts("");

     }

     For(i,1,n) {

         For(j,1,m) {

             printf("%d ",dn[i][j]);

         } puts("");

     }

     For(i,1,n) {

         For(j,1,m) {

             if(is[i][j]) printf("%d(%d)",a[i][j],is[i][j]);

             else printf("%d",a[i][j]);

     }*/

     pr[]=;

     For(i,,) pr[i]=pr[i-]*;

     memset(f,/,sizeof(f));

     inf=f[][][];

     f[][][]=;

     int up=pr[m+]-;

     For(i,,n) {

         For(j,,m) {

             For(s,,up) if(f[i][j][s]!=inf) {

                 int prs=s;

                 if(j==) s*=;

                 int f1=get(s,j),f2=get(s,j+);

                 int ii,jj;

                 if(j==m) ii=i+,jj=;

                 else ii=i,jj=j+;

                 if(!f1) {

                     if(!f2) {

                         if(is[i][j]) {

                             if(rr[i][j]) GM(f[ii][jj][s+is[i][j]*pr[j]],f[i][j][prs]+a[i][j]);

                             if(dn[i][j]) GM(f[ii][jj][s+is[i][j]*pr[j-]],f[i][j][prs]+a[i][j]);

                         }

                         else {

                             GM(f[ii][jj][s],f[i][j][prs]);

                             if(rr[i][j]&&dn[i][j]) {

                                 GM(f[ii][jj][s+pr[j-]+*pr[j]],f[i][j][prs]+a[i][j]);

                                 GM(f[ii][jj][s+*pr[j-]+pr[j]],f[i][j][prs]+a[i][j]);

                             }

                         }

                     }

                     if(f2==) {

                         if(is[i][j]==)

                             GM(f[ii][jj][s-pr[j]],f[i][j][prs]+a[i][j]);

                         else if(!is[i][j]) {

                             if(rr[i][j]) GM(f[ii][jj][s],f[i][j][prs]+a[i][j]);

                             if(dn[i][j]) GM(f[ii][jj][s+pr[j-]-pr[j]],f[i][j][prs]+a[i][j]);

                         }

                     }

                     if(f2==) {

                         if(is[i][j]==)

                             GM(f[ii][jj][s-*pr[j]],f[i][j][prs]+a[i][j]);

                         else if(!is[i][j]) {

                             if(rr[i][j]) GM(f[ii][jj][s],f[i][j][prs]+a[i][j]);

                             if(dn[i][j]) GM(f[ii][jj][s+*pr[j-]-*pr[j]],f[i][j][prs]+a[i][j]);

                         }

                     }

                 }

                 else if(f1==) {

                     if(!f2) {

                         if(is[i][j]==)

                             GM(f[ii][jj][s-pr[j-]],f[i][j][prs]+a[i][j]);

                         else if(!is[i][j]) {

                             if(rr[i][j]) GM(f[ii][jj][s-pr[j-]+pr[j]],f[i][j][prs]+a[i][j]);

                             if(dn[i][j]) GM(f[ii][jj][s],f[i][j][prs]+a[i][j]);

                         }

                     }

                     if(f2==) ;

                     if(f2==&&!is[i][j])

                         GM(f[ii][jj][s-pr[j-]-*pr[j]],f[i][j][prs]+a[i][j]);

                 }

                 else if(f1==) {

                     if(!f2) {

                         if(is[i][j]==)

                             GM(f[ii][jj][s-*pr[j-]],f[i][j][s]+a[i][j]);

                         else if(!is[i][j]) {

                             if(rr[i][j]) GM(f[ii][jj][s-*pr[j-]+*pr[j]],f[i][j][s]+a[i][j]);

                             if(dn[i][j]) GM(f[ii][jj][s],f[i][j][s]+a[i][j]);

                         }

                     }

                     if(f2==&&!is[i][j])

                         GM(f[ii][jj][s-*pr[j-]-pr[j]],f[i][j][s]+a[i][j]);

                     if(f2==) ;

                 }

                 s=prs;

                 if(f[][][]!=inf) {

                     int debug=;

                 }

             }

         }

     }

     if(f[n+][][]==inf) puts("-1");

     else printf("%d\n",f[n+][][]);

     //cerr<<clock()<<endl;

     Formylove;

 }

巴特西

NOIp2018集训test-9-23

最新文章

热门文章