2017年浙江工業大學大學生程式設計迎新賽熱身賽 F-方塊 I
題目鏈接：https://ac.nowcoder.com/acm/problem/14595
大致題意：三種字母（代表三種顏色）組成的字串，相鄰同色相消，求最佳決策下的最短字串長度，
PS：雖然題目標簽是 博弈論 SG函式，但這題顯然不是常規的博弈模型，連對奕雙方都不存在，只能說在最河駁現了SG的思想…
思路
對于任意字串，我們分兩種情況:
- 全體字符相同，如 aaaaaa
- 不符合第一種情況的字串
情況一就是終止局勢，所以答案顯然，
因此我們只討論情況二：
首先我們知道情況二最侄訓轉為終止局勢，不考慮決策是否最優，合并到最后的結果肯定是各種長度的字符全部相同的串，
下面開始規律探索
逆向思考
考慮可以在下一步變為AAA的串，可以分為三種情況：ABCA，BCAA，CBAA（其他情況都與某一種對稱）
觀察如下轉變：
1.ABCA->CCA->CB->A
2.BCAA->BBA->BC->A
3.CBAA->CCA->CB->A
…
可以發現：任意可以在下一步變為AAA的字串都可以轉化為單個A！
隨后我們可以發現任意能在下一步變為奇數個A的字串也都可以轉變成單個A，只需要如上述一樣在一端產生一個BC或CB并向另一端合并奇數個A即可，然后考慮后繼是偶數個A的情況，顯然也可以通過合并掉多余的A而僅剩2個A；此外，B和C的情況同理，
顯然任意情況二的字串都會經歷下一步變為奇數或偶數個A（或B，C）的情況，
因此顯然有結論：任意情況二的字串最終都會化為單個字符或兩個字符相同的串，
因此我們只需要判斷最終是單個還是兩個，
我們將A，B，C看成1，2，3
觀察一下異或運算
1^2=3;
1^3=2;
2^3=1;
…
可以發現
字符不同時，異或與游戲規則是相符的；
字符相同時，偶數個同字符異或的結果為0，奇數個結果為本身，若在串結尾前遇到不同字符，則0 ^ 不同字符=不同字符, 本身 ^ 不同字符=第三種字符，相當于這個不同的字符向前合并了上述相同字符的串，與游戲規則再度吻合；若一直到結尾都為相同字符，則結果為0.則0代表之前存在偶數個同字串，根據之前的結論可知答案為2，
總結
若為同字符的串，則輸出原串長度；
若字符不同，則化為123，從左到右求異或，若結果為0則輸出2，否則輸出1；
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn =5e3+5;
const int mod=998244353;
#define INF 0x3f3f3f3f
//#define int ll
#pragma GCC optimize(0)
using namespace std;
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//freopen("data.in","r",stdin);
string s;
while (cin>>s)
{
int ans=0;
int f=1;
for (int i=0;i<s.size();i++)
{ans^=s[i]-'a'+1;if (s[0]!=s[i]) f=0;}
if (f) cout<<(s.size())<<endl;
else cout<<(ans==0?2:1)<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/126529.html
標籤：AI
上一篇：新人求助，有關于資料流