银河美术馆-Beautyyu

私以为没必要转二叉树

本题应为三维dp,体现的是泛化物品的背包的思想(详见<背包九讲>)

只是决定价值(本题体现为节省的费用)的因素不是单一的重量(体现为产树量),此外还有一个维度据上一个伐木场的距离

具体来说,一个伐木场节省的费用可以是其自己和儿子们的产树量之和和上一个伐木场的距离的成绩,这样我们就简单地设计出了状态转移策略

代码见下.蒻的英语不是很好请见谅

//by beautyyu
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ull unsigned long long
using namespace std;
struct edge{
    int v,w,nxt;
}e[40000];
int head[200],pwp[200],pre[200],memf[200][200][100],memd[200][200][100];
//pwp--sum weight of a subtree,pre--distance from a node to root
//memf--memory for function'f',the same as memd
int w[200],n,k;
int f(int rt,int fa,int kk);
int d(int l,int fa,int kk);
int dfs(int rt,int pr){//calculate 'pwp' and 'pre'
    pre[rt] = pr;
    pwp[rt] = w[rt];
    for (int i = head[rt];i;i = e[i].nxt)
        pwp[rt] += dfs(e[i].v,pr + e[i].w);
    return pwp[rt];
}
int main (){
    scanf("%d%d",&n,&k);
    int al,be,cnt = 0;
    for (int i = 1;i <= n;++ i){
        scanf("%d%d%d",&w[i],&al,&be);
        e[++ cnt] = edge{i,be,head[al]};
        head[al] = cnt;
    }
    //read end
    //first set
    dfs(0,0);
    int sum_ = 0;
    for (int i = 1;i <= n;++ i)
        sum_ += w[i] * pre[i];
    memset(memf,-1,sizeof(memf));
    memset(memd,-1,sizeof(memd));
    //main code
    cout << sum_ - f(0,0,k);
    return 0;
}
int f(int rt,int fa,int kk){
//the value produced by a subtree'rt',the last sawmill 'fa',the rest sawmill I can build
    if(memf[rt][fa][kk] != -1) return memf[rt][fa][kk];
    if(!kk) return memf[rt][fa][kk] = 0;
    return  memf[rt][fa][kk] =  max(d(head[rt],fa,kk),
        d(head[rt],rt,kk - 1) + pwp[rt] * (pre[rt] - pre[fa]));
}
int d(int l,int fa,int kk){
//the value produced by a list begin with 'l','fa'and'kk'are the same as the function 'f'
    if ((!l)||(!kk)) return memd[l][fa][kk] = 0;
    if(memd[l][fa][kk] != -1) return memd[l][fa][kk];
    int ans = 0;
    for (int i = 0;i <= kk;++ i)
        ans = max(ans,f(e[l].v,fa,i) + d(e[l].nxt,fa,kk - i));
    return memd[l][fa][kk] = ans;
}

#关于1699的一些话

其实也没什么好说的啦

##1699知识竞赛

由微笙无上计算机协会和学生会学习活动部联合举办

作为一个新生社团,微笙无上的第一次独立活动

---

从最开始策划是上学期的事情,由于和学习活动部的原定计划冲突,在团委老师的协调下微笙挑战赛和一站到底合并为了今天的1699知识竞赛

尽管过程中由许多不如意和两方的冲突,终于还是把活动办下来了

• 最早先是策划阶段,总共进行了三次还是四次会面才敲定下所有赛制流程.

• 接着开始宣传了.一开始由我制作宣传页,不过因为效果不尽人意又重置了一版,结果自己只是作为p图的.而学生会方面的海报则是早先就做好了

• 然后是初赛的准备阶段.因为此前还没有过经验,zjl的赛事程序和我负责的美工都是反复经过了修改

• 在赛前突然就接下了operator的任务其实只是严某太懒不想自己上del>.由于是第一场参赛数量最多的初赛,何况全部都是限时题,需要保持连续三小时高度专精.结果自然是累的不行当晚和朋友出去吃饭几乎抱怨了一晚.另外由于时间紧迫题目数量的质量都有严重缺陷安南还是下一任联合国秘书长呢,六十道题基本不够用.但总体上这一场还是顺利的进行了

• 第二个学期一开学就开始准备复赛.毕竟UI设计沿用上一场的风格所以作为美工没有太大工作量.以及比赛只有四场 现场主持过程也轻松了很多.私以为是最好的一场

• 决赛阶段使用了一套新的UI,并且所有题目都经过细细审核,我自己也出了半套题,组织加了两套题.但实际赛场并不尽如人意,观众比复赛场少了太多.半决结束后几乎已经成了自娱自乐.而决赛过程中也出现了内部暗示的情况.实在有些可惜

虽然最后结果并不是太完美,或者说和预想由不小差距,但是当最后所有获奖者,所有staff在一起合影的时候,实在是非常开心,所有的不快都被一种自足所覆盖.

毕竟是自己第一次作为策划之一去做独立活动啊

说到底,即使是自娱自乐,做活动的过程就已经很让人享受了啊

最后附一张完美的合影

题意简述:

有n个机器，每个机器有2个芯片，每个芯片可以放k个电池。
每个芯片能量是k个电池的能量的最小值。
两个芯片的能量之差越小，这个机器就工作的越好。
现在有2nk个电池，已知它们的能量，我们要把它们放在n个机器上的芯片上，
使得所有机器的能量之差的最大值最小

自然,求解最大值最小问题应当用二分实现.主程序很容易就能写出来了

int n,k,m;
int arr[1000005];
int main (){
    cin >> n>>k;
    m = ((n * k) << 1);
    for (int i = 1;i <= m;++ i){
        scanf("%d",&arr[i]);
    }
    sort(arr + 1,arr + 1 + m);
    int l = 0,r = arr[m] - arr[1];
    while (l < r){
        int mid = l + ((r - l) >> 1);
        if (!canit(mid))
            l = mid + 1;
        else r = mid;
    }
    cout << l;
    return 0;
}

重点就在于check函数的实现

能否让每一组芯片差值都小于限定值t呢?

此前我们要先给电池分配制定一个最优策略,这个策略的分配方式一定能使满足约束的机器尽量多

而进一步观察还可以发现:对于一颗芯片的k颗电池,只有最小的那颗电池可以决定一个方案的优度,我们称之为有效电池,而剩下的k-1颗电池只不过是用于”凑数”的而已,我们称之为填充电池.不同的两颗芯片交换填充电池(假如它们比有用电池大的话),对结果是没有影响的

那么问题可以解释为:

一个满足约束t的有用电池分配方案,是否有足够的填充电池使这个方案实现??

那么就来分配有用电池

一个有用电池应当是一组k个电池中最小的,因此理应从小到大分配有用电池

而一组芯片的能量差最小,这组芯片的两颗有用电池应当是相邻的(当然事先应该为电池按能量排序)

int j = 1;//为第j组芯片寻找有用电池
int cnt = 0;//记录当前所需的额外填充电池
for (int i = 1;i <= 2*n*k;++ i){
    if (energy[i + 1] - energy[i] <= t)//假如这组电池满足约束,可以作为有用电池
        ++ j,cnt += 2 * (k - 1);//为这组芯片分配k-1个填充电池,并为下一组芯片寻找有用电池
    else
        cnt --;//假如这组电池不满足约束,那第i颗电池永远也没有机会成为有用电池了.但它还可以发光发热--为之前的有用电池充当填充电池(注意这些有用电池一定比第i颗电池能量小,因为它们已经按能量排序了).那么有了这位"志愿者",我们就可以省下一颗额外填充电池
    if (j >= n) return 1;
}

注意:如果分配如上述那样顺利的话,这个方案就是成立的–一颗电池要么作为有用电池,要么作为填充电池,总之没有”永久废弃”的,而题目保证了有恰好2nk颗电池,如果每颗电池都被用到,那这些电池当然就会正好用完.所以这个方案就是成立的

那么反过来,方案不成立是什么情况?出现了”永久废弃”的电池

什么情况下第i颗电池连”别人的填充电池”都无法做到?如果此前的有用电池没有耗费任何一颗额外填充电池,那么第i颗电池也就没办法去替代节省一颗额外填充电池,那么它就被永久废弃了.

于是完整的check函数如下(和上面那份代码实现方式不太一样,不过函数命名的意义是相同的)

bool canit(const int &t){
    int cnt = 0,i = 1;
    for (int j = 1;j <= n;++ j){
        while (cnt >= 0 && arr[i + 1] - arr[i] > t) ++i,--cnt;
        if (cnt < 0) return 0; //一旦没有额外填充电池,就说明出现了永久废弃电池,这种方案就不成立了
        cnt += ((k - 1) << 1);
        i += 2;
    }
    return 1;
}

是一篇拖延症晚期拖了好久才开始写的学习笔记

大概记一下关于二分和分治的感想吧

二分

二分也没啥好说的(况且作为蒟蒻也只会写二分答案),基本套路就是二分答案在检查一下答案,把求值问题转化为判定性问题

值得注意的是:关于限定最大值求最小和限定最小值求最大应当有两种不同的处理

//限定最小值求最大
while (l < r){
    mid = l + ((r - l + 1) >> 1);
    if (!check(mid)) r = mid - 1;
    else l = mid;
}
return l;
//限定最大值求最小
while (l < r){
    mid = l + ((r - l) >> 1);
    if (!check(mid)) l = mid + 1;
    else r = mid;
}

两者本质的共同点在于:

1. 当区间长为偶时,一定要将区间平分,否则在区间长足够小的时候会陷入死循环
2. 当mid可以满足约束时,一定要将它包含在下一个检查的区间里,否则若mid为解时程序将求不出解

此外:

二分查找配合前缀/后缀和数组进行使用有奇效

分治

挺广泛的一个操作,包括线段树在内许多东西都是利用的分治的思想.这里记两个印象比较深刻的分治

二分的分治

经典的就是平面最近点对问题.平面问题反正先离散就是了.接着对x值分成两部分–这是没道理的暴力的分.当分至只有一个点时就得到一个当前最优状态maxint

而分治的核心在于合并操作:整个算法的复杂度就是合并复杂度加上一个logN.对于平面最近点对问题的合并暴力又不失效率:对于割线两边距离不大于当前最优值的点进行配对,查看是否有更优解.(此外除了x值的限定还可以对y值进一步限定).复杂度上看它是一个N^2的合并,但实际上这个"暴力"的算法效率很高

总的来说,如果能写出一个高效的合并,分治可以将一个N降为logN

快排的分治

这种分治用于求第k大问题等.和其它分治相比,它的特色在于:没有一个固定的mid值,它只有一个随机取的mid的价值,并通过比较这个价值的大小从两边向中间逼近,从而求出mid值,用于确定下一个区间.也就是二分的分治的反向操作

当然,由于鄙人比较弱,所以不知道这个操作除了求第k大之外还有什么用

#a*学习笔记

这篇文章是鄙人学习aStar主要参考的文章,私以为对aStar的讲解十分有逻辑了

aStar本质上是一个宽度优先算法 -对于一个状态 拓展出它能转移的所有状态 将这些状态推入队列 再逐个拓展 直到目标状态

但不同的是aStar算法中的队列变成了优先队列-对于更有可能优的状态我们优先去拓展它。而优的判定就通过一个启发函数来实现

###a*基本概念

a*一般用于解决最小花费/最大价值问题

1. 起始状态start: 由题面给出的起始状态
2. 目标状态goal: 由题面给出的目标状态
3. 已使用花费g_cost: 由start转移到now的花费
4. 估计花费h_cost : 由now转移到goal的估计花费,在寻路问题中一般使用曼哈顿估价
5. 花费评估f_cost: 评估本条道路的总花费,即f_cost = g_cost + h_cost
6. 开启列表openset: 目前已拓展出的状态,一般是一个以f_cost作为优先度的堆
7. 关闭列表offset: 禁用拓展的状态和处理完成的状态
8. 追溯表comeFrom: 存储父子关系,一般在询问拓展路径的情况下用到

###a*操作方式

1. 从openset中取出F最小的点now,并加入offset
2. 判读该点是否为goal,真则完成搜索过程
3. 对于now转移得neighbor,对于一个neighbor而言:
   1. 它在offset中:它被continue了
   2. 它在openset中:
      1. 它的G值优于openset中的那位,则将其替代,更新comeFrom
      2. 它的G值不如openset中的那位,则不管它
   3. 它不在openset中:加入openset

a*的操作原理大约是这样 更具体的讲解可以翻阅篇首提到的博客

###值得注意的是

1. 当一个状态被放入openset之后,它可能还会被其他状态所拓展来的替代,即上边的3-2-1的情况,因此:当goal进入openset中后,我们并未得到最优路径,当它进入offset时的路径才是最优的,这点与朴素的bfs是不同的
2. 对于上边的3-2-2的情况:由于新状态的G值优于原有状态的G值,因此它的F值也更优,直接扔进堆中一定在原有的状态之上,也就是说:3-2-2和3-3并不需要区别处理
3. offset即bfs中的判重操作,可以是布尔数组也可以是其他东西

##a* 模板

以下均为个人向,c++内容

//status
struct node{
    int ;// value about the state
    int f,g,h;//three cost function
    void forecast(){//update the f_cost and g_cost
        f = g + (h = /*pass*/);
        return ;
    }
    bool ifgoal(){//check if it is goal
        return ;
    }
    bool operator < (const node &al) const{//declear the priority
        return f > al.f;
    }
    void putoffset(){//put the state into the offset
        return;
    }
    bool ifoffset(){//check if the state is in the offset
        return;
    }
};
priority_queue<node> openset;
/*(?) offset*/
bool astar(){
    while (!openset.empty()){
        node r = openset.top();openset.pop();
        if (r.ifgoal()) return 1;
        // when the goal node in the offset ,it is the real best way;
        r.putoffset();
        for (){
            node th = /*a new state*/;
            if (/*it is forbidden*/ || th.ifoffset()) continue;
            th.forecast();
            openset.push(th);
        }
    }
    return 0;
}