Candy Cane Feast
第一题签到题，依题意模拟即可。注意细节，细节决定成败。
Cowntact Tracing 2
贪心。
读题 奶牛传染，每个奶牛每晚传染左边和右边的奶牛。给定一个传染情况，求最开始最少有几个奶牛。
我们记 k 为造成当前传染情况的传染天数。可以知道，传染的天数越多，被传染的牛就越多。所以很容易得到，造成当前局面的天数越多初始的奶牛就越少。那我们只需要求出造成当前局面的最大天数即可。
对于当前的传染情况，我们可以将他们分成一个一个的传染群(如下图)。因为奶牛只能传染其左边和右边的奶牛，所以不同传染群的牛一定不会相互传染。对于每个传染群，我们可以分别求出如果该传染群中只有一个最初传染源时的天数。其中最小天数的就是造成整个传染情况的最大天数。根据我们前面得到的结论，当天数为最大的时最初奶牛的数目就是最小了。
一些实现细节 这些内容请自行使用草稿纸计算
- 记 len 为传染群的最终牛数
- 记 day 该传染群的最初牛最少时的传染天数
当day在边界上 $day =len-1$，当day不在边界上 $day =ceil(len/2)-1$
- 记 s 为一头牛在 k天下传染的牛数
$s=(1+2k)$ //一头牛一天会传染两头牛（左边和右边），k天传染2*k头。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
char c[N];
int n, pre_list[N], cnt;
int main() {
scanf("%d", &n);
int last = -1;
for (int i = 1; i <= n; i++) {
cin>> c[i];
if(c[i] == '0') last = -1;
if(c[i] == '1') {
if(last != -1) pre_list[last] = max(pre_list[last],i-last+1);
else last = i, pre_list[last] = 1;
}
}
int tmp = max(pre_list[1]-1,0);
int minday = tmp==0?0x3f3f3f3f:tmp;
for(int i = 2; i <= n; i++) {
if(pre_list[i] == 0) continue;
if(i+pre_list[i]-1 == n) {
minday = min(minday,pre_list[i]-1);
}
else
minday = min(minday, int(ceil(pre_list[i]*1.0/2)-1));
}
int ans = 0;
int k=minday*2+1;
for(int i = 1; i <= n; i++) {
ans += ceil(pre_list[i]*1.0/k);
}
printf("%d",ans);
return 0;
}
Farmer John Actually Farms
暴力枚举。
读题 给定 $h_i$ , $a_i$ , $t_i$ 。$h_i$为初始高度，$a_i$ 为每天的长高度，$t_i$为限制条件（这个数组包含 0 到 N-1 的全部整数）。
纯暴力：
我们记树为 i 枚举其他的数记为j ， 对于每个i，j，求出至少要几天，或至多几天内满足 $h_i$ > $h_j$。记为 $day_{i,j}$
if(h[j]>h[i]){
if(a[j]>=a[i]) day1[0]++;
else {
int tmp=ceil((h[j]-h[i])/(a[i]-a[j]));
day2[tmp]++;
}
}
if(h[j]==h[i]) {
if(a[j]>a[i]) day1[1]++;
}
if(h[j]<h[i]) {
if(a[j]>a[i])
day1[ceil( (h[i]-h[j])/(a[j]-a[i]) )]++;
}
以上是我自己的想法。考完发现，时间不过，连这题的纯暴力都没写完。考后还发现自己遗漏了关键信息。如果你和我一样只想到 $O(n^2)$ 的写法的话，先别往下看了，回过头看看题目。你是否遗漏了某些信息？是不是有什么东西没有用到？
暴力+优化：
关键信息：
他将给你一组由不同整数组成的数组 $t_1$,$\dots$,$t_N$
，这个数组包含 0 到 N-1 的全部整数。
这说明如果存在答案，最终的h[i]之间的数是有严格的大小关系的。如果我们把树按照 $t_i$ 为关键字进行小到大进行排序。最终 $h$ 数组是从小到大进行排序的。
因此我们不需要求出 $day_{i,j}$ 只需要求出$day_{i,i+1}$ 即可。时间复杂度为 $O(n\log n)$ + $O(n)$ 。
考后反思：
- 题面信息很重要，没思路看题目，思考信息的用处。
- 细节决定成败，别让调代码占据了你的时间
- 思路复杂不要谎，先别急，理清思路再写代码