实小社团练习赛8

本文总阅读量次

T1

枚举+打擂台
注意，检测点没有人数限制。

T2

模拟题
情况很多，需要分情况考虑。
两头奶牛如何分配，使得最近的两头奶牛距离D尽可能大。
假设两头奶牛没加入前，相邻两头奶牛的距离为： $D 1$ 、 $D 2$ ...
相邻奶牛的最短距离为目前最优解，即 $m i n D = m i n (D 1, D 2. . .)$
所以，要明确的是，加入两头奶牛后，新产生的距离不可能比 $m i n D$ 大，但有可能比 $m i n D$ 小，所以为了使得答案最优解，会把两头奶牛放到之前奶牛之间间隔大的区间。
这题难就难在放在哪里，罗列出来你就知道漏了什么情况。
候选方案1：一头放入先前奶牛相邻的最大距离 $m a x 1$ ，另一头放到第二大距离 $m a x 2$ ，两头奶牛产生新的间距中取小的（假设 $o n e = m i n (m a x_{1} / 2, m a x_{2} / 2)$ ）跟 $m i n D$ 比较。
候选方案2：两头奶牛放入先前奶牛相邻的最大距离，有可能比方案1更优，新产生的间距（假设 $t w o = m a x_{1} / 3$ ）跟 $m i n D$ 比较。
刚才考虑的都是两头奶牛之间的距离，其实还存在一个区间只有一头奶牛的情况（植树问题？），即最左边和最右边，有可能会形成一条线段一个点（有牛的牛栏）的情况。
候选方案3：最左边的区间长度（左端点无奶牛的情况）有可能比 $m a x 1$ 大，所以要跟方案1和方案2的结果进行比较。

if(l>0){
   one = max(one,min(l,max1/2)); //奶牛放入左端点后距离为l，跟方案1的距离pk，看谁大。one是max1跟max2比较的结果，所以l不用跟max2比较。
   two = max(two,l/2); //左边区间放入两头奶牛，只要分成两个区间即可。植树问题？two代表max1分成3个区间后的平均值
}

候选方案4
右边区间处理同上。
候选方案5：还有一种情况，将两头奶牛分别放在左端点和右端点，前提左右端点都没有奶牛，只要一个端点有奶牛，此方案无效。即 $m i n (l, r)$ 也加入候选方案。
前4个候选方案，最后结果保存在 $o n e$ 和 $t w o$ 中，候选方案5放在 $m i n (l, r)$ 中，我们需要在这3个结果中找出最大者，即：
$m a x (o n e, t w o, m i n (l, r))$ ，最后此结果跟 $m i n D$ 比较，找出最优解。
计算左端点和右端点空牛栏长度

    //左端空牛栏计算
    for(int i = 0; i < n; i++)
        if(s[i]=='0') l++;
            else break;
    if (l==n){                 //特判，牛栏全空的，那么两头奶牛放两端即可
        cout<<n-1<<endl;
        return 0;
    }

右端点计算同上，但不要特判了，不要问为什么……
寻找最大间距长度和第二大间距长度
简单，只是一个横向扫描：

int cnt = 1;   //注意题中的描述，间距=区间长度去掉一个端点后的长度
    for(int i = l + 1; i < n-r; i++){
        if(s[i]=='1'){
            mind=min(mind,cnt); //顺便求了最短间距
            if(cnt>=max1){  //等于可不能丢，万一第一大和第二大相等呢
                max2 = max1;
                max1 = cnt;
            }else max2=max(max2,cnt);
            cnt = 1;
        }else cnt++;
    }

然后按前面分析的步骤写即可。

T3

模拟+排序
拿到题目后，仔细读题，然后思考题目的切入口。
题目告诉我们存在一个感染半径R，那不妨可以找一个不会感染的最小半径R，只要相邻两头奶牛中，一头没被感染，我们可以认为这两头奶牛之间的距离不会感染病毒，在这些距离中寻找一个最小的值。因为规模很小，直接枚举也可以求这个安全距离，例如：假设b数组记录是否感染，a数组记录奶牛的位置。

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        if(b[i]!=b[j]) R=min(R,abs(a[i]-a[j]));

排序做法

按位置从小到大排序，记住把感染状态一起跟着排序。
然后枚举相邻两只奶牛的感染情况，如果不相等，则有一只没被感染，更新最小安全距离。
然后按位置从小到大排序（还是逃不掉排序），把感染生病的奶牛位置塞入一个数组，枚举整个数组，如果相邻两头奶牛的距离大于或等于安全距离R，说明找到一个新的感染群体，即后面的奶牛感染跟前面的奶牛无关；反之如果相邻两头病牛的距离小于R，说明它们是彼此感染的，属于一个感染群体。

ans = 1; //第一头病牛看成一个群体
for(int i = 2; i <= 病牛总数; i++){ 
    if(f[i]-f[i-1]>=R) ans++; //找到新的感染群体
}

T4

DFS
当第一个 $x$ 确定后，第二个 $x$ 在第一个基础上枚举，即：

for(int i = max(1,x-p) ; i <= min(s,x+p); i++)

这里一定要考虑越界的情况。
又因为 $n$ 可变，所以考虑枚举->DFS(深搜),但是第一个数必须在主程序枚举，这是因为首先要确定第一个加数。

for(int i = 1; i <= s-p+1; i++)

深搜需要几个参数呢？即下一次搜索需要知道哪些信息？
加数个数，当前的和，当前的加数
因为只有知道上一次的加数，才能确定下一次搜索的范围。
于是：

void dfs(int cnt,int sum, int x){
   if(来个剪枝呗) return;
   if(cnt==n){
        if(sum==s)ans++; //找到方案
        return;
    }
    //然后丢上枚举范围，dfs函数填空题即可
}

主程序在第一个加数枚举的时候，进行dfs填空题即可.

d f s (1, i, i)