首页 > 三子棋
开通博客写题解
头像 yingluosanqian
发表于 2022-12-02 22:19:03
出题人题解 Part I(A-D) A 三子棋 题面简述 给定一个 3×33 \times 33×3 的棋盘，共有 3×3=93 \times 3 = 93×3=9 个格子，初始时每个格子均没有放置棋子。 A 和 B 轮流行动，每次行动的人，必须在当前棋盘上选择一个没有放置棋子的格子，然后在该格子放 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 竹_yin
发表于 2022-12-02 23:08:02
F. 先考虑第 222 到 n−1n-1n−1 个人 容易发现，到第 iii 个人选择时总共就只有 222 个位置选择，且其中一个是 i+1i+1i+1。 且位置 iii 仅能被 第i−1i-1i−1个人占据，且第i−1i-1i−1个人占据第 iii 个位置的概率为 12\frac{1}{2}21​ 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 竹_yin
发表于 2022-12-02 22:33:22
G. 设 dpi,jdp_{i,j}dpi,j​ 为考虑前 iii 个 111 交换到第 jjj 个时前iii个 111 均互不相邻的最小操作数。 枚举 jjj 的同时从 j−2j-2j−2 开始往低位转移即可。 时间复杂度 O(n3)O(n^3)O(n3)。 #include<bits/st 展开全文
去ta的博客 赞 (4) 回复(2) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”