[考试反思]1012csp-s模拟测试70：盘旋

这套题比较烂。。。

上来看到T2是原题，一想上一次考试遇到原题就不换，这次应该也是，于是直接开始码，码了一半然后换题了

T1打表找规律或者推式子都不难。。。

T2水的一匹暴力剪枝即可，但是我并不知道数据那么那么水所以还花了很多时间优化

T3神奇的大模拟，挺有意思但是考场上不可能有人能拿到20+

所以因为题比较烂，所以我就上去了？

隔了一场之后RP守恒又恢复了？

啊啊不要乱说啊再过十几分钟就又要考一场了啊。。。

T1：木板

具体化式子也就是个初中数学，结论就是(最大平方因子的平方根-1)<<3，打个100的表就出来了

 #include<cstdio>

 int main(){

     long long n,mx;scanf("%lld",&n);

     while(n){

         for(long long i=;i*i<=n;++i)if(n%(i*i)==)mx=i;

         printf("%lld\n",(mx-)<<);scanf("%lld",&n);

     }

 }

183B

T2：打扫卫生

看到数据范围，直接上根号。

dp[i]表示以i为某一段的结尾，到i为止的最优dp值。

几个比较明显的性质：

0）$dp[i]<=i$

1）颜色数超过$\sqrt{i}$时不必再考虑从前面转移。否则转移来的值不满足上一条

2）任意$i<j$有$dp[i]<=dp[j]$

运用第二条打一个暴力，及时跳出。

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int dp[],n,m,a[],al[],cal;

 int min(int a,int b){return a<b?a:b;}

 int main(){//freopen("2.in","r",stdin);freopen("bl.out","w",stdout);

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;++i){scanf("%d",&a[i]);if(a[i]==a[i-])i--,n--;}

     for(int i=;i<=n;++i)dp[i]=i;

     for(int i=;i<=n;++i){

         int knd=;

         for(int j=i-;~j;--j){cal++;

             knd+=al[a[j+]]==i?:;

             if(knd*knd>=dp[i])break;

             al[a[j+]]=i;

             dp[i]=min(dp[i],dp[j]+knd*knd);

         }

     }printf("%d\n",dp[n]);std:cerr<<cal<<endl;

 }

800ms

然后你就AC了。

显然复杂度还是$O(n^2)$的。对拍随机数据，其最内层循环进入了900000000次。

可见题目的数据还不如随机数据。

优化，上述做法的复杂度瓶颈在于你只保证了你扫了$\sqrt{i}$个颜色，但不一定是$\sqrt{i}$个位置。

那么其实可以发现，从i往前扫，到连续的一段区间上的颜色数都相等，根据那第2条性质，那么你直接从这个区间的左端点转移即可。

那么现在的问题是：你要O(1)找到从位置i往前最远到哪里有恰好k种颜色。

考虑位置i，它的颜色为p，那么你找到上一次p出现的位置，这个位置以后再也不会贡献颜色数了，以后不会从它转移。

那么很自然的想法就是一个链表，把上一个p跳过，这一个p加入。

这样沿着链表往前跳，每次必然遇到一个新颜色，颜色数+1。

根据性质1，你最多跳$\sqrt{i}$种颜色。

总复杂度$n\sqrt{n}$。

 #include<cstdio>

 int dp[],n,m,a[],lp[],lst[],nxt[];

 int min(int a,int b){return a<b?a:b;}

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;++i){scanf("%d",&a[i]);if(a[i]==a[i-])i--,n--;}

     for(int i=;i<=n;++i)dp[i]=i;

     lst[]=;nxt[]=;

     for(int i=;i<=n;++i){

         int knd=,l=lp[a[i]];

         lp[a[i]]=i;

         if(l)lst[nxt[l]]=lst[l],nxt[lst[l]]=nxt[l];

         nxt[lst[]]=i,lst[i]=lst[],lst[]=i,nxt[i]=;

         for(int j=lst[];j;j=lst[j]){

             knd++;

             if(knd*knd>=dp[i])break;

             dp[i]=min(dp[i],dp[lst[j]]+knd*knd);

         }

     }printf("%d\n",dp[n]);

 }

T3：骆驼

大模拟。

结论是5*5的网格任意选取起点终点都有解。

所以把这些5*5网格拼接一下就好了。

分奇偶讨论，有些人需要特判5和15的点。

最好好好利用关键位置（3，3）,能简单不少（但是我用的不是。。所以特别麻烦）

大网格的拼接也可以搜索，不一定要执迷于for循环自行讨论。。。

终于打出来了！

 #include<cstdio>

 int n,s[][][][][][],ans[][],sx,sy,ex,ey,ord[][];

 const int xx[]={,,,-,,,-,-};

 const int yy[]={,-,,,,-,,-};

 #define tx x+xx[i]

 #define ty y+yy[i]

 bool sch(int stp,int x,int y){

     if(stp==)return x==ex&&y==ey;

     if(x==ex&&y==ey)return false;

     for(int i=;i<=;++i)if(tx>&&ty>&&tx<=&&ty<=&&!s[sx][sy][ex][ey][tx][ty]){

         s[sx][sy][ex][ey][tx][ty]=stp+;

         if(sch(stp+,tx,ty))return true;

         s[sx][sy][ex][ey][tx][ty]=;

     }return false;

 }

 void fill(int x,int y,int sx,int sy,int ex,int ey){

     for(int i=;i<=;++i)for(int j=;j<=;++j)ans[x*-+i][y*-+j]=s[sx][sy][ex][ey][i][j]++*ord[x][y];

 }

 int main(){scanf("%d",&n);

     for(int i=;i<=;++i)for(int j=;j<=;++j)for(int k=;k<=;++k)for(int l=;l<=;++l)

         s[sx=i][sy=j][ex=k][ey=l][i][j]=,sch(,i,j);

     int bl=n/;

     if(bl==)for(int i=;i<=;++i)for(int j=;j<=;++j)ans[i][j]=s[][][][][i][j];

     else if(bl==){

         for(int i=;i<=;++i)for(int j=;j<=;++j)ans[i][j]=s[][][][][i][j]>?n*n-+s[][][][][i][j]:s[][][][][i][j];//(1,1)

         ord[][]=;ord[][]=;ord[][]=;

         ord[][]=;ord[][]=;ord[][]=;ord[][]=;

         fill(,,,,,);fill(,,,,,);fill(,,,,,);fill(,,,,,);fill(,,,,,);

         fill(,,,,,);fill(,,,,,);fill(,,,,,);

     }

     else if(bl&){int alc=-;

         for(int i=;i<=bl;++i)ord[i][]=++alc;

         for(int i=bl;i>;--i)if(i&)for(int j=;j<=bl;++j)ord[i][j]=++alc;

             else for(int j=bl;j>;--j)ord[i][j]=++alc;

         ord[][bl]=++alc;ord[][bl]=++alc;

         for(int i=bl-;i>;--i)if(i&)ord[][i]=++alc,ord[][i]=++alc;

             else ord[][i]=++alc,ord[][i]=++alc;

         for(int i=;i<bl;++i)fill(i,,,,,);

         fill(bl,,,,,);

         for(int i=;i<=;++i)for(int j=;j<=;++j)ans[i][j]=s[][][][][i][j]>?n*n-+s[][][][][i][j]:s[][][][][i][j];//(1,1)

         for(int i=;i<=bl;i+=)for(int j=;j<=bl;++j)fill(i,j,,,,);

         for(int i=;i<=bl;i+=)for(int j=;j<=bl;++j)fill(i,j,,,,);

         for(int i=;i<bl-;i+=)fill(,i,,,,),fill(,i,,,,);

         for(int i=;i<bl;i+=)fill(,i,,,,),fill(,i,,,,);

         fill(,bl,,,,);fill(,bl,,,,);fill(,bl-,,,,);fill(,,,,,);fill(,bl-,,,,);

     }else{int alc=-;

         for(int i=;i<=bl;++i)ord[i][]=++alc;

         for(int i=bl;i;--i)if(i&)for(int j=bl;j>;--j)ord[i][j]=++alc;

             else for(int j=;j<=bl;++j)ord[i][j]=++alc;

         for(int i=;i<bl;++i)fill(i,,,,,);

         fill(bl,,,,,);

         for(int i=;i<=;++i)for(int j=;j<=;++j)ans[i][j]=s[][][][][i][j]>?n*n-+s[][][][][i][j]:s[][][][][i][j];//(1,1)

         for(int i=;i<=bl;i+=)for(int j=;j<=bl;++j)fill(i,j,,,,);

         for(int i=;i<=bl;i+=)for(int j=;j<=bl;++j)fill(i,j,,,,);

     }

     for(int i=;i<=n;++i,puts(""))for(int j=;j<=n;++j)printf("%3d ",ans[i][j]);

 }

巴特西

[考试反思]1012csp-s模拟测试70：盘旋

最新文章

热门文章