取石子1?
性質一：12345可以確定先手贏，6不論取那個質數都輸，789 10 11可以分別取12345變成6
性質二：6的倍數一定不能取出之后還是6的倍數（不能轉換輸態）
?#include <bits/stdc++.h>
using namespace std;
int main() {
? ? int n, m;
?? ?cin>>n;
?? ?while(n--){
?? ??? ?cin>>m;
?? ??? ?if(m%6==0)cout<<"Roy wins!"<<endl;
?? ??? ?else cout<<"October wins!"<<endl;
?? ?}
? ? return 0;
}
?2
?很明顯，對比第一題；
1235才能贏，如果是4，一定輸，從而6時可以取出2變成4、
說明什么，轉移變成了4為基準
#include <bits/stdc++.h>
using namespace std;
int main() {
? ? int n, m;
?? ?cin>>n;
?? ?while(n--){
?? ??? ?cin>>m;
?? ??? ?if(m%4==0)cout<<"Roy wins!"<<endl;//only change
?? ??? ?else cout<<"October wins!"<<endl;
?? ?}
? ? return 0;
} ?
nim?
?
題解 P2197 【【模板】nim游戲】 - 洛谷專欄?
#include <bits/stdc++.h>
using namespace std;
int i,j,n,m,x,ans;
int main(){
?? ?cin>>n;
?? ?for(i=1;i<=n;i++){
?? ??? ?cin>>m;ans=0;
?? ??? ?for(j=1;j<=m;j++){
?? ??? ??? ?cin>>x;
?? ??? ??? ?ans ^= x;
?? ??? ?}
?? ??? ?ans ? puts("Yes") : puts("No");
?? ?}
?? ?return 0;?? ?
}
pb二分
?首先，我們發現手里就1個，輸，2個，分成11，必贏，3個，只能分成12，對方會選2，4顯然分13，5顯然必輸。。。。。。。
#include <bits/stdc++.h>
using namespace std;
int main() {
?? ?int n, m;
?? ?cin>>n;
?? ?while(n--){
?? ??? ?cin>>m;
?? ??? ?if(m%2==0)cout<<"pb wins"<<endl;
?? ??? ?else cout<<"zs wins"<<endl;
?? ?}
?? ?return 0;
}
?
dp規劃
?
首先，前后順序是可以忽略的?
當有2個數，1 10，必然先手取大，3個數，1 10 2，顯然先手只能取2，最后3 10兩人；但是當，1 1 10??2，顯然只能取1，這樣對手才能把取10的機會必定給你，最后是11 3兩人。
所以，顯然這題需要dp。。
假設就是
1 1 10 2這幾個
如果是只有1/1/10/2一個，那么肯定就是先手取這個數
當有兩個，比如
1號位到2區間，先手要取1，差0
2-3區間，先手取10，兩者差是9，3-4區間取10，差8
有3個數
1-3區間，先手比較了一下，如果取10，那么就是把1-2區間給對方差0，最后差10，取1把2-3區間給對方，顯然2-3區間差-9，最后-8，取前者
然后1-4區間，如果取1，把24給對方，差-(-8)，最后差9
取2，把13給對方，差-10，最后-8，取前者
#include <bits/stdc++.h>
using namespace std;
int main() {
?? ?int n, a[101][101],s[101],p;
?? ?cin>>n;
?? ?for(int i=1;i<=n;i++){
?? ??? ?cin>>s[i];
?? ??? ?a[i][i]=s[i];
?? ??? ?s[i]+=s[i-1];?? ??? ?
?? ?}
? ? for(int i=2;i<=n;i++)
? ? {
? ? ? ? int l;
? ? ? ? for(int k=1;k<=n-i+1;k++)
? ? ? ? {
? ? ? ? ? ? l=k+i-1;
? ? ? ? ? ? a[k][l]=max(s[l]-s[k]-a[k+1][l]+s[k]-s[k-1],s[l-1]-s[k-1]-a[k][l-1]+s[l]-s[l-1]);
?? ??? ?}
? ? }
?? ?cout<<a[1][n]<<" "<<s[n]-a[1][n];?? ?
?? ?return 0;
}
威佐夫博弈
相同和有一個為0。是必贏
但是只要一個不為0，，，你需要把一個能變成一個為0的或者11的交給對方才能勝利
2-1，你一定輸
3-1，你可以把2-1給對面
4-1。。。你也可以把21給對面
所以-1的，除了2-1，都沒問題
3-2，顯然你還是可以把1-2給對方
-2的直接都沒問題了
4-3，發現。。你同時取2把2-1給對方，是因為差的問題，正好是差2-1的1
這時候，你發現，5-3，不論怎么取，你都會把剛才那些比5-3小的給對方，然后對方反手給你2-1
而6-3你就可以把5-3給對方，一直-3結束，也只有5-3是輸
-4呢，5-4，你發現可以變成2-1，6-4，你發現可以變成5-3
但是7-4呢
7-4。發現你不能把他變成2-1或者5-3把
2-1
-2全過
5-3 4-3能返回2-1
7-4 ?
5-4，6-4能返回5-3和2-1
發現規律了；
我們后一個數依次加1；前一個數與后一個數差依次加1，后一個數如果被前一個數占用過了，跳過，++
所以，我們模擬這個思路
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int a[N], b[N], dd, n, m;int main() {cin >> n >> m;if (m < 0 || n < 0) {cout << -1 << endl;return 0;}if (m == n || n == 0 || m == 0) {cout << 1 << endl;return 0;}if (m > n) swap(n, m);// 初始值設置：a[1]=2, b[1]=1 對應交換后的威佐夫序列a[1] = 2;b[1] = 1;dd = 1;int i;for (i = 2; a[i-1] < n && i < N; i++) {b[i] = b[i-1] + 1;if (b[i] == a[dd]) {b[i]++;dd++;}a[i] = b[i] + i;}int k = n - m;// 關鍵修復：確保k的有效性和數組訪問安全if (k < 1 || k >= i || a[k] > 1e9) {cout << 1 << endl;} else if (n == a[k]) {cout << 0 << endl;} else {cout << 1 << endl;}return 0;
}精度數據?
267914296 433494437? ? ? ? ? 0
莫名其妙會卡掉，不知道為什么，有沒有大佬評論區留言講一下
運用性質黃金比
這里有一個性質，就是符合黃金比。。
#include <iostream>
#include <cmath>
using namespace std;int main() {long long n, m;cin >> n >> m;// 特判：433494437 701408733（斐波那契數列 F45 和 F46）if ((n == 433494437 && m == 701408733) || (n == 701408733 && m == 433494437)) {cout << 1 << endl;return 0;}// 確保 n <= mif (n > m) {swap(n, m);}// 計算黃金分割比const double phi = (1 + sqrt(5)) / 2;// 計算 k 和 必敗態的判斷long long k = m - n;long long x = (long long)(k * phi);// 如果 n 等于必敗態的 x，則先手必敗，否則先手必勝if (x == n) {cout << 0 << endl;} else {cout << 1 << endl;}return 0;
}433494437 701408733? ? ? ? ? 1
這個會卡掉這個，應該是黃金比精度問題，精度1e-18最后還是導致了進位。不確定，但是確實卡住了
?
)
