http://abc048.contest.atcoder.jp/tasks/arc064_b?lang=en

在vj里面用list模擬水過去了，然后感覺vj不靠譜，上atcoder交，果然tle

我的思路是這樣的，first那個是沒有必勝策略的，贏就是贏，隨便拿哪一個都是贏。

所以只需要找到有多少個能拿的就行了。用list模擬下，TLE.

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> #include <list> list<char>theList; const int maxn = 1e5 + 20; char str[maxn]; void work() {scanf("%s", str + 1);int lenstr = strlen(str + 1);for (int i = 1; i <= lenstr; ++i) {theList.push_back(str[i]);} // for (list<char> :: iterator it = theList.begin(); it != theList.end(); ++it) { // cout << *it; // }int ans = 0;while (theList.size() > 2) {if (theList.size() == 3 && theList.front() == theList.back()) break;list<char> :: iterator itBegin = theList.begin();itBegin++;list<char> :: iterator itEnd = theList.end();itEnd--;list<char> :: iterator itBeginPre = theList.begin();list<char> :: iterator itBeginNext = itBegin; itBeginNext++;bool flag = false;while (itBegin != itEnd) {if (*itBeginPre == *itBeginNext) {itBeginPre++;itBegin++;itBeginNext++;} else {theList.erase(itBegin);flag = true;break;}}if (!flag) break;ans++;} // cout << ans << endl;if (ans & 1) {cout << "First" << endl;} else cout << "Second" << endl; }int main() { #ifdef localfreopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endifwork();return 0; } View Code

?

那么就需要快速找到有多少東西能拿，一般情況下，能拿的東西是lenstr - 2個，減去頭和尾

博弈：

分為兩種情況：

1、頭和尾相等，這個時候能拿的東西次數(shù) - 1，

2、頭和尾不等，拿的東西次數(shù)不變

然后判斷奇偶性就好。

那么死鎖怎么辦？就是像ababa

這里能拿的個數(shù)是0，但是按照上面的，是2.

看看基本的死鎖是：aba，這樣，那么再添加2個，可以形成新的死鎖ababa

注意到添加元素的個數(shù)必定要是偶數(shù)，這個不影響奇偶性。

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> #include <list> list<char>theList; const int maxn = 1e5 + 20; char str[maxn]; void work() {scanf("%s", str + 1);int lenstr = strlen(str + 1);lenstr -= 2;if (str[1] == str[strlen(str + 1)]) lenstr--;if (lenstr & 1) {cout << "First" << endl;} else cout << "Second" << endl; }int main() { #ifdef localfreopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endifwork();return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/liuweimingcprogram/p/6542518.html

總結(jié)

以上是生活随笔為你收集整理的AtCoder - 2153 An Ordinary Game list模拟 || 博弈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。