1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
|
using namespace std; #define forl(i, l, r) for (int i = l; i <= r; i++) #define forr(i, r, l) for (int i = r; i >= l; i--) #define for1(i, n) for (int i = 1; i <= n; i++) #define fro1(i, n) for (int i = 1; i <= n; i++) #define for0(i, n) for (int i = 0; i < n; i++) #define fro0(i, n) for (int i = 0; i < n; i++) #define meminf(a) memset(a, inf, sizeof(a)) #define mem_1(a) memset(a, -1, sizeof(a)) #define mem0(a) memset(a, 0, sizeof(a)) #define oper(type) bool operator <(const type y)const #define mp make_pair #define pb push_back #define fi first #define se second typedef pair<long long, long long> pll; typedef vector<long long> vll; typedef pair<int, int> pii; typedef unsigned long long ull; typedef vector<int> vii; typedef long double db; typedef long long ll; typedef int itn; int (int &a,int &b,int &c,int &d){return scanf("%d%d%d%d",&a,&b,&c,&d);} int (int &a,int &b,int &c){return scanf("%d%d%d",&a,&b,&c);} int (int &a,int &b){return scanf("%d%d",&a,&b);} int (ll &a){return scanf("%lld",&a);} int (int &a){return scanf("%d",&a);} int in(char *s){return scanf("%s",s);} int in(char &s){return scanf("%c",&s);} int in(db &a){return scanf("%Lf",&a);} void out(int a){printf("%d",a);} void outln(int a){printf("%dn",a);} void out(ll a){printf("%lld",a);} void outln(ll a){printf("%lldn",a);} const db pi = acos((db)-1); const ll inf =0x3f3f3f3f; const db eps = 1e-8; const int N = 1.6e6; const ll mod = 1e9+7; int sign(db a) { return a < -eps ? -1 : a > eps;} int db_cmp(db a, db b){ return sign(a-b); }
int ans[N]; ll pow3[23]; bool iskong[23];
int len;
int fun(ll status){ int ans_status=0; ll tmp_sta=status; int *wei=new int[23]; bool have0=0; for0(i,len){ int flag=tmp_sta%3; wei[i]=flag; if(flag==0)have0=1; if(iskong[i]){ ans_status*=3; ans_status+=flag; } tmp_sta/=3; } if(ans[ans_status]<inf){ delete [] wei; return ans[ans_status]; } for(int i=0;i+2<len;i++){ if(wei[i]==1&&wei[i+1]==2&&wei[i+2]==1){ delete [] wei; return ans[ans_status]=-1; } } if(!have0){ delete [] wei; return ans[ans_status]=0; } int res = -1; delete [] wei; tmp_sta=status; for0(i,len){ int flag=tmp_sta%3; if(flag==0){ res = max(res,-fun(status+pow3[i])); res = max(res,-fun(status+2*pow3[i])); if(res==1)break; } tmp_sta/=3; }
return ans[ans_status]=res; } int main(){ int t; in(t); char s[23]; pow3[0]=1; for1(i,22){ pow3[i]=pow3[i-1]*3; } while(t--){ meminf(ans); mem0(iskong); in(s); ll tmp=0; len=strlen(s); assert(len<23); for0(i,len){ tmp*=3; if(s[i]=='L')tmp+=1; else if(s[i]=='O')tmp+=2; else iskong[len-i-1]=1; } outln(fun(tmp)); } return 0; }
|
近期评论