[USACO 2018 December Contest]作业总结

时间:2023-02-04 21:40:32

t1 Convention

题目大意

每一头牛都有一个来的时间,一共有\(n\)辆车,求出等待时间最长的那头牛等待的最小时间。

解法

第一眼看到这道题还以为是\(2018noip\)普及组的t3魔鬼题,但是不一样。
我们因为要查找最大最小值,很容易就想到用二分查找。
那么直接查找答案,也就是等待的时间,然后用\(O(n)\)的复杂度的贪心验证就可以了,放的下且能放进去,那么就放。
总体复杂度是\(O(nlogn)\)
\(ps.\)要注意边界的判断。

t2 Convention II

题目大意

让当前最前面的牛吃草,求出最长的等待时间。

解法

非常明显每次都是要按照编号和时间来排序,而且我们需要一个一个从头开始遍历,那么很明显是用优先队列,或者是双关键字的堆排序(这个玩意比较麻烦,还是c++自带的stl比较好写)

t3 Mooyo Mooyo

题目大意

每次会消除有三个及三个以上相同颜色方块的联通块,每次消除后,未被消除的方块都会收到重力的作用,调到下面,如果还有联通块,那么继续消除,知道没有为止。

解法

这道题简直就是简化简化简化版的\(mayan\)游戏,直接暴力不要怂,数据这么小,直接暴力删除,暴力\(update\)。
时间复杂度比较玄学,但是绝对可以过。mayan游戏都可以暴力过,为什么这道题不能?

t4 Fine Dining

题目大意

求出能否让一只奶牛的路径通过一个有甘草捆的点,且增长的时间小于等于甘草捆的美味值。

解法

首先要求出增长的是时间,就需要求出原来的时间,原来的时间就是已\(n\)为起点到每个点的最短距离。
因为要路过一定要路过某一个有干草堆的节点,那么就做\(k\)遍最短路,求出从这个节点到每个节点和终点节点的最短距离,在和美味值和原来的最短距离的和进行比较。
但是这样很明显复杂度超标,那么应该怎么做呢?
我们设置一个超级源,超级源到每一个干草堆的距离是原来的最短距离\(dis[u]\)减去美味值,也就是增加的时间,那么我们只要从\(n\)号节点跑一边最短路就可以了。

t5 Cowpatibility

题目大意

每个奶牛有\(5\)个数,求出有多少对奶牛中五个数没有一个是相等的。

解法

这不是跟这道题目完全一样的吗???前几天刚刚做过 只不过数字从4个变成了5个,而且求的是不是朋友的个数。
但是还是一样的呀!!!容斥原理弄起来,如果我们要求出不是朋友的个数,那么就拿总数,也就是总对数\(n*(n-1)/2\)减掉是朋友的对数。
因为每个奶牛有\(5\)个数,所以我们就不能用5维数组来存储,会\(MLE\)的,那么就用二进制压缩,那么就用\(bitset\)就可以了。

t6 teamwork

题目大意

将\(n\)个数分成\(k\)组,

解法

DP一下

状态:\(f[i]\)表示前\(i\)个数的最大值。

转移方程:\(f[i]=f[j]+max(a[i]...a[j])*(i-j+1)\),其中(i+j-1<=k)。

答案就是\(f[n]\)。

ac代码

#include<bits/stdc++.h>
#define N 10005
using namespace std;
int f[N],a[N];
int n,k;
int read(){
    int w=0,x=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return w?-x:x;
}
int main(){
    n=read(),k=read();
    for(int i=0;i<n;i++) a[i]=read();
    f[0]=a[0];
    for(int i=1;i<n;i++){
        int MX=a[i];
        for(int j=i;j>=0&&i+1-j<=k;j--){
            MX=max(MX,a[j]);
            if(j==0) f[i]=max(f[i],MX*(i-j+1));
            else f[i]=max(f[i],f[j-1]+MX*(i-j+1));
        }
    }
    printf("%d\n",f[n-1]);
    return 0;
}

t7 Balance Beam

题目大意

每次有二分之一的概率移动某一个往前或往后移动一格,如果走到边缘就为\(0\),每次走到一个点就得到当前这个点的分数,求出分数的期望。

解法

期望题好难啊QAQ,看了别人的博客才知道怎么做,看到洛谷中颜色是黑色,真的觉得不容易。

关键在于需要考虑当前是选择移动还是直接结束。一个很明了的观点:如果当前移动后的收益期望比当前位置的收益大,那么会选择移动;否则选择直接停止。直接停止的贡献已经知道,那么要求的就是当前点选择移动操作后的收益期望。

那么我们将所有的点都画在一个坐标系上,然后将答案也标在上面,可以发现,这个玩意是个凸包。

那么我们的期望方程是(f[l[i]])*(r[i]-i)+f[r[i]]*(i-l[i])))/(r[i]-l[i])

至今不是特别明白是什么东西

t8 Sort It Out

题目大意

给定一个长为n的排列,可以选择一个集合S使这个集合内部元素排到自己在整个序列中应该在的位置(即对于集合S内的每一个元素ii,使其排到第i号位置,使得整个排列在排序后为上升序列。求满足这样条件的,且集合大小最小的集合中字典序第k小的集合。

题解

选取一个集合等价于将这个集合内所有元素排到自己该处于的位置(即元素i应该在位置i)。

进一步发现集合内的元素很自觉的到了正确的位置,而集合外的元素不会更改相对位置,为了使最终整个排列单调递增,即要求集合外的元素必须满足在一开始就是单调递增的。

求字典序第k小的满足题意的集合,取反一下,就是求序列中字典序第k大的最长上升子序列。

利用上面这题的思想,已经可以求得以每个元素开头的LIS长度和数量

这题和上面这题虽有不同,但本质类似,想想一般线段树求第 k大的过程,正是依次确定每一层的节点,而为了确定每一层的节点,就需要用到所有节点子树和

同理,假设当前要求的序列的LIS长度为 t,则求第k大LIS的一个思想就是先确定第1个数,再在确定第1个数的基础上确定下一个数……以此类推可以最终确定LIS的每一位

细化一下,就是将所有可能作为LIS的第i位的数 放进第i个vector里,将每个vector内部进行元素排序,在确定每一位时从大到小确定,若当前值后面牵扯的LIS数量小于k,则将k减去这个数量然后检查下一个值,否则将这个值确定下来并开始确认下一位

(值得注意的一点,若求LIS第ii层选定了位置R的元素,则接下来都不能选择R左边的元素)

t9 The Cow Gathering

题目大意

给定树和一些树上有向边,每次删去叶子,询问每个结点能否最后一个删去

解法

判断一个点能否最后一个删,就把它提做根,然后把所有儿子都往上指

加入一条边 (u,v)可以发现以v为根时u的子树都没法最后删

根据这个性质,每次加边钦定一些点答案就是0
怎样快速找到u在以v为根的树中的子树?用类似遥远的国度那题的方法,直接以1号点为根建树,然后这时换根只需要分类讨论一下:如果v在u子树外,不用动;如果v在子树内,那找到v在u的哪个儿子的子树里,除了这个子树其他所有结点钦定答案为0。具体实现就找倍增找v的deep[v]-deep[u]-1级祖先(因为如果暴力遍历儿子,复杂度不对),覆盖就dfs序差分一下

因此需要判下图是否无解

我们把已经确定答案为0的结点确定边的方向,然后加上树上有向边判环。