生活随笔
收集整理的這篇文章主要介紹了
abc242 D(脑子一团浆糊)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目
題意: 給定僅含A、B、C的字符串，進行至多t = 1e18次迭代，每次迭代是獨立地將A->BC,B->CA,C->AB.求t次迭代后，第k個位置的字母是what?
思路: 感覺是除除除，因為我們可以根據k反推推回它是由數組原始位置的哪個字母變來的。然后哩？如果t很大，我們發現這個字母是a、b、c輪著變換的，%3即可。注意這里下標從0開始，方可保證%3正確性和一致性。怎么想出來的俺也不知道，被自己菜哭了，今晚連著兩把都被暴捶。
時間復雜度: O(log1e18)
代碼:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<complex>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<list>
#include<set>
#include<queue>
#include<stack>
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i<=b;++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define p_ priority_queue
using namespace std
;
typedef complex
<double> CP
;
typedef pair
<int,int> PII
;
typedef long long ll
;
const double pi
= acos(-1.0);
const int INF
= 0x3f3f3f3f;
const ll inf
= 1e18;
const int N
= 2e5+10;
const int M
= 1e6+10;
const int mod
= 1e9+7;
const double eps
= 1e-6;
inline int lowbit(int x
){ return x
&(-x
);}
template<typename T
>void write(T x
)
{if(x
<0){putchar('-');x
=-x
;}if(x
>9){write(x
/10);}putchar(x
%10+'0');
}
template<typename T
> void read(T
&x
)
{x
= 0;char ch
= getchar();ll f
= 1;while(!isdigit(ch
)){if(ch
== '-')f
*=-1;ch
=getchar();}while(isdigit(ch
)){x
= x
*10+ch
-48;ch
=getchar();}x
*=f
;
}
#define int long long
int n
,m
,k
,T
;
char s
[M
];
int fun(int t
,int k
)
{if(t
==0) return s
[k
]-'A';else if(k
== 0) return (s
[0]-'A'+t
)%3;return (fun(t
-1,k
/2)+k
%2+1)%3;
}
void solve()
{scanf("%s",s
);read(m
);while(m
--){ll t
,k
; read(t
),read(k
);k
--;printf("%c\n",fun(t
,k
)+'A');}
}
signed main(void)
{ T
= 1;while(T
--){solve();}return 0;
}
總結
以上是生活随笔為你收集整理的abc242 D(脑子一团浆糊)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
