今日热讯：D 宿命之间的对决【2023牛客寒假算法基础集训营3】

2023-01-20 23:10:46 来源：博客园

【资料图】

D宿命之间的对决

原题链接

题意

现在给定一个正整数n，小红和小紫轮流操作，每次取n的一个因子x，使得n减去x。谁先将n减到0谁输。小红先手操作，她想知道在双方足够聪明的情况下，谁会获得最终的胜利？

思路

奇偶相加减，（同偶异奇）

设奇数a为$2k_1 + 1$，奇数b为$2k_2 + 1$，偶数c为$2k_3$，偶数d为$2k_4$.($k\in Z$)奇 $-$ 奇 $=$ 偶$(2k_1 + 1) - (2k_2 + 1) = 2(k_1 - k_2) = 2k_{new}$奇 $-$ 偶 $=$ 奇$(2k_1 + 1) - 2k_3 = 2(k_1 - k_3) + 1 = 2k_{new} + 1 $偶 $-$ 偶 $=$ 偶$2k_3 - 2k_4 = 2(k_3 - k_4) = 2k_{new}$偶 $-$ 奇 $=$ 奇$2k_3 - (2k_1 + 1) = 2(k_3 - k_1) - 1= 2k_{new} + 1$

奇数的因子中一定没有偶数，偶数的因子中一定有奇数和偶数$\Rightarrow$ 奇数只能变为偶数，偶数总能变为奇数
递推

$n = 1$时，先手只能减去因子1变为0，因此先手必败$n = 2$时，先手可以选择减去因子1，后手变为$n = 1$时的必败态，因此$n = 2$时先手必胜$n = 3$时，先手只能减去因子1，后手变为$n = 2$时的必生态，因此$n = 3$时先手必败$n = 4$时，先手可以选择减去因子1，后手变为$n = 3$时的必败态，因此$n = 4$时先手必胜$n =$偶数,偶数总能变为奇数,奇数只能变为偶数,因此先手只要每次减为奇数就能保持自己是偶数$n =$奇数,奇数只能变为偶数,偶数总能变为奇数,因此后手只要每次减为奇数就能保持自己是偶数$\Rightarrow$ 偶数先手总是能转变为前后已有的后手的必败态，奇数先手只能转变为前后已有的后手的必胜态$\Rightarrow$ 偶数先手必胜，奇数先手必败

代码

点击查看代码

#include#include#include#include#include#include#includeusing namespace std;#define X first#define Y secondtypedef long long LL;const char nl = "\n";void solve(){LL n;cin >> n;if(n%2)cout << "yukari";else cout << "kou";}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);solve();}

关键词：可以选择