2021/09/01 基础算法例题测试 日志

本蒟蒻写的蒟蒻日志，不慎点入的大佬轻喷呀

2021/09/01 P.M.

14:15-16:15

Problems	Equation	Dominoes	Queue	Josephus	Happy	Lift	Group	Fight
预估分数	100	100	100	100	100	100	0	100
实际分数	100	100	100	100	100	80	0	90

解题报告

A:Equation (方程f(x)的根)

一道水题.

看到区间求零点直接上二分.

注意精度,使用double形变量.

（很显然,1e-10的精度是不能暴力的）

 学到了：a的b次幂可以用exp(x*log(2))求得.需要包含<cmath>库.

 (水漫金山了这)

B:Dominoes (骨牌游戏)

第一看就想到在n*m的方格中放1*2的骨牌,纠结了一会是不是状压DP.实际上是恍惚的毛病犯了,是我没看见是在n*2的网格中放骨牌.发现之后直接找数据.画了半分钟,画到n=3的时候就直觉感觉是斐波那契数列.继续画了一会,觉得没问题就过了.

C:Queue (大神排队)

我觉得题解说的很好啊w

/*

本题是经典的贪心问题.

首先,定义i号人的影响力为ai,承受力为bi.假定之前所有人都已用最优策略确定了顺序,考虑最后两个人i和j的顺序.若为i、j,那么i所受伤害为sum-bi,j所受伤害为sum+ai-bj;若为j、i,那么j所受伤害为sum-bj,i所受伤害为sum+aj-bi. 其中,sum为之前所有人的影响力之和.

比较max(sum-bi,sum+ai-bj)和max (sum-bj, sum+aj-bi)的大小.明显,sum-bi<sum+aj-bi,sum-bj<sum+ai-bj.所以,只需要比较sum+ai-bj和sum+aj-bi的大小.假定sum+ai-bj<sum+aj-bi,那么,我们可以得到ai+bi<aj+bj.

*/

从上面的分析可以看出,如果i比j放在前面更优,就一定有ai+bi<aj+bj.那么,只需要按照a+b为关键字升序排序,即可得到最优排列,计算出最大的伤害值,即为答案.

除了标题Queue挺迷惑的说,其他没什么了.

D:Josephus (新约瑟夫游戏)

题目的描述真的很奇怪：“假设n个人站成一圈,从第1人开始交替的去掉游戏者”最初并没有看懂.

最初想到的就是模拟,因为原来就做过一个模拟的“约瑟夫游戏”,while套for即可.但是手动模拟一番之后还是很懵.

由于题目是直接输入一个人数,直接输出结果,于是考虑递推.分析如下：

每个人都会得到1元,只有最后的幸存者多得1元.即求最后幸存者数.假设经过m次出圈操作后剩final(m)个人,所以问题的解转化为求final(m)+n.分析得当进行第i次的final(i)=i时,人数不再减少,此时的i即为m.否则对剩下的final(i)个人进行出圈操作.

设jose(i)表示i个人的圈报数后的幸存者编号;设报数为k的人出圈;那么jose(i-1)可理解为第一轮第一次报数k出去之后的状态.

手动模拟后发现规律,整理规律后得到地推公式:jose(i)=(jose(i-1)+1)%i+1,边界条件为jose(1)=1.

顺推每个jose(i).当遇到jose(i)=i,将i赋给final(i).否则将final(jose(i))赋给final(i).

如果是模拟的话,也是用队列模拟求final(m)即可.

E:Happy (开心的金明)

01背包的板题,很显然.

每个物品的价值为价格*重要度.

F:Lift (奇怪的电梯)

一道入门搜索题,宽搜或深搜都可以轻松过.

但因为电梯移动的特点,可以直接循环求解.每次遍历找到已经找到的点,将改点能到达而且未被标记过的点的最小次数记为当前点次数+1即可.易证一个点第一次被标记时的次数为最小次数.终点被标记到时即为答案.如果未到达终点,且当前所有已标记的点无法再到达任何未标记点,则无法到达.这样通过n<=200的数据完全没问题.

一道题没有绝对正解,换个角度也许会有新发现(哪怕这道题很简单).

G:Group (团伙)

一读到题就知道时并查集板题咯,可是当时学的太水直接跳过了.相当于现在拿出来认真复习一下.

很简单的思路:

如果a和b是朋友关系,基本并查集操作;

如果a和b是敌对关系,合并a+n和b,合并b+n和a;(反集)

对于a的两个(多个一样)敌人b,c,使用上述步骤操作后b与c自然合并在一起了.如此,符合敌人的敌人是朋友的规则.

初始化每人的祖先为自己,最后遍历一遍求祖先数量即可.

int ans,n,m;
int a,b,f[2500];

int find(int x){//并查集普通操作
    if(f[x]!=x)f[x]=find(f[x]);
    return f[x];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=2*n;i++)//重要初始化
        f[i]=i;
    for(int i=1;i<=m;i++){
        char ch;
        cin>>ch;
        scanf("%d%d",&a,&b);
        if(ch=='F')
            f[find(a)]=find(b);
        else//反集添加
            f[find(a+n)]=find(b),
            f[find(b+n)]=find(a);
    }
    for(int i=1;i<=n;i++)//统计祖先数
        if(f[i]==i)ans++;
    printf("%d",ans);
}

H:Fight (遭遇战)

经典的模拟题,注意特判即可.

使用两个棋盘数组分别记录两个人路径.注意转弯和停下来的处理即可.