【tyvj模拟赛】—— 第二轮

模拟赛 tyvj ZZQBXT

昨天今天两天参加了tyvj，即QBXT的模拟赛。
需要承认，虽然QBXT收费BT，但是题目出的还是很厉害的
然而一个D2爆零的人有什么资格评论题目

那么总结一下好了。

Day 1

T1

题目大意是有一个矩阵，按照一定规则从外到里遍历，直到中心点，给出初始点坐标和步数，看走到了哪。

YY

我采取的算法是判断到了第几圈然后模拟，至于到了第几圈，代码大概长这样

int calc(int x,int y){
    int max_num=min(n+1,m+1)/2;
    for (int i=0;i<=max_num;i++){
        if ((x==i||x==m-i) && (y>=i&&y<=n-i)) return i;
        if ((x>=i&&x<=m-i) && (y==i||y==n-i)) return i;
    }
}

然后很长的一段模拟

while (z){
        if (y==cnt){
            if (x<m-cnt){
                int temp=m-cnt-x;
                if (z<temp){
                    x+=z;z-=z;
                    break;
                }
                z-=temp,x+=temp;
//              printf("%d %d\n",x,y);
                continue;
            }
            else if (x==m-cnt){
                int temp=n-cnt-y;
                if (z<temp){
                    y+=z;z-=z;
                    break;
                }
                z-=temp,y+=temp;
//              printf("%d %d\n",x,y);
                continue;
            }
        }
        if (y==n-cnt){
            if (x>cnt){
                int temp=x-cnt;
                if (z<temp){
                    x-=z;z-=z;
                    break;
                }
                z-=temp,x-=temp;
//              printf("%d %d\n",x,y);
                continue;
            }
            if (x==cnt){
                int temp=y-cnt-1;
                if (z<temp){
                    y-=z;z-=z;
                    break;
                }
                z-=temp,y-=temp;
                cnt++;
//              printf("%d %d\n",x,y);
                continue;
            }
        }
        if (x==cnt){
            int temp=y-cnt-1;
            if (z<temp){
                y-=z;z-=z;
                break;
            }
            z-=temp,y-=temp;
//          printf("%d %d\n",x,y);
            cnt++;
            continue;
        }
        if (x==m-cnt){
            int temp=n-y;
            if (z<temp){
                y+=z;z-=z;
                break;
            }
            z-=temp,y+=temp;
//          printf("%d %d\n",x,y);
            continue;
        }
    }

但是这样搞，只有70.
后来经过ghbdalao的提示，想到一件事情，就是说，我这种模拟方法，当走到中心点无法搞事情的时候是会没办法减小z然后T掉。
然后八成是T掉了 【手动滑稽

正解
正解倒是没有那么复杂，直接从头开始找，然后消除整行。

T2

T2让我们对于一个排列计算所有区间最大最小值的差值，并计算这些差值的个数

YY
我开始想的时候看到区间最大最小值，就毫不犹豫使用了ST表。
然后n^2查找。
理想得分60，实际得分30；

那么为什么只有30，我想是因为以下原因
1.ST表预处理是O(Nlogn)的，再加上t，有可能给出一个非常大的常数
2.我没有注意到数据范围，数据范围已经暗示了O(n^2)只要有常数就会炸掉

正解
那么到底应该怎么办。
首先，有一个很简单的让我的程序变为60的方法，就是去掉ST表。
为什么可以直接去掉ST表呢？
在题中，我们枚举了每一个区间，那么枚举左右端点的时候我实际上就是枚举了每一个数，这样的话我们开两个变量记录最小值最大值，然后统计就可以了。

说完60我们说100。
其实正解让我很无语，利用了题中一句话数据保证随机生成来保证复杂度
可以想到不一定是每次都会改变最小最大值的，因为数据随机，可以想到每次最大值最小值的改变最多不会超过logn次。
因为要隔一段才改变，并且最大值最小值符合单调性原则，可以使用单调队列预处理出下一次改变的位置，然后和60分方法一样枚举左端点计算即可。
复杂度是没有保证的，但是可以确定的是预处理O(n)，然后平均复杂度可能在O(nlogn)上下的样子。

T3

T3先介绍了一个定义，在一个序列中每个数的位置和其值差值的绝对值不超过k的序列叫做k近似数列
要求在一个序列，部分数被确定的情况下，找出k近似数列的个数。

YY
我一看到这题就不是很想写了。
说实话这么大的数据我一开始认为是某种数学方法所以就没有再细想。
因此我一开始就计划好了要拿30的分数，从结果看确实达到了要求。

那么就不好意思的说一下我30的解法。
其实很简单，枚举每个数字是否可用然后dfs就可以了。

正解
正解自然是dp

在这里把题解上给出的多种dp解法都说一下好了。

50
看到可用与否，01表示状态然后使用状压dp就可以作为一个思路了。
我们用dp[i]表示形成i这个状态时可以有的方案数，那么枚举到j位时，可以进行如下转移

//dp[i]由当前枚举到的第pos位前的k转移而来，现在不妨设temp为前k位的状态
//当当前位未被赋值时候
for (int t=0;t<k;t++){
    if (i&(1<<(pos-t))) continue
    dp[i+(1<<(pos-t))]+=dp[i];
}
//当当前位已被赋值时，我这一位就必须选val[i]
dp[i]+=dp[i-(1<<val[i]-1)]

70
50的解法中数组是开不下的，但是对于第i位实际用到的只有i-k+1到i+k位。
所以开数组的时候可以开两维dp[i][j]，其中i表示位置，j表示i-k+1至i+k的状态。
递推时按照50分解法即可。

100
本蒟蒻并不会的矩阵快速幂。
代码待更新。

Day 2

Day 2我爆零了我就不再说自己的解法了，直接上正解

T1

简单来说，组合数求最后的0。
求0个数，可以转化为求min(num_2,num_5)
递推加上前缀和优化即可。
另外有优化：if (i%5==0) num_2[i]=num[i/5]+1;

T2

传说中的NOI原题？
这是个关于树的题，大意是在树上加边然后求最远距离。
我这题无脑敲了Floyd，结果爆零233
按说暴力BFS40，但是我没有拿到。
按说搞事情贪心又是20，但是我没拿到。
按说……算了，我写不出正解。

那么看看正解是什么。
首先对于给出的图我们先建树，建树以后我们可以确定每个询问必然只有以下两种情况

1.询问的两个点在一棵子树上，这样的话对于这颗子树可以运用树归方法求解
2.不在，我们可以分类讨论

T3

dp，FFT，不会

蒟蒻瑟瑟发抖