2023年4月

单例模式(Singleton Pattern):采取一定的方法保证在整个的软件系统中,对某个类只能存在一个对象实例,并且该类只提供一个取得其对象实例的方法。

通俗点来讲:就是一个男人只能有一个老婆,一个女人只能有一个老公

单例模式一共有8种方式实现,下面一一举例:

1、饿汉式(静态常量属性)

实现步骤

  1. 构造器私有化
  2. 在类的内部定义
    静态常量对象
  3. 向外暴露一个
    静态的公共方法getInstance,返回一个类的对象实例

参考代码

/**
 * Husband,一个女人只能有一个老公husband -> Husband实现单例模式
 * 方式1:饿汉式(静态常量属性)实现单例模式
 */
public class Husband {
    // 第二步:创建私有的静态常量对象
    private static final Husband husband = new Husband();

    // 第一步:构造器私有化
    private Husband() {
    }

    // 第三步:向外提供一个静态的公共方法,以获取该类的对象
    public static Husband getInstance() {
        // 返回的永远是 同一个 husband对象
        return husband;
    }
}

细节说明

  1. 为什么构造器要私有化? -> 使外部无法创建Husband对象,只能使用已经准备好的对象 -> 不能滥情
  2. 为什么属性设置成final? -> 只创建这一个对象husband,以后不会再变 -> 一生只钟情一人
  3. 为什么设置成类变量static? -> 构造器已被私有化,外部无法创建Husband对象,需要类内部提前准备好对象 -> 在类加载时将对象准备好
  4. 为什么公共方法要用static? -> 非static方法属于对象,需要通过对象.方法名()调用 -> 外部类无法创建对象,在没有对象时,外部类无法访问非static方法
  5. 为什么叫饿汉式? -> 只要加载了类信息,对象就已经创建好 -> 只要饿了,就吃东西

优缺点

  • 优点:实现了在整个软件过程中创建一次类的对象,不存在线程安全问题(反射会破坏单例模式安全性),调用效率高
  • 缺点:如果只加载了类,并不需要用到该类对象,对象也已经创建好 -> 存在内存资源浪费问题。

2、饿汉式(静态代码块)

实现步骤

  1. 构造器私有化
  2. 定义静态常量不初始化
  3. 静态代码块中为类属性初始化创建对象
  4. 向外提供一个静态的公共方法,以获取该类的对象

参考代码

/**
 * Husband,一个女人只能有一个老公 -> Husband实现单例模式
 * 方式2:饿汉式(静态代码块)实现单例模式
 */
public class Husband {
    // 第二步:创建私有的静态常量对象
    private static final Husband husband;

    static {
        husband = new Husband();
    }

    // 第一步:构造器私有化 -> 外部无法创建该类对象,只能使用已经准备好的对象
    private Husband() {
    }

    // 第三步:向外提供一个静态的公共方法,以获取该类的对象
    public static Husband getInstance() {
        // 返回的永远是 同一个 husband对象
        return husband;
    }
}

细节说明
:原理和第一种饿汉式相同,都是利用类加载时完成对象属性的创建

优缺点同上一种饿汉式

3、懒汉式(线程不安全)

实现步骤

  1. 构造器私有化
  2. 定义一个私有静态属性对象
  3. 提供一个公共的static方法,可以返回一个类的对象

参考代码

/**
 * 一个男人只能有一个老婆wife -> Wife类实现单例模式
 * 方式3:懒汉式单例模式(线程不安全)
 */
public class Wife {
    // 第二步:设置私有静态属性
    private static Wife wife = null;

    // 第一步:构造器私有化
    private Wife() {
    }

    // 第三步:向外提供获取对象的静态方法
    public static Wife getInstance() {
        if (wife == null) { // 如果没有老婆,则分配一个老婆
            wife = new Wife();
        }
        return wife;
    }
}

细节说明

  1. 为什么叫懒汉式? -> 即使加载了类信息,不调用getInstance()方法也不会创建对象 -> 饿了(加载类信息)也不吃东西(不创建对象),懒到一定程度。
  2. 为什么要if判断? -> 防止每次调用时都会重新创建新的对象 -> 防止滥情

优缺点

  • 优点:只有需要对象时才会调用方法返回该类对象,没有则创建对象,避免了资源浪费 -> 实现了延时加载

  • 缺点:
    线程不安全
    ,分析if代码块:

    if (wife == null) {
        // 当线程1进入if代码块后,还没有完成对象的创建之前,线程2紧随其后也进入了if代码块内
        // 此时就会出现线程1创建了对象,线程2也创建了对象 -> 破坏了单例模式 -> 线程不安全
        wife = new Wife();
        // 通俗的来讲:多个女生看上了同一个男生,问男生有没有老婆?男生回答没有老婆 -> 多个女生先后都当过男生的老婆 -> 前妻太多 -> 违背了单例模式的"一生只钟情一人"的核心思想
    }
    

4、懒汉式(同步代码块)

参考代码

/**
 * 一个男人只能有一个老婆wife -> Wife类实现单例模式
 * 方式4:懒汉式单例模式(同步代码块,线程安全,性能差)
 */
public class Wife {
    // 第二步:设置私有静态属性
    private static Wife wife = null;

    // 第一步:构造器私有化
    private Wife() {
    }

    // 第三步:向外提供获取对象的静态方法
    public static Wife getInstance() {
        synchronized(Wife.class) { // 同步代码块,每个线程进入if判断前都需要获得互斥锁,保证同一时间只有一个线程进入
            if (wife == null) {
                wife = new Wife();
            }
        }
        return wife;
    }
}

说明:给if语句加上synchronized关键字,保证每一次只有一个线程获得互斥锁进入同步代码块,并且将同步代码块全部执行完之后释放锁,切换其他线程执行,类似于数据库中事务的概念(给SQL语句增加原子性),这里是给if语句增加原子性,要么全部执行,要么都不执行。

优缺点

  • 优点:线程安全(反射会破坏安全性)

  • 缺点:性能差 -> 只有第一次创建对象时需要同步代码,确保同一时间只有一个线程进入if语句,后面线程再调用该方法时,对象已经创建好只需要直接返回 -> 每一次线程调用该方法后,都需要等待获取其他线程释放的互斥锁 -> 浪费了大量时间在 等待获取互斥锁 上 -> 效率低下

    通俗的来讲:多个女生问同一个男生有没有老婆? -> 男生回答:需要成为对象才有资格知道(设置同步代码块,线程需要获取互斥锁才能执行代码) -> 每一个女生都需要经过一段长时间的发展,处成对象(线程获取互斥锁) -> 男生告诉自己的对象自己没有老婆(一个线程进入if判断) -> 男生有了老婆(创建对象) -> 返回对象

5、懒汉式(同步方法)

参考代码

/**
 * 一个男人只能有一个老婆wife -> Wife类实现单例模式
 * 方式5:懒汉式单例模式(同步方法,线程安全,性能差)
 */
public class Wife {
    // 第二步:设置私有静态属性
    private static Wife wife = null;

    // 第一步:构造器私有化
    private Wife() {
    }

    // 第三步:向外提供获取对象的静态方法
    public synchronized static Wife getInstance() { // 同步方法,原理和同步代码块实现懒汉式相同
        if (wife == null) {
            wife = new Wife();
        }
        return wife;
    }
}

优缺点
:和同步代码块实现懒汉式类似,这里不过多赘述。

6、懒汉式(DCL模式⭐)

DCL模式实现懒汉式单例模式,即双重检查机制(DCL, Double Check Lock),线程安全,性能高
<- 面试重点

参考代码

/**
 * 一个男人只能有一个老婆wife -> Wife类实现单例模式
 * 方式6:懒汉式单例模式(DCL模式 -> 双重检查,线程安全,性能高)
 */
public class Wife {
    // 第二步:设置私有静态属性
    // volatile关键字:极大程度上避免JVM底层出现指令重排情况,极端情况除外
    private static volatile Wife wife = null;

    // 第一步:构造器私有化
    private Wife() {
    }

    // 第三步:向外提供获取对象的静态方法
    public static Wife getInstance() {
        // 第一层if判断作用:当对象已经创建好时,直接跳过if语句,返回已经创建好的对象,不在等待获取互斥锁 -> 节省时间,提高性能
        if (wife == null) {
            // 注意:这里容易有多个线程同时进入第一层if的代码块中,等待获取对象锁
            synchronized (Wife.class) { // 同步代码块,保证每个线程进入if判断前都需要获得互斥锁
                // 第二层if判断作用:当有多个线程都进入了第一层if语句内,会出现线程1进入时对象为空,则创建对象,释放互斥锁,线程2获得互斥锁后如果没有第二层if判断,则直接创建对象,破坏了单例模式 -> 第二层if保证线程安全
                if (wife == null) {
                    wife = new Wife();
                    // 在JVM底层创建对象时,大致分为3条指令
                    // 1.分配内存空间 -> 2.构造器初始化 -> 3.对象引用指向内存空间
                    // JVM为了执行效率,会打乱指令顺序(指令重排),有可能是1 -> 3 -> 2
                    // 当执行到3时,对象还没有创建完成,但是其他线程在第一层if判断已经创建好对象直接返回,显然不合理(对象属性还没有初始化完成) -> 保证指令执行顺序不被打乱(保证单条语句编译后的原子性) -> 使用volatile变量,禁止JVM优化重排指令
                }
            }
        }
        return wife;
    }
}

DCL模式的两层if判断的作用:

  • 第一层if:已经创建好对象时直接返回,不再排队获取互斥锁,提升效率
  • 第二层if:保证线程安全

通俗的来讲:

  1. 有多个女生问同一个男生有没有老婆?

  2. -> 男生口头回答说
    没有老婆
    (进入第一层if判断,如果有老婆则直接远离:不要去碰一个已婚的男人,他是一个女人的余生,不是你的男人不要情意绵绵) -> 其中一个女生和男生处成对象(一个线程获取到互斥锁) -> 经过发展后,女生和男生登记结婚,民政局办理结婚证时检查男生婚姻情况(第二层if判断) --未婚--> 成为夫妻,男生获得老婆

  3. 获得老婆信息

优缺点

  • 优点:性能高,线程安全,延时加载
  • 缺点:由于JVM底层模型,volatile不能完全避免指令重排的情况,会偶尔出现问题,反射、序列化会破坏双检索单例。

7、懒汉式(静态内部类)

参考代码

/**
 * 一个男人只能有一个老婆wife -> Wife类实现单例模式
 * 方式7:懒汉式单例模式(静态内部类,线程安全,性能高)
 */
public class Husband {
    private Husband() {}

    private static class Wife {
        private static Husband husband = new Husband();
    }

    public static Husband getInstance() {
        return Wife.husband;
    }
}

细节说明

  1. 静态内部类实现的单例模式同样是懒汉式 -> 外部类加载时并没有创建好对象,只有调用特定方法时才会加载静态内部类信息(内部类的静态对象属性创建完毕)
  2. 静态内部类的方式实现的单例模式:线程安全(只有在第一次加载内部类信息时才会创建对象),效率高(不需要获取互斥锁)

优缺点

  • 优点:线程安全,效率高,实现了延迟加载
  • 缺点:只适合简单的对象实例,需要创建的对象实例有复杂操作时(如要对 对象实例 进行其他赋值操作),代码会更复杂。反射会破坏单例模式。

8、饿汉式(枚举)

参考代码

enum Husband {
    HUSBAND;
}

说明:除了第8种枚举类实现单例模式,其他七种模式都会被反射、序列化破坏单例模式(因为反射可以获得类的私有属性的构造器),只有枚举类实现的单例不会被反射破坏,反射无法获取到枚举类的构造方法。

优缺点

  • 优点:线程安全,调用效率高,不会被反射、序列化破坏枚举单例
  • 缺点:不能延时加载

前言

整个框架的开发及调通是在3月27日晚上22点完成,如下:

image.png

这篇文章真的是拖了太久了,久到我居然把代码部分完成后,彻底给忘了,这记性,真的是年纪大了!

框架的设计开发

1、框架搭建设计要素

  • 日志&测试步骤
  • 报告&失败截图
  • 配置文件&数据源设计
  • 公共函数&API封装
  • 测试数据&参数化、解耦
  • 测试套件&测试用例设计、组装

2、工程结构

image.png

3、日志

日志可以很好辅助我们定位问题,示例代码如下:

class LogUtils:

    def __init__(self, log_path=log_path):
        """
        通过python自带的logging模块进行封装
        """
        self.logfile_path = log_path
        # 创建日志对象logger
        self.logger = logging.getLogger(__name__)
        # 设置日志级别
        self.logger.setLevel(level=logging.INFO)
        # 设置日志的格式
        formatter = logging.Formatter('%(asctime)s - %(filename)s [line:%(lineno)d] - %(levelname)s: %(message)s')
        """在log文件中输出日志"""
        # 日志文件名称显示一天的日志
        self.log_name_path = os.path.join(self.logfile_path, "log_%s" % time.strftime('%Y_%m_%d')+".log")
        # 创建文件处理程序并实现追加
        self.file_log = logging.FileHandler(self.log_name_path, 'a', encoding='utf-8')
        # 设置日志文件里的格式
        self.file_log.setFormatter(formatter)
        # 设置日志文件里的级别
        self.file_log.setLevel(logging.INFO)
        # 把日志信息输出到文件中
        self.logger.addHandler(self.file_log)
        # 关闭文件
        self.file_log.close()

        """在控制台输出日志"""
        # 日志在控制台
        self.console = logging.StreamHandler()
        # 设置日志级别
        self.console.setLevel(logging.INFO)
        # 设置日志格式
        self.console.setFormatter(formatter)
        # 把日志信息输出到控制台
        self.logger.addHandler(self.console)
        # 关闭控制台日志
        self.console.close()

    def get_log(self):
        return self.logger

4、数据源

这里我用的是
Excel
,示例如下:

image.png

示例代码如下:

class ExcelUtils(object):
    @staticmethod
    def get_element_Data():
        """
        通过pandas读取excel中的数据,返回字典映射
        """
        data_list = pd.read_excel(excel_path).values.tolist()  # reading file
        dict_elements = {}
        for data in data_list:
            dict_elements[data[0]] = data[1] + "," + data[2]
        return dict_elements

可能评论区会有人说用
yml、json、csv
做数据源会更好,我不认同!

为什么用
Excel
做数据源?

  • 所有的测试框架和测试工具,都应该以使用者角度考虑问题,以易用性和上手难度为先。
  • 所有做测试工具及平台、测试框架,都是为他人服务,所以越简单,越好操作,更好,后期可以再优化、
  • 上面做数据源,可能自我感觉技术上显得高大上,很牛逼,但是抱歉,使用者,根本不知道
    yml、json
    是啥你怎么办,可以学,没错(互联网时代时间成本太昂贵了),不是不可能遇到,是因为最不可控的是使用者人群,不是吗?

框架的一开始设计很重要,所以整体的设计要清晰明了。

感动自己的实现不重要,而是被团队需要的实现,才会显得自己重要!

5、基础层

这里主要用于处理,元素对象和原生API的封装,部分代码示例如下图:

image.png

image.png

6、测试用例


action
层写测试用例,示例代码如下:

class PageAction(BasePage):

    def order(self, taste: str):
        """
        根据口味选餐
        :param taste:
        :return:
        """
        # 将第一个五花肉石锅拌饭加入购物车
        self.element_click("将第一个五花肉石锅拌饭加入购物车")
        # 选择口味
        self.element_click(taste)
        # 确定选择
        self.element_click("确定选择")
        # 共选择份数
        total = self.get_elementText("共选择份数")
        return total

调用
action
层,执行测试用例,示例代码如下:

# -*- coding: utf-8 -*-
"""
# @Time    : 2023/03/20 20:55
# @Author  : longrong.lang
# @FileName: order_test.py
# @Software: PyCharm
# @Blog    :https://www.cnblogs.com/longronglang/
# @Motto:ABC(Always Be Coding)
"""
import minium

from action.page_action import PageAction


@minium.ddt_class
class OrderTest(minium.MiniTest):
    """
    测试登录功能
    """
    pageAction = None

    @minium.ddt_case(
        {"taste": "蒜香味", "count": " 1 "},
        {"taste": "姜葱味", "count": " 1 "},
        {"taste": "盐焗味", "count": "3"}
    )
    def test_Order(self, value):
        try:
            self.pageAction = PageAction(self.mini, self.page)
            total = self.pageAction.order(value["taste"])
            self.assertEqual(total, value["count"])
        except AssertionError as err:
            self.pageAction.screen_shot()
            self.fail(err)



7、测试报告

觉得
minium
的测试报告颜值还可以,还可以看到历史的,感觉还不错,如下:

image.png

失败有截图还有日志:

image.png

image.png

B站看运行效果:
https://www.bilibili.com/video/BV1Dk4y147Sn

写在最后

到此,关于
minium
系列暂时告一段路了,感谢大家对我的支持,觉得我的文章对您有帮助,请帮忙转发!

我是六哥,后面还会陆续更新其他教程文章,还请继续关注我!

Nim or not Nim

类似于 NIM 游戏,有
\(n\)
堆石子,不过每个回合玩家可以从某个堆中删除任意数量的对象,也可以将堆分成两个较小的石堆,拿走最后一个石子的人获胜。

还是一个裸的求 sg 函数的题,但由于范围过大,肯定不能每次来求sg函数值。
于是需要打表。
发现当
\(x % 4 == 0\)
时,sg(x) = x - 1,当
\(x % 4 == 3\)
时,sg(x) = x + 1,其余情况下,sg(x) = x。
于是就做完了。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
int getsg(int x){
    if(x % 4 == 0)return x - 1;
    else if(x % 4 == 3)return x + 1;
    return x;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int a,n,ans = 0;
        scanf("%d",&n);
        for(int i = 0; i < n; i++){
            scanf("%d",&a);
            ans = ans ^ getsg(a);
        }
        if(ans == 0)printf("Bob\n");
        else printf("Alice\n");
    }
    return 0;
}

[AGC017D] Game on Tree

有一棵
\(N\)
个节点的树,节点标号为
\(1,2,⋯,N\)
,边用
\((x_i,y_i)\)
表示。 Alice 和 Bob 在这棵树上玩一个游戏,Alice先手,两人轮流操作:
选择一条树上存在的边,把它断开使树变成两个连通块。然后把不包含
\(1\)
号点的联通块删除
当一个玩家不能操作时输,你需要算出:假如两人都按最优策略操作,谁将获胜。

样例1:

 5
 1 2
 2 3
 2 4
 4 5

如图:
image
首先注意每棵树默认根节点为
\(1\)
,就不需要傻傻地统计点的度数来找根了。。。。

这个题也算是
\(NIM\)
游戏的翻版,区别就是将模型转换到图上了。

对于一个存在分岔的节点,可以类比
\(NIM\)
游戏中通过异或将多组游戏合并为一个等价的游戏的结果。如图中的节点
\(2\)
,分别断开
\(2-3\)

\(2-4\)
两条边,就相当于拆成了两个子游戏,将两个游戏的结果异或起来就行了。

类似上述思路,递归处理整个图即可。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int n;
vector<int> g[MAXN + 5];
int getsg(int u,int fa){
    int ans = 0;
    for(int i = 0; i < g[u].size(); i++){
        int v = g[u][i];
        if(v == fa)continue;
        int get = getsg(v,u);
        ans ^= (get + 1);//加上删去的边
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i = 1; i < n; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 0;
    ans ^= (getsg(1,1));
    if(ans)cout << "Alice";
    else cout << "Bob";
}

P2964 [USACO09NOV]A Coin Game S

小 A 和小 B 在玩游戏。
初始时,有
\(n\)
个硬币被摆成了一行,从左至右第
\(i\)
个硬币的价值为
\(c_i\)

游戏的规则是,两人交替从这堆硬币的
左侧
连续取出若干硬币,然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了
\(k\)
个硬币,那么本次自己最多取出
\(k \times 2\)
个硬币。当没有硬币可取时,游戏结束。
游戏开始时,由小 A 先动手取硬币,最多取出
\(2\)
个硬币。
请求出当双方都尽可能使自己的累计价值最大的情况下,小 A 能获得的累计价值最大是多少。

一道博弈
\(dp\)
的题,刚接触这类题好像总是不太好下手。因为不明白该怎么转移才能保证“双方都采用最优策略”。
现在看来,陷入这种思维陷阱的原因就是总是站在
你所要求得答案的玩家
的角度进行思考,又因为两个玩家的操作是交错的,如此就造成了局限性,使你在转移的时候无法顾及另一方也满足他的
最优策略

解决方法就是不要只站在一个人的角度思考整盘游戏,应站在
当前进行操作的人
的位置思考整个游戏。后文还会详细解释这个思路。
同时,博弈
\(dp\)
类的题目常常会采用
逆向
\(dp\)

的思维方式,这个题就是一个例子。

思考题目,感觉
\(dp\)
过程中描述状态的重要的两个因子就是:

  • 当前最多能拿的硬币数量。
  • 剩余的硬币序列的最前面一个硬币的下标是从哪里开始的。
    定义状态为
    \(dp[i][j]\)
    表示当
    \(i\)
    以前所有硬币都拿完时,此时最多能拿多少个硬币所能获得的最大价值。

这个思维就是上文所提到的站在
游戏双方的角度
进行思考。如果不是这样,那么
\(dp\)
维度中就会引入
当前游戏决策者
这一维,十分不利于构建转移方程,也就使得我们陷入了上文提到的思维陷阱。

然而现在似乎出现了个问题,假设我们从前往后进行
\(dp\)
,过程中每个人每一步所拿的硬币数量对于正在进行
\(dp\)
的我们是未知的,小 A 就不一定是拿走最后那个硬币的人,那么又怎么才能确定小 A 所获得的最大价值对应哪个
\(dp\)
状态呢?
故这里就要采用
逆向
\(dp\)

。我们不思考每个人从前往后拿硬币所能得到的最大价值,转而思考每个人从后往前放置等价值硬币所最多能放置的最大价值。这需要稍微修改一下
\(dp\)
状态。首先将原硬币序列逆向,定义
\(dp[i][j]\)
表示前
\(i\)
个硬币被放置,下一步操作最多能放置
\(j\)
个,即这次操作最多能放置
\(2 * j\)
个硬币时所能取得的最大价值。由于已经将硬币序列反向了,就可以直接正着
\(dp\)
过去了,这也符合刚才的思路。如此就能保证最后的答案就在
\(dp[n][2]\)
这个状态中。

下面思考怎么转移状态。
首先记录一个硬币序列的前缀和
\(sum[i]\)
。可以确定的是,每次放置硬币的最大数量不超过
\(n\)
。当前最多放置
\(2 * j\)
个硬币。
因此可以直接枚举一个范围在
\(1~2 * j\)

\(k\)
。又因为我们将硬币序列反向后
\(dp\)
,就相当于也把操作序列反向了。于是存在:

\[dp[i][j] = \max(dp[i][j],sum[i] - dp[i - k][k])
\]

又引入了一个
\(k\)
,就相当于有三维了,时间复杂度为
\(O(n^3)\)
。怎么优化呢。
首先
\(i\)
\(j\)
这两维肯定是要枚举的,考虑优化
\(k\)
这一维。

\(dp[i][j−1]\)
是枚举
\(k\)
从等于
\(1\)
到等于
\(2×(j−1)\)
,在
\(2×(j−1)\)

\(sum[i]−dp[i−k][k]\)
中取一个
\(max\)
值。
\(dp[i][j]\)
是枚举
\(k\)
从等于
\(1\)
到等于
\(2×j\)
,在
\(2×j\)

\(sum[i]−dp[i−k][k]\)
中取一个
\(max\)
值。
所以可知
\(dp[i][j]\)
是严格包含
\(dp[i][j−1]\)
的,我们只需要在
\(dp[i][j−1]\)
的基础上继续枚举
\(k=2×j−1\)

\(k=2×j\)
这两种状态即可。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3;
int n,a[MAXN + 5],sum[MAXN + 5],dp[MAXN + 5][MAXN + 5];
int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
    }
    for(int i = n; i >= 1; i--){
        sum[n - i + 1] = sum[n - i] + a[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int k = 2 * j - 1;
            dp[i][j] = dp[i][j - 1];
            if(k <= i)dp[i][j] = max(dp[i][j],sum[i] - dp[i - k][k]);
            if(k + 1 <= i)dp[i][j] = max(dp[i][j],sum[i] - dp[i - k - 1][k + 1]);
        }
    }
    cout << dp[n][1];
}

Varacious Steve

Steve 和他的一个朋友在玩游戏,游戏开始前,盒子里有
\(n\)
个甜甜圈,两个人轮流从盒子里抓甜甜圈,每次至少抓
\(1\)
个,最多抓
\(m\)
个。
最后一次将当盒子的甜甜圈抓完的人是这一轮游戏胜利者,他可以将所有抓到的甜甜圈吃完,另外一个人是这轮的失败者,他抓到的所有甜甜圈要重新放到盒子里。
下一轮游戏由上一轮的失败者开始抓,游戏继续。直到若干轮后,所有的甜甜圈被吃完,游戏结束。
游戏的目标是吃到尽量多的甜甜圈。游戏最开始,由Steve先抓,两个人均采用最优策略,请问Steve最多可以吃到多少甜甜圈。

也是一道博弈
\(dp\)
呢,只不过用了记搜便于转移罢了。
分析怎样描述
\(dp\)
状态,有如下因子:

  • 当前回合一共有多少个甜甜圈供游戏。
  • 该回合决策者已经拿了多少个甜甜圈。
  • 上一回合的决策者已经拿了多少个甜甜圈。
    于是构建三维
    \(dp[i][j][k]\)
    ,每一维描述从上到下的三个因子之一。(虽然代码中没这么写)同样的,这也是站在每个操作者的角度进行
    \(dp\)

    具体细节见代码注释。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2;
int s[MAXN + 5][MAXN + 5][MAXN + 5],n,m,T;//s就是dp数组
int get(int tot,int l,int r){//分别对应三维状态,l为当前决策者拿了多少个甜甜圈
    if(tot == 0)return 0;
    if(s[tot][l][r])return s[tot][l][r];
    int ans = 0;
    for(int i = 1; i <= min(m,tot - l - r); i++){
        if(tot - l - r - i == 0)ans = max(ans,tot - get(r,0,0));//如果拿完了,就新开一把游戏
        else ans = max(ans,tot - get(tot,r,l + i));//没拿完的话就继续
    }
    return s[tot][l][r] = ans;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(s,0,sizeof s);
        int ans; 
        ans = get(n,0,0);
        cout << ans << "\n";
    }
}

Play Game

Alice 和 Bob 正在玩游戏。有两堆卡片。每堆牌有
\(N\)
张牌,每张牌都有一个分数。他们轮流从两堆中捡起最上面或最下面的牌,这张牌的分数将添加到他的总分中。Alice 和 Bob 都足够聪明,他们会捡起牌来获得尽可能多的分数。你知道 Alice 如果先拿起来能得到多少分数吗?
分析
\(dp\)
状态组成因子:

  • 牌堆1被拿走若干张牌后当前的左端点
    \(l1\)
    和右端点
    \(r1\)
  • 牌堆2被拿走若干张牌后当前的左端点
    \(l2\)
    和右端点
    \(r2\)
    四维的状态,仍采用记忆化搜索。对每一堆牌记录一个前缀和
    \(sum\)
    ,便于转移时快速查找区间和
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 20;
int sum1[MAXN + 5],sum2[MAXN + 5],dp[MAXN + 5][MAXN + 5][MAXN + 5][MAXN + 5],n,a[MAXN + 5],b[MAXN + 5],T;
int dfs(int l1,int r1,int l2,int r2){
    bool emp1 = l1 > r1,emp2 = l2 > r2;
    if(emp1 && emp2)return 0;
    if(dp[l1][r1][l2][r2] != -1)return dp[l1][r1][l2][r2];
    int ans = 0;
    if(!emp1){//假如牌堆1没被拿空
        ans = max(ans,sum1[r1] - sum1[l1 - 1] + sum2[r2] - sum2[l2 - 1] - dfs(l1 + 1,r1,l2,r2));//假如拿牌堆1最下面的一张
        ans = max(ans,sum1[r1] - sum1[l1 - 1] + sum2[r2] - sum2[l2 - 1] - dfs(l1,r1 - 1,l2,r2));//假如拿牌堆1最上面的一张
    }
    if(!emp2){//假如牌堆2没被拿空
        ans = max(ans,sum1[r1] - sum1[l1 - 1] + sum2[r2] - sum2[l2 - 1] - dfs(l1,r1,l2 + 1,r2));//假如拿牌堆2最下面的一张
        ans = max(ans,sum1[r1] - sum1[l1 - 1] + sum2[r2] - sum2[l2 - 1] - dfs(l1,r1,l2,r2 - 1));//假如拿牌堆2最上面的一张
    }
    return dp[l1][r1][l2][r2] = ans;
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(dp,-1,sizeof dp);
        scanf("%d",&n);
        for(int i = 1; i <= n; i++){
            scanf("%d",&a[i]);
            sum1[i] = sum1[i - 1] + a[i];
        }
        for(int i = 1; i <= n; i++){
            scanf("%d",&b[i]);
            sum2[i] = sum2[i - 1] + b[i];
        }
        int ans = dfs(1,n,1,n);
        cout << ans << "\n";;
    }
}

Moving Pebbles(QWQ)

给你
\(N\)
堆石头,两个人玩游戏. 每次任选一堆,首先拿掉至少一个石头,然后移动任意个石子到任意堆中。谁不能拿石子了,谁就输了。请求出哪个玩家存在必胜策略。

不妨先思考一下对于先手来说的必败态。在这样的博弈问题中,一般存在一个情形,使得后手能够完全模仿先手的操作,是一个必败态。拿到这个题里面来看,假如当前石堆为
\(n\)
,且石堆可以被分成
\(x\)
对大小相等的石堆对,那么就是一个必败态。
对于其他状态,先手总可以把它们转化为一个必败态,对先手来说这就是一个必胜态。

接下来考虑如何证明必败态和必胜态之间可以相互转化。

假如现在有
\(n\)
堆石子,为一个必败态。对
\(i\)
这堆石子进行操作,它有
\(A_i\)
个石子。显然随便拿石子,就可以打破以前两两相对的状态。

假如现在为一个必胜态,所有石堆按从小到大排序。
如果
\(n\)
为奇数,需进行操作,将
\(A_n\)
的石子全部分配出去,使得
\(A_1=A_2\)
\(A_3=A_4........\)
那么需要操作的石子为
\((A_2-A_1) + (A_4-A_3) + (A_6 - A_5) + ... + (A_{n-1} - A_{n - 2}) <= A_2 - A_1 + A_4 - A_2 + A_6 - A_4 + ... + A_{n-1} - A_{n - 3} = A_{n-1} - A_1 < A_n\)
,所以可以完成操作。
如果
\(n\)
为偶数,类比上式,仍可分配下去。得证。

然后直接看初状态是必胜态还是必败态就行了。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
template<class T>inline void read(T &a){
    char c;while(!isdigit(c=getchar()));
    for(a=c-'0';isdigit(c=getchar());a=a*10+c-'0');
}
int n,m;
map<int,bool> tag;
int main(){
    while(~scanf("%d",&n)){
        tag.clear();
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            read(m);
            if(tag[m])cnt--,tag[m] = 0;
            else ++cnt,tag[m] = 1;
        }
        if(cnt)cout << "first player\n";
        else cout << "second player\n";;
    }
}

P5932 [POI1999]多边形之战

游戏在一个有
\(n\)
个顶点的凸多边形上进行,这个凸多边形的
\(n-3\)
条对角线将多边形分成
\(n-2\)
个三角形,这
\(n-3\)
条对角线在多边形的顶点相交。
三角形中的一个被染成黑色,其余是白色。双方轮流进行游戏,当轮到一方时,他必须沿着画好的对角线,从多边形上切下一个三角形。切下黑色三角形的一方获胜。

  • 注:如果连接一个多边形中任意两点的线段都完全包含于这个多边形,则称这个多边形为凸多边形。

遇到乍看来没有思路的题,画图辅助思考不失为一种不错的方法。

image

如图,不难发现,如果要割出一个三角形,就必须把它三个方向的三角形全部删去。那么可以知道,在这个游戏中的必胜态是黑色三角形只有一边存在三角形。这时只需切一刀就可以割下这个三角形。

假设三角形的三边所对应的三个方向分别有
\(x\)
\(y\)
\(z\)
个三角形,只需使其中两个元素为
\(0\)
即可赢得游戏。

又由题目知双方都会采用最优策略,所以肯定不存在黑色三角形的一边存在大量没有被割掉的三角形。理想状况是黑色三角形只有一边存在一个三角形。

所以先手是否有必胜策略就和
\(x + y + z\)
的奇偶性有关了。若和模
\(2\)

\(1\)
,则先手按最优策略走,就可以实现上文所提到的理想状况,一刀切下!此时就有必胜策略。若模
\(2\)

\(0\)
,则后手存在必胜策略。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
int n,cnt;
bool vis[MAXN + 5];
map<pair<int,int>,int> m;
vector<int> edge[MAXN + 5];
struct TRI{
    int a,b,c;
}tri[MAXN + 5];
int main(){
    int a,b,c;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    if(a > b)swap(a,b);
	if(a > c)swap(a,c);
	if(b > c)swap(b,c);
	int x = 0,y = 0,z = 0;
	for(int i = 1; i <= n - 3; i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		if(p >= a && p <= b && q >= a && q <= b && r >=a && r <= b)x++;
		else if(p >= b && p <= c && q >= b && q <= c && r >= b && r <= c)y++;
		else z++;
    }
    int k = x + y + z;
    int j = (x == 0) + (y == 0) + (z == 0);
    if(j >= 2)cout << "TAK";
    else if(k & 1)cout << "TAK";
    else cout << "NIE";
}

前言

一、人物简介

  • 第一位闪亮登场,有请今后会一直教我们C语言的老师 —— 自在。

  • 第二位上场的是和我们一起学习的小白程序猿 —— 逍遥。

二、构成和表达方式

  • 位运算符是一组用于在二进制数之间进行操作的运算符
运算符 名称 示例
& 位与 a && b
| 位或 a | b
^ 位异或 a ^ b
~ 位取反 ~a
<< 二进制左移 a << 2
>> 二进制右移 a >> 2

三、位运算符的应用

1、位与运算符 (&)

  • 位与运算符用符号
    &
    表示。

  • 如果两个操作数的对应位都为1,则位与运算的结果为1,否则结果为0

  • 示例代码

#include <stdio.h>

int main() {
  int a = 13; //二进制表示为0b1101
  int b = 11; //二进制表示为0b1011
  int c = a & b;
  printf("%d\n", c); //输出结果为9,二进制表示为0b1001
  return 0;
}

2、位或运算符 (|)

  • 位或运算符用符号
    |
    表示。

  • 如果两个操作数的对应位中至少有一个为1,则位或运算的结果为1,否则结果为0。

  • 示例代码

#include <stdio.h>

int main() {
  int a = 13; //二进制表示为0b1101
  int b = 11; //二进制表示为0b1011
  int c = a | b;
  printf("%d\n", c); //输出结果为15,二进制表示为0b6666661
  return 0;
}

3、位异或运算符 (^)

  • 位异或运算符用符号
    ^
    表示

  • 如果两个操作数的对应位不同,则位异或运算的结果为1,否则结果为0

  • 示例代码

#include <stdio.h>
int main() {
  int a = 13; //二进制表示为0b1101
  int b = 11; //二进制表示为0b1011
  int c = a ^ b;
  printf("%d\n", c); //输出结果为6,二进制表示为0b0110
  return 0;
}

4、位取反运算符 (~)

  • 位取反运算符用符号
    ~
    表示

  • 它会对操作数的每个二进制位取反,即0变成1,1变成0

  • 示例代码

#include <stdio.h>

int main() {
  int a = 13; //二进制表示为0b1101
  int b = ~a;
  printf("%d\n", b); //输出结果为-14,二进制表示为0b66666666666666666666666666666666666666666666666666666610010
  return 0;
}

5、左移运算符 (<<)

  • 左移运算符用符号
    <<
    表示

  • 它将操作数的所有二进制位向左移动指定的位数,并在低位填充0

  • 示例代码

#include <stdio.h>

int main() {
  int a = 13; //二进制表示为0b1101
  int b = a << 2;
  printf("%d\n", b); //输出结果为52,二进制表示为0b110100
  return 0;
}

6、右移运算符 (>>)

  • 右移运算符用符号
    >>
    表示。

  • 它将操作数的所有二进制位向右移动指定的位数,并在高位填充0或1(具体取决于操作数的符号)

  • 示例代码

#include <stdio.h>

int main() {
  int a = 13; //二进制表示为0b1101
  int b = a >> 2;
  printf("%d\n", b); //输出结果为3,二进制表示为0b0011
  return 0;
}

小结

通过本文的讲解,我们学会了6种位运算符的基础用法,在接下来的文章中,将会继续介绍这6种位运算符的高级用法。

Redis 源码解析之通用双向链表(adlist)

概述

Redis源码中广泛使用
adlist(A generic doubly linked list)
,作为一种通用的双向链表,用于简单的数据集合操作。adlist提供了基本的增删改查能力,并支持用户自定义深拷贝、释放和匹配操作来维护数据集合中的泛化数据
value

adlist 的数据结构

  1. 链表节点
    listNode
    , 作为双向链表,
    prev
    ,
    next
    指针分别指向前序和后序节点。
    void*
    指针类型的
    value
    用于存放泛化的数据类型(如果数据类型的
    size
    小于
    sizeof(void*)
    , 则可直接存放在
    value
    中。 否则
    value
    存放指向该泛化类型的指针)。
// in adlist.h
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
  1. 链表迭代器
    listIter
    , 其中
    next
    指针指向下一次访问的链表节点。
    direction
    标识当前迭代器的方向是
    AL_START_HEAD(从头到尾遍历)
    还是
    AL_START_TAIL(从尾到头遍历)
// in adlist.h
typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1
  1. 双向链表结构
    list
    。 其中,
    head

    tail
    指针分别指向链表的首节点和尾节点。
    len
    记录当前链表的长度。函数指针
    dup
    ,
    free

    match
    分别代表业务注册的对泛化类型
    value
    进行深拷贝,释放和匹配操作的函数。(如果没有注册
    dup
    , 则默认进行浅拷贝。 如果没有注册
    free
    , 则不对
    value
    进行释放。如果没有注册
    match
    则直接比较
    value
    的字面值)
// in adlist.h
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

adlist 的基本操作

  1. 创建
    :
    listCreate
    初始化相关字段为零值。可以通过
    listSetDupMethod,
    listSetFreeMethod
    ,
    listSetMatchMethod
    来注册该链表泛化类型
    value

    dup
    ,
    free

    match
    函数。
/* Create a new list. The created list can be freed with
 * listRelease(), but private value of every node need to be freed
 * by the user before to call listRelease(), or by setting a free method using
 * listSetFreeMethod.
 *
 * On error, NULL is returned. Otherwise the pointer to the new list. */
list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

image

  1. 在链表首插入新节点
    :
    listAddNodeHead
  • 在空链表插入新节点: 为
    value
    创建新节点,并让
    list

    head

    tail
    都指向新节点。
    image

  • 在非空链表插入新节点:
    (1) 将新节点的
    next
    指向当前首节点(当前首节点将成为第二节点, 将会是新节点的后继节点)
    (2) 将当前节点的
    prev
    指向新节点, 新节点作为新的首节点将成为原首节点的前驱节点。
    (3) 将
    head
    从原本指向旧的首节点改为指向新节点, 将新节点作为链表首。
    (4) 链表总计数加一
    image

/* Add a new node to the list, to head, containing the specified 'value'
 * pointer as value.
 *
 * On error, NULL is returned and no operation is performed (i.e. the
 * list remains unaltered).
 * On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    listLinkNodeHead(list, node);
    return list;
}

/*
 * Add a node that has already been allocated to the head of list
 */
void listLinkNodeHead(list* list, listNode *node) {
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;
}
  1. 在链表尾插入新节点
    :
    listAddNodeTail
  • 在空链表插入新节点: 逻辑与
    listAddNodeHead
    实现一致。
  • 在非空链表插入新节点:
    (1) 将新节点的
    prev
    指向当前首节点(当前尾节点将成为倒数第二节点, 将会是新节点的前驱节点)
    (2) 将当前节点的
    next
    指向新节点, 新节点作为新的尾节点将成为原尾节点的后继节点。
    (3) 将
    tail
    从原本指向旧的尾节点改为指向新节点, 将新节点作为链表尾。
    (4) 链表总计数加一

image

/* Add a new node to the list, to tail, containing the specified 'value'
 * pointer as value.
 *
 * On error, NULL is returned and no operation is performed (i.e. the
 * list remains unaltered).
 * On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    listLinkNodeTail(list, node);
    return list;
}

/*
 * Add a node that has already been allocated to the tail of list
 */
void listLinkNodeTail(list *list, listNode *node) {
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
}
  1. 在链表指定位置插入
    value

    :
    listInsertNode
    。如果
    after
    为非零, 则将新节点作为
    old_node
    后继节点。否则,新节点作为
    old_node
    前驱节点。下图以
    after
    为非零作为例子, 描述了这部分的代码逻辑。
    (1) 将新节点的
    prev
    指向
    old_node
    (新节点插入在
    old_node
    之后);
    (2) 将新节点的
    next
    指向
    old_node
    的后继节点(
    old_node
    的后继节点将成为新节点的后继节点);
    (3) 将
    old_node

    next
    指向新节点;
    (4) 将新节点的后继节点的
    prev
    指向新节点(
    old_node
    的原后继节点现在成为了新节点的后继节点) 。
    (5) 链表总计数加一

image

list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (after) {
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {
        node->next = old_node;
        node->prev = old_node->prev;
        if (list->head == old_node) {
            list->head = node;
        }
    }
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    if (node->next != NULL) {
        node->next->prev = node;
    }
    list->len++;
    return list;
}
  1. 删除链表指定节点
    :
    listDelNode
    。 下图以删除中间节点为例,展示了删除的流程。
    (1) 待删除节点的前驱节点的
    next
    指向待删除节点的后继节点;
    (2) 待删除节点的后继节点的
    prev
    指向待删除节点的前驱节点;
    (3) 待删除节点的
    next

    prev
    都置为
    NULL
    ;
    (4) 链表总计数减一
    (5) 如果有注册
    free
    函数,则用
    free
    函数释放待删除节点的
    value
    。然后释放待删除节点。

image


/* Remove the specified node from the specified list.
 * The node is freed. If free callback is provided the value is freed as well.
 *
 * This function can't fail. */
void listDelNode(list *list, listNode *node)
{
    listUnlinkNode(list, node);
    if (list->free) list->free(node->value);
    zfree(node);
}

/*
 * Remove the specified node from the list without freeing it.
 */
void listUnlinkNode(list *list, listNode *node) {
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;

    node->next = NULL;
    node->prev = NULL;

    list->len--;
}

5.
链表的 Join 操作
:
listJoin
在链表
l
的末尾添加列表
o
的所有元素。 下图以两个链表都不为
NULL
的场景为例。
(1)
o
的首部节点的
prev
指向
l
的尾部节点;
(2)
l
的尾部节点的
next
指向
o
的首部节点(1,2 步将两个链表链接起来);
(3)
l

tail
指向
o

tail
(
o

tail
作为新链表的尾部);
(4)
l
链表总计数加一;
(5) (6) 清空
o
链表的信息;

image

/* Add all the elements of the list 'o' at the end of the
 * list 'l'. The list 'other' remains empty but otherwise valid. */
void listJoin(list *l, list *o) {
    if (o->len == 0) return;

    o->head->prev = l->tail;

    if (l->tail)
        l->tail->next = o->head;
    else
        l->head = o->head;

    l->tail = o->tail;
    l->len += o->len;

    /* Setup other as an empty list. */
    o->head = o->tail = NULL;
    o->len = 0;
}
  1. 其他函数
    : 其他函数实现较为简单,这里简单罗列一下,感兴趣的可以去看下源码。
// 获取 list 的迭代器
listIter *listGetIterator(list *list, int direction);
// 返回迭代器的下一个元素,并将迭代器移动一位。如果已遍历完成, 则返回 NULL
listNode *listNext(listIter *iter);
// 释放迭代器资源
void listReleaseIterator(listIter *iter);

// 拷贝链表
list *listDup(list *orig);

// 在链表中查找与 key 匹配的 value 所在的第一个节点。
// 如果不存在,则返回 NULL。
// 匹配操作由 list->match 函数提供。
// 如果没有注册 match 函数, 则直接比较 key 是否与 value 相等。
listNode *listSearchKey(list *list, void *key);

// 返回指定的索引的元素。 如果超过了链表范围, 则返回 NULL。
// 正整数表示从首部开始计算。
// 0 表示第一个元素, 1 表示第二个元素, 以此类推。
// 负整数表示从尾部开始计算。
// -1 表示倒数第一个元素, -2 表示倒数第二个元素,以此类推。
listNode *listIndex(list *list, long index);

// 返回链表初始化的正向迭代器
void listRewind(list *list, listIter *li);
// 返回链表初始化的反向迭代器
void listRewindTail(list *list, listIter *li);

// 将链表尾部节点移到首部
void listRotateTailToHead(list *list);
// 将链表首部节点移到尾部
void listRotateHeadToTail(list *list);

// 用 value 初始化节点
void listInitNode(listNode *node, void *value);

adlist 的使用 demo

git@github.com:younglionwell/redis-adlist-example.git

关注公众号了解更多 redis 源码细节和其他技术内容。 你的关注是我最大的动力。

image