1518: 星星點(diǎn)點(diǎn)?

時(shí)間限制(普通/Java):1000MS/10000MS ? ? 內(nèi)存限制:65536KByte

描述

輸入一個(gè)由“*”和“.”組成的字符串，然后根據(jù)規(guī)則生成下一行字符串：?
如果該行的第i和第i+1個(gè)位置上的符號(hào)不同，則下一行的第i個(gè)位置上為“*”，否則為“.”，其最后一個(gè)位置的字符由上一行的第一個(gè)和最后一個(gè)字符決定。反復(fù)應(yīng)用上述規(guī)則足夠多次后，某行的字符排列可能在以后的行中再次出現(xiàn)，或者不會(huì)再次出現(xiàn)。找出最近的相同的兩行之間相差的行數(shù)。

輸入

上述字符串，長(zhǎng)度2<=L<=30。

輸出

相差的行數(shù)（即行號(hào)相減）。

樣例輸入

.*.
***.

樣例輸出

3
1

題目來(lái)源

ZJGSU

?

題目鏈接：tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=1518

模擬題，按照題目意思模擬，將每一個(gè)出現(xiàn)的字符串存入map中，判斷是否出現(xiàn)重復(fù)的，但用字符串模擬會(huì)TLE，題目中只有兩種字符，所以轉(zhuǎn)換成二進(jìn)制進(jìn)行模擬，根據(jù)題目要求提取出轉(zhuǎn)換式子y=(((y&1)<<(n-1))|(y>>1))^y;。

?

#include <string> #include <cstdio> #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string s;map<int,int>m;while(cin>>s){int k=0,n=s.length(),y=0;for(int i=0;i<n;i++){if(s[i]=='*')y|=(1<<i);}//cout<<y<<" ";m.clear();while(1){k++;if(m[y])break;m[y]=k;y=(((y&1)<<(n-1))|(y>>1))^y;//cout<<y<<endl;}//mp[s]=k-m[s];cout<<k-m[y]<<endl;} }

?

?

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

總結(jié)

以上是生活随笔為你收集整理的TZOJ--1518: 星星点点 (二进制模拟)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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