当前位置: 首页 > news >正文

博弈论dp复习笔记

Stones

题目概述

集合 \(A\),小 \(X\) 和小 \(Y\) 选择其中一个数 \(x\),然后将石堆拿走 \(x\) 个,谁不能操作谁输,一开始石堆石头数量为 \(k\).

数据范围:\(1\leq k\leq 10^5,1\leq n\leq 100,1\leq a_i\leq 10^9\)

分析

\(f_i\) 表示到 \(i\) 时若再进行一次操作那他是必胜还是必败。

设后继集合 \(S_i\),有:

\[f_i=[\sum_{x\in S_i}[f_x]]\geq 1 \]

然后没了。

代码

时间复杂度 \(\mathcal{O}(nk)\),代码如下:

#include <iostream>
#include <stdlib.h>
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <cstring>
#define int long long
#define N 105
#define K 100005
using namespace std;
int sg[K],n,k,a[N];
signed main(){cin >> n >> k;int mn = 1e18;for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]),mn = min(mn,a[i]);stable_sort(a + 1,a + 1 + n);for (int i = 0;i < mn;i ++) sg[i] = 0;for (int i = mn;i <= k;i ++) {sg[i] = 0;for (int j = 1;j <= n && a[j] <= i;j ++)sg[i] |= sg[i - a[j]] == 0;}if (sg[k]) puts("First");else puts("Second");return 0;
}
http://www.hskmm.com/?act=detail&tid=26292

相关文章:

  • 10.7阅读笔记
  • 如果你的微信支付界面出现“摇一摇”,说明你的隐私正在泄露
  • 多线程和网络总结
  • 8.RV1126-OPENCV 视频中添加LOGO - 指南
  • 学习记录:响应式系统、文件通知与游戏输入机制的异同
  • oppoR9m刷Linux系统: 制作 scatter.txt 和 导出手机preloader
  • 详细介绍:ASR技术(自动语音识别)深度解析
  • 1.1 采样问题 Sampling and Bandits
  • 10.7 NOIP 模拟赛 T2. 中心极限定理
  • 【题解】10.6 国庆中秋 提高组 热身赛
  • UCB-CS70_离散数学_个人笔记:至少和至多 - Zeeh
  • 几个重要的偏微分方程
  • 虚拟机器人学习自然语言指令技术解析
  • 题解:换乘旅行
  • 2025企业级AI数据防泄漏指南:精准选型与核心指标全景透视
  • 感觉你是那种
  • 鲜花:不会说明你有抑郁症1
  • 【比赛记录】2025CSP-S模拟赛59
  • 使用 C 语言实现英文数字验证码识别系统
  • APlayer的配置方法和相关资料整理(已完成)
  • 详细介绍:目标检测任务的评估指标mAP50和mAP50-95
  • 一些有一定趣味性的杂题
  • 用 Haskell 实现英文数字验证码识别
  • 深入解析:Day43 Python打卡训练营
  • 用 Perl 实现验证码图像识别
  • 实用指南:【结构型模式】代理模式
  • cnblog Test
  • 云数据仓库十年架构演进与技术突破
  • 20251007 模拟测 总结
  • 2025国庆Day6