【u248】交通序列号

Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

在一条笔直的道路上共有N个路口，每个路口处都有关于该条道路的通行的信号灯。

显然，信号灯共有绿(G)、红(R)、黄(Y)三种颜色。

交通部门指出，当绿色信号灯为奇数个，且红色信号灯为偶数个时，该条道路为“通畅的”。

现在交给你一个任务：给定从第一个路口到最后一个路口的所有信号灯的序列，计算出这个序列在“通畅的”道路的字典序中的

序号。

【输入格式】

第一行，正整数N (N <= 10^5)；

第二行，一个长度为N的序列(不含空格)，其中第i个字母表示第i个路口信号灯的状态。

【输出格式】

输出这个序列在“通畅的”道路的字典序中的序号

(由于答案可能比较大，所以你只要输出答案除12345的余数即可。

注意，若此道路不通畅，请输出”invalid”[不含双引号]) 。

【数据规模】

对于40%的数据，N<=15；

对于70%的数据，N<=10^4;

对于100%的数据，N<=10^5。

Sample Input1

4

RGYR

Sample Output1

9

这20种通畅道路分别是（按字典序，此部分无须输出）

GGGY、GGYG、GRRY、GRYR、GYGG、

GYRR、GYYY、RGRY、RGYR、RRGY、

RRYG、RYGR、RYRG、YGGG、YGRR、

YGYY、YRGR、YRRG、YYGY、YYYG

【样例说明】

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u248

【题解】

用f[i][2][2]表示交通序列的长度为i,第2维表示绿灯的奇偶性，第三维表示红灯的奇偶性的方案数;(0为偶数、1为奇数);

//黄灯在状态中没必要体现出来;

则有状态转移方程

    f[1][0][0] = 1;// e e yellow

    f[1][0][1] = 1;// e red e

    f[1][1][0] = 1;// green e e

    f[1][1][1] = 0;//no exist

    f[i][0][0] = f[i-1][1][0]+f[i-1][0][1]+f[i-1][0][0]

    f[i][0][1] = f[i-1][1][1]+f[i-1][0][0]+f[i-1][0][1]

    f[i][1][0] = f[i-1][0][0]+f[i-1][1][1]+f[i-1][1][0]

    f[i][1][1] = f[i-1][0][1]+f[i-1][1][0]+f[i-1][1][1]

其中从左到右分别表示在i-1表示的序列的末尾加上一盏绿、红、黄灯;由此来转移状态;注意取模就好;

这个i数组有什么用呢->分析法搞出比输入的序列的字典序小的序列有多少个；

按照字典序G->R->Y来搞;

比如输入样例RGYR

就先搞出GXXX有多少个->ans1->根据奇偶性来用f[3][x][x];ans1就等于f[3][t][t];

然后确定第一位为R；第二位为G;因为字典序是最小的所以不用理它递增G灯个数；

…以此类推就能求出比当前序列的字典序小的序列的个数了；

最后加1就是答案；

不要忘记判断一开始的序列是不合法的情况.

【完整代码】

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <string>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

void rel(LL &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t) && t!='-') t = getchar();

    LL sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

void rei(int &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)&&t!='-') t = getchar();

    int sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

const int MAXN = 1e5+10;

const int dx[5] = {0,1,-1,0,0};

const int dy[5] = {0,0,0,-1,1};

const double pi = acos(-1.0);

const int MOD = 12345;

int n,hong=0,lv = 0,ans = 1;

int f[MAXN][2][2];//0表示偶数1表示奇数 第一格为绿，第二格为红

char s[MAXN];

//目标是绿奇红偶

int pd(int x)

{

    if (x&1) return 1;  else  return 0;

}

void solve_green(int now)

{

    lv++;

    int len = n-now;

    //lv==0 red ==0

    if (!pd(lv)&&!pd(hong))

        ans = (ans + f[len][1][0])%MOD;

    //lv==1 red ==1

    if (pd(lv) && pd(hong))

        ans = (ans + f[len][0][1])%MOD;

    //lv= 0,red = 1;

    if (!pd(lv) && pd(hong))

        ans = (ans + f[len][1][1]) % MOD;

    //lv =1 ,red = 0;

    if (pd(lv) && !pd(hong))

        ans = (ans + f[len][0][0]) % MOD;

    lv--;

}

void solve_red(int now)

{

    hong++;

    int len = n-now;

    //lv==0 red ==0

    if (!pd(lv)&&!pd(hong))

        ans = (ans + f[len][1][0])%MOD;

    //lv==1 red ==1

    if (pd(lv) && pd(hong))

        ans = (ans + f[len][0][1])%MOD;

    //lv= 0,red = 1;

    if (!pd(lv) && pd(hong))

        ans = (ans + f[len][1][1]) % MOD;

    //lv =1 ,red = 0;

    if (pd(lv) && !pd(hong))

        ans = (ans + f[len][0][0]) % MOD;

    hong--;

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    f[1][0][0] = 1;// e e yellow

    f[1][0][1] = 1;// e red e

    f[1][1][0] = 1;// green e e

    f[1][1][1] = 0;//no exist

    rep1(i,2,1e5)

    {

        //green red yellow

        f[i][0][0] = (f[i-1][1][0]+f[i-1][0][1]+f[i-1][0][0])%MOD;

        f[i][0][1] = (f[i-1][1][1]+f[i-1][0][0]+f[i-1][0][1])%MOD;

        f[i][1][0] = (f[i-1][0][0]+f[i-1][1][1]+f[i-1][1][0])%MOD;

        f[i][1][1] = (f[i-1][0][1]+f[i-1][1][0]+f[i-1][1][1])%MOD;

    }

    cin >>n;

    cin >> s+1;

    //G R Y

    rep1(i,1,n)

        switch(s[i])

        {

            case 'G':

                lv++;

                break;

            case 'R':

            {

                solve_green(i);

                hong++;

                break;

            }

            case 'Y':

            {

                solve_green(i);

                solve_red(i);

                break;

            }

        }

    if ((pd(lv)==0)||(pd(hong)==1))

        cout <<"invalid";

    else

        cout << ans << endl;

    return 0;

}

巴特西

【u248】交通序列号

最新文章

热门文章