生活随笔
收集整理的這篇文章主要介紹了
博弈论练习1
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
博弈論練習1
\;
1.ProjectEuler306 Paper-strip Game
題目描述
Solution
令SG[i]SG[i]SG[i]表示連續iii個格子的SGSGSG值。
SG[0]=SG[1]=0SG[i]=mexj=0n?2{SG[j]xorSG[i?j?2]}SG[0]=SG[1]=0 \\ SG[i]=mex_{j=0}^{n-2}\{SG[j]\;\;xor\;\;SG[i-j-2]\} SG[0]=SG[1]=0SG[i]=mexj=0n?2?{SG[j]xorSG[i?j?2]}
直接暴力時間復雜度O(n2)O(n^2)O(n2)，
打表找規律，發現有34位的循環節，之后O(n)O(n)O(n)求解答案即可。
\;
2.AGC002E-Candy Piles
題目描述
Solution
本題有兩種操作：
1.整體減1。
2.刪除最大的數。
我們把數從大到小排序，按數的大小柱形圖，相當于每次可以刪掉底行或刪掉首列，f[i][j]f[i][j]f[i][j]表示已經刪除前iii行前jjj列的勝負狀態，發現每一個對角線的fff值都是相同的。
因此直接從起點走到輪廓線判斷奇偶性即可。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se secondusing namespace std
;template<typename T
>inline bool upmin(T
&x
,T y
) { return y
<x
?x
=y
,1:0; }
template<typename T
>inline bool upmax(T
&x
,T y
) { return x
<y
?x
=y
,1:0; }typedef long long ll
;
typedef unsigned long long ull
;
typedef long double lod
;
typedef pair
<int,int> PR
;
typedef vector
<int> VI
;const lod eps
=1e-11;
const lod pi
=acos(-1);
const int oo
=1<<30;
const ll loo
=1ll<<62;
const int mods
=998244353;
const int MAXN
=600005;
const int INF
=0x3f3f3f3f;
inline int read()
{int f
=1,x
=0; char c
=getchar();while (c
<'0'||c
>'9') { if (c
=='-') f
=-1; c
=getchar(); }while (c
>='0'&&c
<='9') { x
=(x
<<3)+(x
<<1)+(c
^48); c
=getchar(); }return x
*f
;
}
int a
[MAXN
];
int main()
{int n
=read();for (int i
=1;i
<=n
;i
++) a
[i
]=read();sort(a
+1,a
+n
+1,greater
<int>());for (int i
=0;i
<=n
;i
++)if (i
+1>a
[i
+1]){int r
=i
;while (a
[r
+1]==i
) r
++;puts((((a
[i
]-i
)&1)||((r
-i
)&1))?"First":"Second");break;}return 0;
}
3.CF1110G. Tree-Tac-Toe
題目描述
Solution
首先，后手是個弟弟，他永遠不能贏QAQQAQQAQ。
因此考慮什么時候先手必勝：
1.若有一個度數為4及以上的結點，則先手必勝。
2.若有一個度數為3的結點，它的子節點的度數至少為1,2,2，則先手必勝。
3.若有存在3個以上度數為3的結點，必然存在條件2，則先手必勝。
4.若僅有2個度數為3的結點，則若他們之間的距離是偶數，則先手必勝。
否則必然平局。
O(n)O(n)O(n)實現分類討論即可。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se secondusing namespace std
;template<typename T
>inline bool upmin(T
&x
,T y
) { return y
<x
?x
=y
,1:0; }
template<typename T
>inline bool upmax(T
&x
,T y
) { return x
<y
?x
=y
,1:0; }typedef long long ll
;
typedef unsigned long long ull
;
typedef long double lod
;
typedef pair
<int,int> PR
;
typedef vector
<int> VI
;const lod eps
=1e-11;
const lod pi
=acos(-1);
const int oo
=1<<30;
const ll loo
=1ll<<62;
const int mods
=998244353;
const int MAXN
=2000005;
const int INF
=0x3f3f3f3f;
inline int read()
{int f
=1,x
=0; char c
=getchar();while (c
<'0'||c
>'9') { if (c
=='-') f
=-1; c
=getchar(); }while (c
>='0'&&c
<='9') { x
=(x
<<3)+(x
<<1)+(c
^48); c
=getchar(); }return x
*f
;
}
char st
[MAXN
];
int n
,nodenum
,d
[MAXN
];
vector
<int> e
[MAXN
],V
[MAXN
];
void add_edge(int u
,int v
)
{e
[u
].PB(v
),e
[v
].PB(u
);d
[u
]++,d
[v
]++;
}
int dfs(int x
,int father
,int dep
,int y
)
{if (x
==y
) return dep
&1; for (auto v
:e
[x
]){if (v
==father
) continue;int q
=dfs(v
,x
,dep
+1,y
);if (q
!=-1) return q
;}return -1;
}
bool solve()
{for (int i
=1;i
<=nodenum
;i
++) {if (d
[i
]>=4) return 1;V
[d
[i
]].PB(i
);}if (V
[3].size()>=3) return 1;if (V
[3].size()==2&&dfs(V
[3][0],0,1,V
[3][1])) return 1;for (auto x
:V
[3]){ int cnt1
=0,cnt2
=0;for (auto v
:e
[x
]) if (d
[v
]>=2) cnt2
++;if (cnt2
>=2) return 1;}return 0;
}
int main()
{int Case
=read();while (Case
--){n
=nodenum
=read();for (int i
=1;i
<n
;i
++){int u
=read(),v
=read();add_edge(u
,v
);}scanf("%s",st
+1);for (int i
=1;i
<=n
;i
++)if (st
[i
]=='W'){nodenum
+=3;add_edge(i
,nodenum
-2);add_edge(nodenum
-2,nodenum
-1);add_edge(nodenum
-2,nodenum
);}puts(solve()?"White":"Draw");for (int i
=1;i
<=nodenum
;i
++) e
[i
].clear(),V
[i
].clear(),d
[i
]=0;}return 0;
}
4.CF388C. Fox and Card Game
題目描述
Solution
這題雖然是Div.1CDiv.1CDiv.1C但是很簡單啊。
這個博弈游戲中，先手想要拿到最大的權值和，而后手的目的是盡可能地阻止先手拿到大的權值。
考慮每一行的數，倘若先手拿到a[(n+1)/2+1...n]a[(n+1)/2+1...n]a[(n+1)/2+1...n]中的某一個數能拿到最優解，那么先手必然會阻止他拿到他想拿到的那個數，換句話說，在后手刻意而為的情況下，先手永遠拿不到每一行中的a[(n+1)/2+1...n]a[(n+1)/2+1...n]a[(n+1)/2+1...n]這些數。
對于nnn為偶數，先手能拿的只有前n/2n/2n/2個。
對于nnn為奇數，先手必然能拿的是前n/2n/2n/2，并剩下最中間一個數。對于每一個奇數行剩下的數從大到小排序，先手必然可以選到排序后奇數位上的數，剩下的數全部由后手選到。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se secondusing namespace std
;template<typename T
>inline bool upmin(T
&x
,T y
) { return y
<x
?x
=y
,1:0; }
template<typename T
>inline bool upmax(T
&x
,T y
) { return x
<y
?x
=y
,1:0; }typedef long long ll
;
typedef unsigned long long ull
;
typedef long double lod
;
typedef pair
<int,int> PR
;
typedef vector
<int> VI
;const lod eps
=1e-11;
const lod pi
=acos(-1);
const int oo
=1<<30;
const ll loo
=1ll<<62;
const int mods
=998244353;
const int MAXN
=600005;
const int INF
=0x3f3f3f3f;
inline int read()
{int f
=1,x
=0; char c
=getchar();while (c
<'0'||c
>'9') { if (c
=='-') f
=-1; c
=getchar(); }while (c
>='0'&&c
<='9') { x
=(x
<<3)+(x
<<1)+(c
^48); c
=getchar(); }return x
*f
;
}
vector
<int> V
;
int main()
{int n
=read(),ans1
=0,ans2
=0;for (int i
=1;i
<=n
;i
++){int x
=read();for (int j
=1;j
<=x
;j
++)if (j
<=x
/2) ans1
+=read();else if (j
==(x
+1)/2) V
.PB(read());else ans2
+=read();}sort(V
.begin(),V
.end(),greater
<int>());for (int i
=0;i
<V
.size();i
++)if (i
&1) ans2
+=V
[i
];else ans1
+=V
[i
];printf("%d %d\n",ans1
,ans2
);return 0;
}
5.CF388C. Fox and Card Game
題目描述
Solution
答案必然集中在序列的中間幾個數中。
先手先進行kkk次操作會讓答案區間平移若干格，直接維護即可。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se secondusing namespace std
;template<typename T
>inline bool upmin(T
&x
,T y
) { return y
<x
?x
=y
,1:0; }
template<typename T
>inline bool upmax(T
&x
,T y
) { return x
<y
?x
=y
,1:0; }typedef long long ll
;
typedef unsigned long long ull
;
typedef long double lod
;
typedef pair
<int,int> PR
;
typedef vector
<int> VI
;const lod eps
=1e-11;
const lod pi
=acos(-1);
const int oo
=1<<30;
const ll loo
=1ll<<62;
const int mods
=998244353;
const int MAXN
=600005;
const int INF
=0x3f3f3f3f;
inline int read()
{int f
=1,x
=0; char c
=getchar();while (c
<'0'||c
>'9') { if (c
=='-') f
=-1; c
=getchar(); }while (c
>='0'&&c
<='9') { x
=(x
<<3)+(x
<<1)+(c
^48); c
=getchar(); }return x
*f
;
}
int a
[MAXN
],dp1
[MAXN
],dp2
[MAXN
],ans
[MAXN
];
int main()
{int n
=read();for (int i
=1;i
<=n
;i
++) a
[i
]=read(),upmax(ans
[1],a
[i
]);for (int i
=1;i
<n
;i
++) upmax(dp1
[min(i
,n
-i
)],max(a
[i
],a
[i
+1]));for (int i
=2;i
<n
;i
++) upmax(dp2
[min(i
-1,n
-i
)],max(min(a
[i
-1],a
[i
]),min(a
[i
],a
[i
+1])));for (int i
=n
/2;i
>=1;i
--) ans
[i
<<1]=max(ans
[(i
+1)<<1],dp1
[i
]),ans
[i
<<1|1]=max(ans
[(i
+1)<<1|1],dp2
[i
]);for (int i
=n
;i
>=1;i
--) printf("%d ",ans
[i
]);return 0;
}
總結
以上是生活随笔為你收集整理的博弈论练习1的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
